Sachverhalt:
A.
A._ Anonim Sirketi (Klägerin, Beschwerdegegnerin) ist eine türkische Gesellschaft mit Sitz in U._. Seit 1980 war sie an mehr als 35 öffentlichen Bauprojekten auf dem Territorium des libyschen Staates (Beklagter, Beschwerdeführer) beteiligt. Am Anfang der 1990er-Jahre stellte sie ihre Arbeiten infolge unbezahlter Rechnungen ein.
Zwischen 1994 und 2005 versuchte die Klägerin, die Zahlung der offenen Rechnungen durch den Beklagten zu erwirken. Zwischen 2007 und 2008 beteiligte sie sich an einem vom libyschen Finanzministerium durchgeführten "Audit and Review of Outstanding Liabilities of Libya's Treasury". Ab 2009 versuchte sie vergeblich, die Zahlung der im Rahmen dieses Audits festgestellten Summe zu erwirken. Am 27. September 2012 erhob sie Klage beim erstinstanzlichen Gericht in Beida, Libyen. Mit Entscheid vom 29. Oktober 2012 verurteilte dieses Gericht den Beklagten zur Zahlung von 1'906'360.23 libyschen Dinar (LD) zzgl. Zinsen aufgrund von offenen Forderungen aus den vorerwähnten Bauprojekten sowie Schadenersatz in der Höhe von 1'000'000.-- LD für die fruchtlosen Inkassobemühungen (nachfolgend: Beida-Urteil). Der Beklagte blieb diesem Verfahren fern. Am 23. Januar 2013 erhob der Beklagte, vertreten durch die Streitbeilegungsabteilung ("State Litigation Department"), Berufung gegen dieses Urteil. Am 31. Januar 2018 hob das zuständige Berufungsgericht das Beida-Urteil auf.
Am 9. Dezember 2013 schlossen die Parteien eine Vergleichsvereinbarung ("Settlement Agreeement") ab. Dabei wurde der Beklagte vom stellvertretenden Finanzminister ("Deputy Minister in the Libyan Ministry of Finance") vertreten. In der Vergleichsvereinbarung verpflichtete sich der Beklagte, der Klägerin 5'420'308.707 LD zu bezahlen. Sodann sah die Vergleichsvereinbarung vor, dass alle nationalen oder internationalen Gerichts- und sonstigen Verfahren im Zusammenhang mit dem Beida-Urteil eingestellt werden. Die Vergleichsvereinbarung selbst beinhaltete keine Schiedsklausel.
Am 25. März 2018 leitete der Beklagte, vertreten durch die staatliche Streitbeilegungsabteilung, Klage gegen die Klägerin ein und verlangte die Feststellung, die Vergleichsvereinbarung sei ungültig und nichtig (sog. "Tripolis-Verfahren").
B.
Bereits zuvor, am 31. August 2016, hatte die Klägerin bei der Internationalen Handelskammer in Paris einen Antrag auf ein Schiedsverfahren auf der Grundlage des türkisch-libyschen Investitionsschutzabkommens vom 25. November 2009 (nachfolgend: ISA) gestellt. Die Parteien einigten sich auf Genf als Sitz des Schiedsgerichtsverfahrens. Am 22. Juli 2019 erliess das Schiedsgericht folgenden Schiedsspruch:
"I. Respondent's objections against the Arbitral Tribunal's jurisdiction are rejected;
II. The A rbitral Tribunal has jurisdiction over all of Claimant's claims based on the BIT and raised in this arbitration;
X. Respondent has breached Article 2 (2) of the BIT by failing to accord fair and equitable treatment to Claimant's investment;
XXV. Respondent shall pay damages to Claimant in the amount of USD 21,865,554, including pre-award simple interest accrued at 4% per annum;
XXV. Claimant's claims for moral damages are rejected;
XXV. All other requests and claims are rejected;
XXV. Respondent shall pay interest on the sum USD 21,865,554 awarded from the date of the notification of the Award at the rate of LIBOR + 3% per annum, compounded annually;
XXV. -IX [Kosten und Entschädigung]."
Es stellte fest, die Klägerin stütze ihre Ansprüche einerseits auf materielle Verpflichtungen des Beklagten gemäss ISA, namentlich Art. 2 Abs. 2 und Art. 4 ISA, sowie eine im ISA (stillschweigend) enthaltene Schirmklausel ("umbrella clause"), welche den Beklagten unmittelbar gestützt auf das ISA zur Einhaltung eingegangener Verträge verpflichte. Zusätzlich zu dieser abkommensbasierten ("treaty-based") Grundlage argumentiere die Klägerin auch vertraglich, indem sie eine Verletzung der Vergleichsvereinbarung geltend mache. Im Hinblick auf seine Zuständigkeit erwog das Schiedsgericht, die Vergleichsvereinbarung vom 9. Dezember 2013 sei unter libyschem Recht gültig, sie habe eine Geldforderung im Zusammenhang mit einer Investition nach Art. 1 Abs. 2 ISA zum Inhalt, weshalb sie ihrerseits eine geschützte Investition im Sinne des Abkommens sei, und die aus dem behaupteten Nichteinhalten der Vereinbarung erwachsene, zu beurteilende Streitigkeit, sei erst nach Inkrafttreten des ISA am 22. April 2011 entstanden. Somit sei das Schiedsgericht gestützt auf Art. 8 und Art. 10 ISA zuständig, ungeachtet dessen, dass die Vergleichsvereinbarung selber keine Schiedsklausel enthalte.
C.
Mit Beschwerde in Zivilsachen vom 16. September 2019 beantragt der Beklagte dem Bundesgericht, der Schiedsspruch sei kostenfällig aufzuheben und es sei festzustellen, dass das Schiedsgericht unzuständig sei.
Die Beschwerdegegnerin beantragt, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Das Schiedsgericht verzichtete auf eine Vernehmlassung. Die Parteien replizierten bzw. duplizierten unaufgefordert.
Mit präsidialer Verfügung vom 19. Dezember 2019 wurde das Sicherstellungsgesuch der Beschwerdegegnerin gutgeheissen. In der Folge wurde Sicherheit im Umfang von Fr. 79'975.-- bei der Bundesgerichtskasse geleistet.
Mit präsidialer Verfügung vom 25. März 2020 wurde der Beschwerde die aufschiebende Wirkung gewährt.
Mit Eingabe vom 21. September 2020 stellte der Beschwerdeführer ein Erläuterungsgesuch zur Verfügung betreffend aufschiebende Wirkung und beantragte, es sei zu erläutern, ob die am 25. März 2020 verfügte Suspensivwirkung die Vollstreckbarkeit des Schiedsspruchs des Schiedsgerichts mit Sitz in Genf vom 22. Juli 2019 und darüber hinaus dessen Wirkungen insgesamt, einschliesslich seiner Rechtskraft und seiner Bindungswirkung hemme (Ziff. 1 und 2). Ausserdem stellte er zwei Begehren um Erlass vorsorglicher Massnahmen (Ziff. 3 und 4). Die Beschwerdegegnerin beantragte mit Eingabe vom 8. Oktober 2020, auf das Erläuterungsgesuch gemäss Rechtsbegehren 1 und 2 sei nicht einzutreten, eventuell sei dieses abzuweisen. Die Gesuche um Erlass vorsorglicher Massnahmen gemäss Rechtsbegehren 3 und 4 seien abzuweisen, soweit darauf einzutreten sei. Mit dem vorliegenden Entscheid in der Sache werden diese Gesuche gegenstandslos.

Erwägungen:
1.
Nach <ref-law> ergeht der Entscheid des Bundesgerichts in einer Amtssprache, in der Regel in jener des angefochtenen Entscheids. Wurde dieser in einer anderen Sprache abgefasst, bedient sich das Bundesgericht der von den Parteien verwendeten Amtssprache. Der angefochtene Entscheid ist in englischer Sprache abgefasst. Da es sich dabei nicht um eine Amtssprache handelt und die Parteien ihre dem Bundesgericht eingereichten Rechtsschriften in Übereinstimmung mit <ref-law> i.V.m. <ref-law> auf Deutsch verfassten, ergeht der Entscheid des Bundesgerichts praxisgemäss in der Sprache der Beschwerde (<ref-ruling> E. 1 S. 524).
2.
Im Bereich der internationalen Schiedsgerichtsbarkeit ist die Beschwerde in Zivilsachen unter den Voraussetzungen der Art. 190-192 IPRG (SR 291) zulässig (<ref-law>).
2.1. Der Sitz des Schiedsgerichts befindet sich vorliegend in Genf. Sämtliche Parteien hatten im massgebenden Zeitpunkt ihren Sitz ausserhalb der Schweiz (<ref-law>). Da die Parteien die Geltung des 12. Kapitels des IPRG nicht ausdrücklich ausgeschlossen haben, gelangen die Bestimmungen dieses Kapitels zur Anwendung (<ref-law>).
Beim angefochtenen Schiedsentscheid handelt es sich um einen Endentscheid. Dieser kann nach <ref-law> mit Beschwerde angefochten werden.
2.2. Die Beschwerde im Sinne von <ref-law> ist grundsätzlich rein kassatorischer Natur, d.h. sie kann nur zur Aufhebung des angefochtenen Entscheids führen (vgl. <ref-law>, der die Anwendbarkeit von <ref-law> ausschliesst, soweit dieser dem Bundesgericht erlaubt, in der Sache selbst zu entscheiden). Soweit der Streit die Zuständigkeit des Schiedsgerichts oder dessen Zusammensetzung betrifft, gilt davon eine dahingehende Ausnahme, dass das Bundesgericht selber die Zuständigkeit oder die Unzuständigkeit des Schiedsgerichts feststellen bzw. über die Ablehnung des betreffenden Schiedsrichters befinden kann (<ref-ruling> E. 3.3.4 S. 616 mit Hinweisen). Es ist auch nicht ausgeschlossen, dass das Bundesgericht die Sache an das Schiedsgericht zurückweist (Urteile 4A_418/2019 vom 18. Mai 2020 E. 2.3; 4A_294/2019 vom 13. November 2019 E. 2.2; 4A_462/2018 vom 4. Juli 2019 E. 2.2; 4A_628/2018 vom 19. Juni 2019 E. 2.2).
Die Anträge des Beschwerdeführers sind demnach zulässig.
2.3. Zulässig sind allein die Rügen, die in <ref-law> abschliessend aufgezählt sind (<ref-ruling> E. 5 S. 187; <ref-ruling> E. 1a S. 53; <ref-ruling> E. 1a S. 282). Nach <ref-law> prüft das Bundesgericht nur die Rügen, die in der Beschwerde vorgebracht und begründet worden sind; dies entspricht der in <ref-law> für die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht vorgesehenen Rügepflicht (<ref-ruling> E. 5 S. 187; zit. Urteil 4A_418/2019 E. 2.4; Urteil 4A_80/2018 vom 7. Februar 2020 E. 2.2; jeweils mit Hinweisen). Appellatorische Kritik ist unzulässig (<ref-ruling> E. 3.1 S. 567; <ref-ruling> E. 3b S. 382; zit. Urteil 4A_80/2018 E. 2.2).
2.4. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den das Schiedsgericht festgestellt hat (<ref-law>). Dazu gehören sowohl die Feststellungen über den Lebenssachverhalt, der dem Streitgegenstand zugrunde liegt, als auch jene über den Ablauf des vorinstanzlichen Verfahrens, also die Feststellungen über den Prozesssachverhalt, zu dem namentlich die Anträge der Parteien, ihre Tatsachenbehauptungen, rechtlichen Erörterungen, Prozesserklärungen und Beweisvorbringen, der Inhalt einer Zeugenaussage, einer Expertise oder die Feststellungen anlässlich eines Augenscheins gehören (<ref-ruling> E. 1.3.1 mit Hinweisen).
Das Bundesgericht kann die Sachverhaltsfeststellung des Schiedsgerichts weder berichtigen noch ergänzen, selbst wenn diese offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (vgl. <ref-law>, der die Anwendbarkeit von <ref-law> sowie <ref-law> ausschliesst). Es überprüft die tatsächlichen Feststellungen des angefochtenen Schiedsentscheids auch im Rahmen der Zuständigkeitsrüge nur, wenn gegenüber diesen Sachverhaltsfeststellungen zulässige Rügen im Sinne von <ref-law> vorgebracht oder ausnahmsweise Noven (<ref-law>) berücksichtigt werden (<ref-ruling> E. 3.1 S. 224, 239 E. 3.1 S. 244; <ref-ruling> E. 3.1 S. 477; <ref-ruling> E. 2.2.1; zit. Urteil 4A_418/2019 E. 2.5; je mit Hinweisen).
2.5. Das Bundesgericht prüft die Zuständigkeitsrüge nach <ref-law> in rechtlicher Hinsicht frei, einschliesslich materieller Vorfragen, von deren Beantwortung die Zuständigkeit abhängt (<ref-ruling> E. 4.1 S. 563; <ref-ruling> E. 3.1 S. 244; <ref-ruling> E. 3.1 S. 567; <ref-ruling> E. 5 S. 141; Beispiele im Bereich des Investitionsschutzes: <ref-ruling> E. 3.4.1 S. 148 f.; zit. Urteil 4A_80/2018 E. 2.5; Urteile 4A_65/2018 vom 11. Dezember 2018 E. 2.4.1 und E. 3.2.1-3.2.3; 4A_157/2017 vom 14. Dezember 2017 E. 3.3.4).
Beurteilen sich solche Vorfragen nach ausländischem Recht, überprüft das Bundesgericht dessen Anwendung im Rahmen der Zuständigkeitsbeschwerde ebenfalls frei und mit voller Kognition. Dabei folgt das Bundesgericht der in der anwendbaren ausländischen Rechtsordnung klar herrschenden Auffassung und bei Kontroversen zwischen Rechtsprechung und Lehre der höchstrichterlichen Judikatur (<ref-ruling> E. 3.2; zit. Urteil 4A_80/2018 E. 2.5; je mit Hinweisen).
3.
3.1. Die hier relevanten Teile von Art. 8 ISA lauten wie folgt:
" Settlement of Disputes Between One Contracting Party and Investors of the Other Contracting Party
1. Disputes between one of the Contracting Parties and an investor of the other Contracting Party, in connection with his investment, shall be notified in writing, including detailed information, by the investor to the recipient Contracting Party of the investment. [...].
2. If these disputes, cannot be settled in this way within ninety (90) days [...], the dispute can be submitted, as the investor may choose, to the competent court of the Contracting Party in whose territory the investment has been made or to international arbitration under:
(a) [...]
(b) [...]
(c) the Court of Arbitration of the Paris International Chamber of Commerce.
3. Once the investor has submitted the dispute to the one of the dispute settlement procedures mentioned in paragraph 2 of this Article, the choice of one of these procedures is final.
4. Notwithstanding the provisions of paragraph 2 of this Article;
(a) only the disputes arising directly out of investment activities which have obtained necessary permission, if any, in conformity with the relevant legislation of both Contracting Parties on foreign capital, and that effectively started shall be subject to the jurisdiction of the International Center for Settlement of Investment Disputes (ICSID), in case both Contracting Parties become signatories of this Convention, or any other international dispute settlement mechanism as agreed upon by the Contracting Parties;
(b) [...]
(c) [...]
5. [...]"
3.2. Ausserdem bestimmt Art. 10 ISA:
"The present Agreement shall apply to investments in the territory of a Contracting Party made in accordance with its laws and regulations by investors of the other Contracting Party before or after the entry into force of this Agreement. However, this Agreement shall not apply to disputes that have arisen before its entry into force."
4.
Ist ein internationales Schiedsgericht mit Sitz in der Schweiz Erstgericht, wurde also das Verfahren zuerst bei ihm anhängig gemacht, so braucht es die Existenz eines parallelen Verfahrens vor einem staatlichen Gericht oder einem Schiedsgericht (im In- oder Ausland) unter dem Gesichtspunkt der Regeln der Rechtshängigkeit nicht zu beachten. Als Erstgericht hat das Schiedsgericht Vorrang (Urteil 4P.124/2001 vom 7. August 2001 E. 3c/dd; CHRISTIAN OETIKER, in: Zürcher Kommentar zum IPRG, 2018, N. 39 zu <ref-law>; STEPHANIE PFISTERER, in: Basler Kommentar Internationales Privatrecht, 4. Aufl. 2020, N. 19 zu <ref-law>; KAUFMANN-KOHLER/RIGOZZI, International Arbitration, Law and Practice in Switzerland, 2015, Rz. 5.61). Das Tripolis-Verfahren wurde erst am 25. März 2018 eingeleitet; das vorliegende Schiedsverfahren wurde - sofern es denn überhaupt die gleichen Parteien und den gleichen Streitgegenstand betrifft, was die Beschwerdegegnerin bestreitet - demgegenüber gemäss den Feststellungen des Schiedsgerichts bereits mit Einreichung des Request for Arbitration vom 29. August 2016 (Eingang beim ICC-Secretariat am 31. August 2016) anhängig gemacht. Grundsätzlich musste das Schiedsgericht somit das Tripolis-Verfahren nicht beachten.
4.1.
Der Beschwerdeführer rügt eine unrechtmässige Ausübung der Kompetenz-Kompetenz durch das Schiedsgericht.
4.1.1. Zwar habe das Schiedsgericht gestützt auf <ref-law> über die Gültigkeit der Vergleichsvereinbarung als Vorfrage der Zuständigkeit selbständig entscheiden können. Angesichts der fehlenden Abrede der Schiedsgerichtsbarkeit in der Vergleichsvereinbarung selbst habe er, der Beschwerdeführer, aber das Recht gehabt, die Gültigkeit der Vereinbarung vor dem zuständigen staatlichen Gericht in Libyen prüfen zu lassen. Er habe sich nicht mit der vorfrageweisen Prüfung durch ein Schiedsgericht begnügen müssen. Sei das Gericht in Tripolis also zuständig gewesen, sei dessen Urteil in der Schweiz auch anerkennungsfähig. Daher hätte das Schiedsgericht seinen Entscheid mit dem ihm bekannten Verfahren beim Gericht in Tripolis, in dem identische Begehren gestellt worden seien, koordinieren müssen. Dies sei eine Regel der internationalen Courtoisie. Damit hätte vermieden werden können, dass widersprechende Entscheide im Tripolis-Verfahren und im vorliegenden gefällt worden wären.
4.1.2. Der Beschwerdeführer vermag mit seiner Argumentation nicht durchzudringen: Da das Schiedsverfahren vor dem Tripolis-Verfahren eingeleitet wurde, musste das Schiedsgericht aufgrund der zeitlichen Priorität des Schiedsverfahrens - worauf die Beschwerdegegnerin zutreffend hinweist - nicht einmal auf <ref-law> zurückgreifen, um seine Kompetenz-Kompetenz zu begründen. Dass dem Schiedsgericht aufgrund einer angeblichen internationalen Courtoisie oblegen wäre, seinen Entscheid mit dem Tripolis-Verfahren zu koordinieren, weist der Beschwerdeführer nicht rechtsgenüglich nach.
Anzufügen bleibt, dass der Argumentation des Beschwerdeführers auch insofern nicht zu folgen ist, als er angibt, mangels fehlender Schiedsklausel in der Vergleichsvereinbarung habe er sich nicht mit der vorfrageweisen Prüfung der Gültigkeit der Vergleichsvereinbarung durch ein Schiedsgericht begnügen müssen, sondern habe diese von einem staatlichen Gericht prüfen lassen dürfen. Um diese Behauptung zu belegen, verweist er auf eine Literaturstelle (SCHOTT/COURVOISIER, in: Basler Kommentar Internationales Privatrecht, 3. Aufl. 2013, N. 7 zu <ref-law>), bei der aber lediglich für den Fall, dass nicht einmal der Anscheineiner gültigen Schiedsabrede gegeben ist, die Auffassung vertreten wird, diesfalls sei dem potentiell Schiedsbeklagten nicht zuzumuten, die Frage der schiedsgerichtlichen Zuständigkeit vor dem Schiedsgericht zu erörtern. Von einer solchen Ausgangslage kann hier aber keine Rede sein.
4.2. Nach Auffassung des Beschwerdeführers hätte das Schiedsgericht sodann seine Zuständigkeit aufgrund des Prinzips der abgeurteilten Sache verneinen müssen. Denn das Tripolis-Urteil sei in der Schweiz anerkenn- und vollstreckbar und damit für jedes Schiedsgericht in der Schweiz bindend.
Auch dieser Einwand geht fehl. Zum einen ist nicht nachvollziehbar, wie das Schiedsgericht das Tripolis-Urteil hätte berücksichtigen können, wurde dieses vom Beschwerdeführer doch überhaupt nicht in den Schiedsprozess eingeführt. Er macht geltend, das Tripolis-Urteil sei erst nach Abschluss des Schiedsverfahrens ("close of proceedings") am 15. Januar 2019 ergangen und es sei der Beschwerdegegnerin rechtsgültig in beglaubigter Form zusätzlich zur diplomatischen Zustellung am 20. September 2019 zugestellt worden. Obgleich dies zutreffen mag, ändert es nichts daran, dass das Schiedsgericht das Urteil mangels Kenntnis nicht berücksichtigen konnte.
Zum anderen geht der Einwand auch unabhängig von der Kenntnis des Tripolis-Urteils durch das Schiedsgericht an der Sache vorbei: Abgesehen davon, dass der Beschwerdeführer die Rechtskraft des Tripolis-Urteils nicht nachgewiesen hat, wie die Beschwerdegegnerin zu Recht entgegenhält, wird gemäss <ref-law> eine im Ausland ergangene Entscheidung in der Schweiz nicht anerkannt, wenn eine Partei nachweist, dass ein Rechtsstreit zwischen denselben Parteien über denselben Gegenstand zuerst in der Schweiz eingeleitet worden ist, selbst wenn das schweizerische Verfahren länger dauert als das später eingeleitete ausländische Verfahren (DÄPPEN/MABILLARD, in: Basler Kommentar Internationales Privatrecht, 4. Aufl. 2020, N. 66 zu <ref-law>; vgl. auch MARKUS MÜLLER-CHEN, in: Zürcher Kommentar zum IPRG, Band I, 3. Aufl. 2018, N. 104 zu <ref-law>).
5.
Das Schiedsgericht prüfte, ob die Streitigkeit in sachlicher Hinsicht in den Anwendungsbereich des ISA fällt.
5.1. Hierfür verwies es einleitend auf Art. 1 Abs. 2 ISA, der den Begriff der Investition ("investment") in nicht abschliessender Aufzählung (lit. a-e) definiert. Vorliegend handle es sich um eine Investition gemäss Art. 1 Abs. 2 lit. b ISA ("returns reinvested, claims to money or any other rights having financial value related to an investment"). Die Vergleichsvereinbarung selbst sei eine Investition in diesem Sinn, nämlich "claims to money related to an investment", denn sie gewähre der Beschwerdegegnerin einen Anspruch über LD 5'420'308.707. Die Vergleichsvereinbarung sei "related to an investment" in dem Sinne, als sie Ausfluss der Investitionen des Beschwerdeführers in den 1980er- und 1990er-Jahren sei ("in that it flows from, and crystallizes, a range of earlier investments"). Dass diese Investitionen vor dem Inkrafttreten des ISA im April 2011 getätigt worden seien, schade nicht, wie sich aus Art. 10 ISA (vgl. E. 3.2 hiervor) ergebe. Gemäss Art. 10 schütze das ISA auch Investitionen, die vor dem 22. April 2011 getätigt worden seien, nicht jedoch daraus entstandene Streitigkeiten ("disputes"). Die Zuständigkeit des Schiedsgerichts ratione materiae sei somit gegeben.
5.2. Der Beschwerdeführer macht geltend, die Argumentation des Schiedsgerichts basiere ausschliesslich auf der Vergleichsvereinbarung. Sei diese nicht gültig, entfalle die Zuständigkeit. Entsprechend bestreitet er die Gültigkeit unter zwei Aspekten.
5.2.1. Zum einen sei die Vergleichsvereinbarung nicht gültig, da der stellvertretende Finanzminister nicht bevollmächtigt gewesen sei, diese für den Staat Libyen rechtsgültig zu unterzeichnen.
5.2.1.1. Das Schiedsgericht erwog, es könne offenbleiben, ob nach dem auf diese Frage unbestrittenermassen anwendbaren libyschen Recht der stellvertretende Finanzminister tatsächlich befugt gewesen sei, die Vergleichsvereinbarung zu unterzeichnen. Denn er habe jedenfalls über eine "apparent authority" verfügt, auf welche sich die Beschwerdegegnerin in guten Treuen habe verlassen dürfen. Nach libyschem Recht setze eine "apparent authority" zweierlei voraus: Der Vertragspartner, der sich darauf stütze, müsse erstens in gutem Glauben annehmen dürfen, der Vertreter habe Vertretungsmacht, und zweitens müsse der Anschein der Vertretungsmacht vom Vertretenen geschaffen worden sein ("external appearance of authority, as created by the principal"). Die erste Voraussetzung, der gute Glaube, verlange, dass derjenige, der sich auf die "apparent authority" berufe, gewisse Abklärungen darüber getroffen habe ("due diligence duty"); betreffend die zweite Voraussetzung hielt das Schiedsgericht fest, der Anschein der Vertretungsmacht habe in concreto vom Finanzministerium geschaffen worden sein müssen, wobei der Finanzminister seinerseits darum gewusst oder dies (zumindest) geduldet haben musste. Gestützt auf zahlreiche Sachverhaltselemente, bezogen auf die Zeit sowohl vor wie auch nach Abschluss der Vergleichsvereinbarung, bejahte das Schiedsgericht beide Voraussetzungen einer "apparent authority".
5.2.1.2. Der Beschwerdeführer beruft sich auf die Verordnung Nr. 1 von 2012 und das Urteil 15/64 des libyschen Obersten Gerichts vom 6. Januar 1970, aus welchen sich ergebe, dass der stellvertretende Minister keine Kompetenz zum Abschluss der Vereinbarung gehabt habe. Diese rechtlichen Grundlagen seien nicht nur entscheidend für die vom Schiedsgericht offen gelassene Frage, ob der stellvertretende Minister tatsächlich Vertretungsmacht gehabt habe, sondern bestimmten zudem das Sorgfaltsmass unter dem Aspekt der "apparent authority". Angesichts der klaren Kompetenzregelung nach libyschem Recht habe das Schiedsgericht nicht einfach auf von einem Zeugen beschriebene fragwürdige äussere Umstände abstellen dürfen, die angeblich den Anschein der Vertretungsmacht des stellvertretenden Finanzministers begründen würden. Das Umstossen der durch die einschlägige libysche Verordnung vorgegebenen Kompetenzordnung hätte ein gesteigertes Mass an Abklärung vor der Unterzeichnung der Vereinbarung erfordert. Die Beschwerdegegnerin habe nicht den Beweis dafür erbracht, dass sie die entsprechenden Abklärungen vorgenommen habe, weshalb sie sich nicht auf die Anscheinsvollmacht - so das Verständnis der "apparent authority" seitens des Beschwerdeführers - habe berufen dürfen, was das Schiedsgericht indes verkannt habe. Gestützt auf diese einschlägigen Rechtsquellen wäre nämlich zu erwarten gewesen, dass die im relevanten Zeitpunkt anwaltlich beratene Beschwerdegegnerin die Regelung in der Verordnung Nr. 1 beachtet hätte.
Wie die Beschwerdegegnerin zutreffend geltend macht, wurde nicht festgestellt, dass sie durchgehend anwaltlich vertreten war. Vor allem aber ist nicht einzusehen, weshalb ein Anwalt der Beschwerdegegnerin die Verordnung Nr. 1 von 2012 besser kennen müsste, als (offensichtlich) der stellvertretende Finanzminister, die Mitarbeiter des Finanzdepartements und der Finanzminister selbst. Das Schiedsgericht stellte nämlich fest, dass Beamte des libyschen Staats wiederholt und ohne anderweitige Hinweise die Zuständigkeit des stellvertretendenden Finanzministers bestätigten. Wenn der Beschwerdeführer weiter ins Feld führt, das Schiedsgericht habe bei der Feststellung dieses Sachverhalts auf viele "fragwürdige äussere Umstände" abgestellt, übt er unzulässige Kritik an dessen Beweiswürdigung (vgl. E. 2.4 hiervor).
5.2.2. Der Beschwerdeführer rügt sodann, das Schiedsgericht habe sich nicht mit seiner zweiten Einwendung gegen die Gültigkeit der Vergleichsvereinbarung auseinandergesetzt, wonach bei Unterzeichnung der Vereinbarung zwingende formelle Verfahrensvorschriften nicht beachtet worden seien. Art. 4 und Art. 5 des libyschen Gesetzes Nr. 87 erforderten für die Gültigkeit eines Vergleichs die vorgängige Zustimmung durch die Abteilung für Streitbeilegung der libyschen Regierung. Die gegenteilige Auffassung des Experten der Beschwerdegegnerin habe der Experte des Beschwerdeführers verworfen. Da es das Schiedsgericht unterlassen habe, sich mit der Frage des Zustimmungserfordernisses auseinanderzusetzen, habe es eine Gehörsverletzung begangen und sei zu einem falschen Schluss gekommen. Das zuständige Gericht in Libyen habe mit Urteil vom 2. Mai 2019 in der gleichen Frage die Vergleichsvereinbarung denn auch für ungültig erklärt.
Auch auf diesen Einwand muss nicht weiter eingegangen werden: Durfte das Schiedsgericht von einer "apparent authority" ausgehen, waren weitere Ausführungen zu den hier - im Übrigen nur behaupteten - formellen Anforderungen der Gültigkeit der Vereinbarung obsolet. Entsprechend verletzte das Schiedsgericht auch nicht das rechtliche Gehör des Beschwerdeführers.
Der Beschwerdeführer dringt somit mit seinen Rügen gegen die Gültigkeit der Vergleichsvereinbarung nicht durch, womit auch sein unter dem Titel "Keine Zuständigkeit ratione materiae" vorgebrachter Einwand - Unzuständigkeit des Schiedsgerichts, da kein "claim to money" im Sinne von Art. 1 Abs. 2 lit. b ISA vorliege, weil die Vergleichsvereinbarung ungültig sei - gegenstandslos wird. Im Übrigen bestreitet er die Zuständigkeit des Schiedsgerichts in sachlicher Hinsicht nicht.
6.
6.1. Das Schiedsgericht erwog hinsichtlich der zeitlichen Anwendbarkeit des ISA, gemäss Art. 10 ISA (vgl. E. 3.2 hiervor) bedürfe es einer Streitigkeit ("dispute"), die nach Inkrafttreten des ISA, also nach dem 22. April 2011, entstanden sei. Die Vergleichsvereinbarung stelle einen "compromise" nach libyschem Recht dar, der bewirke, dass alle früheren Streitigkeiten aufgehoben würden. Aufgrund der Nichteinhaltung der Vergleichsvereinbarung durch den Beschwerdeführer sei ein neuer Streit im Sinn von Art. 8 und Art. 10 ISA entstanden. Die Vergleichsvereinbarung stelle einen Bruch ("break in the timeline") in den Streitigkeiten zwischen den Parteien dar. Da die Vereinbarung im Dezember 2013 abgeschlossen worden und das ISA am 22. April 2011 in Kraft getreten sei, falle jegliche diese Vereinbarung betreffende Streitigkeit in den Anwendungsbereich des ISA.
6.2. Der Beschwerdeführer rügt, diese ("zu enge", "legalistische") allein auf die Rechtswirkungen einer Vergleichsvereinbarung nach libyschem Recht bezogene Auslegung der Vorinstanz gehe fehl. Die Auslegung der Vergleichsvereinbarung habe nach dem Wiener Übereinkommen vom 23. Mai 1969 über das Recht der Verträge (VRK; SR 0.111) zu erfolgen. Eine Auslegung des ISA nach Treu und Glauben mache klar, dass dessen Vertragsparteien nicht die Absicht gehabt hätten, den vereinbarten Investitionsschutz auf bereits entstandene Auseinandersetzungen zu erstrecken. Dass vorliegend ein Vergleich abgeschlossen worden sei, ändere nichts daran, dass die Auseinandersetzungen zwischen dem Beschwerdeführer und der Beschwerdegegnerin bereits vor dem Abschluss des ISA entstanden seien. Die Ausführungen des Schiedsgerichts zum Verständnis von "compromise" gemäss libyschem Recht träfen nur soweit zu, als es um neue Ansprüche im engeren Sinn ("claims") aus der Vergleichsvereinbarung gehe. Soweit jedoch eine autonome Auslegung, wie bei Investitionsschutzabkommen gefordert, zur Anwendung gelange, gingen die Überlegungen zum libyschen Recht fehl, da sie nicht das umfassende Verständnis von "dispute" im Sinne von Art. 10 ISA berücksichtigten, welches über die Bedeutung von "claim" hinausgehe. Sinn und Zweck des ISA sei es gemäss seiner Präambel, neue Investitionen anzulocken ("encouragement and reciprocal protection of investments") bzw. Anreize für Neuinvestitionen zu schaffen, "which will stimulate the flow of capital and technology and the economic development of the Contracting Parties". Daher sollten alte, vor Inkrafttreten des ISA bestehende Streitigkeiten ausgeschlossen bleiben, da die Vertragsstaaten des ISA Ansprüche, die bereits vor dessen Inkrafttreten zwischen den Parteien kontrovers gewesen seien, nicht vom Rechtsschutz des ISA hätten profitieren lassen wollen, selbst wenn sie nach dessen Inkrafttreten noviert worden seien. Überdies könne der alte Streit erst mit der Erfüllung der Vergleichsvereinbarung als beigelegt gelten.
6.3. Ein Staatsvertrag ist gemäss Art. 31 Abs. 1 VRK nach Treu und Glauben in Übereinstimmung mit der gewöhnlichen, seinen Bestimmungen in ihrem Zusammenhang zukommenden Bedeutung und im Lichte seines Zieles und Zweckes auszulegen. Zusammen mit der Auslegung nach Treu und Glauben garantiert die teleologische Auslegung den "effet utile" des Vertrags. Der auszulegenden Bestimmung ist unter mehreren möglichen Interpretationen derjenige Sinn beizumessen, der ihre effektive Anwendung gewährleistet und nicht zu einem Ergebnis führt, das dem Ziel und Zweck des Vertrags widerspricht (BGE 144 III 599 E. 4.4.2 S. 568; <ref-ruling> E. 8.2.1 S. 139; <ref-ruling> E. 5.2.2 S. 148 f.; <ref-ruling> E. 2.1.3 S. 167; <ref-ruling> E. 3.5.1 S. 503).
6.4. Dem Beschwerdeführer kann nicht gefolgt werden. Vorerst ist fraglich, ob überhaupt eine genügende Rüge (vgl. E. 2.3) vorliegt, wenn der Beschwerdeführer schlicht behauptet, das Schiedsgericht habe das "umfassende Verständnis von 'dispute' im Sinne von Art. 10 ISA" nicht berücksichtigt und nach Treu und Glauben könne sich der Investitionsschutz nicht auf bereits früher entstandene Auseinandersetzungen erstrecken. Im Übrigen ist die Argumentation des Schiedsgerichts überzeugend: Die vorliegende Streitigkeit entstand, weil die Vergleichsvereinbarung nicht erfüllt und deren Gültigkeit bestritten wurde. Dieser Streit um die Gültigkeit der Vergleichsvereinbarung fällt ohne Weiteres unter Art. 10 ISA. Die Vergleichsvereinbarung stellte ihrerseits unmissverständlich klar, dass mit ihrem Abschluss alle nationalen und internationalen Gerichts- und sonstigen Verfahren im Zusammenhang mit dem Beida-Urteil eingestellt werden (vgl. Sachverhalt A.). Es existierten zwischen den Parteien somit keine Streitigkeiten ("disputes") mehr aus der Zeit vor dem Inkrafttreten des ISA. Wie die Beschwerdegegnerin zutreffend anführt, begründete das Schiedsgericht seinen Zuständigkeitsentscheid nicht ausschliesslich mit Verweis auf die Wirkungen eines Vergleichs ("compromise") nach libyschem Recht, sondern primär gestützt auf den Wortlaut der Vergleichsvereinbarung. Damit setzt sich der Beschwerdeführer indes nicht auseinander, weshalb auch keine genügende Rüge vorliegt. Auf die Frage, welche Rechtswirkungen ein Vergleich nach libyschem Recht hat, braucht somit nicht weiter eingegangen zu werden.
Auch der Hinweis auf Sinn und Zweck des ISA gemäss dessen Präambel hilft dem Beschwerdeführer nicht. Mit diesem Vorbringen scheint er behaupten zu wollen, dass unter den Schutz des ISA nur nach dessen Abschluss angelockte und damit getätigte Investitionen fallen. Diese Argumentation widerspricht jedoch dem Wortlaut von Art. 10 ISA, der ausdrücklich von "investments [...] before or after the entry into force of this Agreement" spricht. Im Übrigen basiert das ISA, wie die nicht abschliessende Aufzählung ("not exclusively") der als "investment" geschützten Vermögenswerte in Art. 1 Abs. 1 ISA belegt, auf einer breiten vermögensorientierten Sichtweise, die nicht auf der Vornahme einer bestimmten Handlung (Transaktion) beruht. Das Abkommen bezweckt daher sowohl die Förderung als auch den gegenseitigen Schutz von Investitionen (vgl. zu dieser Unterscheidung zwischen transaktionsbasiertem und vermögensorientiertem Ansatz <ref-ruling> E. 4.4.2 und 4.4.3 S. 570 f.). Das Schiedsgericht ging daher zu Recht davon aus, dass das ISA auch zeitlich anwendbar ist.
An diesem Ergebnis vermag auch der Hinweis des Beschwerdeführers auf die von ihm ins Recht gelegten ICSID-Entscheide nichts zu ändern. Solche Entscheide stellen im Bereich des internationalen Investitionsschutzes ohnehin keine eigentlichen Rechtsquellen dar, nach denen sich das Schiedsgericht zu richten hätte (<ref-ruling> E. 4.4.2 S. 569).
Auf die von der Beschwerdegegnerin bereits vor dem Schiedsgericht und erneut im Beschwerdeverfahren vorgebrachte Alternativbegründung, wonach die Zuständigkeit unabhängig von der Gültigkeit der Vergleichsvereinbarung auch gegeben wäre, weil ihre Tätigkeiten in Libyen in den 1980er- und 1990er-Jahren Investitionen im Sinne von Art. 8 ISA seien und die Vorgehensweise des Beschwerdeführers im Zusammenhang mit dem Abschluss der Vergleichsvereinbarung und der Bestreitung deren Gültigkeit eine Verletzung des durch das ISA garantierten Gebots der fairen und gerechten Behandlung ("fair and equitable treatment", FET; vgl. dazu auch BGE <ref-ruling> E. 3 S. 496 ff.) darstelle, braucht daher nicht mehr eingegangen zu werden.
7.
Die Beschwerde ist somit abzuweisen, soweit darauf einzutreten ist. Dem Ausgang des Verfahrens entsprechend wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 60'000.-- werden dem Beschwerdeführer auferlegt.
3.
Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 80'000.-- zu entschädigen. Diese Entschädigung wird aus der an die Bundesgerichtskasse bezahlten Sicherheitsleistung ausgerichtet.
4.
Dieses Urteil wird den Parteien und dem Schiedsgericht mit Sitz in Genf schriftlich mitgeteilt.
Lausanne, 2. November 2020
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Kiss
Der Gerichtsschreiber: Bittel