Aller au contenu principal
Maths-App

Cours · Bac+3 (ingénieur)

Optimisation

Fiches de cours et sous-notions liées à ce chapitre.

Connecte-toi pour t'entraîner

Pas assez de questions pour un entraînement ciblé sur cette notion.

Convexité

Non commencé

Définitions

Une fonction f:Rn→Rf : \mathbb{R}^n \to \mathbb{R} est convexe si f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y)f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y) pour λ∈[0,1]\lambda \in [0,1]. Équivalent : epigraphe convexe, ou Hessienne ∇2f⪰0\nabla^2 f \succeq 0 si C2C^2.

Strictement convexe ⇒\Rightarrow au plus un minimum global. Fonctions convexes : normes, exe^x, x2x^2, −ln⁡x-\ln x sur x>0x>0. Dualité convexe (Fenchel) et conditions KKT pour optimisation sous contraintes. En ingénierie : moindres carrés, Lasso, problèmes de flux sont convexes (résolution globale garantie).

ff convexe : f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y)f(\lambda x+(1-\lambda)y)\leq\lambda f(x)+(1-\lambda)f(y). Si C2C^2 : ∇2f⪰0\nabla^2 f\succeq 0. Minimum local = global.

Exemples : normes, exe^x, x2x^2, −ln⁡-\ln. KKT pour contraintes.

Formules

  • f convexe ⇔∇2f(x)⪰0 (si C2)f \text{ convexe } \Leftrightarrow \nabla^2 f(x) \succeq 0 \text{ (si } C^2\text{)}
  • f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y)f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y)
  • Minimum local ⇒ minimum global (convexe)\text{Minimum local } \Rightarrow \text{ minimum global (convexe)}
  • min⁡f(x) s.c. gi(x)≤0⇔ conditions KKT\min f(x) \text{ s.c. } g_i(x) \leq 0 \Leftrightarrow \text{ conditions KKT}

Exemples

Exemple 1

Convexité de ∥Ax−b∥2\|Ax-b\|^2.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Hessienne 2ATA⪰02A^TA\succeq 0 : convexe ; unique min si AA plein rang colonnes. (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Convexe (moindres carrés).

Exemple 2

x4x^4 sur R\mathbb{R} : minimum.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Convexe, ∇f=4x3=0\nabla f=4x^3=0 en 00 : minimum global unique. (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Min global en 00.

À retenir

Gradient

Non commencé

Définitions

Le gradient ∇f(x)=(∂f∂x1,…,∂f∂xn)T\nabla f(x) = (\frac{\partial f}{\partial x_1}, \ldots, \frac{\partial f}{\partial x_n})^T pointe dans la direction de plus forte croissance ; ∥∇f∥\|\nabla f\| donne la pente maximale. Orthogonal aux lignes de niveau f(x)=cf(x) = c.

Descente de gradient : xk+1=xk−αk∇f(xk)x_{k+1} = x_k - \alpha_k \nabla f(x_k) ; convergence si αk\alpha_k assez petit (Lipschitz). Méthode du gradient conjugué pour quadratiques. Newton : xk+1=xk−H−1∇fx_{k+1} = x_k - H^{-1}\nabla f (ordre 2). En ML : SGD avec mini-batch pour grands jeux de données.

∇f\nabla f : direction de plus forte croissance. Descente : xk+1=xk−α∇f(xk)x_{k+1}=x_k-\alpha\nabla f(x_k). Newton : −H−1∇f-H^{-1}\nabla f. SGD en ML.

Condition nécessaire d'optimum intérieur : ∇f(x∗)=0\nabla f(x^*)=0.

Formules

  • ∇f(x)Td≤0⇒f deˊcroıˆt localement le long de d\nabla f(x)^T d \leq 0 \Rightarrow f \text{ décroît localement le long de } d
  • xk+1=xk−α∇f(xk);α∼O(1/L) si L-Lipschitzx_{k+1} = x_k - \alpha \nabla f(x_k) \quad ; \quad \alpha \sim O(1/L) \text{ si } L\text{-Lipschitz}
  • ∇f(x∗)=0 (condition neˊcessaire optimum)\nabla f(x^*) = 0 \text{ (condition nécessaire optimum)}
  • GC : directions conjugueˊes pour f(x)=12xTAx−bTx\text{GC : directions conjuguées pour } f(x) = \frac{1}{2}x^TAx - b^Tx

Exemples

Exemple 1

Gradient de f(x,y)=x2+2y2f(x,y)=x^2+2y^2.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) ∇f=(2x,4y)\nabla f=(2x,4y). Descente avec α\alpha petit converge vers (0,0)(0,0). (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

∇f=(2x,4y)\nabla f=(2x,4y) ; min en (0,0)(0,0).

Exemple 2

Ordre de grandeur Newton vs gradient.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Newton : dizaines d'itérations sur quadratique bien conditionné ; gradient : souvent 10210^2–10410^4. (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Newton plus rapide localement (ordre 2).

À retenir

Méthodes numériques

Non commencé

Définitions

Méthodes numériques d'optimisation : simplexe (linéaire), Newton et quasi-Newton (BFGS), Levenberg-Marquardt (moindres carrés non linéaires), pénalités et barrières pour contraintes. Critères d'arrêt : ∥∇f∥<ε\|\nabla f\| < \varepsilon, ∣fk−fk−1∣<δ|f_k - f_{k-1}| < \delta.

Complexité : simplexe O(n3)O(n^3) pire cas pratique souvent bien ; gradient O(n)O(n) par itération. Conditionnement du Hessien impacte convergence. Line search (Armijo, Wolfe) choisit le pas αk\alpha_k.

Méthodes numériques : simplexe (PL), BFGS, Levenberg-Marquardt, barrières. Critères d'arrêt sur ∥∇f∥\|\nabla f\| ou Δf\Delta f.

Line search (Armijo/Wolfe). Conditionnement du Hessien critique.

Pourquoi c’est central : cette notion structure les preuves et calculs du programme ; maîtriser définitions et hypothèses évite les applications hors cadre.

Formules

  • Simplexe : min⁡cTx s.c. Ax≤b, x≥0\text{Simplexe : } \min c^Tx \text{ s.c. } Ax \leq b,\ x \geq 0
  • BFGS : mise aˋ jour quasi-Newton de Hk−1\text{BFGS : mise à jour quasi-Newton de } H_k^{-1}
  • ∥xk+1−xk∥<ε ou ∣fk+1−fk∣<δ\|x_{k+1} - x_k\| < \varepsilon \text{ ou } |f_{k+1} - f_k| < \delta
  • LM : (JTJ+λI)δ=−JTr\text{LM : } (J^TJ + \lambda I)\delta = -J^T r

Exemples

Exemple 1

Calibrage non linéaire : LM.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) (JTJ+λI)δ=−JTr(J^TJ+\lambda I)\delta=-J^Tr : interpolate Gauss-Newton / gradient. (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Levenberg-Marquardt pour moindres carrés non linéaires.

Exemple 2

Complexité pratique.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Gradient : O(n)O(n) / itération ; Newton : factorisation O(n3)O(n^3) sauf structure. (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Choisir selon nn et sparsité.

À retenir