C. R. Acad. Sci. Paris, t. 333, Série I, p. 801–806, 2001Analyse numérique/Numerical Analysis(Calcul des variations/Calcul of Variations)

Algorithme de dualité pour un problèmed’optimisation non convexe : applicationà un problème de Stokes non linéaire *

Nadia RAÏSSI, Mustapha SERHANI

Laboratoire SIANO, département de mathématiques et d’informatique, faculté des sciences,Université Ibn Tofail, B.P. 133, Kénitra, MarocCourriel : n.raissi@mailcity.com; mserhani@hotmail.com

(Reçu le 7 janvier 2001, accepté après révision le 13 septembre 2001)

Résumé. Nous utilisons une méthode de dualité pour résoudre un problème d’optimisation nonconvexe. Nous construisons un algorithme convergeant vers un∂-point critique et nousétablissons le lien avec un point critique du problème primal. L’application de cette méthodeà une version non linéaire du problème de Stokes conduit à une solution faible. 2001Académie des sciences/Éditions scientifiques et médicales Elsevier SAS

Duality algorithm for a nonconvex optimization problem: application toa nonlinear Stokes problem

Abstract. We apply a duality method for solving a nonconvex optimization problem. We construct analgorithm converging to a ∂-critical point and we establish the relationship with criticalpoint of the primal problem. The application of this method to a nonlinear Stokes problemleads to a weak solution. 2001 Académie des sciences/Éditions scientifiques et médicalesElsevier SAS

Abridged English version

In this work, we study a method of duality for finding critical points, that are solutions of Euler equationof a nonconvex optimization problem in which the cost is a difference of two convex functions defined ona Hilbert spaces. The formulation of this type of problems is given as

(P) a0 = infx∈X

F1(x) −F2(Λx),

whereX andY are two real Hilbert spaces,F1 : X → R ∪ +∞ is convex, l.s.c.,F2 : Y → R is convex,continuous andΛ : X → Y is linear compact.

We construct a dual problem of (P) given by (Q)

inf(x,z)∈X×Y ∗

L(x, z),

Note présentée par Roland GLOWINSKI.

S0764-4442(01)02130-9/FLA 2001 Académie des sciences/Éditions scientifiques et médicales Elsevier SAS. Tous droits réservés 801

N. Raïssi, M. Serhani

where the LagrangianL(x, z) := F1(x) +F ∗2 (z)− 〈Λx, z〉, for all (x, z) ∈X × Y ∗.

Under the assumptions cited below we construct a nonsmooth algorithm (see algorithm) converging toa∂-critical point of the dual problem (Q), that is,(x, z) ∈X × Y ∗ satisfying

Λ∗z ∈ ∂F1(x),Λx ∈ ∂F ∗

2 (z).

The convergence theorem is the following:

THEOREM 1. – Assume that the hypotheses H1–H3 and H4 or H′4 are satisfied (see below). Let

(Γk)k := (xk, zk)k ⊂ X × Y ∗ be the sequence generated by the algorithm . Then one of the followingassertions holds:(i) (Γk)k is a finite set and its last element is a ∂-critical point of the problem (Q); or(ii) (Γk)k is an infinite and bounded sequence, has at least one weak cluster point in X × Y ∗ and every

weak cluster point of (Γk)k is a ∂-critical point of the problem (Q).

We also establish a relationship between this∂-critical point of the dual problem (Q) and a criticalpoint of the primal problem (P) under an additional hypothesis which is the Gâteaux differentiability of thefunctionF2.

THEOREM 2. – Assume that H1–H3 are satisfied and that F2 is Gâteaux differentiable. Let (x, z) ∈X × Y ∗ be a ∂-critical point of the problem (Q). If ∂p(−F2 Λ)(x) = ∅, then x is a critical point of (P).

Applying this duality to the following nonlinear Stokes problem

(S)

−∆u+ gradp = f(x,u(x)),Divu = 0 in Ω,

u = 0 on ∂Ω,

whereΩ is bounded open subset ofRn and∂Ω it’s boundary leads to a weak solution.

1. Problèmes primal et dual

Le problème traité dans cette Note est le suivant : soientX , Y deux espaces de Hilbert.

(P) a0 = infx∈X

F (x),

oùF (x) = F1(x)− F2(Λx). Par la suite, nous ferons réference au problème (P) comme problème primal.

Hypothèses de base :H1 F1 : X → R∪ +∞ est convexe, semi-continue inférieurement (s.c.i.), et il existeγ1 > 0, c1 > 0 et

d1 tels que

F1(x) c1‖x‖γ1 + d1; (1)

H2 F2 : Y → R est convexe, continue, et il existeγ2 0, c2 0, d2 etd3 tels que

d3 F2(y) c2‖y‖γ2 + d2 ; (2)

H3 Λ : X → Y opérateur linéaire compact.Sous les hypothèses H1–H3, Auchmuty a démontré que, pour un choix adéquat des constantesc1, c2, γ1

etγ2, le problème (P) admet une solution (cf. [2]).

802

Algorithme de dualité pour un problème non convexe

1.1. Problème dual

Le problème (P) est non convexe, notre but est d’utiliser la dualité non convexe pour trouver les pointscritiques de (P). Pour cela nous introduisons un Lagrangien particulier (cf. [2]), qui nous permettra deconstruire le problème dual de (P) :

L(x, z) = F1(x) + F ∗2 (z)− 〈Λx, z〉, ∀(x, z) ∈X × Y ∗,

oùF ∗2 est la conjuguée de Fenchel deF2. Le problème dual est :

(Q) inf(x,z)∈X×Y ∗

L(x, z).

Dans [2], la relation de dualité suivante est établie :

inf (P)= inf (Q). (3)

Remarque 1. – 1. Il est clair que le LagrangienL est convexe et semi-continu inférieurement par rapportà chaque variable séparément.

2. Dans [2] il est démontré queL(x, z) a0, pour tout(x, z) ∈X × Y ∗.

2. Lien entre les problèmes primal et dual

La relation (3) donne seulement le lien entre les valeurs minimales des problèmes primal (P) et dual (Q).Un des résultats originaux de ce travail consiste à établir un lien entre les points critiques de (P) et les∂-points critiques de (Q) définies ci-dessous.

DÉFINITION 1. – On dit que(x,z) ∈X × Y ∗ est un∂-point critique de (Q) siΛ∗z ∈ ∂pF1(x),Λx ∈ ∂pF

∗2 (z),

où∂pf désigne le sous-différentiel proximal (qui coïncide dans ce cas avec le sous-différentiel au sens del’analyse convexe carF1 etF ∗

2 sont convexes).

L’étude des∂-points critiques de (Q) serait pertinente si un lien avec les points critiques du problème (P)(c’est-à-direx ∈ X , tel que0 ∈ ∂pF (x)) est établi. Ce lien est obtenu en utilisant les outils de l’analyseproximale (cf. [3]).

THÉORÈME 1. – On suppose outre H1–H3 que F2 est Gâteaux différentiable et que ∂p(F2 Λ)(x) = ∅.Si (x,z) ∈X × Y ∗ est un ∂-point critique de (Q). Alors x est un point critique de (P).

La preuve est donnée dans [5] et est basée sur la règle de calcul, relative au sous-différentiel proximal,suivante :

∂pF1(x) + ∂p(−F2 Λ)(x) ⊂ ∂pF (x).

3. Algorithme

Sous les hypothèses de base H1–H3, nous construisons un algorithme générant deux suites(xk)k et(zk)k

qui convergent vers un∂-point critique de (Q). Notons d’abord que sous l’hypothèse H1 la multifonction∂pF1 est semi-continue supérieurement (s.c.s.) (cf. [1]), c’est-à-dire, pourx ∈ int(domF1), pour chaqueε > 0, il existeη1(x, ε) > 0 tel que, pour toutx′ ∈ x+η1(x, ε)BX nous avons∂pF1(x′) ⊂ ∂pF1(x)+εBX .De même∂pF

∗2 est s.c.s. compte tenu de l’hypothèse H2, ainsi, pourz ∈ int(domF ∗

2 ), pour chaqueε > 0,il existeη2(z, ε) > 0 tel que, pour toutz′ ∈ z + η2(z, ε)BY ∗ nous avons∂pF

∗2 (z′) ⊂ ∂pF

∗2 (z) + εBY .

Fixons (x0, z0) ∈ int(domF1) × int(domF ∗2 ). Nous pouvons choisir la restriction deη1(·, ε) sur

l’ensembleK1 := x∈ int(domF1) : il existez ∈ int(domF ∗2 ) telle queL(x, z) L(x0, z0) comme une

803

N. Raïssi, M. Serhani

fonction ηK1(ε) croissante, indépendamment dex et telle queηK1(ε) ε, et la restriction deη2(·, ε) surK2 := z ∈ int(domF ∗

2 ) : il existex ∈ int(domF1) telle queL(x, z) L(x0, z0) comme une fonctionηK2(ε) croissante, indépendante dez et telle queηK2(ε) ε.

3.1. Algorithme Soient(x0, z0) ∈ int(domF1) × int(domF ∗

2 ) donnée, K1 etK2 définis ci-dessus etR0, R0 les rayonsdes boules de centresx0 et z0 contenues dansdomF1 etdomF ∗

2 respectivement.1. (x0, z0) ∈ int(domF1)× int(domF ∗

2 ) donnée,0 < ε0 1.2. 2.1. Pourk = 0, poserr0(x0) = miny∈∂F1(x0) ‖y−Λ∗z0‖ = ‖α0 −Λ∗z0‖ oùα0 ∈ ∂F1(x0).

2.2. Pourk > 0, poser rk(xk) = ‖αk − Λ∗zk‖ où αk ∈ ∂F1(xk) et vérifiant ‖αk − αk−1‖ ε0 r

k−1(xk−1)/2.3. Sirk(xk) = 0 fairexk+1 = xk et aller à 6.4. Sinon choisirdk ∈X vecteur unitaire vérifiant−

⟨αk −Λ∗zk, d

k⟩

ε0rk(xk).

5. Poserθk := infηK1

(12ε0 · rk(xk)),Rk

fairexk+1 = xk + θkdk.

6. 6.1. Pourk = 0, poserr0(z0) = minw∈∂F∗2 (z0) ‖w−Λx1‖= ‖β0 −Λx1‖ oùβ0 ∈ ∂F ∗

2 (z0).6.2. Pourk> 0, posersk(zk) = ‖βk − Λxk+1‖ où βk ∈ ∂F ∗

2 (zk) et vérifiant ‖βk − βk−1‖ ε0 s

k−1(zk − 1)/2.7. Sisk(zk) = 0 faire zk+1 = zk et aller à 10.8. Sinon choisirqk ∈ Y ∗ vecteur unitaire vérifiant−

⟨βk −Λxk+1, q

k⟩

ε0sk(zk).

9. Poserδk := infηK2

(12ε0 · sk(zk)), Rk

faire zk+1 = zk + δkqk.

10. Sirk(xk) = sk(zk) = 0 stop.Sinon aller à 2.

Fin de l’algorithme

L’algorithme ci-dessus génère deux suites(xk)k et (zk)k, nous démontrons que la suite(xk, zk)k

converge faiblement vers un∂-point critique et que(xk)k converge faiblement vers le point critiquerecherché du problème primal (P) et que la suite(zk)k converge faiblement∗.

4. Convergence de l’algorithme

Sous l’une des deux hypothèses supplémentaires suivantes nous démontrons la convergence del’algorithme. Soientγ1, γ2, c1, c2 les coefficients définis dans (1) et (2)H4 γ1 > γ2 > 1 ;H′

4 γ1 = γ2 > 1 et‖Λ‖< (γ1c1)µ1(γ2c2)1−µ1 , oùµ1 = γ′1(γ1 + γ′

1) etγ′1 = γ1/(γ1 − 1).

THÉORÈME 2. – Sous les hypothèses H1–H3 et H4 ou H′4, si (Γk)k = (xk, zk)k ⊂X×Y ∗ est la double

suite générée par l’algorithme , Alors :(i) (Γk)k est finie et l’élément correspondant au plus grand indice est un ∂-point critique de (Q) ; ou(ii) (Γk)k est infinie bornée et admet une sous-suite qui converge faiblement vers un ∂-point critique de (Q).

Démonstration. – Nous allons donner les grandes lignes de la preuve de (ii), (cf. [5] pour unedémonstration complète). Si(Γk)k est infinie :1ère étape : nous exploitons la convexité deL par rapport à chaque variable séparément pour démontrerque les deux suitesrk(xk)k et rk(zk)k convergent vers zéro. En effet, le LagrangienL est minoré(L(x, z) a0) et la suiteL(xk, zk)k est décroissante, donc elle est convergente; en particulier,

L(xk, zk)−L(xk+1, zk+1) −→k→+∞

0.

Le résultat découle de ce fait.2ème étape : nous montrons que les deux suites(xk)k et (zk)k admettent respectivement des sous-suites

804

Algorithme de dualité pour un problème non convexe

qui convergent faiblement, l’idée de la démonstration repose sur le fait que les ensembles de niveaux sontbornés.3ème étape : le résultat de la deuxième étape entraîne que

αj −→j→+∞

Λ∗z fortement et βj −→j→+∞

Λx fortement.

Les propriétés des multifonctions convexes∂F1 et∂F1 nous permettent d’obtenirΛ∗z ∈ ∂F1(x),Λx ∈ ∂F ∗

2 (z),

c’est-à-dire(x,z) est un∂-point critique de (Q). 5. Application : problème de Stokes

Dans cette application, nous étudions un problème d’équations aux dérivées partielles, non linéaire, nonconvexe, à savoir un problème non linéaire de Stokes. Nous utilisons les résultats de la dualité obtenusdans les premières sections pour démontrer que le problème admet une solution et nous démontrons quel’algorithme converge vers une solution faible de ce problème. SoientΩ ⊂ R

n un ouvert borné et∂Ω safrontière, le problème se présente ainsi

(S)

−∆u+ gradp = f(x,u(x)),Divu = 0 dansΩ,

u = 0 sur∂Ω,

La fonctionf : Ω × Rn → R

n est telle quef(x, s) = (f1(x, s1), . . . , fn(x, sn)), où s = (s1, . . . , sn). OnposeW = v ∈ (H1

0(Ω))n; Div v = 0 ; W est un espace de Hilbert pour le produit scalaire suivant :

((v,w)

)2,Ω

=n∑

i, j=1

∫Ω

∂vj

∂xi

∂wj

∂xidx.

5.1. Formulation variationnelle

La formulation variationnelle du problème (S) s’écrit :

(V) trouveru∈W tel que :∫

Ω

n∑i, j=1

∂uj

∂xi

∂wj

∂xidx =

∫Ω

f(x,u(x)

)w(x)dx, ∀w ∈W.

Notre but est de trouver une solution du problème (V), pour cela nous allons construire un problème (S1)pour lequel les∂-points critiques du problème dual qui lui est associé sont des solutions de (V). Posons

F1(u) =12‖u‖2 pour toutu ∈W,

F2(q) =n∑

i=1

∫Ω

∫ pi(x)

0

f i(x, t)dtdx pour toutq ∈(L2(Ω)

)n,

et

Λ :(H1

0(Ω))n −→

(L2(Ω)

)n

l’injection compact ; et considérons le problème suivant :

(S1) minu∈W

F (u),

805

N. Raïssi, M. Serhani

oùF (u) = F1(u)− F2(Λu). Le problème (S1) a la forme du problème (P) étudié dans la partie théorique,il suffit maintenant, pour étudier l’existence des solutions, de vérifier les hypothèses H1–H3 et H4 ou H′

4

pour pouvoir appliquer l’algorithme de dualité au problème (S1).

5.2. Existence de solution du problème (S)

La proposition suivante assure que les hypothèses H1–H3 et H4 ou H′4 sont satisfaites.

PROPOSITION 3. – On suppose que, pour tout i = 1, . . . , n, f i est de Carathéodory ; si pour touti = 1, . . . , n, f i(x, ·) est croissante et hi(x)t f i(x, t) gi(x)t pour tout t ∈ R, où gi est telle que :

sup1in

(supx∈Ω

gi(x))

13‖Λ‖1/7

et infx∈Ω

hi(x) > 0 pour tout i = 1, . . . , n,

alors les hypothèses H1–H3 et H′4 sont satisfaites.

(Cf. [5] pour une démonstration complète.).Toutes les hypothèses sont vérifiées pour appliquer l’algorithme et le Lagrangien est donné par :

L(u, q∗) = F1(u) + F ∗2 (q∗)− 〈i · u, q∗〉, ∀(u, q∗) ∈W ×

(L2(Ω)

)n

La convergence de l’algorithme est assurée par le résultat suivant. Les détailles de la démonstration sontdonnées dans [5].

THÉORÈME 4. – Sous les hypothèses de la proposition 3, l’algorithme converge vers (u,q∗) qui estun ∂-point critique du problème dual de (S1). De plus, u est solution de la formulation variationnelle (V)et (u,p∗), où p∗ est telle que q∗ = gradp∗, est solution faible du problème de Stokes (S).

Démonstration. – La proposition 3 assure la convergence de l’algorithme vers un∂-point critique(u,q∗)du problème dual de (S1) et avec les règles de calculs nous démontrons queu est solution de la formulationvariationnelle (V) et queq∗ n’est autre que le gradient dup∗ cherché dans le problème de Stokes. Et ondémontre par suite que(u,p∗) est solution faible du problème de Stokes (S).

Remerciements. Les auteurs remercient le professeur Jonathan Borwein et son PDF Yves Lucet ainsi que lesprofesseurs Francis Clarke, Alexandre Ioffe et Zoubida Mghazli pour la lecture de ce manuscrit et leurs remarqueset commentaires fructueuses le long de ce travail.

* Ce travail a été supporté partiellement par l’action integrée (005/MA/97) liant le laboratoire SIANO à l’équipe duprofesseur Francis Clarke de l’institut Girard-Desargues de l’université Claude-Bernard de Lyon.

Références bibliographiques

[1] Aubin J.-P., Cellina A., Differential Inclusions, A Series of Comprehensive Studies in Mathematics, Springer-Verlag, 1984.

[2] Auchmuty G., Duality algorithms for nonconvex variational principles, Numer. Funct. Anal. and Optimiz. 10 (3 & 4)(1989) 211–264.

[3] Clarke F.H., Ledyaev Yu.S., Stern R.J., Wolenski P.R., Nonsmooth Analysis and Control Theory, Graduate Texts inMath., Vol. 178, Springer-Verlag, 1998.

[4] Ekeland I., Temam R., Analyse convexe et problèmes variationnels, Dunod, Gauthier-Villars, 1974.[5] Serhani M., Raïssi N., Duality approach for finding a critical points of a nonconvex optimization problem

application to a Stokes boundary problem, Preprint.

806