AnnalesÉcoles d'ingénieurs

X-ENS MP 2020 — Maths C

Minimisation sous contraintes : pénalisation, Karush-Kuhn-Tucker et algorithme d'Uzawa · 12 pages

Le problème étudie la minimisation d'une fonction $f$ sur une partie $K$ de $\mathbb{R}^n$ définie par des contraintes $g_i(x) \leqslant 0$ . Après des préliminaires sur les fonctions convexes et $\alpha$ -convexes, les fonctions coercives, la projection sur un convexe fermé et le cône des directions admissibles, il justifie la méthode de pénalisation, démontre le lemme de Farkas puis le théorème de Karush-Kuhn-Tucker, et étudie le problème dual via le lagrangien et ses points selles, jusqu'à la convergence de l'algorithme d'Uzawa $\mu_{k+1} = P(\mu_k + \rho g(x_{\mu_k}))$ pour des contraintes affines.

Le sujet, partie par partie

Notations et Partie I — Préliminaires p. 3–4

Fonctions convexes · Extrema et optimisation · Ensembles convexes · Calcul différentiel · Compacité · Projection orthogonale et moindres carrés — fonction convexe, fonction $\alpha$ -convexe, fonction coercive, projection sur un convexe fermé, cône admissible, condition nécessaire d'optimalité, inégalité de monotonie du gradient

Partie II — Pénalisation p. 5

Optimisation sous contraintes d'inégalité · Fonctions convexes · Compacité · Suites numériques — méthode de pénalisation, fonction pénalisée, minimum unique, sous-suite convergente, contraintes d'inégalité

Partie III — Théorème de Karush-Kuhn-Tucker p. 5–7

Optimisation sous contraintes d'inégalité · Ensembles convexes · Fonctions convexes · Espaces vectoriels et dimension · Topologie, compacité, connexité — lemme de Farkas, cône convexe fermé, théorème de Karush-Kuhn-Tucker, multiplicateurs de Lagrange, contraintes actives, condition de qualification

Partie IV — Étude du problème dual p. 7–8

Optimisation sous contraintes d'inégalité · Descente de gradient · Points fixes et suites itératives · Fonctions convexes — lagrangien, problème dual, point selle, théorème d'Uzawa, algorithme d'Uzawa, projection sur l'orthant positif, gradient projeté

Dans l'édifice

Dérivabilité Applications différentiables Théorème de Hahn-Banach Fonctions de classe Cᵏ Inégalité des accroissements finis Compacité Espaces de Hilbert et théorème de projection Suites réelles et limites Théorème de Bolzano-Weierstrass Complétude de ℝ Espaces vectoriels et sous-espaces Familles libres, génératrices, bases Dimension d'un espace vectoriel Sommes directes, supplémentaires, projecteurs Espace topologique Caractérisations de la connexité Topologie de ℝ Théorème du point fixe de Banach Théorème du point fixe de Knaster-Tarski