Optimisation sous contraintes - Feuille de TD 4
(conditions de Karush-Kuhn-Tucker)
Exercice 1 Minimiser la fonction
F (x, y) = x2 − 14x + y 2 − 6y − 7
sur l’ensemble
C = {(x, y) ∈ R2 ; x + y ≤ 2 et x + 2y ≤ 3}.
Interpréter géométriquement le problème.
Exercice 2 On considère la fonction J définie par
∀(x, y) ∈ R2 , J(x, y) = x2 − xy,
et l’ensemble
C = {(x, y) ∈ R2 , y ≤ 2x, x2 + y 2 = 1}.
a) Représenter graphiquement l’ensemble C. Quels sont les points réguliers pour les
contraintes qui définissent C ?
b) Trouver le minimum de J sur C.
c) Trouver le maximum de J sur C.
d) Représenter graphiquement à la main, puis à l’aide de la fonction contour (Oc-
tave/Matlab) les lignes de niveau de J, et retrouver les résultats précédents
géométriquement.
Exercice 3 Soient n1 , n2 , . . . nk des entiers strictement positifs. On définit, sur le
simplexe ( )
Xk
Sk = (pi )1≤i≤k ∈ Rk , pi = 1 et ∀i, pi ≥ 0 ,
i=1
la fonction
k
Y
F (p1 , p2 , . . . pk ) = pni i .
i=1
a) Maximiser F sur Sk .
b) Que se passe-t-il si certains des ni sont nuls ?
c) Interpréter en termes statistiques le résultat de la question a).
1
Exercice 4 (régression linéaire avec contrainte) Soient x = (xi ), y = (yi ) deux vecteurs
de Rn (n ≥ 2). On suppose dans toute la suite que les (xi )1≤i≤n sont deux à deux
distincts.
a) Décrire un algorithme permettant de trouver les réels a et b, avec b ≥ 0, qui
minimisent l’erreur quadratique
n
X
E(a, b) = (yi − axi − b)2 .
i=1
b) Écrire une fonction [a,b]=regression bpos(x,y) qui implémente cet algorithme.
c) Donner un exemple numérique quand n = 3 pour lequel la contrainte b ≥ 0 est
saturée (on donnera les vecteurs x et y de R3 choisis, et les valeurs de a et b
retournées par l’algorithme proposé à la question précédente).
Exercice 5 (projection sur un simplexe) Dans tout l’exercice, n est un entier au moins
égal à 2 et Rn est muni de sa norme euclidienne usuelle. On considère le sous-ensemble
C de Rn défini par ( )
Xn
n
C = (xi )1≤i≤n ∈ R+ , xi = 1 .
i=1
1. Quelle interprétation classique peut-on faire des éléments de C ?
2. Décrire C sous la forme usuelle d’un sous-ensemble de Rn soumis à des contraintes
(égalité(s) et inégalité(s)), avec n + 1 contraintes au total.
3. Montrer que C est convexe.
4. Soit y = (yi )1≤i≤n un vecteur donné de Rn . Montrer qu’il existe un unique
x̄ = (x̄i )1≤i≤n ∈ C vérifiant
J(x̄) = min J(x),
x∈C
1
où J : Rn → R est définie par J(x) = kx − yk2 .
2
5. Montrer, à l’aide du théorème de Karush-Kuhn-Tucker, qu’il existe λ ∈ R et
(µ1 , µ2 , . . . µn ) ∈ Rn+ tels que
∀i ∈ {1, 2, . . . n}, µi x̄i = 0 et x̄i − yi + λ − µi = 0.
6. En déduire que
∀i ∈ {1, 2, . . . n}, x̄i = max(0, yi − λ).
2
7. On suppose dans toute la suite que y1 ≤ y2 ≤ . . . ≤ yn (on peut toujours se
ramener à ce cas par permutation des vecteurs de base). Montrer qu’il existe un
unique entier j ∈ {1, 2, . . . , n} tel que λ ∈]yj−1 , yj ], avec la convention y0 = −∞.
8. On pose !
n
1 X
∀k ∈ {1, 2, . . . , n}, λk = −1 + yi .
n−k+1 i=k
Montrer que λ = λj , où j est l’indice de la question précédente.
9. Montrer que la suite finie (λk )1≤k≤n est strictement décroissante.
10. En déduire qu’il existe un unique indice k ∈ {1, 2, . . . , n} tel que λk ∈]yk−1 , yk ],
puis que k = j.
11. Déduire de tout ce qui précède un algorithme pour calculer x̄ à partir de y.
12. Implémenter cet algorithme par une fonction x = argminJ(y) prenant en entrée
un vecteur colonne y (on supposera que y vérifie les hypothèses de la question 7)
et renvoyant la solution x̄ dans un vecteur colonne x de même taille que y.
13. Calculer à la main les λk , puis j et enfin x̄ pour y = t (−0.05, 0.1, 0.2, 0.2, 0.6).
Vérifier la solution obtenue à l’aide de la fonction proposée à la question précédente.