C. R. Acad. Sci. Paris, t. 329, SCrie I, p. 1027-1032, 1999

Analyse numCrique/Numerical Analysis

(Contr6le optimal/Optima/ Control)

Stabilit6 en optimisation convexe non diffhrentiable

Said HILOUT

L3MA-SPZMI, tClkport 2, Universiti de Poitiers, B.P. 30179,86962 Futuroscope-Chassneuil cedex, France

Courriel : hilout@13ma.univ-poitiers.fr

(Regu le 5 janvier 1999, accept6 aprk &vision le 4 octohre 1999)

RCsumC.

Abstract.

Dans cette Note, nous Ctudions la stabilitk de la solution optimale par rapport aux perturbations du paramktre d’un probkme de programmation mathkmatique convexe non diffkrentiable. Sous une nouvelle hypothkse de croissance, nous obtenons une majoration du reste du dkveloppement a l’ordre deux de la fonction valeur. Le rksultat principal est une analyse de stabilitk de type Hiilder et de type Lipschitz. 0 1999 AcadCmie des sciences&ditions scientifiques et mkdicales Elsevier SAS

Stability analysis of a nonsmooth convex mathematical

programming problem

In this Note, we study the stubility of the optimal solution of a nonsmooth convex program with respect a the parameter. Under a new growth assumption, estimate of the remainder term in the second-order expansion of the value function is established. The main results are Hiilder and Lipschitz type stability. 0 1999 AcadCmie des scienceskditions scientifiques et mkdicales Elsevier SAS

A bridged English Version

This paper consists of a study of stability in convex programming. Under a new growth condition, we obtain an estimate of the remainder term in the second-order expansion of the value function close to the origin of a parametrized nonsmooth convex program. The consequence is a H6lder and Lipschitz type dependence of the optimal solution when the cone constraints are subject to small perturbations. Let f be some convex function on X = R” and A be some linear operator from X into Y = W” and consider the nonsmooth convex mathematical programming

P(Y)

min f(z),

AXE y+K,

Note pr&entCe par Alain BENSOUSSAN.

0764~4442/99/03291027 0 1999 AcadCmie des scienceskditions scientifiques et mkdicales Elsevier SAS. 1027 Tous droits rCservCs.

S. Hilout

where the vector 7) represents the parameter and K is the cone in y defined by equalities and inequalities constraints:

K = {:,y E R”’ : y, = 0 (1 < i < 7.). y, > 0 (r+ 15 ,I 5 tn,}.

Let 1: be the value (or marginal) function of F’(v) defined by:

We assume the following: Hl : (Underestimation of the growth of degree (1 hypothesis)

3p > 0 such that ,f(.r:) > f(:~.(~) + tff(~~~.:~: - :ro) + !! 11.1. - :QII~, ‘d:r E B(.r.o.~):

H2 : (Overestimation of the growth of degree p hypithesis)

3 R > 0 such that f(:~:) < S(:I:~~) + clf(:~:~,:.r: - .I:,)) + t 11.1. - :~,,ll~~, ‘d..r, E B(.x,.E),

where tlf(:~~,h) = & +(f(:~:~+th) - f(~“)), : I’() is the optimal solution of P(0). B(:r:o. ir) is the ball

centered at :I:() with radius c, /I III1 and II . II’, are respectively the Y(p)) and O(q) norm (~1 > p > 1). AL I AT(Al~lT)-1 d enotes the pseudo-inverse of d/1, .AT being the adjoint of il.

Recently appeared some papers which have investigated the stability analysis of a mathematical programming problem under with the quadratic growth conditions. LemarCchal and Sagastizibal [ 121 have studied the remainder term in first-order development of a convex function: they have proved that the quadratic growth condition is satisfied if and only if the associate subdifferential satisfies a linear growth condition. The same authors [ 131 have used this condition in the study of the Moreau-Yosida regularization. Bonnans and Ioffe [2] have characterised the quadratic growth for a min-max convex problem with C’ functions. Janin and Gauvin [9], [IO] have obtained a Lipschitz stability result assuming a sub- and super-quadratic growth condition in a finite-dimensional space. An extension of this result in a Hilbert space for an equality constraints case and an application to the study of Mossolov’s problem are presented in [S].

1. Main results

C(f.u) = {CT E af(n:,)) ; ((T&) > (A.?/). t/x E A(:l+)}.

then, either: C(f. ;y) = GJ, in which case:

or C( ,f. y) # 63, in lvhich case:

1028

StabilitC en optimisation convexe non diffkrentiable

1. Hypothkses et notations

Dans cette etude, on se place dans le cas de dimension fink (X = R” ct Y = R”’ ). Nous consideronh le probleme de programmation mathematique perturb6 :

oB .f est une fonction convexe continue pas necessairement differentiable, A est un operateur lit&ire de S darts Y et I? designe le cone de R”’ defini par :

On fait les hypotheses suivantes sur f : HI : (Hypothese de minoration de la croissance de degre (1)

3 p > 0 tel que S(:r) 2 ,J(.I:~~) + (l./‘(:r,,.:~. - :I:,,) + c \\:I. - ,r,,l\~, V.I. E 13(.r,,.r) ;

H-12 : (Hypothese de majoration de la croissance dt!degrC 11)

3X > 0 tel que f(:r) <_ f(:r,,) + clS(.co.:r - J(,) + :i )):r - .roII~~. ‘V::r, E T3(.r,,.c),

otl (If(q): h) = iii; + (f(.r:o + Us) - f(X.,))), . 10 est une solution optitnale du probleme (1) associec i

g = 0, B(.ro. c) la boule ouverte de R” de centre .rll et de rayon c, /( ’ (1,’ ct I/ I),, sont respectivement les normes P(T)) et P(cI) par rapport a la base de R” formee de vecteurs base de Kw e/1 et dc vecteurs

base de 1n1 il:, 11 et q etant deux reels tels que (1 > 11 > 1 et A’ = ilr (I-1.A”‘) d-i le pseudo-inverse de .q.

Rmurqw 1.1. - On prend une norme B(r)) (ou B(c~)) de telle sorte qu’on ait un << theoreme de Pythagore )) : si X = Xt ~2 .Y2, oLi X1 = E(c:r A ef X2 = Irn A: et .si .I‘ = .r, + ,I’~ uwc’ x1 E S,,

.I:? E X2, alors :

L’egalite precedente n’est pas valable pour les autres decompositions de X.

Les resultats du premier ordre pour les problemes convexes et non convexes sont trait& dans [3], 141, [I I]. 181, 171, ]14], le second ordre est ttudie dans [I], 121.

1029

S. Hilout

On suppose que la condition de Mangasarian-Fromovitz (CMF) est r6alisCe en xo solution optimale du problkme (1) associCe B y = 0, i.e. : (a) Ai (1 5 % 5 r) sont 1inCairement independants ; (b) 32 E R’” tel que iliz = 0 (1 5. ?: 5 r), Aix > 0, % E I(zo), oa I(x) = (2 : T+l<%<rn,; A’x = 0} et A’ sont les vecteurs lignes de la matrice A. Sous la condition (CMF), il existe des multiplicateurs de Lagrange Kuhn-Tucker, i.e. : 3 X E K+ = {A E R’” ; XTu > 0, Vu E K} tel que :

ATX E 3f(xo), XTAzo = 0,

ou encore

(2)

On note

A(ico) = {A E R”‘, X satisfait (2)},

V(Y) = A,r&$K. f (xl:

C(f,y) = {o E af(xo), (qA$) > (X.y), V’x E @o)}.

On vCrifie que (voir [14]) :

au(o) = A(x0).

2. StabilitC de type Hiilder

Le thCor&me suivant donne une majoration du reste du dCveloppement B l’ordre deux de la fonction valeur du probEme (1) au voisinage de l’origine sow l’hypoth&e H2 et la condition de Mangasarian- Fromovitz (CMF). Cette majoration du reste fait intervenir un ensemble qui a la m&me forme que C(f, y) et le pseudo-inverse d’une sous-matrice de A.

THEORBME 2.1. - Sow l’hypothkse de majoration de la croissance de degre’ p et la condition de Mangasarian-Fromovitz (CMF), il existe 6 > 0, tel que, pour toute perturbation y vkr$iant 11;y/1/ 5 6, on ait : 1) il existe 5 E df(xo), /\ E R’“, X; > 0, i E I(:Q) et une sous-matrice AL de A, tels que :

rang AL = rang A; AEX = 27, (X, A,gO) = 0, dT/(O, ~1) = (G, A&) :

2) si l’on pose :

C(f>y) = (0 E af(xo) : (a:Aiy) > (X,y), VA E I},

l’alternative suivante est ve’ri@e : - soit C(f, y) = 0 et dans ce cas :

1030

Stabilitk en optimisation convexe non diffhentiable

- soit C(f, y) # 0 et duns ce cas :

ok p* est le conjugue’ de p et I l’ope’rateur identite de R”.

Idee de la demonstration. - La demonstration du theoreme 2.1 s’appuit sur le lemme suivant (voir [6], [lo]).

LEMME 2.1. - Sous la condition de Mangasarian-Fromovitz (CMF) et l’hypothtse de majoration de la croissance de degre’ p, il existe S > 0, tel que, pour toute perturbation y ve’riJant 11 y 11 5 S, la fonction valeur du probltme (1) satisfasse

w(y) < w(O) + max min Olaf A&y+Ko

Oli

K,={yIEwy Yi = 0 (1 i i I T), yi L 0, i E 1(x0)}.

TH~OR~ME 2.2. - Sous les hypotheses de majoration et de minoration de la croissance de degres respectifs p et q (1 < p < q) et la condition de Mangasarian-Fromovitz (CMF), il existe S > 0 tel que, pour toute perturbation y ver$ant l]~y]] 5 6, on ait : - soit C( f, y) # 0 et duns ce cas :

- soit C(f, y) = 0 et dans ce cas :

02 l]Allp = IIA4lP - ,,:,zo ll4lP .

Demonstration. - (Voir [6].)

3. StabilitC de type Lipschitz

Supposons dans cette section que les hypotheses de minoration et de majoration de la croissance Hl et H2 sont de m&me degre (4 = p). Le resultat suivant donne une stabilite de type Lipschitz de la solution optimale du probleme (1).

COROLLAIRE 3.1. - Si f satisfait les hypotheses de minoration et de majoration de la croissance Hl et H2 avec @ = q) et si la condition de Mangasarian-Fromovitz (CMF) est realise’e en x0, alors il existe S > 0 tel que, pour toute perturbation y vtri$ant ]]yll 2 6, on ait :

1031

S. Hilout

- soit C( f: y) # 0 et duns ce cm :

- soit C(f. y) = 0 et dam ce cas :

Ddmotzstration. - La dkmonstration est la m&me que celle du thCor&me 2.2 avec p = q.

RCf&ences bibliographiques

[I] Auslender A., Cominetti R., First and second order sensitivity analysis of nonlinear programs under directional constraint qualification conditions, Optimization 21 (1990) 351-363.

[2J Bonnans J.F., Ioffe A.D.. Quadratic growth and stability in convex programmin, o with multiple solutions. J. Convex

Anal. 2 (l/2) (1995) 41-57. [3] Gauvin J., Janin R., Directional behaviour of optimal solutions in nonlinear mathematical programming, Mathematics of

Operations Research 13 (I 988) 629-649. [4] Gauvin J., Janin R.. Directional Lipschitzian behaviour of optimal solutions and directional derivatives for the optimal

value function in nonlinear mathematical programming, in: Analyse non lineaire. H. Attouch et al. (Eds.). CRM et Gauthier-Villars. Paris, 1989, pp. 305-324.

[5] Hilout S., Directional Lipschitzian optimal solution of infinite-dimentional optimization problems. Appl. Math. Lett. I I (6) (1998) 123-128.

[6] Hilout S., Stabilite hiilderienne et lipschitzienne de la solution optimale d’un probleme de programmation mathematique

convexe non differentiable, These de I’UniversitC de Poitiers, 1998. [7] Hiriart-Urruty J.-B., Lemarechal C., Convex Analysis and Minimization Algorithms, Springer-Verlag, 1993 (deux volumes). [S] Janin R., Directional derivative of the marginal function in nonlinear programming, Mathematical Programming 21 (1984)

110~126. 191 Janin R.. Gauvin J., Lipschitz continuity of the optimal solution to elementary convex programs, in: Proc. Catalan days

Applied Mathematics, Presses Universitaires de Perpignan, M. Sofonea, J.N. Corvellec (Eds.), 1995. pp. 149-161.

IlO] Janin R., Gauvin J., Lipachitr stability in nonsmooth convex programs, SIAM J. Optim. (B paraitre). Ill] Janin R., Mado J.C., Narayaninsamy J., Second order multipliers and marginal function in nonlinear programs,

Optimization 22 (1991) 163-176. I 121 Lemarechal C., Sagastizabal C., More than first-order developments of convex functions: Prima-Dual Relations, J. Convex

Anal. 3 (2) (1996) 81-110.

[ I31 Lemarechal C., Sagastizabal C., Pratical aspects of the Moreau-Yosida regularization: Theoretical preliminaries, SIAM J. Optimi. 7 (2) (1997) X67-385.

1141 Rockafellar R.T., Convex Analysis, Princeton University Press, 1970.

1032