Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Optimisation quadratique successive
Résumé
L'optimisation quadratique successive est un algorithme de résolution d'un problème d'optimisation non linéaire. Un tel problème consiste à déterminer des paramètres qui minimisent une fonction, tout en respectant des contraintes d'égalité et d'inégalité sur ces paramètres. On parle aussi de l'algorithme OQS pour Optimisation Quadratique Successive ou de l'algorithme SQP pour Sequential Quadratic Programming, en anglais.
C'est un algorithme newtonien appliqué aux conditions d'optimalité du premier ordre du problème. Plus précisément, on peut le voir comme un algorithme de Josephy-Newton appliqué à ces conditions d'optimalité, écrites comme un problème d'inclusion fonctionnelle ou comme un problème de complémentarité. De ce fait, l'algorithme bénéficie d'une convergence locale rapide, mais chaque itération pourra demander beaucoup de temps de calcul (c'est surtout vrai dans les premières itérations). Par ailleurs, l'algorithme ne fait pas de distinction entre minima et maxima (comme l'algorithme de Newton pour minimiser une fonction sans contrainte), mais ses itérés sont attirés par tout point stationnaire «régulier». L'algorithme se globalise facilement, ce qui veut dire que l'on connait des techniques permettant la plupart du temps de forcer la convergence des itérés, même si le premier itéré n'est pas proche d'une solution du problème d'optimisation.
L'algorithme requiert que les fonctions définissant le problème d'optimisation soient «suffisamment» différentiables. Il se définit naturellement en utilisant les dérivées secondes des fonctions définissant le problème, mais il se décline aussi sous une forme quasi-newtonienne, qui ne requiert donc que l'évaluation des dérivées premières.
Connaissances supposées : le calcul différentiel (on linéarise des fonctions) et les conditions d'optimalité des problèmes d'optimisation avec contraintes (qui est le système linéarisé) ; l'approche utilisée pour introduire l'algorithme sera mieux comprise si l'on a pris connaissance auparavant de l'algorithme de Josephy-Newton, mais ce dernier point n'est pas essentiel ; bien sûr, l'algorithme a un lien étroit avec l'algorithme de Newton.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.