Optimality Conditions for Optimization Problems with Complementarity Constraints.
Optimization problems with complementarity constraints are closely related to optimization problems with variational inequality constraints and bilevel programming problems. In this paper, under mild constraint qualifications, we derive some necessary and sufficient optimality conditions involving the proximal coderivatives. As an illustration of applications, the result is applied to the bilevel programming problems where the lower level is a parametric linear quadratic problem.
Introduction
. The main purpose of this paper is to derive necessary and
su#cient optimality conditions for the optimization problem with complementarity
constraints (OPCC) defined as follows:
y, u)
s.t. #u, #(x, y, y, u) # 0
y, y, u) # 0, (x, y, u)
and# is a nonempty subset of R n+m+q .
(OPCC) is an optimization problem with equality and inequality constraints.
However, due to the complementarity constraint (1.1), the Karush-Kuhn-Tucker
(KKT) necessary optimality condition is rarely satisfied by (OPCC) since it can be
shown as in [9, Proposition 1.1] that there always exists a nontrivial abnormal multi-
plier. This is equivalent to saying that the usual constraint qualification conditions,
such as the Mangasarian-Fromovitz condition, will never be satisfied (see [8, Proposition
3.1]). The purpose of this paper is to derive necessary and su#cient optimality
conditions under mild constraint qualifications that are satisfied by a large class of
OPCCs.
To motivate our main results, we formulate problem (OPCC),
as the following optimization problem with a generalized equation constraint:
(GP) min f(x, y, u)
y, u) +N(u,R q
y, y, u) # 0,
where
N(u, C) := # the normal cone of C at y if
# Received by the editors May 26, 1997; accepted for publication (in revised form) May 4, 1998;
published electronically March 17, 1999. This work was supported by the Natural Sciences and
Engineering Research Council of Canada and a University of Victoria internal research grant.
http://www.siam.org/journals/siopt/9-2/32188.html
Department of Mathematics and Statistics, University of Victoria, Victoria, BC V8W 3P4,
Canada (janeye@uvic.ca).
OPTIMIZATION PROBLEMS WITH COMPLEMENTARITY CONSTRAINTS 375
is the normal cone operator in the sense of convex analysis.
y, -
u) be a solution of (OPCC),
single-valued and smooth, then the generalized equation constraint (1.2) would reduce
to an ordinary equation. Using the KKT condition, we could deduce that if a
constraint qualification is satisfied for (GP) and the problem data are smooth, then
there exist KKT multipliers # R l , # R d , # R q such that
y, - u) +#L(-x, -
y, -
y, -
y, -
(-u) #,
y, - u)# 0,
where # denotes the usual gradient, M # denotes the transpose of the matrix M , and
NC denotes the map y # N(y, C). However, u # N(u, R q
in general a set-valued
map. Naturally, we hope to replace #N R q
(-u) # by the image of some derivatives
of the set-valued map u # N(u, R q
acting on the vector #. The natural candidate
for such a derivative of set-valued maps is the Mordukhovich coderivative (see Definition
2.3) since the Mordukhovich coderivatives have a good calculus, and in the case
when the set-valued map is single-valued and smooth, the image of the Mordukhovich
coderivative acting on a vector coincides with the usual gradient operator acting on
the vector (see [6, Proposition 2.4]). Indeed, as in [7], we can show that if (-x, -
y, - u) is
an optimal solution of (OPCC) and a constraint qualification holds, then there exist
q such that
y, -
y, -
y, -
y, -
y, - u))(#),
y, - u)# 0,
where D # denotes the Mordukhovich coderivative (see Definition 2.3). Recall from [7,
Definition 2.8] that a set-valued
R q with a closed graph is said to be
pseudo-upper-Lipschitz continuous at (-z, - v) with - v #(-z) if there exist a neighborhood
U of -
z, a neighborhood V of - v, and a constant - > 0 such that
The constraint qualification for the above necessary condition involving the Mor-
dukhovich coderivative turns out to be the pseudo-upper-Lipschitz continuity of the
set-valued map
y, u)+N(u,R q
y, u)+v 3 # 0}
at (-x, -
y, - u, 0). This constraint qualification is very mild since the pseudo-upper-
Lipschitz continuity is weaker than both the upper-Lipschitz continuity and the pseudo-
Lipschitz continuity (the so-called Aubin property). However, the Mordukhovich
normal cone involved in the necessary condition may be too large sometimes. For ex-
ample, in [7, Example 4.1], both (0, 0) and (1, 1) satisfy the above necessary conditions,
but only (1, 1) is the unique optimal solution. Can one replace the Mordukhovich
normal cone involved in the necessary condition by the potentially smaller proximal
normal cone? The answer is negative in general, since the proximal coderivative as
defined in Definition 2.3 usually has only a "fuzzy" calculus. Consider the following
376 J. J. YE
optimization problem:
min -y
s.t. y -
The unique optimal solution (0, does not satisfy the KKT condition but satisfies
the necessary condition involving the Mordukhovich coderivatives. It does not satisfy
the necessary condition with the Mordukhovich normal cone replaced by the proximal
normal cone. This example shows that some extra assumptions are needed for the
necessary condition involving the proximal coderivatives to hold. In this paper such a
condition is found. Moreover, we show that the proximal normal cone involved in the
necessary condition can be represented by a system of linear and nonlinear equations,
and the necessary optimality conditions involving the proximal coderivatives turn out
to be su#cient under some convexity assumptions on the problem data.
Although the optimization problems with complementarity constraints are a class
of optimization problems with independent interest, the incentive to study (OPCC)
mainly comes from the following optimization problem with variational inequality
constraints (OPVIC), where the constraint region of the variational inequality is a
system of inequalities:
R,# is a nonempty subset of R m+n and S(x) is the solution set
of a variational inequality with parameter x; i.e.,
. The recent monograph [4] by Luo, Pang,
and Ralph has an extensive study for (OPVIC). The reader may find the references
for the various optimality conditions for (OPVIC) from [4].
(OPCC) is closely related to OPVICs and bilevel programming problems. Indeed,
if is C 1 and quasi convex in y and a certain constraint qualification condition holds
at - y for the optimization problem
min #F (-x, -
then by the KKT necessary and su#cient optimality condition, (-x, -
y) is a solution
of (OPVIC) if and only if there exists - u # R q such that (-x, -
y, - u) is a solution of the
following optimization problem:
(KS) min f(x, y)
s.t. #u, (x,
which is a special case of (OPCC).
In the case where F (x,
# R is di#erentiable and
pseudoconvex in y, (KS) is equivalent to the following bilevel programming problem
(BLPP), or so-called Stackelberg game:
(BLPP) min f(x, y)
OPTIMIZATION PROBLEMS WITH COMPLEMENTARITY CONSTRAINTS 377
where S(x) is the set of solutions of the problem (P x
We organize the paper as follows. Section 2 contains background material on
nonsmooth analysis and preliminary results. In section 3 we derive the necessary and
su#cient optimality conditions for (OPCC). As an illustration of applications, we also
apply the result to (BLPP), where the lower level is a linear quadratic programming
problem.
2. Preliminaries. This section contains some background material on non-smooth
analysis and preliminary results which will be used later. We give only concise
definitions that will be needed in the paper. For more detailed information on the
subject, our references are Clarke [1, 2], Loewen [3], and Mordukhovich [6].
First we give some concepts for various normal cones and subgradients.
Definition 2.1.
Let# be a nonempty subset of R n . Given -
z #
cl# , the closure
of
set# , the convex cone
#z
is called the proximal normal cone to
set# at point - z, and the closed cone
N(-z, := { lim
is called the limiting normal cone
to# at point -
z.
Remark 2.1. It is known that
if# is convex, then the proximal normal cone
and the limiting normal cones coincide with the normal cone in the sense of convex
analysis.
Definition 2.2. Let f : R n
R #} be lower semicontinuous and finite at
z # R n . The limiting subgradient of f at -
z is defined to be the set
N(-z,
where denotes the epigragh of f .
Remark 2.2. It is known that if f is a convex function, the limiting subgradient
coincides with the subgradient in the sense of convex analysis. For a locally Lipschitz
function f ,
#f(x), where # denotes the Clarke generalized gradient and co
denotes the convex hull. Hence the limiting subgradient is in general a smaller set
than the Clarke generalized gradient.
For set-valued maps, the definition for limiting normal cone leads to the definition
of coderivative of a set-valued map introduced by Mordukhovich (see, e.g., [6]).
Definition 2.3. Let # : R n
R q be an arbitrary set-valued map (assigning to
each z # R n a set #(z) # R q which may be empty) and (-z, - v) # cl Gr#, where Gr#
denotes the graph of #; i.e., (z, v) # Gr# if and only if v #(z). The set-valued
maps from R q into R n defined by
v), Gr#)}
are called the proximal and Mordukhovich coderivatives of # at point (-z, - v), respectively

378 J. J. YE
Proposition 2.4. Suppose B is closed, -
# B. Then
Proof. Since -
is closed, there exists a neighborhood of -
x that is not
contained in B. Therefore, from the definition of the proximal normal cone, we have
In the following proposition we show that the proximal normal cone of a union of
a finite number of sets is the intersection of the proximal cones.
Proposition 2.5.
are closed. Then
Proof. Let # N # (-x, . Then, by definition, there exists a constant M > 0 such
that
#, x - x# M #x -
#x
the above inequality implies that # m
Conversely, suppose # m
there exists
#, x -
#x
That is, there exists
#, x - x# M #x -
#x
which implies that # N #
The above decomposition formula for calculating the proximal normal cones turns
out to be very useful, since when a set can be written as a union of some convex sets,
the task of calculating the proximal normal cones is reduced to calculating the normal
cone to convex sets which are easier to calculate. The following proposition is a nice
application of the decomposition formula and will be used to calculate the proximal
normal cone to the graph of the set-valued map N R q
for general q in Proposition 2.7.
Proposition 2.6.
Proof. It is easy to see that GrNR+
We discuss the following three cases.
Case 1. -
In this case, (-x, - y)
closed, by Proposition 2.4
we have in this case
OPTIMIZATION PROBLEMS WITH COMPLEMENTARITY CONSTRAINTS 379
Case 2. -
y < 0.
In this case, (-x, - y)
closed, by Proposition 2.4
we have in this case
Case 3. -
In this case, (-x, -
. By Proposition 2.5 we have
(R - [0, #))
Now we are in a position to give an expression for the proximal normal cone to
the graph of the set-valued map N R q
for general q.
Proposition 2.7. For any (-x, - y) #GrN R q
, define
I
I 0 := I 0 (-x, -
Then
y), GrN R q
Proof. Since
we have
if and only if
GrNR+ .
Hence from the definition, it is clear that
if and only if
The rest of the proof follows from Proposition 2.6.
It turns out that we can express any element of N # ((-x, - y),GrN R q
by a system
of nonlinear equations as in the following proposition.
J. J. YE
Proposition 2.8.
if and only if there exist # R 2q
such that
Proof. By Proposition 2.7, (# N # ((-x, -
y), GrN R q
if and only if
By the definition for the index sets I 0 , I + , L in Proposition 2.7, we have
Since for any (-x, - y) # GrN R q
y # 0, for nonnegative vectors # and #, (2.1) is
equivalent to
Hence the existence of nonnegative vectors # and # satisfying (2.1)-(2.2) is equivalent
to the following condition:
Consequently, it is equivalent to
The proof of the proposition is therefore complete.
Finally, we would like to recall the following definition of a very mild constraint
qualification called "calmness," introduced by Clarke [1].
Definition 2.9. Let -
x be a local solution to the following mathematical programming
problem:
minimize f(x)
OPTIMIZATION PROBLEMS WITH COMPLEMENTARITY CONSTRAINTS 381
and C is a closed subset of R d . The above
mathematical programming problem is said to be calm at -
x provided that there exist
positive # and M such that for all (p, q) #B, for all x in -
x+#B satisfying g(x)+p #
where B is the open unit ball in the appropriate space.
It is well known that the calmness condition is a constraint qualification for the
existence of a KKT multiplier and the su#cient conditions for the calmness condition
include the linear independence condition, the Slater condition, and the Mangasarian-
Fromowitz condition. Moreover, the calmness condition is satisfied automatically in
the case where the feasible region is a polyhedron.
3. Optimality conditions for OPCC. Let (-x, -
y, -
# and g(-x, -
y, -
y, -
I
y,
y, - u) < 0},
I 0 (-x, -
y,
y,
Where there is no confusion, we simply use L, I + , I 0 instead of L(-u), I
y, -
u),
I 0 (-x, -
y, -
u), respectively. It is clear that {1, 2, . ,
y, -
y, -
u).
Let
y, u)
y, y, u) # 0
#u, #(x, y, y, u) # 0
be the feasible region of (OPCC). For any I # {1, 2, . , q}, let
F I :=
y, u)
y, y, u) # 0
y,
y, u) # 0 #i # {1, 2, . , q}\I
denote a piece of the feasible region F .
Taking the "piecewise programming" approach in the terminology of [4], as in
Corollary 2 of [5], we observe that the feasible region of the problem (OPCC) can
be rewritten as a union of all pieces I . Therefore, a local solution
y, -
u) for (OPCC) is also a local solution for each subproblem of minimizing the
objective function f over a piece which contains the point (-x, - y, -
u). Moreover, if
y, -
u) is contained in all pieces and all subproblems are convex, then it is a global
minimum for the original problem (OPCC). Hence the following proposition follows
from this observation.
Proposition 3.1. Let (-x, - y, -
u) be a local optimal solution to (OPCC). Suppose
that f , g, , L are locally Lipschitz near (-x, - y, -
and# is closed. If for any given
index set # I 0 , the problem of minimizing f over F#L is calm in the sense of
Definition 2.9 at (-x, - y, -
u), then there exist # R l , # R d , # R q , # R q such that
y, -
l
y,
d
y,
y, -
y, -
(3.
J. J. YE
y, -
Conversely, let (-x, - y, -
u) be a feasible solution for (OPCC), and for all index sets
I 0 , there exist # R l , # R d , # R q , # R q such that (3.1)-(3.3) are satisfied.
If f is either convex or pseudoconvex, g is convex, , L are a#ne,
and# is convex,
then (-x, - y, -
u) is a minimum of f over all (x, y, u) #I0 F#L. If in addition to the
above assumptions I
y, - u) is a global solution for (OPCC).
Proof. It is obvious that the feasible region of (OPCC) can be represented as
the union of pieces I . Since -
y, - u) < 0
y, -
u), and
y, u)
y, y, u) # 0
y,
y,
y, u) # 0 #i # I 0 \#
we have
y, - u) #I0 F#L
and
y, -
Hence if (-x, -
y, - u) is optimal for (OPCC), then for any given index set # I 0 , (-x, -
y, -
is also a minimum for f over F#L . Since this problem is calm, by the well-known
nonsmooth necessary optimality condition (see, e.g., [1, 2, 3]), there exist # R l ,
q such that (3.1)-(3.3) are satisfied. Conversely, suppose
that for each # I 0 there exist # R l , # R d , # R q , # R q such that (3.1)-
are satisfied and the problem is convex. By virtue of Remarks 2.1 and 2.2, the
limiting subgradients and the limiting normal cones coincide with the subgradients
and the normal cone in the sense of convex analysis, respectively. Hence, by the
standard first-order su#cient optimality conditions, (-x, -
y, -
u) is a minimum of f over
F#L for each # I 0 and hence is a minimum of f over #I0 F#L . In the case when
I and the feasible region
y, -
is a global optimal for (OPCC) in this case. The proof of the proposition is now
complete.
Remark 3.1. The necessary part of the above proposition with smooth problem
data is given by Luo, Pang, and Ralph in [4] under the so-called "basic constraint
qualification."
Note that the multipliers in Proposition 3.1 depend on the index set # through
(3.3). However, if for some pair of index sets # I 0 ) and I 0 \#, the components
of the multipliers are the same, then we would have a necessary condition
that does not depend on the index set #. In this case the necessary condition turns
out to be the necessary condition involving the proximal coderivatives as in (b) of the
following theorem.
Theorem 3.2. Suppose f, g, L, are continuously di#erentiable. Then the following
three conditions are equivalent:
OPTIMIZATION PROBLEMS WITH COMPLEMENTARITY CONSTRAINTS 383
(a) There exist # R l , # R d , # R q such that
y,
l
y, -
d
y, - u)
y,
y, -
(b) There exist # R l , # R d , # R q such that
y, -
l
y,
d
y, -
y, -
y, - u))(#),
y, -
(c) There exist # R l , # R d , # R q , # R 2q
such that (3.4) and (3.5)
are satisfied and
y, -
y, -
Let (-x, - y, -
u) be a local optimal solution to (OPCC),
that there exists an index set # I 0 such that the problem of minimizing f over F#L
and the problem of minimizing f over F (I 0 \#L are calm. Furthermore, suppose that
l
y, -
d
y, -
y,
y, -
implies that # the three equivalent conditions (a)-(c) hold.
Conversely, let (-x, -
y, - u) be a feasible solution to (OPCC),
let f be pseudoconvex, g be convex, #, L be a#ne. If one of the equivalent conditions
(a)-(c) holds, then (-x, -
y, -
u) is a minimum of f over all (x, y, u) #I0 F#L . If in
addition to the above assumptions I
y, -
u) is a global solution
for (OPCC).
Proof. By the definition of the proximal coderivatives (Definition 2.3),
y, - u))(#)
if and only if
384 J. J. YE
Hence the equivalence of condition (a) and condition (b) follows from Proposition 2.7.
The equivalence of condition (b) and condition (c) follows from Proposition 2.8.
Let (-x, - y, -
u) be a local optimal solution to (OPCC),
it is also a local optimal solution to the problem of minimizing f over F#L and
the problem of minimizing f over F (I 0 \#L . By the calmness assumption for these
two problems, there exist # i
(3.1)-(3.3), which implies that
l
y, -
d
y, - u)
y, -
y, -
By the assumption we arrive at # 1
I0 . Since by (3.3), # 1
I0 \# 0, we have
That is, condition (a) holds.
The su#cient part of the theorem follows from the su#cient part of Proposition
3.1.
As observed in [4, Proposition 4.3.5], the necessary optimality conditions (3.4)-
(3.6) happen to be the KKT condition for the relaxed problem
(RP) minf(x, y, u)
s.t. y,
y, -
u),
y, -
u),
y, y, u) # 0,
and (#) satisfies (3.4)-(3.6) if and only if it satisfies the KKT condition for the
subproblem of minimizing f over the feasible region F#L , i.e., (3.1)-(3.3) with the
smooth problem data
y, - u). Conse-
quently, if the strict Mangasarian-Fromovitz constraint qualification (SMFCQ) holds
for problem (RP) at (#) which satisfies (3.4)-(3.6), then (#) is the unique
multiplier which satisfies (3.4)-(3.6). Since the index sets # only a#ect the (# I0 , # I0 )
components of the multiplier (#), we observe that the existence of multipliers
satisfying (3.4)-(3.6) is equivalent to the existence of multipliers satisfying (3.1)-(3.3)
for all index sets # I 0 (-x, -
y, -
u) with the components (# I0 , # I0 ) having the same sign.
From the proof of Theorem 3.2, it is easy to see that the condition that no nonzero vectors
satisfy (3.9)-(3.10) is a su#cient condition for the existence of common (# I0 , # I0 )
components of the multiplier (#) for all index sets # I 0 (-x, -
y, -
u). Hence this
condition refines the su#cient condition of a unique multiplier such as the SMFCQ
for the relaxed problem proposed in [4, Proposition 4.3.5].
We now give an example which does not have a unique multiplier satisfying (3.4)-
but does satisfy the condition proposed in Theorem 3.2.
OPTIMIZATION PROBLEMS WITH COMPLEMENTARITY CONSTRAINTS 385
Example 3.1 (see [4, Example 4.3.6]). Consider the following OPCC:
s.t.
x 2 are any real numbers, are obviously solutions
to the above problem. As pointed out in [4, Example 4.3.6], SMFCQ does not hold
for this problem. However, we can verify that it satisfies our condition. Indeed, the
equation (3.9) for this problem is
which implies that
Moreover, the calmness condition is satisfied since the constraint region for each
subproblem F#L is a polyhedron due to the fact that # and g are both a#ne. Hence
by Theorem 3.2, if (-x, -
u) is a local minimum to the above problem, then there exist
# such that
which implies #
is a global optimal solution according to Theorem 3.2 and (-x, 0, 0) with
are local optimal solutions.
To illustrate the application of the result obtained, we now consider the following
bilevel programming problem (BLQP), where the lower level problem is linear
quadratic:
(BLQP) min f(x, y)
s.t. y # S(x),
where G and H are l - n and l - m matrices, respectively, a # R l , and S(x) is the
solution set of the quadratic programming problem with parameter x:
where Q # R m-m is a symmetric and positive semidefinite matrix, p # R n , q
are q - n and q -m matrices, respectively, and b # R q .
Replacing the bilevel constraint by the KKT condition for the lower level problem,
it is easy to see that (BLQP) is equivalent to the problem
(KKT) min f(x, y)
386 J. J. YE
which is an OPCC. Let (-x, - y) be an optimal solution of (BLQP) and -
u a corresponding
u,
Then
I
The feasible region of problem (KKT) is
and for any I # {1, 2, . , q},
y, u) # R
Since F#L for any index set # I 0 has linear constraints only, the problem of
minimizing f over F#L is calm. Hence the following result follows from Proposition
3.1.
Corollary 3.3. Let (-x, - y) be an optimal solution of (BLQP) and - u a corresponding
multiplier. Suppose that f is locally Lipschitz near (-x, -
y). Then for each
I 0 , there exist # R m , # R d , # R q such that
If f is either convex or pseudoconvex, then the above necessary condition is also
su#cient for a feasible solution (-x, -
y, -
u) of (KKT) to be a minimum of f over all
y, u) #I0 F#L . In particular, if f is either convex or pseudoconvex and I
{1, 2, . , q}, then the above condition is su#cient for a feasible solution (-x, - y) to be
a global optimum for (BLQP).
The following result follows from Theorem 3.2.
Corollary 3.4. Let (-x, - y) be an optimal solution of (BLQP) and - u a corresponding
multiplier. Suppose that f is C 1 and
implies # there exist # R m , # R d , # R q such that
OPTIMIZATION PROBLEMS WITH COMPLEMENTARITY CONSTRAINTS 387
Equivalently, there exist # R l , # R d , # R q such that (3.16)-(3.17) are satisfied
and
Equivalently, there exist # R l , # R d , # R q , # R 2q
such that (3.16)-(3.17)
are satisfied and
Conversely, let (-x, -
y) be any vector in R n+m satisfying the constraints G-x+H -
be pseudoconvex. If there exists -
(3.11)-(3.12) such that one of the above equivalent conditions holds, then (-x, - y, -
u) is a
minimum of f over all (x, y, u) #I0 F#L . In addition to the above assumptions,
if I
y) is a global minimum for (BLQP).

Acknowledgments

. The author would like to thank Dr. Qing Lin for a helpful
discussion of Proposition 2.8.



--R

Optimization and Nonsmooth Analysis

Optimal Control via Nonsmooth Analysis
Mathematical Programs with Equilibrium Constraints
Piecewise Sequential Quadratic Programming for Mathematical Programs with Nonlinear Complementarity Constraints
Generalized di
Necessary optimality conditions for optimization problems with variational inequality constraints
Optimality conditions for bilevel programming problems
Exact penalization and necessary optimality conditions for generalized bilevel programming problems
--TR

--CTR
Jin-Bao Jian, A Superlinearly Convergent Implicit Smooth SQP Algorithm for Mathematical Programs with Nonlinear Complementarity Constraints, Computational Optimization and Applications, v.31 n.3, p.335-361, July      2005
Houyuan Jiang , Daniel Ralph, Extension of Quasi-Newton Methods to Mathematical Programs with Complementarity Constraints, Computational Optimization and Applications, v.25 n.1-3, p.123-150
optimality conditions;optimization problems;bilevel programming problems;complementarity constraints;proximal normal cones