Dossier complet — Optimisation

L3 · S5 · Mathématiques avancées

Dossier pédagogique original Matrice MI. Contenu d’entraînement non officiel; il ne remplace pas le support ou la maquette d’un établissement.

Objectifs d’apprentissage

• Formuler un problème de minimisation en distinguant variables, fonction objectif, contraintes et domaine admissible.

• Reconnaître la convexité d’un ensemble ou d’une fonction et en déduire la portée des conditions d’optimalité.

• Calculer et interpréter les conditions du premier ordre, y compris les multiplicateurs de Lagrange et les contraintes actives.

• Mettre en œuvre une descente de gradient avec un pas explicite, puis analyser convergence, stabilité et arrêt.

• Comparer des solutions, justifier un choix numérique et communiquer les limites d’un modèle de planification linéaire.

Prérequis

• Calcul différentiel à une et plusieurs variables : dérivées partielles, gradient et matrice hessienne.

• Algèbre linéaire élémentaire : produits matriciels, formes quadratiques et résolution de petits systèmes.

• Bases de programmation et de calcul numérique : boucles, tolérance, représentation des nombres réels et lecture de tableaux.

Cours

1. Formulation et convexité

Modèle et convexité

Un problème s’écrit $\min_{x\in C} f(x)$ : $x$ contient les décisions, $f$ mesure le coût et $C$ regroupe les choix admissibles. Une contrainte est une égalité $h(x)=0$ ou une inégalité $g(x)\leq0$. Un ensemble est convexe si tout segment entre deux de ses points y reste inclus. Une fonction est convexe si elle reste sous ses cordes ; si elle est deux fois dérivable, sa hessienne positive semi-définie le certifie. Alors tout minimum local est global, mais il faut encore établir l’existence. Erreur fréquente : confondre domaine convexe et fonction convexe, ou oublier la frontière.

Exemple guidé. Minimiser $f(x)=x^2-4x+5$ sur $[0,3]$. On écrit $f(x)=(x-2)^2+1$ : le minimum est donc atteint en $x=2$ et vaut $1$. Vérification : $f(0)=5$ et $f(3)=2$. Point de contrôle : le segment entre deux points de $[1,4]$ reste-t-il dans cet intervalle ? Justifiez avec la combinaison $tx+(1-t)y$.

Points-clés

• Séparer variables, objectif, contraintes et ensemble admissible.
• La convexité transforme une condition locale en garantie globale, sous réserve d’existence.
• Comparer points critiques et frontière lorsqu’un domaine est borné.

2. Conditions du premier ordre

Gradient et points critiques

Pour une fonction différentiable, un optimum intérieur $x^*$ vérifie $\nabla f(x^*)=0$. C’est une condition nécessaire, pas une preuve : un point stationnaire peut être minimum, maximum ou selle. La hessienne positive définie indique un minimum local strict, la négative définie un maximum ; une hessienne indéfinie indique une selle. Sur une frontière, il faut examiner les bords. Pour une égalité $h(x)=0$, les multiplicateurs imposent $\nabla f=\lambda\nabla h$ et la contrainte ; la régularité de $h$ reste à vérifier.

Exemple guidé. Minimiser $f(x,y)=x^2+y^2$ sous $x+y=1$. Avec $L=x^2+y^2-\lambda(x+y-1)$, les équations $2x-\lambda=0$, $2y-\lambda=0$ donnent $x=y$, puis $(x,y)=(1/2,1/2)$. La valeur est $1/2$. La stricte convexité rend ce minimum global et unique. Point de contrôle : expliquez pourquoi $(0,0)$ n’est pas un candidat admissible avant de calculer un gradient.

Points-clés

• Un gradient nul est un filtre de candidats, pas une preuve automatique de minimum.
• La hessienne distingue minimum, maximum et selle lorsque le test est concluant.
• Une contrainte d’égalité impose de résoudre simultanément stationnarité et faisabilité.

3. Descente de gradient

Itération et choix du pas

La descente de gradient utilise $x_{k+1}=x_k-\eta_k\nabla f(x_k)$. Un pas trop grand crée oscillations ou divergence ; un pas trop petit ralentit le calcul. Pour $f(x)=\tfrac12x^TQx-b^Tx$, avec $Q$ définie positive, un pas constant converge si $0<\eta<2/\lambda_{\max}(Q)$. On surveille variation de l’objectif, norme du gradient et nombre maximal d’itérations. Une simple tolérance sur $x$ peut être trompeuse si les variables ont des échelles différentes. Une projection est nécessaire quand les itérés doivent rester admissibles.

Exemple guidé. Pour $f(x)=\tfrac12(x-4)^2$, le gradient vaut $x-4$. Depuis $x_0=0$, avec $\eta=1/2$, on obtient $x_1=2$, $x_2=3$, puis $x_3=3,5$ : l’erreur est divisée par deux. La limite est $4$. Point de contrôle : avec un pas $3$, calculez les deux premiers itérés et constatez l’alternance autour de $4$ ; elle montre pourquoi la stabilité du pas doit être étudiée.

Points-clés

• Le pas contrôle le compromis entre stabilité et vitesse de convergence.
• Un arrêt sérieux combine progression, norme du gradient et plafond d’itérations.
• Une projection est nécessaire lorsque les itérés doivent rester admissibles.

4. Contraintes d’inégalité et conditions KKT

Contraintes d’inégalité

Pour $g_i(x)\leq0$ et $h_j(x)=0$, les conditions KKT ajoutent des multiplicateurs $\lambda_i\geq0$. Elles exigent faisabilité, stationnarité et complémentarité $\lambda_i g_i(x)=0$. Une contrainte inactive est stricte et son multiplicateur vaut zéro ; une contrainte active est saturée et peut porter un multiplicateur positif. En problème convexe avec qualification des contraintes, KKT est nécessaire et suffisant. Sinon, il peut seulement être nécessaire. Erreurs fréquentes : oublier la complémentarité ou changer la convention de signe sans changer celle du multiplicateur.

Exemple guidé. Minimiser $(x-3)^2$ sous $x\leq1$. Avec $g=x-1$ et $L=(x-3)^2+\lambda(x-1)$, la frontière donne $x=1$. La stationnarité $2(1-3)+\lambda=0$ donne $\lambda=4\geq0$ ; la complémentarité est satisfaite. La valeur minimale est $4$. Point de contrôle : pour $x\geq1$, écrivez plutôt $g=1-x\leq0$ et vérifiez que le signe du multiplicateur change avec la convention.

Points-clés

• KKT combine faisabilité, stationnarité, signe des multiplicateurs et complémentarité.
• La contrainte active explique pourquoi l’optimum peut ne pas annuler le gradient.
• La suffisance dépend de la convexité et d’une qualification des contraintes.

5. Planification linéaire et interprétation d’une solution

Décision sous ressources

Un programme linéaire optimise $c^Tx$ sous $Ax\leq b$ et $x\geq0$. Lorsque la région admissible est non vide et qu’un optimum existe, un optimum est atteint sur un sommet, parfois sur une arête. Il faut vérifier les unités, les bornes et chaque contrainte ; arrondir avant ce contrôle peut rendre une solution infaisable. Une contrainte active est saturée et représente souvent une ressource limitante. Sa valeur duale donne une information marginale seulement dans la plage où la structure optimale reste stable.

Exemple guidé. Un atelier choisit $A,B\geq0$, avec $2A+B\leq4$, et maximise $3A+2B$. Les sommets sont $(0,0)$, $(0,4)$ et $(2,0)$. Les bénéfices sont $0$, $8$ et $6$ : $(0,4)$ est optimal, avec contrainte de temps active. Point de contrôle : ajoutez $A+B\leq3$, trouvez les nouveaux sommets et réévaluez ; une ancienne solution ne reste pas automatiquement optimale.

Points-clés

• Un modèle linéaire doit expliciter unités, bornes et sens de chaque variable.
• La vérification porte sur la faisabilité et la valeur de l’objectif aux candidats.
• Les contraintes actives donnent une lecture concrète des goulets d’étranglement.

Exercices corrigés

Exercice 1 · Fondamental

Minimiser f(x)=x^2-6x+11 sur l’intervalle [1,5]. Déterminer le minimum et expliquer pourquoi il est global.

Correction détaillée

On dérive : f'(x)=2x-6, donc le seul point critique est x=3. Il appartient à [1,5]. On compare les valeurs : f(1)=6, f(3)=2 et f(5)=6. Le plus petit résultat est 2, atteint en x*=3. Une autre lecture est f(x)=(x-3)^2+2 : le carré est toujours positif ou nul, donc 2 est directement une borne inférieure atteinte en 3. Le minimum est global sur l’intervalle.

Exercice 2 · Fondamental

Pour f(x,y)=x^2+2y^2-4x+8y, calculer le gradient, trouver le point critique et classer ce point.

Correction détaillée

Le gradient est ∇f(x,y)=(2x-4,4y+8). La stationnarité impose x=2 et y=-2. La hessienne est H=[[2,0],[0,4]], positive définie car ses valeurs propres sont 2 et 4, toutes deux positives. Le point (2,-2) est donc un minimum local strict. Comme la fonction est quadratique strictement convexe sur R², ce minimum est aussi global. Sa valeur est f(2,-2)=4+8-8-16=-12.

Exercice 3 · Intermédiaire

Minimiser f(x,y)=x^2+4y^2 sous la contrainte x+y=3. Résoudre par multiplicateur de Lagrange et justifier l’unicité.

Correction détaillée

On pose L=x²+4y²+λ(x+y-3). Les équations sont 2x+λ=0, 8y+λ=0 et x+y=3. De 2x=8y, on obtient x=4y. Donc 5y=3, y=3/5 et x=12/5. La valeur vaut (12/5)²+4(3/5)²=144/25+36/25=180/25=36/5. La fonction est strictement convexe et l’ensemble x+y=3 est affine ; tout point stationnaire est l’unique minimum global sur cette droite.

Exercice 4 · Intermédiaire

Minimiser f(x,y)=(x-2)^2+(y-1)^2 sous x+y≤2 et x≥0, y≥0. Identifier les contraintes actives et la solution.

Correction détaillée

Le point non contraint (2,1) viole x+y≤2. Sur la frontière x+y=2, le point le plus proche de (2,1) se trouve en projetant orthogonalement : poser y=2-x donne f=(x-2)²+(1-x)². Sa dérivée 4x-6 s’annule en x=3/2, donc y=1/2. Ce point respecte les bornes et la contrainte est active. Les multiplicateurs des bornes sont nuls, tandis que la contrainte de somme porte une valeur positive : ∇f=(-1, -1) en (3/2,1/2), opposé au gradient de x+y-2, ce qui donne λ=1 avec la convention L=f+λ(x+y-2). La convexité stricte rend la solution unique.

Exercice 5 · Avancé

Une ferme choisit x hectares de blé et y hectares de maïs. Maximiser 5x+4y sous x+y≤10, 2x+y≤14, x,y≥0. Déterminer tous les sommets pertinents, la solution optimale, les contraintes actives et l’effet d’une unité supplémentaire de la première ressource tant que la base reste inchangée.

Correction détaillée

Les axes donnent (0,0), (0,10) et (7,0), mais (7,0) est limité par x+y≤10 et reste admissible tandis que 2x+y=14. L’intersection des deux ressources vérifie x+y=10 et 2x+y=14, donc x=4,y=6. Les sommets admissibles sont (0,0), (0,10), (7,0) et (4,6). Les objectifs valent 0,40,35 et 44 : l’optimum est (4,6), valeur 44. Les deux contraintes de ressources sont actives ; les non-négativités ne le sont pas. Pour les prix duaux p et q, les productions positives imposent p+2q=5 et p+q=4, d’où q=1 et p=3. Une unité supplémentaire de la première ressource augmente donc l’objectif marginalement de 3, tant que la même base reste optimale et que les données ne sortent pas de cette plage de sensibilité.

Quiz d’autoévaluation

Question 1

Dans un problème convexe différentiable sans contrainte, que signifie ∇f(x*)=0 ?

• x* est nécessairement un maximum global ✓ x* est un candidat d’optimalité ; si f est convexe, c’est un minimum global • x* est forcément sur la frontière • la fonction est constante partout

Explication : Le gradient nul est une condition de stationnarité. Pour une fonction convexe, tout point stationnaire est un minimum global, mais sans convexité il peut être une selle ou un maximum.

Question 2

Quelle propriété caractérise un ensemble convexe C ?

• Toute paire de points possède la même valeur de f ✓ Le segment reliant deux points de C est contenu dans C • C ne contient aucun point frontière • C doit être fini

Explication : Pour x et y dans C et t dans [0,1], la combinaison tx+(1-t)y doit rester dans C. La convexité ne dépend ni de la finitude ni d’une fonction objectif.

Question 3

Que dit la complémentarité en KKT pour une contrainte g_i(x)≤0 ?

• λ_i+g_i(x)=1 ✓ λ_i g_i(x)=0 • λ_i=g_i(x) • λ_i doit toujours être strictement positif

Explication : Le produit nul signifie qu’une contrainte inactive a un multiplicateur nul, tandis qu’un multiplicateur non nul ne peut correspondre qu’à une contrainte active.

Question 4

Quel risque principal accompagne un pas trop grand en descente de gradient ?

• La fonction devient automatiquement convexe ✓ Les itérés peuvent osciller ou diverger • Toutes les contraintes deviennent actives • Le gradient devient exactement nul dès la première itération

Explication : Le pas détermine l’amplitude du déplacement. Au-delà d’une zone de stabilité, les itérés dépassent le minimum et peuvent s’éloigner au lieu de réduire l’objectif.

Question 5

Dans une formulation linéaire, que représente une contrainte active ?

• Une contrainte respectée avec une marge strictement positive ✓ Une contrainte saturée à l’optimum • Une variable forcément entière • Une contrainte qui peut être supprimée sans analyse

Explication : Une contrainte active est satisfaite à l’égalité. Elle peut matérialiser une ressource limitante, mais son importance doit être interprétée avec la structure complète du modèle.

Question 6

Quelle matrice permet de classer un point critique pour une fonction deux fois différentiable ?

✓ La matrice hessienne • La matrice identité uniquement • La matrice des contraintes seulement • La matrice des valeurs de f sans dérivée

Explication : La hessienne rassemble les dérivées secondes. Sa définie-positivité ou négativité donne un test local concluant dans les cas réguliers.

Question 7

Pourquoi vérifier les unités dans un modèle de planification ?

• Pour rendre toutes les variables égales à zéro ✓ Pour éviter de comparer ou additionner des grandeurs incompatibles • Pour garantir un optimum entier • Pour remplacer les contraintes par des commentaires

Explication : Une capacité en heures ne peut pas être combinée directement avec un coefficient en kilogrammes sans conversion. La cohérence dimensionnelle protège le modèle contre une erreur silencieuse.

Question 8

Quelle stratégie d’arrêt est la plus défendable pour une descente numérique ?

• Arrêter après exactement une itération • Utiliser uniquement l’affichage de x ✓ Combiner variation de l’objectif, norme du gradient et plafond d’itérations • Arrêter dès qu’un nombre est négatif

Explication : Plusieurs critères évitent les arrêts prématurés ou les boucles interminables. Le plafond protège aussi contre une divergence ou des données mal conditionnées.

Glossaire

• Ensemble admissible — Ensemble des vecteurs de décision qui satisfont simultanément toutes les contraintes du problème.
• Convexité — Propriété selon laquelle tout segment entre deux points admissibles reste admissible ; pour une fonction, la corde reste au-dessus du graphe.
• Gradient — Vecteur des dérivées partielles, indiquant la direction de plus forte augmentation locale d’une fonction.
• Hessienne — Matrice des dérivées secondes d’une fonction, utilisée pour étudier la courbure locale et classer un point critique.
• Contrainte active — Contrainte d’inégalité satisfaite à l’égalité au point étudié ; elle peut limiter directement le déplacement possible.
• Multiplicateur de Lagrange — Variable auxiliaire qui pondère une contrainte dans les équations de stationnarité d’un problème contraint.
• Condition KKT — Ensemble de conditions de faisabilité, stationnarité, signe dual et complémentarité pour des problèmes sous contraintes.
• Descente de gradient — Méthode itérative qui soustrait un multiple du gradient afin de réduire progressivement une fonction objectif.

TP · Mini-cas : planifier une production sous deux ressources

Une petite imprimerie fabrique des affiches et des brochures. Une affiche consomme 2 heures d’atelier et 1 unité de papier ; une brochure consomme 1 heure et 2 unités de papier. La semaine offre 40 heures et 30 unités de papier. Les marges sont respectivement de 18 € et 14 €. Construire puis résoudre un modèle linéaire, sans supposer que les quantités doivent être entières.

Objectifs

• Traduire un énoncé en variables, objectif et contraintes avec unités explicites.

• Tracer ou décrire la région admissible et repérer ses sommets.

• Comparer la solution optimale aux scénarios tout-affiche et tout-brochure.

• Interpréter les contraintes actives et rédiger une limite du modèle.

Étapes

1. Définir x et y comme quantités hebdomadaires d’affiches et de brochures, puis écrire la fonction de marge 18x+14y.

2. Écrire les contraintes 2x+y≤40, x+2y≤30 et x,y≥0 ; vérifier l’homogénéité des unités.

3. Calculer les intersections avec les axes et l’intersection des deux droites de capacité ; éliminer les points non admissibles.

4. Évaluer la marge sur chaque sommet, documenter les contraintes actives et, si possible, vérifier le résultat par un court script ou un tableur.

5. Tester une perturbation de 1 heure disponible en plus, puis expliquer pourquoi une nouvelle résolution est nécessaire avant de conclure à un gain.

Livrables attendus

• Une page de modélisation annotée avec variables, unités, hypothèses et contraintes.

• Un tableau des sommets, de leur faisabilité et de leur marge, accompagné d’un graphique ou d’un schéma.

• Une note de synthèse de 300 à 500 mots avec solution, contraintes actives, test de sensibilité et limite.

Critères d’évaluation

• Modèle exact et unités cohérentes : 30 %.

• Calcul vérifiable des sommets et de l’optimum : 30 %.

• Interprétation des contraintes actives et de la sensibilité : 25 %.

• Clarté, reproductibilité et limites explicitement discutées : 15 %.

Piste de résolution

La région est délimitée par les deux ressources et les axes. L’intersection satisfait 2x+y=40 et x+2y=30, soit x=50/3 et y=20/3. Il faut comparer ce point avec les intersections d’axes admissibles : (0,15), (20,0) ainsi que l’origine. Les marges sont respectivement 0, 210, 360 et 1180/3 ; la meilleure solution continue est donc (20,0), avec 360 €. La contrainte d’atelier est active et celle du papier dispose d’une marge de 10 unités. Une heure supplémentaire peut modifier le sommet pertinent, mais son gain doit être recalculé dans le nouveau polyèdre ; l’analyse suppose des ventes illimitées et des productions fractionnables.

Sujets originaux d’entraînement (non officiels)

Sujet original de préparation — Optimisation, session normale

Ce sujet est entièrement original et non officiel. Il ne s’agit jamais d’une épreuve d’années passées ni d’une annale ; il sert uniquement à s’entraîner.

Exercice 1

Étudier les points critiques de f(x,y)=x²+xy+y²-2x-4y. Classer le point trouvé et calculer la valeur minimale.

Correction : Le gradient vaut (2x+y-2, x+2y-4). Le système donne y=2-2x et x+2(2-2x)-4=0, donc -3x=0, x=0 et y=2. La hessienne [[2,1],[1,2]] a les valeurs propres 1 et 3, positives : elle est définie positive. Le point (0,2) est l’unique minimum global. Sa valeur est 0+0+4-0-8=-4.

Exercice 2

Résoudre par KKT la minimisation de x²+y² sous x+y≥1 et x,y≥0. Donner les contraintes actives.

Correction : On écrit g=1-x-y≤0 et L=x²+y²+λ(1-x-y)-μx-νy, avec λ,μ,ν≥0. Le point non contraint (0,0) viole x+y≥1 ; la frontière est donc active. Par symétrie et stationnarité 2x-λ-μ=0, 2y-λ-ν=0, le candidat intérieur aux bornes est x=y=1/2. Il est admissible, les bornes x≥0,y≥0 sont inactives, donc μ=ν=0 et λ=1. La solution unique est (1/2,1/2), de valeur 1/2.

Exercice 3

Appliquer trois itérations de descente de gradient à f(x)=1/2(x-5)² depuis x0=1 avec η=0,4. Donner x1,x2,x3 et commenter la convergence.

Correction : Le gradient est x-5. Ainsi x1=1-0,4(-4)=2,6 ; x2=2,6-0,4(-2,4)=3,56 ; x3=3,56-0,4(-1,44)=4,136. L’erreur est multipliée par 0,6 à chaque étape : elle décroît sans changer de signe. Comme 0<η<2 pour cette quadratique de courbure 1, la suite converge vers 5, mais trois itérations ne donnent pas encore la précision finale.

Sujet original de préparation — Optimisation, session de rattrapage

Ce sujet est entièrement original et non officiel. Il ne s’agit jamais d’une épreuve d’années passées ni d’une annale ; il sert uniquement à s’entraîner.

Exercice 1

Minimiser f(x)=|x-2| sur [-1,4]. Discuter la différentiabilité et donner une justification directe.

Correction : La fonction n’est pas dérivable en x=2, mais sa définition donne f(x)≥0 pour tout x. En x=2, f(2)=0, donc le minimum global vaut 0 et est atteint uniquement en x=2. Les dérivées sur les morceaux sont -1 pour x<2 et 1 pour x>2 ; le changement de pente confirme le creux, sans qu’une condition de gradient nul soit applicable au point.

Exercice 2

Un atelier choisit x,y≥0 avec x+y≤12 et 3x+y≤18. Maximiser 5x+2y. Énumérer les sommets et conclure.

Correction : Les sommets admissibles sont (0,0), (0,12), (6,0) et l’intersection x+y=12, 3x+y=18, qui donne x=3,y=9. Les objectifs valent 0,24,30 et 33. Le maximum est donc 33 en (3,9). Les deux contraintes sont actives en ce point ; les non-négativités ne le sont pas.

Exercice 3

Pour f(x,y)=1/2(x²+4y²), effectuer une itération de gradient depuis (2,-1) avec η=0,25, puis calculer la nouvelle valeur de f.

Correction : Le gradient est (x,4y). En (2,-1), il vaut (2,-4). L’itération est (2,-1)-0,25(2,-4)=(1,0). La valeur initiale est 1/2(4+4)=4 ; la nouvelle valeur vaut 1/2(1+0)=0,5. L’objectif diminue nettement. Le pas doit toutefois être étudié par rapport aux deux courbures avant de généraliser le comportement à toutes les itérations.

Parcours de révision sur quatre semaines

Semaine 1 · Modélisation, ensembles admissibles et convexité

Reprendre le chapitre 1, transformer trois situations concrètes en modèles, puis vérifier convexité par la définition des segments. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.

Semaine 2 · Gradient, hessienne et égalités

Résoudre quatre systèmes de stationnarité, classer les points avec la hessienne et refaire l’exercice de Lagrange sans regarder le corrigé. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.

Semaine 3 · KKT et descente de gradient

Construire un tableau de contraintes actives/inactives, dérouler cinq itérations à la main et coder un arrêt avec deux tolérances. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.

Semaine 4 · Planification linéaire et synthèse

Faire le mini-sujet normal en temps limité, résoudre le mini-cas de production et rédiger une fiche erreurs fréquentes, unités et interprétation. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.