Open Journal of Optimization, 2013, 2, 109115 Published Online December 2013 (http://www.scirp.org/journal/ojop) http://dx.doi.org/10.4236/ojop.2013.24014 Open Access OJOp On the Second Order Optimality Conditions for Optimization Problems with Inequality Constraints Mourad Naffouti Department of Mathematics, Faculty of Science, Mathematics, Physics and Natural of Tunis, Tunis, Tunisia Email: mouradnaffouti@gmail.com Received August 28, 2013; revised October 2, 2013; accepted October 27, 2013 Copyright © 2013 Mourad Naffouti. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. ABSTRACT A nonlinear optimization problem (P) with inequ ality constraints can be converted into a new optimization problem (PE) with equality constraints only. This is a Valentine method for finite dimensional optimization. We review second order optimality conditions for (PE) in connection with those of (P). A strictly complementary slackness condition can be made to get the property that sufficient optimality conditions for (P) imply the same property for (PE). We give some new results (see Theorems 3.1, 3.2 and 3.3) .Without any assumption, a counterexample is given to show that these con ditions are not equivalent. Keywords: Optimality Conditions; Constraint Qualifications; Copositivity 1. Introduction Consider the following optimization problem min such th at 0,1,, i fx P xiI m x where n is open and ,i fg are 2 C functions. Results on second order optimality conditions can be found in [13]. Converting inequality constraints into equality con straints, we get the following problem: 2 min such that 0,1, , , ii m fx PE xy iIm xy This method is known to be a Valentine meth od [46]. In the literature, second order optimality conditions for Valentine method are not studied. Second order optimality conditions for (P) are related to copositivity and are NPhard [7]. Second order opti mality conditions for (PE) are related to the definiteness of a matrix in a vector subspace and there are efficient algorithms [8]. A strictly complementary slackness con dition must be made to get the property that sufficient optimality conditions for (P) imply the same property for (PE). Recall that the classical KarushKuhnTucker first and second order optimality conditions for a local minimizer * for (P), stated under the linear independence con straint qualification (LICQ), can be written as follows: There exists a unique Lagrange multiplier* such that the Lagrangian function: 1 ,m ii i Lxf xgx Satisfies ** ** 1** ,0 0, 0 0, 1, , ii ii Lx gx CN gx iI m And 2** * 2,0, Txx CNhL xhhCx where * Cx is the critical cone: if
M. NAFFOUTI Open Access OJOp 110 ** /0 i Ixig x Then *** * ***** /0, 0, ()/0, 0, i iii Cxhfxhg xhiIx CxhgxhgxhiIx The sufficient second order optimality condition for a feasible point is: there exists a Lagrange multiplier such that 2* 2,0, , 0 Txx CShL xhhC xh The fact that * or is the same for all critical vectors is very restrictive and, without (LICQ) or con vexity assumptions, very difficult to get [9,10]. Recently, many authors have weakened the constraint qualification (LICQ) and 2 CN are obtained [911]. In Daldoul Baccari [12], a numerical method is given in order to test the constant rank condition of Martinez et al. [11]. An other difficulty is that there is no efficient algorithm to test the conditions: 2 CN or 2.CS Note that if *0 for all * iIx then * Cx is a vector subspace and efficient algorithms for 2 CN exist ([8]). In this paper, we are interested by the use of efficient algorithms to test 2 CN or 2.CS A first step is the conversion of (P) into (PE). Our main result is the following theorem. It is stated without any constraint qualification (linear independence, MangasarianFromovitz or convexity assumptions). Theorem 1.1. Let * and ** , y be feasible points for (P) and (PE) respectively where ** i ygx , then: 1) * is a minimizer for (P) if and only if ** , y is a minimizer for (PE). 2) If a generalized Lagrange multiplier 0,m satisfies the necessary second order optimality conditions for (P) at * , then 0, is a generalized Lagrange multiplier fo r (PE) and satisfies the necessary second order optimality conditions at ** , y 3) A generalized Lagrange multiplier 0,m for (PE) satisfies sufficient second order optimality co nditions at ** , y if and only if the following conditions hold: a) 0, is a generalized Lagrange multiplier for (P) b) 0 i if *0 i gx c) 0, satisfies sufficient second order optimality conditions for (P) at* Note that 1) The minimizers * and ** , y cited in the first item of Theorem 1.1 could be local or global. 2) The strict complementary slackness condition 0 i if *0 i gx is crucial in 3) and can be seen by the following simple counterexample: 2 min /0xx 3) Existence of Lagrange multiplier in the second and third item of the theorem is not guaranteed [9]. We begin with some notations : The (generalized) Lagrangian function of (P) is defined on nm by 00 1 ,, m ii i fx gx The (generalized) Lagrangian function 00 ,, ,xy of (PE) is defined on nm m by 2 000 1 ,, ,m ii i i yfxgxy The Lagrangian function L of (P) is ,,1,Lx x The Lagrangian function 0 L of (PE) is 00 ,, ,,1,Lxy xy The gradient of f with respect to x is the column vector ,T xfx is its transpose and the gra dient of with respect to is the column vector 00 1 ,, xix m xi i fx gx The Hessian matrix of with respect to is 22 00 1 2 ,, m ii i xxxxxx fx gx The set of feasible points of (P) is /0, i gx iI The set of feasible points of (PE) is 2 0,/0, mii ygxyiI The critical cone at x is d/d0, 0, , TT ni xfxxgxh CPx iIx where /0 i Ixigx The critical cone at 0 ,xy is the subspace
M. NAFFOUTI Open Access OJOp 111 dd,d/ d2d0, ,, T iii Xxygxxyy CPExy iIx For 0 ,, m Pxx is the set of gener alized Lagrange multipliers of (P) at . 00 ,,Px if and only if 0 0,0 0, 0 ,,0 , x i ii iI I x i The set of regular Lagrange multipliers of (P) at a feasible point is 00 0 ,/1,,, m Px Px For 0 ,, m xy , is the set of generalized Lagrange multipliers of (PE) at ,. y 00 ,,,PE x y if and only if 0 0 0 ,0 ,, ,0 xxy The set of regular Lagrange multipliers of (PE) at , y is 00 0 ,,/ 1, ,,, m PExy PExy The set of normalized Lagrange multipliers of (P) at *0 x is ** 1000 1 ,,,/ 1 m i i Px Px The set of normalized Lagrange multipliers of (PE) at ***0 ,Xxy is ** ** 1000 1 ,,,,, /1 m i i PE xyPE xy x satisfies the strictly complementary slackness condition if the following condition holds. 00 ,,, 0,/0 ii SCSPi gxx Necessary first and second order optimality condi tions for (P) can be written in the following form ([13], Theorem 9.3). Theorem 1.2. If * is a local minimizer for (P) then: 0,Px (1.1) * 0 *0 2 0 d,, ,, /d, ,d0. Txx CPx Px xxx (1.2) The necessary second order optimality conditions (1.2) can be written as * 01 *0 2 ,, * ,, d0.max d d,. Txx Px xx xCPx x (1.3) In the same way, for a local minimizer *** , xy of (PE), we have * 0,PEX (1.4) * 01 *0 2 ,, * max d . , , ,d 0. d Txx PE XXX XCPE X X (1.5) For * x the generalized sufficient second order optimality conditions, * 2,GSCP x, for (P) are that * 0,Px. Or * 1,Px are not empty and, for every * d,, d0,xCPx x one has * 01 2 ,, *0 maxd, ,d0. Txx Px xx x (1.6) For 0 * X, the generalized sufficient second order optimality conditions, * 2,GSCPE X for (PE) are that * 0,PEX or * 1,PEX are not empty and, for every * d,,d0,XCPEXX one has * 01 2* ,, 0 ,,md0.axd Txx PE XXXX (1.7) The classical sufficient second order optimality con dition for (P), at * x , is that there exists ** ,Px such that *2** ,d0,dd,, d 0 Txx xL xxCPxxx (1.8) In the same way, the classical sufficient second order optimality condition for (PE), at 0 * X, is that there exists ** ,PE X such that *2** ,d 0,dd,, d 0 Txx XL xCPEXXXX (1.9) In [14,15], the existence of such multipliers is studied. We say that * 0,,Px satisfies the suffi cient second order optimality co nditions for (P) if *2* 0 ,, d0dd,0 d,, Txx xxCPxxxx (1.10) In the same way, * 0,,PE X satisfies the sufficient second order optimality conditions for (PE) if * 0*2 0 ,, d0dd,0 d,, Txx XXCPEXXX X (1.11) 2. Some Properties of (PE) and (P) Let * be a local minimizer for (P) and * the cor responding minimizer for (PE). It is easy to see that
M. NAFFOUTI Open Access OJOp 112 ** 00 ,,PxPEX (2.1) The following properties are easy to check: If * dd,d, xy CPEX and ** ** 0,/0, 0, TT CPxd fx dgx diIx (2.2) Then ** 0 d, , CPx CPx (2.3) And ** 0,,WSCSCP xCPx (2.4) If * 0 d, CPX then there exists dy such that * dd,d, xy CPEX (2.5) If x satisfies the linear independence constraint qualification (LICQ), so is 0 ,Xxy It is easy to see that ** 00 ,,0, i PE XiIx (2.6) 3. Optimality under Regularity We begin with the regular case and extend the result of ([16], Proposition 1.32). Theorem.3.1. Let * be a feasible point for (P), satis fies (LICQ) and (SCS), then the classical sufficient sec ond order optimality condition (1.8) holds if and only if the classical sufficient second order optimality condition (1.9) holds. Proof. * satisfies (LICQ) and * ,Px is a sin gleton * ,Px . Also * ,PE X and, from (SCS), we have ** 0, iiIx The first part of the theorem is the Proposition 1.32 of [16]. To prove the “only if”, Let * d, CPx and d0x. Put d0 i y if * iIx and * * d d2 T i i i xx yy If * iIx. We have * dd,d, xy CPEX and d0X. From * 0, iiIx , we get 22 0** ** ,d ,d0d.dTT xx xx XXXL xL x In the above theorem, (LICQ) is not necessary and one can prove the following theorem (see [16], Proposition 1.31). Theorem.3.2. Let ** * 00 ,,PX such that ** 0, iiIx Then ** 0, satisfies the sufficient second order optimality conditions for (P) if and only if it satisfies the sufficient second order optimality conditions for (PE) hold. The main result of this section is the following theo rem (compare with [16], Proposition 1.32). Theorem.3.3. Let * be a feasible point for (P) and such that 1) There exists a multiplier ** * 00 ,,PX such that ** 0, iiIx 2) The sufficient second order optimality condition * 2,GSCP x hold Then *** , xy satisfies the sufficient second or der optimality conditions * 2,GSCPE X. Proof. Let * dd,d,, d0.XxyCPEXX We know that * d, CPx and we have two cases: 1) d0.x This means that d0y, d0 i y for all * iIx and * 2 *** 0 2* 0,,d2d0dii iI Tx x xXXXy 2) 0.dx From * 2,,GSCP x there exists * 01 ,,Px such that *2 0 ,d,d0 Txx xxx And * * 00 2 * 2 2* 0 d,,d ,d2 d 0 d, Txx ii ix Tx I x X x XX xy 4. A Counterexample The following counterexample shows that * 2,,GSCPE X do not imply * 2,,GSCP x Example 4.1. 2 min such that ,0, 1,,6 ,, i z Pgxy iziI xyz where 2 1,232 xyxy y 2 2,232 xyxy y 22 3,3 xy yx
M. NAFFOUTI Open Access OJOp 113 2 4,232 xyxyx 2 5,232 xyxyx 22 6,3 xy xy We list some properties of (P): 1) 2 12 3 ,,4, xy gxyyg xy and 2 45 6 ,,4, xy gxyxgxy 2) * , 0,0,000,0, xzz is a minimizer for (P) 3) *3 ,,,/00,0,0CPxd xyzz 4) * ,0,0,0Px and * 2,,GSCP x do not hold. Consider the associated (PE) pro blem : 2 2 min such that ,0, 1,,6 ,,, ii i z PE gxyizuiI xyzu Its generalized Lagrangian function is, with ,,, , xyzu 2 0 6 2 00 1 ,,, . ii i i zgxyizu ** ,0Xx is a minimizer for (PE) and we get 6 *01 0,,00. i i Xi 6 * 000 1 ,,0/0, 0 i i PE Xi *9 ,,,,/0CPEXd xyzuz * *0 22 12 22 2 2 34 2 0 2 56 , ,, 22322 232 232232 2 2322232 Txx dCPEX Xd yy xyy yx xyx xy x Qd d yy We can prove Lemma 4.2. For every * ,, ,,,0dCPEXdxyzu, there exists a multiplier * 00 ,,PE X such that * 00 2,, 0 Txx XdQd d Proof. It is easy to see that 6 *2 0 201 * ,,, . , 2 Txxi ii i dCP gyu E dx X We prove, first, that 2 1,0, 0. i gxy uid This is true if 0x or 0y. Suppose that 0x and 0y and 2 1,0, 1,,6 i gxy ui We get 1,0, 1,,6gxy i and, from 1), we obtain 0, 0, 1,,6 i xy ui and this contradicts 0x and 0y. So 0, 0, 1,,6 i xy ui We conclude that we have two cases: 1) 2 ,0, 1,,6 ii i agxyui we have two cases i) There exists ij such that ij aaa . put 0 ,,0,,,1 ij k ji kij we get 0 ij ij This means that * 00 ,,PE X And 202 iij j Qdaaa ji ii) ,. ij aaji We have two cases a) There exists ij such that 0 ij ji We can choose so that 0 ij ij and for 01, 0,, kkij , we get * 00 ,,PE X and 2 20 2iijjjij jij j Qdaaa a i ja ia i b) 0, , ij ja iaij we get 11 2 3 , i aiaa aa and 12 3 1; 1 satisfy 123 230. For 01, 0,, kkij , we get * 00 ,, EX and satisfy 112 233123 22203Qdaaaa aa 2) There exists i such that a 0 i a and j such that 0 j a, it is easy to find 0 i and 0 j , such that
M. NAFFOUTI Open Access OJOp 114 0 ij ij For 01,0,, kkij , we get * 00 ,,PE X And satisfies 20. iij j Qda a 5. Proof of Theorem 1.1. 1) Suppose * is a local minimizer for (P). There ex ists an open ball *,Bx r such that ** ,,()0, i BxrgxiIf xfx Let ** , y be the corresponding feasible point for (PE), that is * ii gx . *,m VBxr is open and ** , yV. We get 2 * * ,, 0, ,, 0, . ii i yVgxy iI Bx rgxiI fx fx Now, suppose that ** , y is local minimizer for (PE), there exists 12 0, 0rr such that ** 2 12 * ,,,,0, ii yBxrByrgxy iI fx fx 2) We know that 0 i if *0. i gx Suppose that * 1iIx and let d0,,1 i yiIi and d0.x For all ** 1 d,dd,d,,yXxyCPExy and 2 * 0 2011 0d,, d2d Txx yXX X . We get that 10 and this is true for any i 3) Suppose th at 0, satisfies the sufficient second order optimality conditions for (PE). This means that for all ** 0dd,d, ,,XxyCPExy we have * 2 2 * 00 2 *0 ,, d ,, d2 0 d dd ii i Tx x Txx I xXX x X x y Suppose that * 1iIx and let d0,,1 i yiIi and d0.x For all ** 1 d,dd,d ,,yXxyCPExy and 2 * 00 11 2 0d,, d2d. Txx XXyX We get that 10 and this is true for any * ,. iiIx 6. Concluding Remarks In the regular case and in the presence of strictly com plementary slackness (SCS), we have shown that an op timization problem (P), with inequality constraints, can be converted into an optimization problem (PE) with equality constraints in such a way that sufficient second order optimality conditions are preserved. Without any regularity assumption, we have shown that sufficient second order op timality conditio ns hold for (PE) if these hold for (P) and if (SCS) holds. REFERENCES [1] F. Jhon, “Extremum Problems with Inequalities as Side Conditions, Studies and Essays, Courant Anniversary Vol ume,” WileyInterscience, Hoboken, 1948. [2] E. S. Levitin, A. A. Milyutin and N. P. Osmolovskii, “Conditions of High Order for a Local Minimum in Prob lems with Constraints,” Russian Mathematical Surveys, Vol. 33, No. 6, 1978, pp. 97168. [3] A. Ioffe, “Necessary and Sufficient Conditions for a Lo cal Minimum. 3: Second Order Conditions and Aug mented Duality,” SIAM Journal of Control and Optimi zation, Vol. 17, No. 2, 1979, pp. 266288. [4] F. A. Valentine, “The Problem of Lagrange with Differ entiable Inequalities as Side Consrtaints, Contribution to the Calculus of Variation 19331937,” University of Chi cago Press, Chicago, 1937, pp. 407448. [5] J. B. HiriartUrruty, “Optimisation et Analyse Convexe, Exercices Corrigées,” EDP Sciences, 2009. [6] L. D. Berkovitz, “Variational Methods of Control and Pro gramming,” Journal of Mathematical Analysis and Ap plications, Vol. 3, No. 1, 1961, pp. 145169. http://dx.doi.org/10.1016/0022247X(61)900130 [7] K. G. Murty and S. N. Kabadi, “Some NPComplete Pro blems in Quadratic and Nonlinear Programming,” Mathe matical Programming, Vol. 39, No. 2, 1987, pp. 117129. http://dx.doi.org/10.1007/BF02592948 [8] Y. Chabrillac and J. P. Crouzeix, “Definiteness and Semi definiteness of Quadratic Forms Revisited,” Linear Alge bra and Its Applications, Vol. 63, No. 1, 1984, pp. 283 292. http://dx.doi.org/10.1016/00243795(84)901502 [9] A. Baccari, “On the Classical Necessary SecondOrder Op timality Conditions,” Journal of Optimization Theory and Applications, Vol. 123, No. 1, 2004, pp. 213221. http://dx.doi.org/10.1023/B:JOTA.0000043998.04008.e6 [10] A. Baccari and A. Trad, “On the Classical Necessary Se condOrder Optimality Conditions in The Presence of Equality and Inequality Constraints,” SIAM. Journal of Optimization, Vol. 15, No. 2, 2004, pp. 394408. http://dx.doi.org/10.1137/S105262340342122X [11] R. Andreani, J. M. Martinez and M. L. Schuverdt, “On SecondOrder Optimality Conditions for Nonliear Pro gramming,” Optimization, Vol. 56, No. 56, 2007, pp. 529542. [12] M. Daldoul and A. Baccari, “An Application of Matrix Computations to Classical SecondOrder Optimality Con
M. NAFFOUTI Open Access OJOp 115 ditions,” Optimization Letters, Vol. 3, No. 4, 2009, pp. 547557. http://dx.doi.org/10.1007/s1159000901349 [13] A. BenTal and J. Zowe, “A Unified Theory of First and Second Order Conditions for Extremum Problems in Topological Vector Spaces,” Mathematical Programming Study, Vol. 19, 1982, pp. 3976. http://dx.doi.org/10.1007/BFb0120982 [14] J. F. Bonnans and A. Shapiro, “Perturbation Analysis of Optimization Problems,” Springer, Berlin, 2000. [15] O. L. Mangasarian and S. Fromovitz, “The Fritz John Necessary Optimality Conditions in the Presence of Equality and Inequality Constraints,” Journal of Mathe matical Analysis and Applications, Vol. 17, 1967, pp. 37 47. [16] D. P. Bertsekas, “Constrained Optimization and Lagrange Multiplier Methods,” Academic Press, Cambridge, 1982.
