OPTIMISATION NUMERIQUE

Master BD2C M1

Tayeb OUADERHMAN

Année universitaire 2023/2024

Copyright © 2022 by Author Name.

All rights reserved. No part of this manuscrit may be used or reproduced in any form whatsoever without written permission except in the
case of brief quotations in critical articles or reviews.

First Edition: Octobre 2022

 Sommaire
O P T I M I S A T I O N N U M É R I Q U E .............................................................................................. I

SOMMAIRE ......................................................................................................................................................................1

1. INTRODUCTION ............................................................................................................................................................2

2. PROBLÈME D’OPTIMISATION: FORMULATION ET ANALYSE ..........................................................................................2

3 OPTIMISATION NUMÉRIQUE SANS CONTRAINTES ....................................................................................................... 11

4 OPTIMISATION NUMÉRIQUE AVEC CONTRAINTES ....................................................................................................... 19

ACKNOWLEDGMENTS .................................................................................................................................................... 40
 Optimisation numérique et Python

1. Introduction
n raison de l'utilisation étendue (et croissante) de l'optimisation dans les

E domaines de la science, de l'ingénierie, de l'économie et de l'industrie, il est

essentiel pour les étudiants et les praticiens de développer une compréhension
des algorithmes d'optimisation.
La connaissance des capacités et des limites de ces algorithmes permet de mieux
comprendre leur impact sur diverses applications, et ouvre la voie à de futurs recherches
sur l'amélioration et l'extension des algorithmes d'optimisation et de leurs applications
ainsi que des logiciels d'optimisation.
Notre objectif dans ce cours est de donner une description complète des techniques
les plus puissantes et les plus récentes pour résoudre les problèmes d'optimisation
continue. En présentant les idées motivantes de chaque algorithme, nous essayons de
stimuler l'intuition du lecteur et de rendre les détails techniques plus faciles à suivre. Les
exigences mathématiques formelles sont réduites au minimum.
Chaque année, les algorithmes d'optimisation sont appelés à traiter des problèmes qui
sont beaucoup plus grands et complexes. En conséquence, ce cours met aussi l'accent sur
les techniques d'optimisation à grande échelle, telles que les méthodes de points intérieurs,
les méthodes inexactes de Newton, les méthodes de régions de confiance ainsi que les
méthodes de pénalité et de barrière pour l'optimisation sous contraintes.

2
 Optimisation numérique et Python

2. Problème
d’optimisation:
Formulation et analyse

C
e chapitre donne une introduction aux bases de l'optimisation numérique et
aidera à construire les outils nécessaires à notre compréhension approfondie dans
les chapitres suivants. Nous aborderons quelques concepts fondamentaux
d'analyse convexe qui seront nécessaires pour des études ultérieures en optimisation, ainsi
qu'une introduction à des codes Python simples.
1. Formulation mathématique
D'un point de vue mathématique, l'optimisation est la minimisation ou la maximisation
d'une fonction soumise à des contraintes sur les variables. Le problème d'optimisation est
formulé de la manière suivante :

1-1

La fonction 𝑓 ∶ 𝑋 ⊂ ℝ𝑛 → ℝ , appelée fonction objectif, est supposée au moins

différentiable. L’ensemble X est appelé ensemble des contraintes (ici X est défini par des
égalités et des inégalités).
où 𝑔𝑘 ∶ ℝ𝑛 → ℝ et ℎ𝑘 ∶ ℝ𝑛 → ℝ sont supposées continues.

2
 T. Ouaderhman

on dit qu’il s’agit d’un problème d’optimisation à n variables de décisions, r contraintes

d’égalités et m contraintes d’inégalités.
Résoudre le problème (1.1) revient à chercher des points de minimum local (ou global).
Premièrement on distinguera les notions de minimum et de maximum des notions
d’infinimum et de supremum.
1.1. Notions de minimum, maximum, infimum, supremum
1.1.1. Définition :
inf (𝑥) )
L’infimum inf(E) ∈ R ∪ {−∞, +∞} de E est le plus grand des minorants (𝑥∈𝐸

Le supremum sup(E) ∈ R ∪ {−∞, +∞} de E est le plus petit des majorants (sup(𝑥) )
𝑥∈𝐸
1.1.2. Proposition : (Suite minimisante/Suite maximisante)
Soit 𝐸 ⊂ ℝ , 𝐸 ≠ 𝜙. Il existe (𝑥𝑛 )𝑛∈ℕ une suite d’éléments de E telle que
lim 𝑥𝑛 = inf(𝐸)
𝑛→+∞

et une suite (𝑦𝑛 )𝑛∈ℕ d’éléments de E telle que :

lim 𝑦𝑛 = sup(𝐸)
𝑛→+∞

La suite(𝑥𝑛 )𝑛∈ℕ est une suite minimisante et (𝑦𝑛 )𝑛∈ℕ une suite maximisante de E.
Démonstration :

3
 Optimisation numérique et Python

1.1.3. Définition : (Minimum, maximum)

Soit E ⊂ R. Un infimum est un minimum si inf(E) ∈ E. Un supremum est un maximum si
sup(E) ∈ E
1.1.4. Définition : (Minimum local/Minimum global)
Soit 𝑓 ∶ 𝑋 ⊂ ℝ𝑛 → ℝ une fonctionnelle à valeurs scalaires
a. x ∈ ℝ𝑛 est un point de minimum local de f sur X si :

On dit alors que f(x) est un minimum local de f sur X.

b. x ∈ ℝ𝑛 est un point de minimum global de f sur X si :

On dit alors que f(x) est un minimum global de f sur X.

Il est important de sélectionner un certain nombre de points candidats à être des extrema
locaux, appelés points critiques ou points stationnaires. Parmi eux, figurent des minima
locaux, des maxima locaux et d’autres qui ne sont ni l’un, ni l’autre, appelés points selle.

1.1.5. Définition : (Domaine realisable)

Le domaine réalisable (feasible region) est l'ensemble des points satisfaisant toutes les
contraintes fournies.

4
 T. Ouaderhman

1.2. Maximisation
Nous venons de définir un problème de minimisation comme notre tâche d'optimisation.
Nous pourrions faire de même avec un problème de maximisation avec quelques petites
modifications.

2. Convexité et optimisation
Les problèmes d’optimisation convexe forment une classe de problèmes que l’on peut
bien étudier et résoudre – en théorie et en pratique, car c’est les problems les plus
fréquemment rencontrés dans les applications et à la base de nombreuses méthodes
développées pour des problèmes plus généraux. C’est à dire, les méthodes efficaces dans
le cas non-convexe sont souvent des extensions de méthodes convexes ou utilisent des
sous-problèmes convexes.
2.1. Gradient et Hessien
On se donne un ouvert U de ℝ𝑛 , une fonction f de U dans ℝ𝑝 et a = (a1, . . . , an) ∈ U. On
note (e1, . . . , en) la base canonique de ℝ𝑛
On dit que f est différentiable en a s’il existe une application linéaire daf de ℝ𝑛 dans ℝ𝑝
telle que

On suppose dans ce paragraphe que p = 1, c’est-à-dire que f est à valeur scalaires.

Pour une fonction f différentiable à valeurs scalaires,

le gradient est défini par :

5
 Optimisation numérique et Python

𝑋 ⊂ ℝ𝑛 → ℝ𝑛
𝜕𝑥1 𝑓(𝑥)
∇𝑓 ∶ 𝜕 𝑓(𝑥)
𝑥 → ∇𝑓(𝑥) = 𝑥2
⋮
[𝜕𝑥𝑛 𝑓(𝑥)]
le vecteur gradient ∇𝑓(𝑥) est toujours perpendiculaire aux contours au point x . le vecteur
gradient est donc dans la direction de l'augmentation maximale de f(x).

2.1.1. Proposition
Pour tout a ∈ U le gradient ∇f(a) est l’unique vecteur tel que pour tout h ∈ ℝ𝑛 on a :

Pour une fonction deux fois continuellement differentiable 𝑓 ∶ ℝ𝑛 → ℝ , sa matrice

hessienne notée par H(f(x)) est définie au point x et d’ordre nxn comme la matrice des
dérivées partielles de second ordre donnée par :

6
 T. Ouaderhman

Une relation importante que nous garderons à l'esprit est que la matrice hessienne est le
Jacobien du vecteur gradient de 𝑓(𝑥), où la matrice jacobienne d'une fonction à valeurs
vectorielles F(x) est la matrice de toutes ses dérivées partielles de premier ordre, donnée
par :

2.1.2. Exemple :

2.1.3. Définition :
𝑥𝑠
Pour une function objectif 𝑓(𝑥) 𝑝𝑜𝑢𝑟 𝑥 ∈ ℝ2 , le point 𝑥 𝑠 =[ 1𝑠 ] est point selle si :
𝑥2
∀𝑥 , ∃𝜀 > 0 tel que les conditions suivantes sont satisfaites :

2.2. Points critiques

Soit 𝑓 ∶ ℝ𝑛 → ℝ une application différentiable. Tout point x ∈ ℝ𝑛 vérifiant :

∇f(x) = 0,
est appelé point critique (ou point stationnaire) de f.
2.3. Dérivée directionnelle
2.3.1. Définition :
On appelle dérivée directionnelle au point x dans la direction d la limite suivante :

où : ∥δ∥=1.

Si cette limite existe, on dit que est la dérivée directionnelle de f en x

2.4. Matrice définie positive, semi-définie positive

7
 Optimisation numérique et Python

Pour une matrice symétrique A de taille n × n, A est définie positive si :

x⊤Ax > 0 pour tout vecteur non nul x
A est d´efinie positive si ses valeurs propres sont strictement positives
La matrice symétrique A est semi-définie positive (noté A ⪰ 0) si
x⊤Ax ≥ 0 pour tout x ∈ ℝ𝑛
et toutes ses valeurs propres sont ≥ 0

2.5. Éléments d’analyse convexe

2.5.1. Definition (Ensemble convexe)
Soit C ⊂ ℝ𝑛 . L’ensemble C est convexe ssi :

c’est-à-dire, si x et y sont deux éléments de C alors le segment qui relie x à y est inclus
dans C.
2.5.2. Definition (Fonction convexe/strictement convexe)
Soit C ⊂ ℝ𝑛 convexe et f : C −→ R.
 f est convexe ssi :

 f est strictement convexe ssi :

2.5.3. Théorème :
Soit C ⊂ ℝ𝑛 convexe et f : C → R différentiable. La fonction f est convexe ssi:

ou de façon équivalente, ssi:

Démonstration :

8
 T. Ouaderhman

2.5.4. Théorème :
Soit 𝑓 ∶ ℝ𝑛 → ℝ une fonctionnelle de classe C2
Si la hessienne H[f](x) de f est une matrice symétrique définie positive pour tout x ∈ ℝ𝑛 ,
alors f est strictement convexe.
Si H[f](x) est une matrice symétrique semidéfinie positive pour tout x ∈ ℝ𝑛 , alors f est
convexe.
Démonstration :

9
 Optimisation numérique et Python

2.6. Condition suffisante d’optimalité globale

2.6.1. Théorème :
Soit C ⊂ ℝ𝑛 convexe et f : C → R différentiable. Soit x* un point de minimum local de f.
 Si f est convexe, alors x* est un point de minimum global de f.
 Si f est strictement convexe, alors x* est l’unique point de minimum global de f.

10
 3 Optimisation
numérique sans
contraintes

C
e chapitre donne une vue globale des fondamentaux de l’optimisationce et présente qu'est exactement
un problème d'optimisation sans contrainte. Dans le cadre de l'optimisation sans contrainte, nous
optimisons une fonction objectif qui dépend de variables réelles, sans aucune restriction sur les variables.
variables réelles.
La formulation du problème est donnée par :
(𝑃) min𝑛 𝐽(𝑢)
𝑢∈ℝ

Où 𝐽 ∶ ℝ𝑛 → ℝ est supposée au moins différentiable

Une discussion détaillée du théorème de Taylor est fournie et a été utilisée pour étudier les conditions nécessaires
et suffisantes de premier ordre et de second ordre pour le minimum local. Des exemples ont également été fournis
afin de mieux comprendre les conditions nécessaires et suffisantes.
Nous nous intéressons aussi dans ce chapitre à la conception de méthodes numériques.

1. Conditions nécessaires et suffisantes

1.1. Condition nécessaires d’optimalité locale de 1er ordre
1.1.1. Théorème :

Soit 𝐽 ∶ 𝑋 ⊂ ℝ𝑛 → ℝ une application différentiable. Si x ∈ IRn réalise un minimum local (resp.

maximum local) de f, alors (Equation d’Euler):

∇𝐽(𝑢(∗) )=0
 Optimisation numérique et Python
2. Conditions d’optimalité d’ordre deux

On supposera que 𝑢∗ existe (éventuellement qu’il est unique) et on se propose de trouver une approximation
(𝑘) (𝑘)
numérique de 𝑢∗ , en construisant une suite {𝑢 }𝑘∈ℕ 𝑡𝑒𝑙 𝑞𝑢𝑒 𝑢 → 𝑢∗
𝑘→∞

Alors une méthode numérique qui peut être envisagée c’est de résoudre numériquement l’équation d’Euler, qui
est en fait un système de n équations avec n inconnues, du type :

où F : IRn → IRn est une fonction donnée (ici F = ∇J)

On se propose ici de donner des méthodes numérique qui sont spécifiques à l’optimisation.
Fondamentalement, il y a deux approches disponibles pour générer 𝑢(𝑘+1) à partir de 𝑢(𝑘) (ou bien 𝐽(𝑢(𝑘+1)) à
partir de 𝐽(𝑢(𝑘) )). Bien que le problème d’optimisation soit le même, chaque famille résout un sousproblème qui
lui est propre.
Direction de descente :
On se donne un point initial 𝑢(0) ∈ ℝ𝑛 et on donnera 𝑢(𝑘+1) comme une fonction de 𝑢(𝑘) . L’expression générale
de 𝑢(𝑘+1) sera :

avec 𝑑(𝑘) ∈ ℝ𝑛 des vecteurs qu’on appelle directions de descente et 𝜌𝑘 ∈ ℝ des scalaires qu’on appelle pas de
descente. Ces noms viennent du fait qu’on cherchera toujours à avoir (entre autres)

L'une des conditions d’arrêt importantes, par exemple, consiste à vérifier si la condition nécessaire du premier
ordre est suffisamment precise ( pour une fonction objective differentiable).
D’autre part, la recherche linéaire consiste à déterminer le pas 𝜌𝑘 ∈ ℝ à effectuer le long d’une direction de
descente 𝑑 (𝑘) . Des valeurs de ce pas peuvent être obtenues par différentes méthodes : par recherche linéaire exacte,
par la méthode d’Armijo ou de Goldstein et par la méthode de Wolfe. Le pas 𝜌𝑘 est souvent choisi afin de vérifier
les deux conditions suivantes :
– la fonction f doit décroître suffisamment le long de la direction de descente;
– le pas αk ne doit pas être trop petit.
Méthode de la région de confiance :
Le principe des méthodes à région de confiance est de remplacer le problème d’optimisation initial par une suite
de sous-problèmes d’optimisation, plus simples à résoudre. Dans chaque sous-problème, la fonction objectif J est
remplacée par une fonction modèle m, à un itére courant u. La région de confiance est définie comme la région à
l’intérieur de laquelle la confiance est donnée à la fonction modèle quant à sa qualité à fournir une bonne
approximation de la fonction objectif. Ainsi, une contrainte supplémentaire existe sur les pas s. Si la décroissance
de la fonction J, évaluée entre le point courant u et le point u* qui minimise la fonction modèle m, n’est pas jugée
suffisante, le rayon de la région de confiance est diminué, et, en général, la direction de recherche est modifiée.
Une description complète des méthodes à région de confiance peut être trouvée dans Conn et al. (2000) et dans
Nocedal et Wright (1999)
Nous voudrions un modèle mk de J en u(k) qui satisfait au minimum les hypothèses suivantes:

12
 T. Ouaderhman

𝑚𝑘 ∈ 𝐶1
𝑚𝑘 (0) = 𝐽(𝑢(𝑘) )
∇𝑚𝑘 (0) = ∇𝐽(𝑢(𝑘) )
Généralement, un modèle quadratique est sélectionné :
𝑚𝑘 (𝑠) = 𝐽(𝑢(𝑘) ) + ∇𝐽(𝑢(𝑘) )𝑇 𝑠 + 𝑠 𝑇 𝐻𝑘 𝑠
avec Hk symétrique (mais pas nécessairement définie positive!).
Pour de petits s, le modèle devrait ressembler à la fonction f , mais plus s est grand, plus il est probable que m et
f soient différents !
Nous allons contrer ce problème en bornant la norme du pas :

où ∆k est le rayon de la région de confiance et ||.||k est une norme, dont le choix peut être dépendant de
l’itération k. Le plus souvent toutefois, nous travaillerons avec la norme 2.
Dès lors, le sous-problème de région de confiance est le problème sous contraintes

La région de confiance à l’itération k est définie comme

La résolution de ce problème peut s’effectuer de manière exacte. Cependant, pour alléger les calculs
numériques, elle s’effectue souvent de manière approchée.
Une bonne détermination du rayon de la région de confiance est alors un point essentiel dans la performance de
telles methods.
3. Méthodes de gradient
la méthode utilisant pour direction de descente l’opposée du gradient de la fonction f au point courant 𝑢(𝑘)

Est dite méthode de gradient.

Une méthode de gradient est dite à pas constant (ou fixe) si ρk est constant (indépéndant du k). Dans le cas
contraire, elle est dite à pas variable.
Pour ρ=1, elle est dite méthode de plus forte descente.
∇𝐽(𝑢(𝑘) )est orthogonal à la ligne du niveau de J dans le point u (k) et la fonction J diminue dans la direction
−∇𝐽(𝑢(𝑘) ) ce qui justifié par le calcul suivant, où on utilise un développement de Taylor :

Nous avons alors :

Le membre de droite de l’égalité précédente est < 0 si ρ > 0 avec ρ “assez petit” et ∇𝐽(𝑢(𝑘) ) ≠ 0
Les méthodes de gradient sont définis alors par les relations :

Il y a plusieurs méthodes de gradient suivant le choix que nous faisons pour 𝜌𝑘 .

13
 Optimisation numérique et Python
Lorsque la minimisation de J est faite de façon exacte, les directions consécutives 𝑑(𝑘) et 𝑑(𝑘+1) sont
perpendiculaires : on s’arrête toujours de façon tangente à une courbe de niveau. La méthode peut prendre un
nombre considérable d’itérations avant de converger à un point critique.

3.1. Méthodes de gradient à pas optimal

En supposant qu’un tel minimum existe, le pas optimal est tel que :

3.1.1. Cas particulier : fonctions quadratiques.

nous supposons que J : IRn → IR est donnée par :

avec A ∈ Mn(IR) matrice SDP (c’est à dire matrice symmétrique et définie positive), b ∈ IRn , c ∈ IR (donc c’est
une forme quadratique associée à une matrice SDP).
Nous devons calculer ρk ∈ IR qui minimise la fonction g : IR 7→ IR donnée par :

14
 T. Ouaderhman

Alors ρk satisfait nécessairement

Ce qui nous donne :

On obtient alors :

Donc la méthode de gradient à pas optimal dans le cas J quadratique est :

3.1.2. Cas où J quelconque

Si J n’est pas quadratique, il peut être difficile de trouver ρk, il faut alors utiliser à chaque pas k une méthode
numérique pour approcher ρk ou de se satisfaire uniquement d’une estimation “assez large” pour ρk. Le
théorème ci dessous nous donne un intervalle tel que si tous les ρk se trouvent dans cet intervalle, alors la
méthode du gradient converge
[Link]. Définition :
Soit J : IRn → IR une function, J est dite elliptique si : 𝐽 ∈ 𝐶 1 𝑒𝑡 ∃𝛼 > 0 telle que

[Link]. Definition
la convergence est dite géométrique si
(où u* est l’unique point de minimum de J sur IRn).
[Link]. Théorème :
Soit J : IRn → IR une function elliptique et que et ∇J soit lipschitzienne ( M constant Lipschitz). Supposons que
la suite {ρk}k∈IN ⊂ IR satisfait la propriété suivante : il existe 𝛼1 𝑒𝑡 𝛼2 avec

Alors la méthode générale de gradient (3.9) converge et la convergence est au

moins géométrique,
Démonstration.

15
 Optimisation numérique et Python
Remarque :

On déduit du Théorème que si ρ est tel que alors la méthode de gradient à pas fixe est

convergente (choisir 𝛼1 𝑒𝑡 𝛼2 = 𝜌 dans le Théorème. En général il est difficile de connaître α et M (en

supposant qu’ils existent). Alors dans la pratique on prends un ρ assez petit pour être sur d’avoir la
convergence. Mais dans ce cas la convergence peut être très lente !
Si J est quadratique avec une matrice A qui est SDP. Alors on peut prendre α = λmin > 0 (la plus petite valeur
propre de A) et M = ||A||2 = ρ(A) = λmax > 0 (la plus grande valeur propre de A).
4. Méthode de descente par coordonnée
Cette méthode consiste à visiter toutes les coordonnées régulièrement pour assurer la convergence. Le parcours
le plus courants est celui de parcours cyclique (Gauss-Seidel)

La convergence vers un minimum pour des fonctions elliptiques est guaranti

L’algorithme de relaxation pour J quadratique n’est autre que l’algorithme de Gauss-Seidel pour la resolution
de système linéaire Au=b. Ceci s’explique par le fait que le point de minimum u* de J satisfait l’équation
d’Euler qui devient dans le cas J quadratique : Au* = b.
5. La méthode d’Armijo
Pour que la fonction J décroît suffisamment le long de la direction de descente on rajoute souvent un terme
négatif βk dans : La façon de procéder est alors de demander à f de décroire autant

16
 T. Ouaderhman
qu’une proportion ω1 ∈ ]0,1[ de ce que ferai le modèle linéarisé de f autour du point xk. On a alors affaire à la
condition d’Armijo :

Ici, la constante ω1 est choisie arbitrairement et est habituellement prise très petite

6. Méthode de Goldstein
Dans la méthode de Goldstein la détermination du pas αk doit vérifier les equation

On peut démontrer qu’il est possible d’obtenir un pas, appelé pas de Goldstein, vérifiant les équations si fk est
continue et bornée inférieurement.
7. Méthode de Wolfe
La méthode de Wolfe consiste toujours à déterminer un pas αk, appelé pas de Wolfe, vérifiant les conditions :

tout en imposant 0 < ω1 < ω2 < 1.

Les critères de Wolfe donnent une façon économique de point de vue algorithmique de calculer le pas
permettant de diminution

8. La méthode des gradients conjugués

8.1. Cas J quadratique
On considère J : IRn → IR une fonction quadratique, e la méthode de gradient à pas optimal consiste à faire :

Ceci est équivalent à chercher l’élément qui minimise J sur

Où l’espace vectoriel engendré par les vecteurs v1 , v2 ,· · · v𝑙 est note par ; c’est un sous-espace
vectoriel de IRn .
On va noter pour tout k ∈ IN :
La méthode des gradients conjugués consiste alors à chercher :

17
 Optimisation numérique et Python

On minimise donc sur un espace plus “grand” que dans la méthode de gradient à pas optimal. Reste à montrer la
facilité de son implementation.
Comme J est quadratique et que u(k) + Gk est un ensemble fermé et convexe, il existe alors une solution unique
du problème.
De plus, on a :

Soit maintenant w ∈ Gk arbitraire. Remarquons qu’on a :

En pregnant et aussi pour On obtient :

Ce qui veut dire que est orthogonal à tout vecteur w de Gk . alors on a :

Remarque:
L’algorithme s’arrête en au plus n itérations, car il existe k ∈ {0, 1, · · · n} tel que

sinon, on aurait n+1 vecteurs non-nuls indépendants en IRn, ce qui est impossible.

8.1.1. Calcul de u(k+1) à partir de u(k)

8.2. Cas de J quelconque

C’est la variante dite de Fletcher-Reeves. Les étapes de l’algorithme sont les suivantes :

18
 T. Ouaderhman

Il y a aussi une variante dite de Polack-Ribiere, qui donne des meilleurs résultats en pratique, avec comme seul
changement :

8.3. Différentes formules

En notant 𝑔𝑘 = ∇𝐽(𝑥 𝑘 ), Les différentes valeurs attribuées à 𝛽𝑘 deffinissent les différentes formes du gradient
conjugué. Si on note 𝑦𝑘 = 𝑔𝑘 − 𝑔𝑘−1 𝑒𝑡 𝑠𝑘 = 𝑥𝑘+1 − 𝑥𝑘

19
Optimisation numérique et Python

20
 T. Ouaderhman

Dans le cas quadratique on a : Dans le cas non quadratique, ces

quantités ont en général des valeurs différentes.

9. Les méthodes à région de confiance

Les méthodes à région de confiance classiques utilisent des fonctions modèles quadratiques. L’essentiel
de la présentation des méthodes à région de confiance est fidèle à Fahl[ ].

9.1. Fonctions modèles utilisant le gradient exact de la fonction objectif

Lorsque le gradient de la fonction objectif est connu, ou peut facilement être évalué de manière exacte.
la fonction modèle est :

Dans ce cas, la méthode est appelée méthode à région de confiance de Newton. Par la suite, aucune
indication ne sera donnée quant à l’éventuelle exactitude du hessien: on supposera uniquement que Hk
est une matrice symétrique uniformément bornée à l’itération k

En cas d’une approximation de hessian, différentes méthodes d’approximation du hessien basées sur la
connaissance du gradient de la fonction f sont présentées dans la litterature. On peut citer parmi les
méthodes les plus connues les méthodes BFGS, DFP

Il est alors nécessaire d’évaluer la valeur de la fonction f au nouveau point. Pour ce faire, on évalue la
réduction réelle, aredk :

Cette réduction est ensuite comparée à la réduction prédite par la fonction modèle, predk :

L’efficacité de la fonction modèle peut être déterminée par le rapport suivant :

Ce rapport est alors utilisé comme critère d’actualisation du rayon de la région de confiance ∆k

Le point central de ces algorithmes est de vérifier que la décroissance de la fonction mquad k est au moins
égale à celle obtenue en appliquant la méthode du point de Cauchy . Le point de Cauchy est défini
comme le point minimisant la fonction mquad k le long de la plus forte pente , et devant satisfaire la
contrainte imposée par le rayon de confiance.

Algorithme 9.1 (Point de Cauchy) :

21
 Optimisation numérique et Python

Calcul pratique du point de Cauchy :

Algorithme 9.2 :(Région de confiance pour des fonctions modèles quadratiques)

22
 T. Ouaderhman

A chaque itération, la réduction de la fonction modèle en un point doit au moins être égale à un multiple
de la décroissance obtenue au point de Cauchy.

A chaque itération, la réduction de la fonction modèle en un point doit au moins être égale à un multiple
de la décroissance obtenue au point de Cauchy. La condition de la fraction de décroissance de Cauchy
(Fraction of Cauchy Decrease, fcd) doit alors être vérifiée.

Or, il a été montré (Powell, 1975) que pour la décroissance de Cauchy, on a :

On a montré qu’on peut aboutir à la condition de décroissance suffisante :

Et les différents théorèmes de convergence globale découlent de cette condition de décroissance

suffisante.

Théorème 1 (Convergence globale faible)

23
 Optimisation numérique et Python
Soit f : Rn → R une fonction continûment dérivable sur X = {x ∈ Rn | f(x) < f(x0)}, et soit {xk} une suite
d’itérés générés par l’algorithme, avec {Hk} uniformément bornée. Si de plus la direction sk vérifie la
condition

on a alors :

Une convergence forte peut par ailleurs être énoncée si l’on impose des contraintes supplémentaires sur
la fonction objectif comme supposer f avec un gradient continu au sens de Lipshitz, inférieurement
borné sur X = {x ∈ Rn | f(x) < f(x0)},

9.2. Fonctions modèles utilisant un gradient approché de la fonction objectif

Généralement, le gradient de la fonction objectif est très difficile à obtenir, et seule une approximation
numérique de ce dernier est accessible.

En notant gk une approximation du gradient exact ∇f(xk), et Hk une approximation du hessien exacte, une
fonction quadratique basée sur un gradient approché peut s’écrire de la manière suivante :

il est nécessaire de prendre en compte la différence entre les gradients exact et approché, La méthode qui
est le plus utilisée est sans doute celle proposée par Carter (1991) :

Comme nous l’avons précisé précédemment, il suffit de déterminer une condition de décroissance
suffisante afin d’être en mesure de prouver la convergence de méthodes à région de confiance. Pour les
méthodes à région de confiance qui utilisent un gradient approché, Moré (1983) on a:

9.3. Optimisation de fonctions modèles générales

Nous allons maintenant nous attacher à décrire les principes d’un algorithme qui utilise des fonctions
modèles générales. lorsque la fonction modèle n’est pas quadratique, rien ne prouve que le point de
Cauchy produise une décroissance suffisante de la fonction modèle. Il semble alors intéressant de
généraliser cette condition de décroissance suffisante aux fonctions quelconques, non nécessairement
quadratiques.

L’algorithme ci-dessous, proposé par Toint (1988), permet de déterminer un pas qui produit une
décroissance suffisante pour une fonction modèle générale.

24
 T. Ouaderhman
Algorithme 9.3: (bien posé suite à la démonstration du lemme d’après Toint (1988).

10. Méthods quasi Newton

Le principe de la méthode de Newton consiste à minimiser successivement les approximations

du second ordre de f, plus précisement si :

Posons :

Soit xk+1 l’optimum de q, alors il vérifie ∇𝑓(𝑥𝑘+1 ) = 0; soit en remplaçant :

Donc :

Si le point x0 et assez proche de la solution optimale locale x* telle que H (x*) soit définie positive, alors
l’algorithme de Newton converge de façon quadratique vers la solution x*. cíest à dire que l’on a :

Cette méthode fonctionne très bien pour les problèmes de petite dimension, lorsque on peut calculer

25
 Optimisation numérique et Python
facilement la matrice Hessienne H et sont inverse. Ce calcul nécessite des itérations plus nombreuses et
couteuses dans les problèmes de grandes tailles.
Pour obtenir une méthode qui converge superlinéairement, il est nécessaire díapproximer l’étape de
Newton asymptotiquement en 1959 Davidon a développé une approche et popularisée par Fletcher et
Powell en 1963. Elle consiste à commencer par n’importe quelle approximation de la matrice Hessienne
et à chaque itération sans évaluer la matrice Hessienne et on obtient quelques méthodes
remarquablement robustes et efficaces.
Il y a plusieurs méthodes de variable métrique, on s’étalera particulièrement sur les trois plus
importantes, la méthode de correction de rang un, la mÈthode DFP (Davidon, Fletcher, Powell), et la
méthode BFGS (Broyden, Fletcher, Goldfarb, Shano).
10.1. Méthode de quasi Newton
Une méthode de quasi Newton est une méthode de type :

xk+1 = xk + λkdk,
dk = -Bkgk,
ou bien :
xk+1 = xk + λkdk,
dk = -Sk -1gk
où Bk (respectivement Sk) est une matrice destinée à approcher l'inverse du Hessien de ƒ
(respectivement le Hessien) de ƒ en xk. Le problème posé est : Quelle stratégie à adopter
pour faire cette approximation ? On peut par exemple poser B1 = I, mais comment ensuite
mettre à jour l'approximation Bk au cours des itérations?

L'idée est la suivante : Prenons et faisons un développement de ∇𝑓(𝑥 ) au

voisinage de xk

ce qui implique :

Les approximations sont exacts si f est quadratique. En particulier avec x = xk+1 et si Bk était une
bonne approximation de alors :

Le principe de la mise à jour consiste à une itération donnée de l’algorithme à appliquer une
formule de type :

avec ∆𝑘 symétrique, assurant la relation de quasi Newton. ainsi que Bk+1 définie positive, sous
l’hypothèse que Bk est définie positive.
Cette formule permet d’utiliser les nouvelles informations obtenues lors de l’étape k de
l’algorithme.

26
 T. Ouaderhman
10.2. Méthode de correction de rang un

Etend donné que est symétrique, la formule de mise à jour de l’approximation du

Hessien Bk est la suivante :

Avec 𝑦𝑘 = 𝑔𝑘+1 − 𝑔𝑘 𝑒𝑡 𝑠𝑘 = 𝑥𝑘+1 − 𝑥𝑘 la condition de quasi Newton s’écrit donc comme suit :

Un choix évident pour vérifier cette dernière équation est de prendre

on obtient :

Algorithme :

Remarque : Si f est quadratique, de matrice Hessienne H définie positive et si s1,s2,…, sn sont des
vecteurs indépendants, alors la méthode de correction de rang un converge au plus dans (n + 1)
itérations
10.3. Méthode de Davidon Fletcher Powell (DFP)

Cette méthode a été proposée par Davidon en 1959 et développé plus tard en 1963 par Fletcher.
La formule de mise à jour de DFP est une formule de correction de rang deux. Et on a:

où :

27
 Optimisation numérique et Python

ak, bk sont des constantes, uk, vk sont deux vecteurs de Rn

Bk+1 doit satisfaire la condition quasi Newton c’est à dire :

Par suite :

Donc :

Un choix Èvident pour satisfaire cette Èquation est de prendre :

D’où :

Algorithme :

28
 T. Ouaderhman

10.4. Méthode de Broyden, Fletcher, Goldfarb et Shanno(BFGS)

La formule de mise à jour de Broyden, Fletcher, Goldfarb et Shanno est une formule de
correction de rang deux, qui síobtient à partir de la formule DFP en intervertissant les rôles de sk
et yk. permet de mettre à jour une approximation Bk de Hessien lui meme et non de son inverse
comme dans le cas de la méthode DFP . a savoir Bk+1 reste définie positive si Bk líest et l’équation
d’approximation de quasi Newton doit être vérifiée:

et

Algorithme :

29
 Optimisation numérique et Python

La méthode BFGS possède les mêmes propriétés que la méthode DFP dans le cas quadratique.
Les directions engendrées sont conjuguées. Cette méthode est reconnue comme étant beaucoup
moins sensible que la méthode DFP aux imprécisions dans la recherche linéaire, du point de vue
de vitesse de convergence. Elle est donc tout à fait adaptée quand la recherche linéaire est faite
de façon économique, avec par exemple la règle de Goldstein ou la règle de wolf et Powell.

10.5. Les méthodes de classe Broyden

Une méthode de classe Broyden est une méthode de quasi-Newton où l’approximation de

l’inverse du Hessien prend la formule suivant :

Si ϕ= 0 on obtient la méthode BFGS

Si ϕ = 1 on obtient la méthode DFP

11. Exemples : codes Python

11.1. Exemple 1 :

Soit la fonctionnelle suivante :

30
 T. Ouaderhman

Programme 1 (Davidon-Fletcher-Powell (DFP) algorithm):

# import the required packages
import [Link] as plt
import numpy as np
import [Link] as au
from autograd import grad, jacobian
import scipy
def func(x): # Objective function (Booth's function)
return (x[0]+2*x[1]-7)**2 + (2*x[0]+x[1]-5)**2

Df = grad(func) # Gradient of the objective function

# draw the contour plot first
x1 = [Link](-10, 10, 100)
x2 = [Link](-10, 10, 100)
z = [Link](([len(x1), len(x2)]))
for i in range(0, len(x1)):
for j in range(0, len(x2)):
z[j, i] = func([x1[i], x2[j]])

contours=[Link](x1, x2, z, 100, cmap=[Link])

[Link](contours, inline=1, fontsize=10)
[Link]("$x_1$ ->")
[Link]("$x_2$ ->")

# define DFP()
def DFP(Xj, tol, alpha_1, alpha_2):
x1 = [Xj[0]]
x2 = [Xj[1]]
Bf = [Link](len(Xj))

while True:
Grad = Df(Xj)
delta = -[Link](Grad) # Selection of the direction of the steepest descent

start_point = Xj # Start point for step length selection

beta = line_search(f=func, myfprime=Df, xk=start_point, pk=delta, c1=alpha_1,
c2=alpha_2)[0] # Selecting the step length
if beta!=None:
X = Xj+ beta*delta
if NORM(Df(X)) < tol:
x1 += [X[0], ]
x2 += [X[1], ]
[Link](x1, x2, "rx-", ms=5.5) # Plot the final collected data showing the
trajectory of optimization
[Link]()
return X, func(X)
else:
Dj = X - Xj # See line 16 of the algorithm
Gj = Df(X) - Grad # See line 17 of the algorithm
w1 = Dj # See line 18 of the algorithm
w2 = [Link](Gj) # See line 19 of the algorithm
w1T = w1.T
w2T = w2.T
sigma1 = 1/([Link](Gj)) # See line 20 of the algorithm
sigma2 = -1/([Link](Gj)) # See line 21 of the algorithm
W1 = [Link](w1, w1)
W2 = [Link](w2, w2)
Delta = sigma1*W1 + sigma2*W2 # See line 22 of the algorithm

31
 Optimisation numérique et Python
Bf += Delta # See line 23 of the algorithm
Xj = X # Update to the new iterate
x1 += [Xj[0], ]
x2 += [Xj[1], ]
DFP([Link]([-7.8, -3.75]), 10**-5, 10**-4, 3.82)
## (array([1., 3.]), 1.5777218104420236e-30)

11.2. Exemple 2 (BFGS algorithm):

Soit la fonctionnelle suivante :

Programme 2 :
# import the required packages
import [Link] as plt
import numpy as np
import [Link] as au
from autograd import grad, jacobian
import scipy

def func(x): # Objective function (Branin function)

return (x[1] - (5.1/(4*[Link]**2))*x[0]**2 + (5/[Link])*x[0] - 6)**2 + 10*(1 -
1/(8*[Link]))*[Link](x[0]) + 10

Df = grad(func) # Gradient of the objective function

# draw the contour plot first
x1 = [Link](-10, 10, 100)
x2 = [Link](-10, 10, 100)
z = [Link](([len(x1), len(x2)]))
for i in range(0, len(x1)):
for j in range(0, len(x2)):
z[j, i] = func([x1[i], x2[j]])

contours=[Link](x1, x2, z, 100, cmap=[Link])

[Link](contours, inline=1, fontsize=10)
[Link]("$x_1$ ->")
[Link]("$x_2$ ->")

# define BFGS()
def BFGS(Xj, tol, alpha_1, alpha_2):
x1 = [Xj[0]]
x2 = [Xj[1]]
Bf = [Link](len(Xj))

while True:

32
 T. Ouaderhman
Grad = Df(Xj)
delta = -[Link](Grad) # Selection of the direction of the steepest descent

start_point = Xj # Start point for step length selection

beta = line_search(f=func, myfprime=Df, xk=start_point, pk=delta, c1=alpha_1,
c2=alpha_2)[0] # Selecting the step length
if beta!=None:
X = Xj+ beta*delta
if NORM(Df(X)) < tol:
x1 += [X[0], ]
x2 += [X[1], ]
[Link](x1, x2, "rx-", ms=5.5) # Plot the final collected data showing the
trajectory of optimization
[Link]()
return X, func(X)
else:
Dj = X - Xj # See line 16 of the algorithm
Gj = Df(X) - Grad # See line 17 of the algorithm

den = [Link](Gj)
num = [Link](Gj)

L = 1 + [Link](Gj)/den
M = [Link](Dj, Dj)/den
N = [Link](Dj, num)/den
O = [Link](num, Dj)/den

Delta = L*M - N - O
Bf += Delta # See line 18 and line 19 of the algorithm
Xj = X # Update to the new iterate
x1 += [Xj[0], ]
x2 += [Xj[1], ]
BFGS([Link]([1.5, 7.75]), 10**-5, 10**-4, 0.25)
## (array([1., 3.]), 0.0)
from [Link] import minimize

def func(x): # Objective function

return (x[1] - (5.1/(4*[Link]**2))*x[0]**2 + (5/[Link])*x[0] - 6)**2 + 10*(1 -
1/(8*[Link]))*[Link](x[0]) + 10

Df = grad(func) # Gradient of the objective function

res=minimize(fun=func, x0=[Link]([1.5, 7.75]), jac=Df, method='BFGS',

options={'gtol':10**-5, 'disp':True, 'return_all':True})
res.x, [Link], [Link]
for i in [Link]: print(i)

33
 Optimisation numérique et Python

4 Optimisation
numérique avec
contraintes
n s’intéresse dans ce chapitre aux problèmes du type suivant : "trouver le minimum d’une fonction

O avec contrainte(s)". D’un point de vue mathématique, le problème se formule de la façon suivante :

Toutefois, nous adopterons le point de vue qui consiste à traiter des problèmes d’optimisation en dimension
finie.
Nous envisagerons essentiellement deux types de contraintes :
 Des contraintes de la forme

avec m ∈ IN∗ et ϕ1, ϕ2, · · · ϕm des fonctions de IRn dans IR données (on dit dans ce cas que U est donné par
des contraintes inégalités larges).
 Dans la pratique on peut rencontrer des problèmes de minimisation avec contraintes égalités, c’est à
dire, des contraintes de la forme

 ou des problèmes avec des contraintes mélangées (égalités et inégalités larges).

 U est un pavé, c’est à dire, il est de la forme :
1. Conditions d’optimalité sous contrainte :
Soient J, θ1, θ2, · · · θm : IRn → IR des fonctions de classe C1 , avec m ∈ IN* . On note :

34
 T. Ouaderhman

Si x ∈ est tel que la famille des vecteurs forme un système libre en IRn alors on dit que x
est un point régulier de . La variété est dite régulière si tous les points de sont réguliers.

Si B est la matrice Jacobienne donnée par : et rang(B) = m ssi x

est régulier.
Théorème 1 :
Soit x ∗ un point régulier de tel que x ∗ soit un extremum local de J sur (minimum local ou maximum
local).

Alors il existe tels que :

s’appellent multiplicateurs de Lagrange.

Ces conditions ne sont pas en général suffisantes.
2. Optimisation sous contraintes d’inégalités
Notons maintenant:

On va s’intéresser au problème de minimisation :

On peut aussi écrire : en introduisant la fonction à valeurs vectorielles :

2.1 Conditions d’optimalité de premier ordre

Définition 1 : On dit que la contrainte est active en v ∈ O si on a :

On introduit alors l’ensemble :

Et ( si )
On dira que v ∈ O est un point régulier de O si :
 soit I(v) = ∅
 soit v est un point régulier de la variété
Lemme 1 :
Soit v ∈ O tel que I(v) ≠∅ et soit w ∈ IRn tel que :
Alors : Alors w est une direction admissible pour v en O.
Corollaire 1 :
Soit v ∈ O tel que I(v) ≠∅ et soit w ∈ IRn tel que :

Supposons que v est un minimum local de J sur O. Alors :

théorème 2 :

35
 Optimisation numérique et Python
Soit x ∗ un point régulier de O. Si x ∗ est un point de minimum local de J sur O alors il existe :
(appellés multiplicateurs de Karush-Kuhn-Tucker) tels que :

Remarque : Si on considère l’ensemble

avec m2 ≥ 1 alors on peut considérer O comme donné uniquement par des contraintes inégalités, en écrivant :

L’hypothèse de régularité n’est satisfaite pour aucun x ∈ O si O comporte au moins une contrainte égalité
transformée artificiellement en deux contraintes inégalités.
Définition :
On dit que les contraintes de O sont qualifiés en v ∈ O si :
a) Soit I(v) = ∅
b) Soit il existe w ∈ IRn tel qu’on a ∀ i ∈ I(v) :

avec en plus :

(Si θi est affine pour tout i ∈ I(v) alors les contraintes de O sont qualifiés en v)
Proposition :
Si un point v ∈ O est régulier alors les contraintes de O sont qualifiés en v.
On a alors le résultat suivant, plus forte que le Théorème 1.
Théorème 2 :
Soit x ∗ ∈ O tel que les contraintes de O sont qualifiés en x ∗ . Si x ∗ est un point de minimum local de J sur O
alors il existe tels que :

Proposition 2 :
Supposons que les fonctions θ1, θ2, · · · , θm sont convexes.
Supposons aussi que
- ou bien toutes les fonctions θ1, θ2, · · · , θm sont affines
- ou bien il existe y ∈ IRn tel que pour tout i = 1, · · · , m on a :

Alors pour tout x ∈ O les contraintes de O sont qualifiés en x.

36
 T. Ouaderhman
3. Point selle et optimisation
Nous introduisons la function donnée par :

On a le résultat suivant :

Si (x ∗ , p∗ ) est un point selle de L alors x ∗ est un point de minimum de J sur O. En plus (x ∗ , p∗ ) satisfait les
conditions de Karush-Kuhn-Tucker, c’est à dire :

On verra aussi une reciproque, sous des hypothèses supplementaires. On cherchera alors à résoudre le problème
appellé le problème dual :

Théorème 3:
Supposons que toutes les fonctions J, θ1, θ2, · · · , θm sont convexes. Supposons aussi qu’il existe p1* ,
p2*, · · · , pm*∈ [0, +∞[ et x* ∈ O tels que les conditions de Karush-Kuhn-Tucker du Théorème 2 soient
satisfaites. Alors
a) x* est un point de minimum de J sur O
b) (x* , p* ) est un point selle de L
4. Retour sur les conditions d’optimalité à contraintes mixtes
Posons :

On suppose les contraintes qualifiées au point x∗ . Alors, une condition nécessaire pour que x∗ soit un
minimum de J est qu’il existe des nombres positifs λ1* , . . ., λm* et des nombres réels µ1* , . . ., µp* tels que :
𝑚1 𝑚2

∇𝑥 𝐽(𝑥 ∗ ) + ∑ 𝜆𝑗∗ . ∇𝑥 𝜃𝑗 (𝑥 ∗ ) + ∑ 𝜇𝑖∗ . ∇𝑥 𝜑𝑖 (𝑥 ∗ ) = 0

𝑗=1 𝑖=1
𝜆𝑗∗ . 𝜃𝑗 (𝑥 ∗ ) = 0, 𝑖 = 1, … , 𝑚1

La relation s’écrit aussi comme :

∇𝑥 L(𝑥 ∗ , 𝜆∗ , 𝜇∗ ) = 0
Où L est le Lagrangien du problème définie sur
𝑚1 𝑚2

L(x, 𝜆, 𝜇) = 𝐽(𝑥 ∗ ) + ∑ 𝜆𝑗 . 𝜃𝑗 (𝑥 ) + ∑ 𝜇𝑗 . 𝜑𝑖 (𝑥 )
𝑗=1 𝑖=1

Toutefois, il est nécessaire, pour pouvoir conclure, d’avoir des résultats précisant si la solution obtenue est
effectivement un minimum. Pour cela, on peut restreindre le nombre de candidats grâce à une conditon du
second ordre.
Théorème 4 :

37
 Optimisation numérique et Python
On suppose que J,f et g sont de classe C 2 , que x* est un minimum (local) de J sur C et le point x* est que les
contraintes sont qualifiées en ce point. On désigne par µ* (resp. λ* ) le vecteur des multiplicateurs de Lagrange
associés aux contraintes égalités (resp. inégalités). Alors, pour toute direction d ∈ Rn vérifiant :
⟨∇𝑥 𝜑𝑖 (𝑥 ∗ )|𝑑⟩ = 0 𝑖 = 1, … , 𝑚2
⟨∇𝑥 𝜃𝑗 (𝑥 ∗ )|𝑑⟩ = 0, 𝑗 ∈ 𝐼0+ (𝑥 ∗ )
⟨∇𝑥 𝜃𝑗 (𝑥 ∗ )|𝑑⟩ ≤ 0, 𝑗 ∈ 𝐼0 (𝑥 ∗ )\𝐼0+ (𝑥 ∗ )
Où : 𝐼0+ (𝑥 ∗)={𝑖, 1 ≤ 𝑖 ≤ 𝑚2 , 𝜑𝑖 (𝑥 ∗ ) = 0 𝑒𝑡 𝜇𝑖∗ > 0 } 𝑒𝑡 𝐼0 (𝑥 ∗ ) = {𝑖, 1 ≤ 𝑖 ≤ 𝑚2 , 𝜑𝑖 (𝑥 ∗ ) = 0 }
On a :
⟨∇2𝑥𝑥 𝐿(𝑥 ∗ , 𝜇∗ , 𝜆∗ ). d|𝑑⟩ ≥ 0

5. Algorithmes de minimisation avec contraintes

Le but de cette section est de donner des algorithmes numériques pour la résolution du problème de
minimisation avec contraintes
5.1 Méthodes de relaxation
On suppose ici le cas où U est un pave :
L’algorithme dans ce cas ressemble à l’algorithme de relaxation pour minimisation sans contraintes.
On se donne :

et on va calculer :

En n pas successifs, On a :

Comme dans le cas sans contraintes, on a le théorème de convergence suivant :

Théorème 5.
Si J : IRn → IR est une fonction elliptique et l’ensemble U est un pavé alors la méthode de relaxation pour la
minimisation de J sur U est bien définie et converge.
5.2 Méthodes de gradient projeté
La méthode du gradient projeté s’inspire des méthodes de gradient décrites dans le chapitre précédent. L’idée de
base consiste à suivre la direction de plus profonde descente, comme dans le cas sans contrainte.
Rappelons que, dans le cas sans contrainte, l’algorithme du gradient, qui est une méthode de descente, s’écrit
sous la forme générique :

38
 T. Ouaderhman
Lorsque l’on minimise sur un ensemble de contraintes C supposé fermé, il n’est pas sûr que x (k) reste dans C.
Il est donc nécessaire de se ramener dans C. On réalise cette dernière opération grâce à une projection sur C,
l’opérateur associé étant note

Ceci donne lieu alors naturellement à l’algorithme du gradient projeté, algorithme identique à celui du gradient
à la projection :

Cette approche paraît simple au premier abord. Toutefois, il ne faut pas oublier que l’on doit connaître
l’opérateur de projection sur C, ce qui n’est pas, à priori simple.
Il est important de remarquer que le calcul à l’étape 2(a) du projeté sur X, peut parfois être aussi difficile
yk est obtenu en résolvant le problème :

Il s’agit donc de résoudre un problème d’optimisation sur un convexe, avec une fonction objectif convexe.
Lorsque le domaine X des contraintes est simple (contraintes de bornes en particulier), c’est faisable. Dès que
les contraintes ne sont pas des contraintes de bornes, le calcul de la projection devient beaucoup plus délicat.

Exemple : Supposons que C soit une intersection de demi-espaces du type

I et J étant des ensembles d’indices non nécessairement disjoints (ceci contient notamment le cas des paves

2) Si l’ensemble des contraintes est

la projection s’écrit alors :

39
Optimisation numérique et Python

Acknowledgments

40