Open Journal of Optimization, 2013, 2, 109-115
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
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
g
xiI m
x








where n
 is open and ,i fg are 2 C
functions.
Results on second order optimality conditions can be
found in [1-3].
Converting inequality constraints into equality con-
straints, we get the following problem:


 
2
min
such that
0,1, ,
,
ii
m
fx
PE
g
xy iIm
xy





 



This method is known to be a Valentine meth od [4-6].
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 NP-hard [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 Karush-Kuhn-Tucker first and
second order optimality conditions for a local minimizer
*
x
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
x
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 [9-11]. 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,
Mangasarian-Fromovitz or convexity assumptions).
Theorem 1.1. Let *
x
and

**
,
x
y be feasible
points for
(P) and (PE) respectively where

**
i
ygx ,
then:
1) *
x
is a minimizer for (P) if and only if


**
,
x
y
is a minimizer for (PE).
2) If a generalized Lagrange multiplier

0,m


 satisfies the necessary second order
optimality conditions for (P) at *
x
, then

0,

 is a
generalized Lagrange multiplier fo r (PE) and satisfies the
necessary second order optimality conditions at


**
,
x
y
3) A generalized Lagrange multiplier

0,m


 for (PE) satisfies sufficient second
order optimality co nditions at


**
,
x
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*
x
Note that
1) The minimizers *
x
and

**
,
x
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
x
fx gx  




 The (generalized) Lagrangian function


00 ,, ,xy

  of (PE) is defined on
nm m


  by
  

2
000
1
,, ,m
ii i
i
x
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
f
xfx is its transpose and the gra-
dient of  with respect to
x
is the column vector
 
00 1
,, xix
m
xi
i
x
fx gx  




 The Hessian matrix of  with respect to
x
is
  
22
00 1
2
,, m
ii
i
xxxxxx
x
fx gx  




 The set of feasible points of (P) is



/0,
i
x
gx iI

 
 The set of feasible points of (PE) is




2
0,/0,
mii
x
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
.
x
 
00
,,Px   if and only if



0
0,0
0,
0
,,0
,
x
i
ii
iI
g
I
x
x
i














 The set of regular Lagrange multipliers of (P) at a
feasible point
x
is
  

00 0
,/1,,,
m
Px Px   
 For

0
,,
m
xy   , is the set of generalized
Lagrange multipliers of (PE) at

,.
x
y
 
00
,,,PE x y   if and only if


0
0
0
,0
,, ,0
xxy










 The set of regular Lagrange multipliers of (PE) at

,
x
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 *
x
is a local minimizer for (P) then:

0,Px (1.1)




*
0
*0 2
0
d,, ,,
/d, ,d0.
Txx
x
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


***
,
X
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 *
x
be a local minimizer for (P) and *
X
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,
X
xy CPEX and
 


** **
0,/0, 0,
TT
CPxd fx dgx diIx 
(2.2)
Then

**
0
d, ,
x
CPx CPx
(2.3)
And


**
0,,WSCSCP xCPx (2.4)
 If

*
0
d,
x
CPX then there exists dy such that



*
dd,d,
X
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 *
x
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. *
x
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,
x
CPx and
d0x. Put d0
i
y if


*
iIx and

*
*
d
d2
T
i
i
i
g
xx
yy


If

*
iIx. We have



*
dd,d,
X
xy CPEX
and d0X. From

*
0,
iiIx
 , we get
 
22
0** **
,d ,d0d.dTT
xx xx
XXXL xL
x
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 *
x
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


***
,
X
xy satisfies the sufficient second or-
der optimality conditions



*
2,GSCPE X.
Proof. Let



*
dd,d,, d0.XxyCPEXX

 We
know that


*
d,
x
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
x
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
g
xyxy y


2
2,232
g
xyxy y


22
3,3
g
xy yx

M. NAFFOUTI
Open Access OJOp
113

2
4,232
g
xyxyx

2
5,232
g
xyxyx

22
6,3
g
xy xy
We list some properties of (P):
1)
 
2
12 3
,,4,
g
xy gxyyg xy and
 
2
45 6
,,4,
g
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


,,, ,
X
xyzu
 

2
0
6
2
00
1
,,, .
ii i
i
X
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
x
yy xyy
yx xyx
xy x
Qd d
x
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
X
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
j

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
,,
P
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 *
x
is a local minimizer for (P). There ex-
ists an open ball

*,Bx r such that




**
,,()0,
i
x
BxrgxiIf xfx
Let

**
,
x
y be the corresponding feasible point for
(PE), that is

*
ii
y
gx .

*,m
VBxr is open
and

**
,
x
yV. We get
 






2
*
*
,, 0,
,, 0,
.
ii
i
x
yVgxy iI
x
Bx rgxiI
fx fx



Now, suppose that

**
,
x
y is local minimizer for
(PE), there exists 12 0, 0rr such that

 




** 2
12
*
,,,,0,
ii
x
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
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,” Wiley-Interscience, 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. 97-168.
[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. 266-288.
[4] F. A. Valentine, “The Problem of Lagrange with Differ-
entiable Inequalities as Side Consrtaints, Contribution to
the Calculus of Variation 1933-1937,” University of Chi-
cago Press, Chicago, 1937, pp. 407-448.
[5] J. B. Hiriart-Urruty, “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. 145-169.
http://dx.doi.org/10.1016/0022-247X(61)90013-0
[7] K. G. Murty and S. N. Kabadi, “Some NP-Complete Pro-
blems in Quadratic and Nonlinear Programming,” Mathe-
matical Programming, Vol. 39, No. 2, 1987, pp. 117-129.
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/0024-3795(84)90150-2
[9] A. Baccari, “On the Classical Necessary Second-Order Op-
timality Conditions,” Journal of Optimization Theory and
Applications, Vol. 123, No. 1, 2004, pp. 213-221.
http://dx.doi.org/10.1023/B:JOTA.0000043998.04008.e6
[10] A. Baccari and A. Trad, “On the Classical Necessary Se-
cond-Order Optimality Conditions in The Presence of
Equality and Inequality Constraints,” SIAM. Journal of
Optimization, Vol. 15, No. 2, 2004, pp. 394-408.
http://dx.doi.org/10.1137/S105262340342122X
[11] R. Andreani, J. M. Martinez and M. L. Schuverdt, “On
Second-Order Optimality Conditions for Nonliear Pro-
gramming,” Optimization, Vol. 56, No. 5-6, 2007, pp.
529-542.
[12] M. Daldoul and A. Baccari, “An Application of Matrix
Computations to Classical Second-Order Optimality Con-

M. NAFFOUTI
Open Access OJOp
115
ditions,” Optimization Letters, Vol. 3, No. 4, 2009, pp.
547-557. http://dx.doi.org/10.1007/s11590-009-0134-9
[13] A. Ben-Tal 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. 39-76.
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.