< Terug naar vorige pagina

Project

Berekenen van de exacte prestaties van black-box-optimalisatiemethoden: een geautomatiseerde tool om het begrip te verbeteren en betere algoritmen te ontwerpen

Optimalisatie-algoritmen worden overal in toegepaste wiskunde gebruikt, waar ze helpen het verbruik of de kosten te minimaliseren, of de impact of winst te maximaliseren, in een grote verscheidenheid aan toepassingen in de wetenschap, techniek, industrie en het bedrijfsleven; ze vormen ook de kern van de meeste technieken voor machine learning. Algoritmen die in de praktijk het beste presteren, zijn vaak die waarvoor we een goed theoretisch begrip hebben. In het bijzonder probeert men gewoonlijk het worst-case gedrag van een bepaald algoritme te analyseren op een typische klasse van invoerproblemen die, eenmaal geïdentificeerd en formeel bewezen, sterke garanties bieden voor de prestaties ervan (zoals nauwkeurigheid na een bepaald aantal iteraties). Het ontwerpen van wiskundige convergentiebewijzen is een hoogst niet-triviaal proces dat creativiteit vereist en vaak alleen niet-strakke grenzen identificeert. Een geheel andere benadering zoals onlangs geïntroduceerd, waarbij het probleem van het identificeren van de worst-case zelf werd voorgesteld als een optimalisatieprobleem, dat effectief kan worden berekend voor een grote klasse van optimalisatie-algoritmen en invoerproblemen (inclusief eerste-orde-methoden die worden toegepast op convexe problemen). ). Het analyseren van deze algoritmen in dergelijke situaties kan daarom volledig worden geautomatiseerd, wat leidt tot moeiteloze bewijzen en bruikbaar inzicht in de worst case-functies. Dit project zal drie complementaire richtingen in dit nieuwe veld van prestatie-inschatting onderzoeken: (1) ten eerste zal men grotere klassen van invoerproblemen onderzoeken, waarbij men de convexiteitseis loslaat (2) ten tweede, zal het raamwerk gegeneraliseerd worden om andere soorten algoritmen mogelijk te maken. deterministische eerste-orde-methoden, (3) ten derde, deze benadering zal worden gebruikt om nieuwe methoden te ontwerpen die de best mogelijke prestaties bereiken.

Datum:24 mrt 2021 →  Heden
Trefwoorden:Optimization, Nonconvex optimization, Performance estimation, Algorithm design
Disciplines:Variatieberekening, optimale controle en optimalisatie, Numerieke analyse, Numerical computation, Automatisatie en controlesystemen
Project type:PhD project