Fiche de cours · Maths-App

Optimisation non linéaire

Non commencé

Définitions

Optimisation non linéaire sans contraintes : $\min f(x)$ , $f$ non linéaire. Conditions optimality : $\nabla f(x^*) = 0$ , $\nabla^2 f(x^*) \succeq 0$ (minimum local). Levenberg-Marquardt pour $\min \|r(x)\|^2$ : hybride Gauss-Newton / gradient.

Contraintes : Lagrangien $\mathcal{L} = f + \sum \lambda_i g_i$ ; KKT : $\nabla f + \sum \lambda_i \nabla g_i = 0$ , $\lambda_i g_i = 0$ , $\lambda_i \geq 0$ . Slater : point intérieur strict $\Rightarrow$ strong duality (convexe).

Optimisation non linéaire : contraintes égalité/inégalité, Lagrangien, KKT, SQP, points intérieurs.

Convexe $\Rightarrow$ optimum global ; sinon minima locaux.

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

$\nabla f(x^*) = 0,\ \nabla^2 f(x^*) \succeq 0$
$x_{k+1} = x_k - (J^TJ + \lambda I)^{-1} J^T r$
$\mathcal{L}(x,\lambda) = f(x) + \sum \lambda_i g_i(x)$
$\nabla_x \mathcal{L} = 0,\ g_i \leq 0,\ \lambda_i \geq 0,\ \lambda_i g_i = 0$

Exemples

Exemple 1

Condition KKT (idée).

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Stationnarité $\nabla_x L=0$ , primale/duale faisables, complémentaire $\mu_i g_i=0$ . (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

KKT nécessaires (sous qualification).

Exemple 2

Quand la convexité sauve.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Si $f$ et domaine convexes : tout point KKT est optimum global. (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Convexe $\Rightarrow$ KKT suffisant.

À retenir

Optimisation combinatoire

Non commencé

Définitions

Optimisation combinatoire : variables entières/binaires, espace discret. TSP (voyageur de commerce) : NP-difficile, $n!$ permutations. Relaxation linéaire (LP) donne borne inférieure. Branch-and-bound : élagage branches non prometteuses.

Coupes : inégalités valides renforcent LP. Programmation entière : simplexe + branch-and-cut. Problèmes polynomiaux : flot max, couplage parfait biparti, arbre couvrant min (Kruskal).

Optimisation combinatoire : variables discrètes, NP-difficile fréquent. Branch & bound, coupes, programmation en nombres entiers.

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

$\min c^Tx \text{ s.c. } Ax \leq b,\ x \in \{0,1\}^n$
$\text{TSP : } \min \sum d_{ij} x_{ij} \text{ (cycle hamiltonien)}$
$\text{Relaxation LP : } x \in [0,1]^n \Rightarrow \text{ borne } \leq \text{opt entier}$
$\text{Kruskal MST : } O(E \log E)$

Exemples

Exemple 1

Relaxation linéaire d'un IP.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Oublier l'intégralité : borne inférieure (min) ; gap d'intégralité à fermer. (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Relaxation $\Rightarrow$ borne.

Exemple 2

Branch & bound (idée).

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Partitionner l'espace discret, élaguer via bornes. (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Séparer / évaluer / élaguer.

À retenir

Métaheuristiques

Non commencé

Définitions

Métaheuristiques explorent l'espace sans garantie optimalité globale : recuit simulé (accepte solutions pires avec probabilité $e^{-\Delta/T}$ , $T$ décroissant), algorithmes génétiques (population, sélection, croisement, mutation), essaims particulaires, tabou search.

Adaptées NP-difficiles, paysages rugueux. Paramètres : température initiale, taux mutation, taille population. Hybrides : métaheuristique + recherche locale.

Métaheuristiques : recuit simulé, génétique, recherche tabou, colonies. Exploration/exploitation. Pas de garantie d'optimalité.

Utile pour paysages non convexes / discrets larges.

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

$P(\text{accepter pire}) = e^{-\Delta/T} \quad \text{(recuit simulé)}$
$T_{k+1} = \alpha T_k,\ \alpha \in (0,1)$
$\text{GA : nouvelle pop = sélection + croisement + mutation}$
$\text{Complexité : } O(N_{\mathrm{iter}} \times \mathrm{coût\_eval})$

Exemples

Exemple 1

Recuit simulé : acceptation.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Accepter une dégradation avec proba $e^{-\Delta/T}$ ; $T\searrow$ . (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Metropolis avec température décroissante.

Exemple 2

Quand les utiliser ?

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Si solveur exact trop lent ( $n$ grand, non linéaire non convexe). (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Heuristique pour instances difficiles.

À retenir

Méthodes numériques

Non commencé

Définitions

Méthodes numériques pour optimisation : line search (Armijo : $f(x + \alpha d) \leq f(x) + c_1 \alpha \nabla f^T d$ ), trust region (modèle quadratique local), différences finies pour gradient si non analytique. Quasi-Newton BFGS approxime Hessien.

Penalty/barrier pour contraintes. Convergence globale vs locale. Critères : gradient norm, contrainte violation, complémentarité.

Méthodes numériques d'optimisation (suite) : line search, trust region, préconditionnement, critères multi-échelles.

Robustesse numérique et reprise après échec de pas.

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

$f(x + \alpha d) \leq f(x) + c_1 \alpha \nabla f^T d \quad \text{(Armijo)}$
$B_{k+1} = B_k + \frac{y_k y_k^T}{y_k^T s_k} - \frac{B_k s_k s_k^T B_k}{s_k^T B_k s_k}$
$\min m_k(p) = f_k + \nabla f_k^T p + \frac{1}{2}p^T B_k p \text{ s.c. } \|p\| \leq \Delta_k$

Exemples

Exemple 1

Trust region vs line search.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Trust region limite le pas dans une boule où le modèle quadratique est fiable. (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Rayon de confiance adapté.

Exemple 2

Préconditionnement.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Changer de métrique pour améliorer $\kappa$ effectif du Hessien / Jacobien. (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Accélère gradient / Newton tronqué.