TECHNIQUES D’OPTIMISATION: IFT 3515 3 février 2016

CHAPITRE 1. GÉNÉRALITÉS. OPTIMISATION SANS CONTRAINTES.

PROGRAMMATION LINÉAIRE

Notions à revoir: ensemble (ouvert, fermé, connexe, borné, compact, frontière, intérieur, point d’accumulation (point
limite), intersection, union, somme, produit cartésien), espace euclidien (distance, norme, produit scalaire), suite
(limite, limite supérieure, limite inférieure), algèbre linéaire (matrice, valeur propre, matrice définie positive, matrice
définie négative), calcul (continuité, différentiabilité, fonction composée (règle de dérivation), dérivée directionnelle,
jacobien, hessien).

1. problème générique: minx∈X f (x) où X ⊂ Rn et f (x) ∈ R.

minimum local x∗ : ∃ǫ > 0 tel que f (x) − f (x∗ ) ≥ 0 ∀x 6= x∗ tel que kx − x∗ k < ǫ.
minimum global x∗ : f (x) − f (x∗ ) ≥ 0 ∀x 6= x∗ .
minimum local strict: remplacer “≥” ci-dessus par “>”.
Une fonction est unimodale si tout minimum local est global.
2. Un ensemble X est convexe si x, y ∈ X ⇒ [x, y] ⊂ X, c-à-d: θx + (1 − θ)y ∈ X pour tout x, y ∈ X et θ ∈ [0, 1].
L’intersection, la somme et le produit cartésien d’ensembles convexes sont convexes. L’union d’ensembles convexes
n’est en général pas convexe. L’enveloppe convexe d’un ensemble X est le plus petit ensemble convexe contenant
X, c’est-à-dire l’intersection de tous les ensembles convexes contenant X. Un polyèdre P = {x : Ax ≤ b} est
l’intersection d’un nombre fini de demi-espaces. Un polytope est l’enveloppe convexe d’un nombre fini de
points. Tout polytope est un polyèdre. Tout point de l’enveloppe convexe d’un nombre fini de points de Rn peut
s’exprimer comme une combinaison convexe d’au plus n + 1 des points originaux.
3. Une fonction f définie sur un ensemble convexe X est convexe sur X si (et seulement si)

f (θx + (1 − θ)y) ≤ θf (x) + (1 − θ)f (y) ∀x, y ∈ X ∀θ ∈ (0, 1).

Toute fonction convexe définie sur un ensemble ouvert est continue et différentiable (presque partout). Toute
fonction convexe est unimodale. Une fonction est strictement convexe si l’inégalité est stricte pour tout x 6= y.
Une fonction est fortement convexe s’il existe une constante positive β telle que

f (θx + (1 − θ)y) ≤ θf (x) + (1 − θ)f (y) − βθ(1 − θ)kx − yk2 ∀x, y ∈ X ∀θ ∈ (0, 1).

Si f est différentiable sur l’ensemble convexe X, alors les deux propriétés suivantes sont équivalentes à la convexité
de f sur X:

inégalité du gradient: f (y) ≥ f (x) + ∇f (x)(y − x) ∀x, y ∈ X

monotonie: (∇f (x) − ∇f (y))(x − y) ≥ 0 ∀x, y ∈ X.

Si l’inégalité est stricte pour x 6= y (monotonie stricte), la fonction f est strictement convexe. Dans la cas de la
forte convexité, on rajoute le terme βkx − yk2 au membre de droite des deux inégalités. On parle alors de forte
monotonie.

Une fonction deux fois différentiable est convexe si et seulement si (x − y)t ∇2 f (x)(x − y) ≥ 0 ∀x, y ∈ X. Si
X = Rn , cette condition revient à dire que la matrice hessienne H(x) = ∇2 f (x) est semidéfinie positive sur
X. Si la matrice hessienne est uniformément définie positive pour tout x dans X (ses valeurs propres sont
bornées inférieurement par un nombre positif), alors la fonction f est fortement convexe. Toute combinaison
linéaire non négative de fonctions convexes est convexe. e maximum d’un ensemble de fonctions convexes est une
fonctionconvexe. Une fonction f est concave si −f est convexe.
4. développement de Taylor:
premier ordre: f (y) = f (x) + ∇f (x)(y − x) + o(ky − xk) = f (x) + ∇f (ξ)(y − x) où ξ ∈ [x, y].
deuxième ordre:
1
f (y) = f (x) + ∇f (x)(y − x) + (y − x)t H(x)(y − x) + o(ky − xk2 )
2
1
= f (x) + ∇f (x)(y − x) + (y − x)t H(ξ)(y − x) où ξ ∈ [x, y].
2

1
5. conditions nécessaires d’optimalité du premier ordre:
g ′ (x∗ ; d) = ∇f (x∗ )d ≥ 0 pour toute direction réalisable d. Si X = Rn , ces conditions se résument à: ∇f (x∗ ) = 0.
Un point satisfaisant les conditions d’optimalité du premier ordre est appelé point stationnaire.
Tout point stationnaire d’une fonction convexe est un minimum global.

6. conditions nécessaires d’optimalité du second ordre: On rajoute aux conditions du premier ordre la con-
dition:
dt H(x∗ )d ≥ 0 si ∇f (x∗ )d = 0.
Si X = Rn cette dernière condition se résume à: H(x∗ ) semidéfinie positive.

7. Un algorithme est une multifonction qui associe à un point xk de Rn un point xk+1 du sous-ensemble A(xk ) de
Rn . Dénotons par X ∗ l’ensemble des solutions. Un algorithme est un algorithme de descente pour la fonction
continue Z définie sur X si:

(i) x∈X et y ∈ A(x) ⇒ y ∈ X

(ii) x∈/ X∗ et y ∈ A(x) ⇒ Z(y) < Z(x)
(iii) x ∈ X∗ et y ∈ A(x) ⇒ Z(y) ≤ Z(x).

Un algorithme est fermé si

xk ∈ X



xk → x

⇒ y ∈ A(x).
y k ∈ A(xk ) 

yk → y


Une multifonction A est fermée si et seulement si son graphe G = {(x, u)|x ∈ X, u ∈ A(x)} est un ensemble
fermé.
théorème de convergence globale: Soit {xk } une suite engendrée par un algorithme de descente. Si X est
/ X ∗ , alors la limite de toute sous-suite convergente appartient à l’ensemble
compact et A(x) est fermé pour tout x ∈
∗
des solutions X .
La choix de la fonction de descente Z est souvent f (xk ) ou kxk −x∗ k2 . Sauf indication contraire, tous les algorithmes
mentionnés dans ces notes sont fermés.

8. ordre de convergence τ d’une suite {rk } vers le nombre r∗ :

|rk+1 − r∗ |
 
def
τ = lim sup β = lim sup <∞ .
p≥0 k→∞ |rk − r∗ |p

Si p = 1 et 0 < β < 1, on dit que la suite converge linéairement (ou géométriquement) vers r∗ avec un taux
de convergence égal à β. Si la suite converge et β = 1 on dit que la convergence est sous-linéaire.
Si p = 2 et 0 < β < ∞, on dit que la convergence est quadratique.
Si p = 1 et β = 0 on dit que la convergence est superlinéaire.

9. Optimisation d’une fonction unidimensionnelle unimodale définie sur un intervalle:

Étant donnés un intervalle [x0 , xN +1 ] = [a, b] et deux points intérieurs x1 et x2 (x1 < x2 ), la connaissance des
valeurs de la fonction f en ces deux points permet de réduire l’intervalle d’incertitude: si f (x1 ) > f (x2 ) on conserve
l’intervalle [x1 , xN +1 ], sinon on conserve l’intervalle [x0 , x2 ].
Supposons que l’intervalle [x1 , xN +1 ] soit retenu. Une stratégie “naturelle” consiste à choisir le prochain point
d’évaluation symétriquement à x2 par rapport à x1 et xN +1 . Il en va de même si l’intervalle [x0 , x2 ] est retenu. Le
choix des points d’évaluation est alors déterminé par l’emplacement du point d’évaluation initial x1 et les valeurs
prises par f aux points d’évaluation successifs. Étant donné un nombre de points d’évaluation N connu a priori, le
choix permettant de réduire au minimum la largeur de l’intervalle d’incertitude est: x1 = a+(FN −1 /FN )(b−a), où
FN est le N ième terme de la suite de Fibonacci définie récursivement par: F0 = F1 = 1, FN = FN −1 + FN −2 . A
l’itération k, la largeur de l’intervalle d’incertitude est (FN −k+1 /FN )(b − a). A la dernière itération, plutôt que de
faire coı̈ncider xN −1 et xN , (ce qui ne donnerait aucune information supplémentaire) on situe xN arbitrairement
proche de xN −1 , de façon à réduire de moitié la largeur de l’intervalle.

2
  √ N  √ N
FN +1 √
Puisque FN = √15 1+2 5 − √15 1−2 5 , on a: limN →∞ FN = (1 + 5)/2 = φ (le nombre d’or des Grecs).
Le taux de convergence asymptotique est égal à 1/φ.
On peut également choisir x1 = a + (b − a)/φ. Ce choix est indépendant de N et reproduit les mêmes rapports
entre les intervalles, modulo un changement d’échelle. Après k itérations, l’intervalle d’incertitude est réduit par un
facteur φk . Cette méthode de la section dorée est asymptotiquement aussi efficace que la méthode de Fibonacci.
À chaque itération, les proportions sont conservées, c-à-d, si a = 0 et b = 1: x1 /1 = x2 /x1 = (1 − x1 )/(1 − x2 ).
10. recherche binaire: si la fonction f est différentiable et que f ′ (a) < 0 et f ′ (b) > 0, on peut déterminer un zéro
de f ′ , c’est-à-dire un point stationnaire de f . Cette technique réduit de moitié l’intervalle d’incertitude à chaque
itération en évaluant f ′ au milieu de l’intervalle: xk+1 = (xk + xk−1 )/2. Si f ′ (x) < 0, au moins un zéro doit se
trouver à droite de x; si f ′ (x) > 0, au moins un zéro doit se trouver à gauche de x.
11. La méthode de Newton unidimensionnelle minimise l’approximation quadratique (Taylor au second ordre)
de la fonction f au point courant. La méthode, comme la recherche binaire, peut s’appliquer à la recherche d’une
racine d’une fonction g. Elle consiste alors à trouver le zéro de l’approximation linéaire de g au point courant,
c’est-à-dire à résoudre l’équation:
g(xk ) + g ′ (xk )(x − xk ) = 0,
dont la solution est: xk+1 = xk − g(xk )/g ′ (xk ). Si g(x∗ ) = 0 et g ′ (x∗ ) 6= 0, la convergence de la méthode vers x∗
est localement quadratique.

12. La méthode de la sécante cherche une racine de l’équation g(x) = 0 en approximant la fonction g par une droite
joignant les deux points les plus récents. Cette droite coupe l’axe des abscisses au point:
xk − xk−1
xk+1 = xk − g(xk ) .
g(xk ) − g(xk−1 )

Si g(x∗ ) = 0 et g ′ (x∗ ) 6= 0 la convergence locale de la méthode est d’ordre 1 + φ = 1/φ.

La méthode de la fausse position (regula falsi) cherche une racine de l’équation g(x) = 0 sur l’intervalle [a, b],
où g(a) < 0 et g(b) > 0, en approximant la fonction g par une droite joignant les deux points les plus récents
ayant des valeurs opposées. La convergence peut être en pratique nettement moins bonne que celle de la recherche
dichotomique.

13. ajustement quadratique: à l’itération k, on minimise le polynôme d’interpolation passant par les points
(xk−1 , f (xk−1 )), (xk−2 , f (xk−2 )) et (xk−3 , f (xk−3 )). L’ordre de convergence de la méthode est d’environ 1.3.

14. méthode de la plus grande pente, ou méthode du gradient: on pose g(x) = ∇f (x)t et on choisit: xk+1 =
xk − αk g(xk ) où αk ∈ arg minα≥0 f (xk − αg(xk )). Si f est la fonction quadratique f (x) = (1/2)xt Qx, où Q est
une matrice symétrique définie positive dont la plus petite valeur propre est a et la plus grande valeur propre est
A, on a l’inégalité de Kantorovitch:

(xt x)2 4aA

t t −1
≥ .
(x Qx)(x Q x) (a + A)2

On en déduit:  2
A−a
f (xk+1 ) ≤ f (xk ).
A+a
 2
Dans le cas général, la convergence est linéaire de taux A−a
A+a .

15. méthode de Newton multidimensionnelle: on généralise la méthode de Newton unidimensionnelle, qui devient
maintenant:
xk+1 = xk − [J(xk )]−1 g(xk ),
où J(xk ) dénote la matrice jacobienne de g évaluée au point xk . Si la fonction g est le gradient d’une fonction
convexe f , alors la direction de Newton est une direction de descente pour f , et on peut rendre la méthode
globalement convergente en effectuant, à chaque itération, une recherche dans cette direction.

3
16. Gauss-Seidel: on minimise la fonction f pour chaque variable séquentiellement, de la première à la dernière, puis
on recommence à la première, etc., ce qui donne, à chaque itération majeure:

xk+1
l ∈ arg min f (xk+1
1 , xk+1
2 , . . . , xk+1 k k
l−1 , x, xl+1 , . . . , xn ), l = 1, . . . , n.
x

On peut également appliquer cette technique à la résolution d’un système d’équations F (x) = 0, ce qui donne:

Fl (xk+1
1 , xk+1
2 , . . . , xk+1 k+1
l−1 , xl , xkl+1 , . . . , xkn ) = 0, l = 1, . . . , n.

La méthode de Jacobi est similaire, mais agit en parallèle sur toutes les variables:

xk+1
l ∈ arg min f (xk1 , xk2 , . . . , xkl−1 , x, xkl+1 , . . . , xkn ), l = 1, . . . , n.
x

et
Fl (xk1 , xk2 , . . . , xkl−1 , xkl , xkl+1 , . . . , xkn ) = 0, l = 1, . . . , n.
Ces méthodes sont des cas particuliers d’approximation de la fonction originelle F par une fonction G plus simple
à manipuler: F (x) ≈ G(x, xk ) avec G(xk , xk ) = F (xk ). Si la fonction F = Ax + b est affine, la méthode de
Gauss-Seidel résoud le système Lx + (A − L)xk = 0, où L est la matrice triangulaire contenant les éléments de A
situés sur ou sous la diagonale principale. La méthode de Jacobi résoud le système diagonal Dx + (A − D)xk = 0,
où D est la diagonale de la matrice A. Si la matrice A est définie positive, les deux méthodes convergent vers la
solution du système.
17. critères d’arrêt d’une minimisation unidimensionnelle: soit d une direction de descente admissible pour la
fonction f au point xk . On définit la fonction unidimensionnelle

ϕ(α) = f (x + αd).

On arrête la minimisation de ϕ lorsqu’un taux de décroissance suffisant a été obtenu, c’est-à-dire

ϕ(α) ≤ ϕ(0) + ǫϕ′ (0)α

pour un certain paramètre 0 < ǫ < 1 et que:

règle d’Armijo: (α assez grand) ϕ(ηα) > ϕ(0) + ǫϕ′ (0)ηα où η > 1.

règle de Goldstein: 0 < ǫ < 1/2 et α assez grand: ϕ(α) > ϕ(0) + (1 − ǫ)ϕ′ (0)α .

règle de Wolfe: 0 < ǫ < 1/2 et α assez grand: ϕ′ (α) ≥ (1 − ǫ)ϕ′ (0) . Ce dernier critère est invariant par
rapport aux changements d’échelle.

En pratique on part d’un α assez grand, qu’on diminue par un facteur constant jusqu’à ce que le critère soit
satisfait. Si les critères d’Armijo, Goldstein ou Wolfe sont couplés à des méthodes engendrant des directions de
recherche fermées, les algorithmes résultant sont globalement convergents.
18. méthodes de directions conjuguées. Soit le problème quadratique convexe
1 t
min f (x) = x Qx + bt x
2
où la matrice Q : n × n est définie positive. Pour tout x on pose

g(x) = ∇f (x)t = Qx + b gk = g(xk ).

On considère un ensemble de directions Q-conjuguées1 :{p0 , . . . , pk }, c’est-à-dire:

pti Qpj 6= 0 ⇐⇒ i = j

ainsi que la variété affine Hk = xk + lin {p0 , . . . , pk }. Soit Pk = (p0 , . . . , pk ). On a:

k
X
min f (x) ≡ min f (xk + Pk α) = f (xk + α i pi )
x∈Hk α∈Rk+1
i=0
1 Par exemple, les directions correspondant aux vecteurs propres de la matrice Q (axes principaux) sont Q-conjuguées.

4
 avec

1 k
f (xk + Pk α) = (x + Pk α)t Q(xk + Pk α) + bt (xk + Pk α)
2
1 t t
= α Pk QPk α + gkt Pk α + f (xk )
2
k h
X 1 t i
= (pi Qpi )αi2 + (gkt pi )αi + f (xk ).
i=0
2

qui est une fonction séparable, simple à minimiser. Son minimum est atteint en αk = −(gkt pk )/(ptk Qpk ). Comme
xk est le minimum de la fonction f sur la variété Hk et que Hn−1 = Rn , la solution optimale est obtenu après
exactement n itérations. On obtient:
gkt pk
xk+1 = xk + αk pk avec αk = − .
ptk Qpk
Pk−1
Pour l’algorithme du gradient conjugué on fait le choix: pk = −gk + j=0 βkj pj . Puisque gi ∈ lin {p0 , . . . , pk−1 }
pour tout i < k, on en déduit que gkt gi = 0 pour tout i < k. Quelques calculs élémentaires (processus
d’orthogonalisation de Gram-Schmidt2 ) permettent d’obtenir la formule:
k−1
X gkt Qpj
pk = −gk + pj .
j=0
ptj Qpj

Notons que gj+1 − gj = Q(xj+1 − xj ) = αj Qpj ⇒ gkt Qpj = gkt (gj+1 − gj )/αj 6= 0 ⇔ j = k − 1, ce qui mène à
l’expression simplifiée:
gkt (gk − gk−1 )
pk = −gk + pk−1 .
αk−1 ptk−1 Qpk−1
t
Enfin, puisque αk−1 = −gk−1 pk−1 /ptk−1 Qpk−1 = kgk−1 k2 /ptk−1 Qpk−1 ⇒ αk−1 ptk−1 Qpk−1 = kgk−1 k2 , on
obtient
pk = −gk + βk−1 pk−1

où le coefficient βk−1 peut s’exprimer sous la forme βk−1 = (gk − gk−1 )t gk /kgk−1 k2 ou βk−1 = kgk k2 /kgk−1 k2 .

ALGORITHME (gradient conjugué) x0 arbitraire

β−1 = 0 p−1 = 0
pk = −gk + βk−1 pk−1 αk = kgk k2 /ptk Qpk
xk+1 = xk + αk pk βk = kgk+1 k2 /kgk k2 = (gk+1 − gk )t gk /kgk k2

Dans le cas non linéaire, on identifie gk à ∇f (xk )t et on utilise soit l’expression βk−1 = kgk k2 /kgk−1 k2 (Fletcher-
Reeves), soit l’expression βk−1 = (gk − gk−1 )t /kgk−1 k2 (Polak-Ribière). La valeur de αk est obtenue à partir
de la recherche linéaire
min f (xk + αpk ).
α≥0

Puisque le minimum n’est pas toujours atteint en n itérations, l’algorithme procède par cycles de n sous-itérations.
La méthode du gradient conjugué est à peine plus coûteuse à implanter que l’algorithme du gradient, et beaucoup
plus efficace.

2 Si {b } est un ensemble de vecteurs linéairement indépendants, on obtient un ensemble de vecteurs orthogonaux définissant le même
k
Pk−1
sous-espace à l’aide de la formule b′k = bk − i=0
hbk , b′i ib′i /kb′i k2 .

5
19. Méthodes quasi-Newton
Comme l’algorithme du gradient conjugué, cette classe de méthodes cherche à tirer le meilleur profit possible de
l’information de premier ordre (gradient) fournie par les itérés. À chaque itération, on résoud un système linéaire
dont la matrice Bk est une approximation de la matrice hessienne H(xk ). Le schéma de l’algorithme est simple:

ALGORITHME (quasi-Newton) x0 arbitraire et B0 définie positive

itération k: résoudre Bk d = −∇f (x ) → dk
k

minα f (xk + αdk ) → xk+1

mise-à-jour de Bk

On souhaite que la matrice Bk possède les propriétés suivantes:

• facile à mettre à jour,
• symétrique,
• “converge” vers la matrice hessienne;
• généralise la méthode de la sécante, c’est-à-dire possède la “propriété de la sécante” (exacte dans le cas
quadratique)

Bk (xk − xk−1 ) = gk − gk−1 .

• résolve un problème quadratique de dimension n en n itérations;
• soit définie positive.
En posant pk = xk+1 − xk et uk = gk+1 − gk , la propriété de la sécante se résume à Bk+1 pk = uk . Une correction
de rang un qui conserve la symétrie est obtenue en posant Bk+1 = Bk + βzz t . On déduit de la propriété de la
sécante la relation Bk pk + βzz t pk = uk . On a:
(uk − Bk pk )(uk − Bk pk )t
(uk − Bk pk )(uk − Bk pk )t = β 2 ptk zz t ptk zz t = β 2 (ptk z)2 zz t ⇒ zz t = .
β 2 (ptk z)2
Or, en prenant le produit scalaire avec pk dans l’égalité de la sécante, on obtient

ptk Bk pk + βptk zz t pk = ptk uk ⇒ β(ptk z)2 = ptk (uk − Bk pk )

(uk − Bk pk )(uk − Bk pk )t
⇒ Bk+1 = Bk + .
ptk (uk − Bk pk )

Il existe des formules permettant d’approximer directement l’inverse de la matrice hessienne. Il y a cependant
avantage, pour des raisons de stabilité numérique, de travailler avec des approximations de la matrice hessienne.
D’une itération à l’autre, il est facile de récupérer la matrice inverse de Bk à l’aide de la formule de Sherman-
Morrison:

uv t A−1
 
t −1 −1
(A + uv ) =A I− ,
1 + v t A−1 u
qui est valide même si la matrice A n’est pas symétrique.
Malheureusement, la matrice Bk n’est pas nécessairement définie positive. Pour cela, il faut utiliser (au moins) une
mise-à-jour de rang deux. La formule suivante, qui définit la famille de Broyden, possède toutes les propriétés
requises, lorsque couplée avec une recherche linéaire adéquate:
(Bk pk )(Bk pk )t uk ut
Bk+1 = Bk − t + t k + ρ(ptk Bk pk )vk vkt
pk B k pk u k pk
uk Bk uk
où vk = − t .
utk pk uk Bk uk

Le choix ρ = 1 a été proposé par Broyden, Fletcher, Goldfarb et Shanno (BFGS) alors que le choix ρ = 0 a été
proposé par Davidon, Fletcher et Powell (DFP). Chaque technique possède des avantages et des inconvénients.

6
20. rappel de programmation linéaire. (voir également les notes du cours IFT 1571: marcotte/Ift1571/[Link])

min cx
x
Ax = b c: 1×n
x≥0 x: n×1 (P)
A: m×n
b: m×1

On suppose que la matrice A (dont la jième colonne sera notée Aj ) est de plein rang. Soit B une sous-matrice
 carrée

xB
(base) formée de m colonnes indépendantes de A. On associe à B les décompositions A = [B|N ] et x = .
 −1  xN
B b
Si l’on fixe le vecteur des variables hors base xN à zéro, on obtient la solution de base x = . Une
0
solution de base est admissible si xB ≥ 0. Réécrivons le programme linéaire (P) en mettant en évidence la
décomposition de A et de x:

min cB xB + cN xN
xB ,xN
BxB + N xN = b
xB , xN ≥ 0

ou, après quelques manipulations élémentaires:

min cB B −1 b + (cN − cB B −1 N )xN

xN

B −1 b − B −1 N xN ≥ 0.

Puisque xB = B −1 b ≥ 0, la solution xN = 0 du programme ci-dessus est réalisable.

L’algorithme du simplexe tente d’améliorer la solution en intégrant dans la base une variable hors-base xj ∗
(j ∗ ∈ N ) dont le coût réduit cj ∗ − cB B −1 Aj ∗ est négatif. La valeur maximale que peut prendre xj ∗ est donnée
par
xj ∗ = arg inf {t : (B −1 b)i − t(B −1 Aj ∗ )i ≥ 0 ∀i ∈ B}.
t

Si t = +∞, le programme linéaire (P) est non borné inférieurement. Sinon, on fait sortir de la base une variable
xi∗ (i∗ ∈ B) telle que
(B −1 b)i∗ − xj ∗ (B −1 Aj ∗ )i∗ = 0.
La nouvelle base est: B ← B ∪ Aj ∗ − Ai∗ .
On continue le processus jusqu’à ce que le vecteur des coûts réduits c − cB B −1 A soit non négatif. [remarque: la
partie de ce vecteur correspondant aux variables de base est nulle puisque cB − cB B −1 B = 0.]
Dualité: Soit y un vecteur 1 × m. Une borne inférieure sur la valeur du programme (P) s’obtient en substituant
aux contraintes Ax = b l’unique contrainte yAx = yb. Si de plus on a que yA ≤ c, on obtient trivialement la borne
inférieure cx ≥ yAx = yb. Si l’on veut maintenant obtenir la meilleure borne inférieure à partir de cette technique,
on est amené à étudier le programme linéaire dual

max yb
y (D)
yA ≤ c

Remarquons que le dual du programme linéaire (D) est (P). De plus, si le problème primal (P) possède un minimum,
on a le résultat:
max yb = min cx.
y x

7
Les conditions primales-duales suivantes caractérisent l’optimalité d’une solution:

Ax = b
primal réalisable
x≥0

yA ≤ c dual réalisable

yb = cx écarts complémentaires
ou (yA − c)x = 0 (orthogonalité)

Les variables y sont appelées variables duales ou parfois multiplicateurs du simplexe. Si B est une base
optimale, c’est-à-dire que les coûts réduits sont tous positifs ou nuls, alors y = cB B −1 est une solution optimale
du problème dual.
On dit qu’une base (ou la solution de base correspondante) est dégénérée si au moins une des variables de base
est nulle. La dégénérescence cause des problèmes dans l’analyse de la convergence de la méthode du simplexe.
Enfin, mentionnons qu’il existe des algorithmes polynomiaux pour la programmation linéaire, basés sur des tech-
niques de programmation non linéaire. En toute probabilité, l’algorithme du simplexe n’est pas polynomial.

8
 CHAPITRE 2. OPTIMISATION AVEC CONTRAINTES: MÉTHODES PRIMALES

N.B. Dans ce qui suit, le gradient sera parfois un vecteur ligne, parfois un vecteur colonne, afin d’éviter la lourde
notation (∇f (x))t . Cela ne devrait pas créer de confusion.
1. conditions nécessaires d’optimalité: Considérons le programme
min f (x)
x
x ∈ X = {x : Ax ≥ b}
Si x est un candidat à l’optimalité (point stationnaire), il ne doit pas y avoir de direction de descente réalisable
en x. Puisque toute direction réalisable peut prendre la forme d = x′ − x pour un certain x′ ∈ X, on obtient la
condition nécessaire d’optimalité du premier ordre:

∇f (x)(x′ − x) ≥ 0 ∀x′ ∈ X

qu’on peut réécrire comme minx′ ∈X ∇f (x)x′ = ∇f (x)x, c’est-à-dire :

x ∈ arg min ∇f (x)x′ .
x ∈X
′

Les conditions d’optimalité primales-duales de ce programme linéaire sont:

Ax ≥ b primal réalisable

yA = ∇f (x) dual réalisable

y≥0

y(Ax − b) = 0 orthogonalité

Ces conditions sont appelées conditions de Karush-Kuhn-Tucker associées à notre programme non linéaire.
Ces conditions sont suffisantes si la fonction f est convexe. Si l’ensemble X = {x : g1 (x) ≥ 0, . . . , gm (x) ≥ 0}
sont non linéaires, on obtient un résultat semblable en linéarisant les contraintes (moyennant certaines conditions
techniques):

g(x) ≥ 0 primal réalisable

y∇g(x) = ∇f (x) dual réalisable

KKT
y≥0

y g(x) = 0 orthogonalité

2. Une méthode primale engendre une suite de points satisfaisant les contraintes. La plupart de ces méthodes sont
également des algorithmes de descente. Les algorithmes suivants seront exposés dans le contexte d’un programme
non linéaire avec contraintes linéaires. Ils peuvent néanmoins être généralisés pour traiter des problèmes non
linéaires plus généraux.
3. Zoutendijk (algorithme non fermé, convergence sous-linéaire): Soit AE x = bE l’ensemble des contraintes satis-
faites à égalité. Une direction de descente d+ est obtenue en résolvant le sous-problème

min ∇f (x)d
d
AE d ≥ 0
kdk ≤ 1

min f (x + αd+ ) → x+ .
α≥0

Si k · k = k · k∞ ou k · k = k · k0 , la direction d+ s’obtient en résolvant un programme linéaire.

9
4. Frank-Wolfe (algorithme fermé, convergence sous-linéaire): Soit y + la solution du programme linéaire

min ∇f (x)(y − x)
y:Ay≥b

min f (x + α(y + − x)) → x+ .

0≤α≤1

Cet algorithme est utile pour résoudre des problèmes de grande taille très structurés, problèmes de réseau par
exemple.
5. gradient projeté I (algorithme fermé):
Soit γ positif et pγ = ProjX (x − γ∇f (x)). On a min0≤α≤1 f (x + α(pγ − x)) → x+ . La direction pγ − x est solution
optimale du problème quadratique
1
min kp − (x − γ∇f (x))k2
p∈X 2

dont les conditions du premier ordre sont:

hpγ − (x − γ∇f (x)), pγ − yi ≤ 0 ∀y ∈ X,

d’où l’on déduit, après avoir posé y = x ci-dessus, que

γ∇f (x)(pγ − x) ≤ −kpγ − xk2 ,

c’est-à-dire que la direction est bien une direction de descente. Si f est fortement convexe (de module β) et son
gradient lipschitzien (de constante L), la convergence est linéaire, même en prenant un pas de 1. En effet, puisque
l’opérateur de projection est contractant et que ProjX (x∗ − γ∇f (x∗ )) = x∗ , on peut écrire:

kpγ − x∗ k2 ≤ kx − γ∇f (x) − (x∗ − γ∇f (x∗ ))k2

≤ kx − x∗ k2 − 2γ(∇f (x) − ∇f (x∗ ))(x − x∗ ) + γ 2 k∇f (x) − ∇f (x∗ )k2
≤ (1 − 2γβ + γ 2 L2 )kx − x∗ k2
< kx − x∗ k2 si γ < 2β/L2 .

6. gradient projeté II (algorithme non fermé, convergence linéaire, si on est chanceux...):

Soit E l’ensemble des contraintes satisfaites à l’égalité et d = Proj{p:AE p=0} (−∇f (x)). On a

min f (x + αd) → x+ .
0≤α≤1

La direction d est solution du programme quadratique:

1
min kd − (−∇f (x))k2 ,
AE d=0 2
dont les conditions d’optimalité de Kuhn-Tucker sont:

AtE y = d + ∇f (x)
AE d = 0.

On suppose que la matrice AE est de plein rang, ce qui permet, après avoir multiplié la première égalité par AE ,
de trouver y = (AE AtE )−1 AE ∇f (x) et

d = −[I − AtE (AE AtE )−1 AE ]∇f (x).

Si d 6= 0, d est une direction de descente. Si d = 0, on a yAE = ∇f (x) et, si le vecteur de multiplicateurs y ne

contient aucune composante négative, les conditions de Kuhn-Tucker sont satisfaites et la solution est optimale.
Sinon, on recalcule la projection en supprimant une contrainte associée au multiplicateur de “mauvais” signe. Soit
j l’indice d’une contrainte de multiplicateur négatif et A la matrice obtenue de AE en supprimant la ligne Aj . Soit
d la projection sur l’ensemble de contraintes réduit. On a:

∇f (x) = AtE y
t
∇f (x) = A y − d.

10
 Le vecteur d ne peut être nul, car alors le système ∇f (x) = AtE y aurait deux solutions distinctes, ce qui est
incompatible avec l’hypothèse que la matrice AE est de plein rang. De plus:

0 > ∇f (x)d = y t AE d = yj Aj d.

Puisque yj est négatif, on en déduit que Aj d > 0 et que la direction d est admissible pour la jième contrainte.
Notons qu’en supprimant simultanément de AE les lignes correspondant à plusieurs multiplicateurs négatifs, on
n’est pas assuré que la direction résultante soit admissible.
7. méthode des contraintes actives (algorithme non fermé, convergence sous-linéaire):
A chaque itération, on relaxe les contraintes qui ne sont pas actives, c’est-à-dire dont la variable duale est nulle.
On se ramène ainsi à une optimisation en présence de contraintes d’égalité seulement, ce qui est plus simple. La
difficulté consiste à gérer la liste des contraintes actives et inactives, à l’aide des variables duales.
8. méthode du gradient réduit (algorithme non fermé): Comme pour l’algorithme du simplexe, on utilise une
décomposition du vecteur x en variables de base xB et variables hors base xN :

min f (xB , xN )
xB ,xN
BxB + N xN = b
xB , xN ≥ 0.

En posant xB = B −1 b − B −1 N xN on obtient:

min g(xN ) = f (B −1 b − B −1 N xN , xN )
xN ≥0

sujet à xB = B −1 b − B −1 N xN ≥ 0.

Le gradient réduit r(x) correspond au vecteur des coûts réduits en programmation linéaire:

r(x) = ∇f (x) − ∇B f (x)B −1 A.

On a: rN (x) = ∇g(xN ) = ∇N f (x) − ∇B f (x)B −1 N et rB (x) = 0. La direction de descente est:

j∈N : dj (x) = −rj (x) si rj (x) < 0;

dj (x) = −rj (x) si xj > 0;
dj (x) = 0 sinon;

j∈B: dB = −B −1 N dN .

Si d(x) = 0, la solution x satisfait les conditions de Kuhn et Tucker. Puis on effectue la minimisation

min f (x + αd) → x+ ,
α≥0

en s’assurant que le vecteur x demeure non négatif.

Comme dans l’algorithme du simplexe, toute variable de base qui s’annule quitte la base pour être remplacée par
une variable hors base. Le choix de la variable hors base n’est pas toujours unique; en effet, même si la solution de
base courante n’est pas dégénérée, il se peut qu’il y ait plusieurs variables hors base positives (ces variables sont
appelées superbasiques). Il se peut aussi que le minimum de f dans la direction d soit atteint sans qu’aucune
variable de base ne s’annule. On répète alors le processus sans changer de base.
La direction d ci-dessus n’est pas fermée. On peut cependant la rendre fermée en adoptant la modification suivante:
j∈N : dj (x) = −rj (x) si rj (x) < 0;
dj (x) = −xj rj (x) si rj (x) > 0 et xj > 0;
dj (x) = 0 sinon;

j∈B: dB = −B −1 N dN .

On appelle algorithme du simplexe convexe la variante de l’algorithme du gradient réduit qui consiste à ne
modifier qu’une seule variable hors base à chaque itération.

11
 CHAPITRE 3. OPTIMISATION AVEC CONTRAINTES: PÉNALITÉS ET BARRIÈRES

1. méthodes de pénalités: soit le problème générique

min f (x)
x∈S
S = {x : gi (x) ≤ 0 i = 1, . . . , n}.

La fonction P est une fonction de pénalité pour le problème ci-dessus si

P (x) = 0 ∀x ∈ S
P (x) > 0 ∀x ∈
/ S.

Cette fonction sert à définir le problème pénalisé (sans contraintes)

minx f (x) + cP (x) PEN(c)

dont on notera une solution globale, qui dépend du facteur de pénalité c, par x(c). Sous certaines conditions
faibles, on a:
lim x(c) = x∗ ,
c→∞

où x∗ est une solution globale du problème originel. Les formes les plus classiques des fonctions de pénalités sont:
Pn
P (x) = 12 i=1 [max{0, gi (x)}]2 = 21 kg + (x)k22
Pn
P (x) = i=1 max{0, gi (x)} = kg + (x)k∞ ,

où gi+ (x) = max{0, gi (x)}. Soit P (x) = 21 kg + (x)k22 . A l’optimum de PEN(c) on a:

∇f (x(c)) + cg + (x(c))∇g(x(c)) = 0.

Posons y(c) = cg + (x(c)). Si x(c) → x∗ et que le point x∗ est un point régulier (cette condition est satisfaite si les
gradients des contraintes actives en x∗ sont linéairement indépendants), on a: limc→∞ y(c) = y ∗ , un vecteur dual
optimal correspondant à la solution primale optimale x∗ .
Sous certaines conditions de régularité, la fonction de pénalité P (x) = kg + (x)k∞ est exacte, c’est-à-dire qu’il
existe une valeur critique c∗ finie telle que la solution de P (c) soit x∗ pour tout c ≥ c∗ . Notons cependant que le
problème pénalisé est alors non différentiable.
Les sous-problèmes sans contraintes sont résolus par des méthodes efficaces: Newton, quasi-Newton, gradients
conjugués, etc.
2. Une fonction de barrière B satisfait aux deux conditions
B(x) > −∞ si x ∈ S
B(x) → ∞ lorsque x approche la frontière de S

et sert à définir le problème

minx f (x) + 1c B(x) BAR(c)

dont on notera une solution optimale, qui dépend du facteur de barrière c, par x(c). Sous certaines conditions
faibles, on a:
lim x(c) = x∗ .
c→∞

Deux formes classiques de fonction de barrière sont:

Pn
B(x) = i=1 −gi1(x))
Pn
B(x) = − i=1 log(−gi (x)) (barrière logarithmique)

12
 Si B est de la première forme on a, à l’optimum de Q(c):
p
X 1
∇f (x(c)) + ∇gi (x(c)) = 0.
i=1
c[gi (x(c))]2

Posons y(c) = 1/c[gi (x(c))]2 . On a, sous certaines conditions: limc→∞ y(c) = y ∗ .

Les problèmes sans contraintes sont résolus à l’aide d’algorithmes efficaces.

3. Une méthode primale-duale pour résoudre le problème convexe

minx f (x)
sujet à g(x) ≤ 0.

Définissons le lagrangien
L(x, y) = f (x) + yg(x).
L’optimum primal-dual (x∗ , y ∗ ) (y ∗ ≥ 0) est un point de selle du lagrangien, c’est-à-dire :

f (x∗ ) + yg(x∗ ) ≤ f (x∗ ) + y ∗ g(x∗ ) ≤ f (x) + y ∗ g(x) ∀x, y (y ≥ 0).

On définit la fonction duale

φ(y) = min L(x, y).
x

La fonction φ est concave et son maximum est atteint en y ∗ . L’algorithme de Arrow consiste à maximiser φ à
l’aide de la méthode du gradient projeté I avec pas fixe. Si la fonction f est strictement convexe, le gradient de
φ est simplement g(x), où x est l’unique minimum de la fonction lagrangienne pour y fixé. On peut également
utiliser une méthode primale duale:

x+ = x − α[∇f (x) + y∇g(x)]t

y+ = max{0, y + αg(x)},

connue sous le nom d’algorithme de Arrow-Hurwicz-Uzawa, et qui converge linéairement si la fonction f est
fortement convexe.

4. La méthode des multiplicateurs est un compromis entre la méthode primale-duale de la section précédente et
la méthode des pénalités. Considérons le problème
1
min f (x) ≡ min f (x) + ckh(x)k22
x:h(x)=0 x:h(x)=0 2

et son lagrangien augmenté

1
L̄(x, y, c) = f (x) + yh(x) + ckh(x)k22 .
2
On minimise L̄ successivement par rapport aux variables x et y, ce qui donne:

min L̄(x, y, c) → x+
x
+
y = y + ch(x).

On peut montrer qu’il existe une valeur finie c∗ telle que L(x, y, c) possède un minimum local en x∗ pour tout
c ≥ c∗ . De plus, sous des conditions faibles, la convergence est linéaire.
Si le problème comporte des contraintes d’inégalité, on transforme celles-ci en contraintes d’égalité en introduisant
des variables d’écart. Ainsi, on remplace la contrainte gi (x) ≤ 0 par la contrainte gi (x) + zi2 = 0.

13
 CHAPITRE 4. MÉTHODES DE POINTS INTÉRIEURS

1. méthodes des ellipsoı̈des

Cette méthode permet de trouver un point réalisable, s’il en existe un, pour un ensemble X défini à partir de
fonctions convexes: X = {x : gi (x) < 0, i ∈ I} et dont l’intérieur n’est pas vide. Soit M0 une matrice symétrique
définie positive telle que X ⊂ E0 = {x : xt M0−1 x ≤ 1}. Soit x0 le centre de l’ellipsoı̈de E0 . Si x0 ∈/ X, soit i
l’indice d’une contrainte violée. Puisque gi est convexe, on a:

X ⊂ {x : gi (x0 ) + ∇gi (x0 )(x − x0 ) ≤ 0}.

L’algorithme construit l’ellipsoı̈de de volume minimal contenant l’intersection de E0 avec le demi-espace défini par
l’inéquation précédente, et répète le processus jusqu’à ce que soit le centre du nouvel ellipsoı̈de fasse partie de X,
soit l’on puisse démontrer que X est vide.

Si l’oracle qui produit l’indice d’une contrainte violée est polynomial, alors l’algorithme est polynomial. C’est le
cas pour la programmation linéaire (Khachyan).

2. méthode primale-duale
Considérons le programme mathématique

min f (x)
x
gi (x) = 0 i ∈ I
x≥0

et ses conditions d’optimalité:

gi (x) = 0 i∈I
X
∇f (x) − yi ∇gi (x) = s KKT
i∈I
sj xj = 0 j ∈ [1..n]

Considérons maintenant une méthode de barrière pour la résolution de ce programme. Pour un paramètre µ
donné, on obtient le programme mathématique (dont la solution est unique)

X
min f (x) − µ log xj
x
j
gi (x) = 0 i ∈ I

dont les conditions d’optimalité sont

gi (x) = 0 i∈I
X
∇f (x) − µ(1/x1 , . . . , 1/xn ) − yi ∇gi (x) = 0.
i∈I

En posant sj = µ/xj , on peut réécrire ce système comme un système de Karush-Kuhn-Tucker perturbé:

gi (x) = 0 i∈I
X
∇f (x) − yi ∇gi (x) = s KKT(µ)
i∈I
sj xj = µ j ∈ [1..n]

14
 L’idée générique d’une classe de méthodes de points intérieurs est de résoudre, à l’aide de la méthode de Newton,
le système de Kuhn-Tucker initial ou le système KT(µ) en s’assurant, dans ce dernier cas, que le paramètre µ ne
décroisse pas trop rapidement d’une itération à l’autre, afin que les conditions de non négativité soient toujours
satisfaites et qu’une itération de la méthode de Newton nous rapproche de la solution du système de Kuhn-Tucker
initial.

La courbe paramétrée x(µ) est appelée chemin central et l’algorithme ne s’en éloigne jamais “trop”. Si la
solution n’est pas unique, l’algorithme produit une suite qui converge vers le centre analytique de l’ensemble
des solutions.
3. cas linéaire (méthode de chemin central)

Dans le cas linéaire, on fait l’hypothèse que la matrice des contraintes A est de plein rang; le système KT(µ) prend
la forme
Ax = b
At y + s = c
Xs = µe (X = diag(x1 , . . . , xn ), e = (1, . . . , 1)t )
et la direction de Newton est solution du système linéaire
    
A 0 0 dx 0
0 At I   dy  =  0  (S = diag(s1 , . . . , sn ))
S 0 X ds µe − XSe
La solution de ce système est
−(AS −1 XAt )−1 AS −1 (µe − XSe)
   
dy
 ds  =  −At dy .
dx S (µe − XSe) − S −1 Xds
−1

Si µ ne diminue pas trop rapidement d’une itération à l’autre, on peu effectuer un pas unitaire. Ceci sera le cas si
le facteur de réduction est fixé à 1 − βn−1/2 , avec β ≤ 1/5. Des méthodes plus “agressives” utilisent des réductions
plus fortes, compensées par un plus grand nombre d’itérations de la méthode de Newton. Ces dernières accélèrent
la convergence. Dans les deux cas, on peut démontrer la polynomialité de l’algorithme.

Note: puisque y = (AAt )−1 A(c−s), on peut se contenter d’appliquer l’algorithme dans l’espace primal des vecteurs
x et s.
4. cas linéaire (méthode primale affine)
Soit le programme linéaire
max ct x
Ax=b,x≥0

et soit x un point admissible dont toutes les composantes soient positives. En effectuant le changement de variable
u = X −1 x, on obtient le programme linéaire
max cXu
AXu = b
u ≥ 0.
Au point u = X̄ −1 x = e, la direction de plus forte descente est
du = −proj{d:AX̄d=0} (X̄c) = −(I − X̄At (AX̄ 2 At )−1 AX̄)Xc
et l’on pose
u+ = u + αdu
x+ = x + αX̄du
= x − αX̄(I − X̄At (AX̄ 2 At )−1 AX̄)X̄c.
On pose α = βαmax où αmax est le pas admissible maximal et β ≈ 1 (β < 1). Sous cette forme simpliste,
l’algorithme, quoique très performant en pratique, n’est pas polynomial.

15
 TECHNIQUES D’OPTIMISATION: EXEMPLES

CHAPITRE 1: GÉNÉRALITÉS. OPTIMISATION SANS CONTRAINTES. SIMPLEXE

1.

u
u
min local strict

u


minimum local min global minimum global

- -
fonction unimodale

2.

uy

u
y

u u
x
x

ensemble convexe (polytope)

“polyèdre” non convexe

3. Une fonction linéaire est convexe mais pas strictement convexe. La fonction f (x) = x2 est strictement convexe.

' $
' $
 
j
 
u
corde & %
u & %

-
fonction convexe

courbes de niveau d’une fonction quasiconvexe

16
4.
 
2 2 1
f (x, y) = xy + x ∇f (x, y) = ( y + 2x x) H(x, y) =
1 0
 
2 1
f (1, 2) = 3 ∇f (1, 2) = ( 4 1 ) H(1, 2) =
1 0
    
x−1 2 1 x−1
f (x, y) ≈ 3 + ( 4 1) + 21 ( x − 1 y − 2)
y−2 1 0 y−2
5.

−∇f (x∗ ) *


u
 
∗ 
point stationnaire x

:

u 
X
x 
Q
direction de descente
Q
Q
Q−∇f (x)
Q
Q
s
Q

Soit f (x, y) = x2 y − y. Les points stationnaires de

2
f sont des zéros du gradient
 ∇f (x, y) = ( 2xy x − 1 ), c’est-à-dire ( ±1 0 ). En ces deux point, la matrice
0 ±2
hessienne vaut H(±1, 0) = . Puisqu’elle est indéfinie, ces deux points ne sont ni des maximums ni
±2 0
des minimums.

6. Soit le programme miny≥0 f (x, y) = x2 + y 3 + y pour lequel le point (x∗ , y ∗ ) = (0, 0) est stationnaire. On a:

∇f (x, y) = ( 2x 3y 2 ) ∇f (x∗ , y ∗ ) = ( 0 0 )
   
2 0 ∗ ∗ 2 0
H(x, y) = H(x , y ) = .
0 6y 0 0

Les directions d telles que ∇f (x∗ , y ∗ )d = 0 sont d = (±1, 0). Ces directions satisfont: dt H(x∗ , y ∗ )d = 2 > 0 et par
conséquent le point (x∗ , y ∗ ) est un minimum local (un minimum global en fait).

7. L’algorithme du gradient (voir plus loin) est un algorithme de descente pour la fonction Z(x) = f (x). De plus,
il est fermé, si l’on définit X = Rn , X ∗ = {points stationnaires} = {x : ∇f (x) = 0}, et que l’on effectue une
recherche linéaire fermée à chaque itération, telle que spécifiée par la règle d’Armijo, par exemple. (voir plus loin.)

8. • Soit γ ∈ (0, 1) et rk = γ k . On a: r∗ = limk→∞ rk = 0 et: limk→∞ (|rk+1 − r∗ |/|rk − r∗ |) = γ. La convergence

est donc linéaire avec taux γ.

• Soit rk = (1/k)k . On a: limk→∞ (rk+1 /rkp ) = ∞ si p > 1. Par contre: limk→∞ (rk+1 /rk ) = 0. La convergence
de la suite vers zéro est donc superlinéaire.
k
• Soit a ∈ (0, 1) et rk = a2 . Puisque limk→∞ (rk+1 /rk2 ) = 1, la convergence de la suite vers zéro est quadratique.

• La suite rk = 1/k converge sous-linéairement vers zéro.

9. • La diminution de l’intervalle d’incertitude par l’évaluation d’un nouveau point:

17
 u
CO
u
u
? 6

u
?
?

x0 x1 x2 xN +1 x0 x1 x2 xN +1

• Suite de points d’évaluation découlant de l’application de la méthode de Fibonacci, si la plus petite valeur
observée de la fonction est toujours obtenue au dernier point d’évaluation.
x5

x0 x4 x3 x2 x1 x6

• Les deux premiers points d’évaluation correspondant à la méthode de la section dorée.

x0 = 0 x2 = 1 − φ x1 = φ xN +1 = 1

10. Recherche dichotomique d’un zéro d’une fonction continue.

f ′ (x)

a b
x2 x4 x3 x1

√
11. On peut approcher la valeur de 2 en appliquant la méthode de Newton à l’équation x2 − 2 = 0. On obtient la
suite définie par:
(xk )2 − 2 xk 1
xk+1 = xk − = + k.
2xk 2 x
Si x0 = 1 on obtient:
x1 = 1/2 + 1/1 = 1.5
x2 = 3/4 + 2/3 = 1.416666667
x3 = 1.414215686
x4 = 1.414213562.

18
12. Si on applique la méthode de la fausse position à la fonction x2 − 2, on obtient:

xk − xk−1 (xk )2 − 2
xk+1 = xk − ((xk )2 − 2) = x k
− .
(xk )2 − (xk−1 )2 xk + xk−1

Si x0 = 0 et x1 = 1 on obtient la suite:

x2 = 1 − (−1/1) = 2
3
x = 1.333333333
x4 = 1.400000000
x5 = 1.414634146
x6 = 1.414211439
x7 = 1.414213562

13.
14. • Soit f (x) = 21 xt Qx + bt x. On a ∇t f (x) = Qx + b et la méthode du gradient prend la forme: xk+1 =
xk − αk (Qxk + b). Soit g k = ∇t f (xk ) et φ(α) = f (xk − αk g k ). On veut:

φ′ (αk ) = ∇f (xk )∇t f (xk+1 ) = 0

→ (Qxk + b)t (Q(xk − αk g k ) + b) = 0
kQxk + bk2
→ αk = .
(Qx + b)t Q(Qxk + b)
k

 
3 1
• Si Q = dans l’exemple ci-dessus, on obtient: a = 2 et A = 5. Le taux de convergence est donc, par
1 4
l’inégalité de Kantorovitch, inférieur à (A − a)2 /(A + a)2 = (5 − 2)2 /(5 + 2)2 = 9/49.
t
15. Soit le système d’équations: x2 + y − 3 = 0, 2x − y 2 + 2 = 0. Au point de départ x0 = ( 1 1 ) , on a:
t
f (x0 ) = ( −1 3 ) . Il s’ensuit:
   
2x 1 2 1
J(x, y) = J(1, 1) =
2 −2y 2 −2
   −1           
1 2 1 −1 1 −2 −1 −1 1 1/6 5/6
x1 = − = = − = .
1 2 −2 3 6 −2 2 3 1 −4/3 7/3

16. Soit f (x, y) = 12 (x + y)2 + x2 − y. On a:

1
min f (x, y) → x+ + y + 2x+ = 0 ⇒ x+ = − y
x 3
1
min f (x, y) → x+ + y + − 1 = 0 → y + = 1 − x+ = 1 + y + .
y 3
A partir de x0 = 1 et y 0 = 2, l’algorithme de Gauss-Seidel produit la suite:

x1 = −2/3 y1 = 5/3
x2 = −5/9 y2 = 14/9
x3 = −14/27 y3 = 41/27
x4 = −41/81 y4 = 122/81 .

17. Soit φ(α) = (α − 1)2 . On a: φ(0) = 1 et φ′ (0) = −2.

• Armijo (ǫ = 1/2 et η = 2):

1
(α − 1)2 ≤ 1 + (−2)α = 1 − α ⇒ α ≤ 1
2
1 1
(2α − 1)2 > 1 + (−2)2α = 1 − 2α ⇒ α >
2 2

19
 • Goldstein (ǫ = 1/3):
2 4
(α − 1)2 ≤ 1− α ⇒ α≤
3 3
4 2
(α − 1)2 > 1− α ⇒ α>
3 3
• Wolfe (ǫ = 1/3): α ≤ 4/3 comme pour Goldstein et:
2 2 1
2(α − 1) > (−2) → α > 1 − = .
3 3 3
18.      
4x1 + x2 − 6 4 1 0
min 2x21 + x1 x2 + x22 − 6x1 − 5x2 g(x) = Q= 0
x = .
x1 + 2x2 − 5 1 2 0
 
6
k = 0 p0 = −g0 =
5

α0 = kg0 k2 /pt0 Qp0 = (62 + 52 )/(6 5)Q(6 5)t = 61/254

     
0 6 1.44
x1 = + 61/254 ≈
0 5 1.20
   
4 × 1.44 + 1.20 − 6 .96
g1 ≈ ≈
1.44 + 2 × 1.20 − 5 −1.16

β0 = kg1 k2 /kg0 k2 ≈ 2.27/61 ≈ .037 (Fletcher-Reeves)

β0 = (g1 − g0 )t g1 /kg0 k2 ≈ (−5.04 − 6.16)t (.96 − 1.16)/61 ≈ 2.31/61 ≈ .038 (Polak-Ribière)

     
−.96 6 −.74
k = 1 p1 = −g1 + β0 p0 ≈ + .037 ≈
1.16 5 1.35

α1 = kg1 k2 /pt1 Qp1 = 2.27/3.84 ≈ .59

     
2 1.44 −.74 1.00
x ≈ + .59 ≈ ≈ x∗ .
1.20 1.35 2.00
On vérifie que les directions p0 et p1 sont bien conjuguées:
    
t t 4 1 6 29
p1 Qp0 ≈ (−.74 1.35) ≈ (−.74 1.35) ≈ −.14 ≈ 0.
1 2 5 16

19. •
20. •
−A1
 −c

  *  −A2

u

 
u  c = y1 A1 + y2 A2
 
x2 
x1 u
x∗ = x3

 contraintes actives en x∗ :
A1 x = b1
u
−c
Ax ≥ b A2 x = b2
x0
c

20
• Considérons le couple de programmes linéaires primal-dual

min x1 +3x2 +2x3 = 2 max 2y1 +y2

x1 − x3 = 1 y1 +y2 ≤ 1

x1 , x2 , x3 ≥ 0 y1 −y2 ≤ 2

y2
6

?

(2, 1)
*
 - y1

y∗
I
@
@

Puisque y1∗ et y2∗ son positifs, on en déduit que x∗1 − x∗3 = 2 et x∗1 + x∗2 + x∗3 = 1. Symétriquement, puisque y2 < 3,
il faut que x∗2 soit nul. Par conséquent: x∗1 = x∗2 = 1/2, et on vérifie aisément que les objectifs primal et dual sont
égaux à 2.

21
 CHAPITRE 2. OPTIMISATION AVEC CONTRAINTES: MÉTHODES PRIMALES

1. •
min f (x) = 2x21 + 2x1 x2 + x22 − 10x1 − 10x2
sujet à x21 + x22 ≤ 5
3x1 + x2 ≤ 6
Les conditions de KKT du problème précédent s’expriment comme
       
4x1 + 2x2 − 10 2x1 3 0
+ y1 + y2 =
2x1 + 2x2 − 10 2x2 1 0
y1 , y2 ≥ 0
y1 (x21 + x22 − 5) = 0
y2 (3x1 + x2 − 6) = 0.

La solution de ce système est: x∗ = (1, 2)t , y ∗ = (1, 0).

• Plusieurs situations font intervenir des contraintes linéaires:

minx≥0 f (x)
Ax = b.

Les conditions de KKT pour de tels problèmes s’écrivent:

Ax = b, x≥0 primal réalisable

∇f (x) − yA ≥ 0 dual réalisable (KKT)

(∇f (x) − yA)x = 0 orthogonalité

2. L’optimum du problème
minx,y≥0 −x
sujet à (1 − x)3 − y ≥ 0

1
(1-x)**3
0.8

0.6

0.4

0.2

-0.2
0 0.2 0.4 0.6 0.8 1 1.2 1.4
t
est le point (1, 0) . Pourtant, en ce point, il n’existe pas (voir figure ci-dessous) de multiplicateur y satisfaisant la
condition de KKT
∇f (1, 0) − λ∇g(1, 0) = (−1, 0) − y(0, −1) ≥ 0.

22
3. Considérons le problème quadratique convexe

minx≥0 (x1 − 2)2 + (x2 − 1)2

sujet à x1 + x2 ≤ 2.

(0,2) u
6

#
−∇f ( 12 , 21 ) 
1




e
  courbes de niveau
 
( 12 , 21 )  "!
u
 u
de l’objectif

x∗
(0,0) u-
(2,0)

Les figures ci-dessous illustrent les directions de descente obtenues à partir de divers algorithmes, en prenant
comme point de référence (1/2, 1/2), dont le gradient est (−3/2, −1/2).

Zoutendijk (norme k · k∞ )

(0,2) u
6

1
−∇f ( 12 , 21 ) 
 

x+ u





x u u x∗



(0,0) u-
(2,0)

4. Frank-Wolfe

(0,2) u
6

−∇f (x+ )
1
−∇f (x)
 
u 
 x∗


u

PP

P
PP u
x PP x +
(0,0) P u-
P
q
(2,0)

5.

23
 gradient projeté I

(0,2) u
6

1



u


u


u  p1/5 u
x  

p1/2 = x∗

(0,0) u-
p1 = (2, 0)

6. gradient projeté II

(0,2) u
6

1

d = p = −∇f (x) 


x + 
u

u u x∗
x
 


(0,0) u-
(2,0)

7. méthode des contraintes actives

(0,2) u
6

1

 
 

x + 

1
u  @ u ++
x  @
R
 x = x∗

(0,0) u-
(2,0)

24
8.
minx≥0 f (x) = x21 + x22 + x23 + x24 − 2x1 − 3x4

sujet à 2x1 + x2 + x3 + 4x4 = 7

x1 + x2 + 2x3 + x4 = 6
 
2 1
Soient x = (2, 2, 1, 0)t , x1 et x2 les variables de base et B = la base. On a: ∇f (x) = (2, 4, 2, −3). On a:
1 1
  
1 −1 2 1 1 4
r(x) = (2, 4, 2, −3) − (2, 4) = (0, 0, −8, −1).
−1 2 1 1 2 1

par conséquent, d3 = 8 et d4 = 1. On peut écrire:

x1 = 1 + x3 − 3x4
x2 = 5 − 3x3 + 2x4

x+
1 = 1 + x3 + 8α − 3(x4 + α) = x1 + 5α
x+
2 = 5 − 3(x3 + 8α) + 2(x4 + α) = x2 − 22α

d’où l’on tire que d1 = 5, d2 = −22 et α ≤ 1/11. On vérifie que le minimum de la fonction f (x + αd) pour
α ∈ [0, 1/11] est obtenu pour α = 1/11. La variable x2 quitte alors la base pour y être remplacée par x3 ou x4 , au
choix.
On note que la direction du gradient réduit ne coı̈ncide pas nécessairement avec la direction du gradient projeté
sur le cône des directions admissibles! En effet, le choix de la base peut influencer la direction du gradient réduit.

25