Active set

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En optimisation mathématique, un problème est défini en utilisant une fonction objectif à minimiser ou maximiser, et un ensemble de contraintes :

g_1(x)\ge 0, \dots, g_k(x)\ge 0

qui définissent l'espace de solutions admissibles qui est l'ensemble des x à tester afin de trouver la solution optimale. Soit un point x admissible, une contrainte

g_i(x) \ge 0

est dite active au point x si g_i(x)=0 et inactive au point x si g_i(x)>0. Par conséquent, les contraintes d'égalité sont toujours actives. L'active set au point x est l'ensemble des contraintes g_i(x) actives au point courant[1].

L'active set est particulièrement important en optimisation car il permet de déterminer quelles contraintes influencent le résultat final. Par exemple, en résolvant un problème d'optimisation linéaire, l'active set fournit les hyperplans qui se croisent au point formant la solution. En optimisation quadratique, comme la solution n'est pas obligatoirement sur l'un des bords du polygone formant la frontière du domaine admissible, une estimation de l'active set nous permet d'avoir un sous-ensemble d'inégalités à regarder pour chercher la solution, ce qui réduit la complexité de la recherche.

En général, un algorithme Active set a la structure suivante :

Trouver un point de départ admissible
répéter jusqu'à « optimisation suffisante » (en observant par exemple les conditions KKT)
résoudre le problème d'égalité défini par l'active set (approximativement)
calculer les multiplicateurs de Lagrange de l'active set
enlever un sous-ensemble de contraintes correspondant aux multiplicateurs de Lagrange négatifs (cela indique en effet que la fonction objectif peut encore être optimisée en rendant inactives les contraintes correspondantes), on enlève les contraintes par ordre du multiplicateur le plus négatif.
fin répéter

Note et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Active set » (voir la liste des auteurs).

  1. (en) Jorge Nocedal et Stephen J. Wright, Numerical Optimization, Springer,‎ 2006, 2e éd. (ISBN 978-0-387-30303-1), p. 308