Introduction à l’optimisation continue

Contrôle
(3 janvier 2017)

Exercice I
On rappelle que pour une fonction convexe f : X → R ∪ {+∞},
1
proxτ f (x) = arg min f (y) + ky − xk2 .
y 2τ
Calculer proxτ f (x) pour τ > 0, et
1. X = R, f (x) = − ln x si x > 0, +∞ si x < 0.
2. f (x) = ψ(kxk) où ψ : R → R ∪ {+∞} est une fonction convexe, paire
avec ψ(0) = 0. On montrera d’abord que f est une fonction convexe, on
calculera ensuite proxτ f en fonction de proxτ ψ .
3. f (x) = kxk3 /3.

Exercice II
On considère un espace de Hilbert X et une fonction strictement convexe, semi-
continue inférieurement (sci) ψ : X → R ∪ {+∞} telle que l’intérieur de dom ψ,
noté D, est non vide, D = dom ψ, ψ ∈ C 1 (D) ∩ C 0 (D), et ∂ψ(x) = ∅ pour
tout x 6∈ D. En d’autres termes, ∂ψ(x) est soit ∅ (si x 6∈ D), ou un singleton
{∇ψ(x)} (si x ∈ D). On suppose aussi que

lim ψ(x) = +∞.

kxk→∞

On définit la “distance de Bregman associée à ψ”, notée Dψ (x, y), pour

y ∈ D et x ∈ X, de la manière suivante:

Dψ (x, y) := ψ(x) − ψ(y) − h∇ψ(y), x − yi .

1. Montrer que Dψ (x, y) ≥ 0, et que Dψ (x, y) = 0 ⇒ y = x. Quel autre

inégalité peut-on écrire si, en outre, ψ est fortement convexe ? Pourquoi est-ce
que Dψ n’est pas une distance au sens classique ?

2. Exprimer DψP lorsque D = X, ψ(x) = kxk2 /2. Lorsque X = Rn , D =

n n
]0, +∞[ , ψ(x) = i=1 xi ln xi .

3. Soit f : X → R ∪ {+∞} une fonction convexe, propre, sci. Soit x̄ ∈ D. On

suppose qu’il existe x ∈ D tel que f (x) < +∞. Montrer qu’il existe un unique
point x̂ ∈ X tel que

f (x̂) + Dψ (x̂, x̄) ≤ f (x) + Dψ (x, x̄) ∀x ∈ X. (1)

4. Expliquer pourquoi ∂(f + ψ) = ∂f + ∂ψ. Écrire la condition d’optimalité

du premier ordre pour x̂. En déduire que x̂ ∈ D.

1
5. Montrer (à partir des conditions d’optimalité) que pour tout x ∈ X,

f (x) + Dψ (x, x̄) ≥ f (x̂) + Dψ (x̂, x̄) + Dψ (x, x̂). (2)

Un algorithme de descente de gradient “nonlinéaire”. On considère le

problème de minimisation:
min f (x) + g(x), (P )
x∈D

pour f, g convexes, sci, propres, et où f est C 1 dans D et g est “simple” au sens
suivant: on suppose qu’on sait résoudre
1
min g(x) + hp, xi + Dψ (x, y)
x τ
pour tout τ > 0, p ∈ X et y ∈ D. On suppose en outre qu’il existe L > 0 tel
que pour tout y ∈ D, x ∈ X

Df (x, y) ≤ LDψ (x, y). (3)

(Ici Df (x, y) = f (x) − f (y) − h∇f (y), x − yi.) On suppose que le problème de
minimisation a une solution. On note F (x) = f (x) + g(x).

6. Montrer que si ψ est 1-convexe (fortement convexe avec paramètre 1) et f

a un gradient L-Lipschitzien, alors (3) est vraie.

Étant donné x̄ ∈ D, τ > 0, on définit maintenant l’opérateur Tτ suivant :

x̂ = Tτ (x̄) est la solution du problème de minimisation
1
min f (x̄) + h∇f (x̄), x − x̄i + g(x) + D(x, x̄). (4)
x∈D τ

7. Expliquer pourquoi ce problème est simple à résoudre. Montrer que si τ est

assez petit, on a la règle de descente suivante: pour tout x ∈ X,
1 1
F (x) + Dψ (x, x̄) ≥ F (x̂) + Dψ (x, x̂).
τ τ

8. On définit l’algorithme suivant : on choisit x0 ∈ D, et pour tout k ≥ 0,

on pose xk+1 = Tτ xk , où τ ≤ L est fixé. Montrer que pour tout k ≥ 0,
F (xk+1 ) ≤ F (xk ). Si x∗ est un minimiseur de F dans D, montrer que
1
F (xk ) − F (x∗ ) ≤ Dψ (x∗ , x0 ).
kτ

9. On suppose que F (x) → +∞ quand kxk → +∞. Pourquoi peut-on trouver

x̃ ∈ D et une sous-suite xkl tels que xkl → x̃ quand l → ∞? Pourquoi est-ce
que x̃ est une solution de (P )?

2
Application: minimisation dans le simplexe unité. On considère le cas
où X = Rd ,
( d
)
X
Σ = x ∈ X : xi ≥ 0 ∀i = 1, . . . , d; xi = 1
i=1

est le simplexe unité et

(
0 si x ∈ Σ
g(x) =
+∞ sinon.
Pd
On choisit ψ(x) = i=1 xi ln xi et D =]0, +∞[d .

10. Exprimer Dψ (x, y) pour x ∈ Σ, y ∈ Σ ∩ D.

11. Montrer que l’algorithme décrit précédemment est implémentable : donner

les détails du calcul de chaque itération.
P Indication : introduire le multiplicateur
de Lagrange pour la contrainte i xi = 1.

Exercice III
On considère un opérateur maximal monotone A dans une espace de Hilbert
(réel) X. On considère aussi une “métrique” M , c’est-à-dire, un opérateur
continu, coercif, et symétrique :

kM xk ≤ kM kkxk ∀x ∈ X, hM x, xi ≥ δkxk2 , hM x, yi = hx, M yi

pour tout x, y ∈ X, où δ > 0.

1. Montrer que (x, y) 7→ hM x, yi =: hx, yiM définit un produit scalaire qui est
équivalent au produit scalaire h·, ·i. Montrer que pour y ∈ X, le problème
1
min kxk2M − hy, xi
x 2

a une solution unique. En déduire que M est inversible. On a noté k.kM la

norme Hilbertienne induite par le M -produit scalaire.

2. Montrer que (M −1 A) est un opérateur maximal monotone dans le M -

produit scalaire. Déduire du théorème de Minty que pour tout y ∈ X, il existe
un unique x tel que
M (x − y) + Ax 3 0.

3. On considère A, B deux opérateurs maximaux monotones et K ∈ L(X, X)

un opérateur continu, linéaire dans X. On définit dans X × X la métrique, pour
τ, σ > 0,
−K ∗
 I 
M := τ .
I
−K σ

Ici I ∈ L(X, X) est l’opérateur identité. Montrer que si τ σ < 1/kKk2 , M est
bien continue et coercive dans X × X.

3
4. En déduire que (pour de tels τ, σ) on peut définir l’algorithme suivant:
on choisit (x0 , y 0 ) ∈ X × X et on définit pour tout k ≥ 0 le nouveau point
(xk+1 , y k+1 ) de la manière suivante :

K∗
 k+1
− xk
  k+1  
Axk+1
  
x 0 x
M + + 3 0.
y k+1 − y k −K 0 y k+1 B −1 y k+1

Exprimer cette itération sous la forme d’une première formule donnant xk+1 à
partir de xk , y k , puis une seconde donnant y k+1 à partir de xk , xk+1 , y k .

5. Dans quels cas sait-on que (xk , y k ) converge ? (et en quel sens ?) Dans ce
cas, que satisfait la limite (x̄, ȳ) ? Écrire en particulier une équation pour x̄.

6. On considère maintenant un opérateur maximal monotone C et le nouveau

schéma itératif :
K∗
 k+1
− xk
  k+1  
Axk+1
    k
x 0 x Cx
M + + 3 .
y k+1 − y k −K 0 y k+1 B −1 y k+1 0

Sous quelles conditions sur τ, σ, C est-ce que cet algorithme converge, et vers
quelle limite ?