Optimisation

Optimisation — extrema libres, Lagrange, convexité & gradient

Idée. Optimiser, c'est trouver le minimum ou le maximum d'une fonction : un coût à réduire, un profit à maximiser, une erreur d'ajustement à minimiser, une énergie à abaisser. En dimension $\ge2$ , on cherche d'abord les points critiques (gradient nul), on détermine leur nature, puis on traite les contraintes (Lagrange) ; la convexité garantit qu'un minimum local est global, et la descente de gradient est l'algorithme universel de minimisation.

A. Extrema libres (sans contrainte)

Point critique : $\nabla f=\vec0$ , c.-à-d. $f_x=f_y=0$ . C'est une condition nécessaire d'extremum à l'intérieur du domaine.
Nature via la Hessienne $H=\begin{pmatrix}f_{xx}&f_{xy}\\ f_{xy}&f_{yy}\end{pmatrix}$ . En posant $r=f_{xx},\ s=f_{xy},\ t=f_{yy}$ et le discriminant $rt-s^2=\det H$ :
- $rt-s^2>0$ et $r>0\Rightarrow$ minimum local ;
- $rt-s^2>0$ et $r<0\Rightarrow$ maximum local ;
- $rt-s^2<0\Rightarrow$ point col (selle) ;
- $rt-s^2=0\Rightarrow$ cas douteux (test non concluant, examiner directement).
De façon équivalente : signe des valeurs propres de $H$ (toutes $>0\Rightarrow$ min, toutes $<0\Rightarrow$ max, signes mixtes $\Rightarrow$ col).

Exemple. $f=x^2+y^2-4x-6y+13=(x-2)^2+(y-3)^2$ : point critique $(2,3)$ , $H=2I$ ( $rt-s^2=4>0$ , $r>0$ ) $\Rightarrow$ minimum global, valeur $0$ .

B. Extrema liés — multiplicateurs de Lagrange

Pour optimiser $f(x,y)$ sous la contrainte $g(x,y)=0$ : à l'optimum, les lignes de niveau de $f$ sont tangentes à la courbe de contrainte, donc les gradients sont colinéaires :

\boxed{\ \nabla f=\lambda\,\nabla g,\qquad g=0\ }

(

\lambda

= multiplicateur de Lagrange). On résout ce système. Avec plusieurs contraintes

g_i=0

\nabla f=\sum_i\lambda_i\,\nabla g_i

Plusieurs lignes de niveau concentriques d'une fonction et une courbe de contrainte ; au point de tangence entre une ligne de niveau et la contrainte, deux vecteurs gradients alignés sont dessinés ; illustration des multiplicateurs de Lagrange. — Multiplicateurs de Lagrange : à l'optimum lié, une **ligne de niveau** de $f$ (en bleu) est **tangente** à la courbe de contrainte $g=0$ (en orange). Les gradients $\nabla f$ et $\nabla g$ y sont alors **colinéaires** ( $\nabla f=\lambda\nabla g$ ) — c'est la condition qui localise l'extremum sous contrainte.

Exemple. Aire maximale d'un rectangle de périmètre $20$ : maximiser $xy$ sous $x+y=10$ . $\nabla f=(y,x)=\lambda(1,1)\Rightarrow x=y=5$ , aire $25$ (le carré).

C. Convexité

$f$ est convexe si sa Hessienne est semi-définie positive en tout point (toutes les valeurs propres $\ge0$ ). Conséquence capitale :

f\ \text{convexe}\ \Longrightarrow\ \text{tout point critique est un minimum }\textbf{GLOBAL}

(plus de minimum local parasite, plus de col). Une somme de fonctions convexes est convexe ; une forme quadratique

\tfrac12\vec x^{\mathsf T}Q\vec x

est convexe ssi

Q

est semi-définie positive (

Q\succeq0

D. Descente de gradient

Pour minimiser $f$ numériquement, on part de $\vec x_0$ et on descend dans la direction de plus forte pente $-\nabla f$ :

\boxed{\ \vec x_{n+1}=\vec x_n-\alpha\,\nabla f(\vec x_n)\ }

\alpha>0

est le pas (learning rate). Trop petit

\Rightarrow

lent ; trop grand

\Rightarrow

divergence. Sur

f(x)=x^2

x_{n+1}=(1-2\alpha)x_n

, stable ssi

0<\alpha<1

. Un mauvais conditionnement (vallée étirée) provoque des zig-zags lents. C'est l'algorithme au cœur du machine learning.

Exemple. $f(x)=x^2$ , $x_0=1$ , $\alpha=0{,}1$ : $x_1=0{,}8$ , $x_2=0{,}64$ , $x_3=0{,}512$ , $\dots\to0$ (suite géométrique de raison $0{,}8$ ).

Optimisation — extrema libres, Lagrange, convexité & gradient

A. Extrema libres (sans contrainte)

B. Extrema liés — multiplicateurs de Lagrange

C. Convexité

D. Descente de gradient

Dans le palier approfondissement (Pro) : Programmation linéaire, dualité & conditions KKT

La suite dans l'app Maths Post-Bac