|
Article Excerpt
In this paper we consider the bilevel programming problem (BLPP), which is a sequence of two optimization problems where the constraint region of the upper-level problem is determined implicitly by the solution set to the lower-level problem. We extend well-known constraint qualifications for nonlinear programming problems such as the Abadie constraint qualification, the Kuhn-Tucker constraint qualification, the Zangwill constraint qualification, the Arrow-Hurwicz-Uzawa constraint qualification, and the weak reverse convex constraint qualification to BLPPs and derive a Karash-Kuhn-Tucker (KKT)-type necessary optimality condition under these constraint qualifications without assuming the lower-level problem satisfying the Mangasarian Fromovitz constraint qualification. Relationships among various constraint qualifications are also given.
Key words: necessary optimality conditions; constraint qualifications; nonsmooth analysis; value function; bilevel programming problems MSC2000 subject classification: Primary: 90C46, 90C26; secondary: 90C30, 90C31 OR~MS subject classification: Primary: programming/nonlinear; secondary: programming/nondifferentiable History: Received August 17, 2005; revised March 13, 2006.
1. Introduction. In this paper we consider the following bilevel programming problem (BLPP):
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
s.t. y [member of] S(x),
[G.sub.k](x,y)[less than or equal to]0 k [member of] K,
where S(x) denotes the set of solutions of the lower-level problem:
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
and F, [G.sub.k], f, [g.sub.i] are functions on [R.sup.n] x [R.sup.m] with finite index sets
I={1,2 ..... p}, K={1,2 .....q}.
We allow p or q to be zero to signify the case in which there are no explicit inequality constraints. In these cases, it becomes clear below that certain references to such constraints are simply to be deleted.
To simplify the exposition and to concentrate on the main ideas, we assume that all defining functions F, [G.sup.k], f, [g.sub.i] are continuously differentiable, and we do not include equality constraints. The results can be easily generalized to the case of the presence of equality constraints in a straightforward manner.
Although the bilevel programming problem was only introduced to the optimization community in the seventies of the 20th century by Bracken and McGill [7], the first formulation of a simpler case was introduced and used on market economy by Stackelberg [29] in 1934, and hence is also known as a Stackelberg game in economic game theory. Bilevel programming problems can be used to model a two-level hierarchical system where the higher level (the leader) and the lower level (the follower) must find vectors x [member of] [R.sup.n] and y [member of] [R.sup.m], respectively, to minimize their individual objective functions F(x, y) and f(x, y) subject to certain constraints. The leader is assumed to select his decision vector first and the follower after that. Under these assumptions on the order of the play, the game will proceed as follows: For any possible decision vector x [member of] [R.sup.n] chosen by the leader, the follower will react optimally by choosing his decision vector y [member of] [R.sup.m] to minimize the objective function f(x, y) subject to constraints [g.sub.i](x, y) [less than or equal to] i [member of] I. Assume also that if the solution set S(x) of the lower-level problem is not a singleton, the follower allows the leader to choose which of them is actually used. Hence, now the leader chooses his optimal decision vector x [member of] [R.sup.n] and y [member of] S(x) to minimize his objective function F(x, y) subject to the constraints [G.sub.k] (x, y) [less than or equal to] k [member of] K. The BLPP has been a hot research area over the last 20 years, and many researchers have made contributions to the area. The reader is referred to monographs Bard [4], Dempe [10], 811 and Shimizu et al. [27] for applications of bilevel programming and recent developments on the subject; and to Dempe [11] and Vincente and Calamai [28] for a bibliography review.
The classical approach to derive necessary optimality conditions for BLPP (see, e.g., Bard and Falk [5]) was to replace the lower-level problem by its Karush-Kuhn-Tucker (KKT) conditions, and the problem of constraint qualification is usually neglected. This approach, however, is only applicable to the case where the lower-level problem is convex, i.e., f(x, x), [g.sub.i](x, x) (i [member of] I) are convex functions, and a certain constraint qualification is satisfied for the lower level. Moreover, the resulting single-level problem belongs to the class of mathematical programs with equilibrium constraints, or MPECs (Luo et al. [18], Outrata et al. [21]), and it is known that the usual constraint qualifications such as the Mangasarian Fromovitz constraint qualification (MFCQ) will never hold (see Ye et al. [35, Proposition 1.1]). Recently, various optimality conditions for MPECs such as the B-stationary condition, the S-stationary condition, the M-stationary condition, and the C-stationary condition, which are weaker than the classical KKT condition and the corresponding constraint qualifications, are developed (see Pang and Fukushima [22], Scheel and Scholtes [26], Ye [30, 32] for detailed discussions).
Dempe [9] and Outrata [20] derived necessary conditions for the case where the solution set S(x) = {y(x)} is a singleton by minimizing the objective function F(x, y(x)) over all x satisfying constraints [G.sub.k](x, y(x)) [less than or equal to] k [member of] K. This approach, however, requires that the solution set S(x) is a singleton, and the map y(x) has certain differentiability properties.
In Ye and Zhu [33, 34], the following approach is taken to reformulate the BLPP. Define the value function of the lower-level problem as an extended value function V: [R.sup.n] [right arrow] [bar.R] by
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
where [bar.R] := R [union] {-[infinity]} [union] {+[infinity]} is the extended real line and inf{[empty set]} = +[infinity] by convention. Then it is obvious that the BLPP can be reformulated as the following single-level optimization problem involving the value function:
[(SP).sub.V] min F(x, y) s.t. f(x, y) - V(x) [less than or equal to] 0, [g.sub.i](x, y) [less than or equal to] i [member of] I, [G.sub.k](x, y) [less than or equal to] k [member of] K.
The above single-level problem is completely equivalent to the BLPP without any convexity assumption on the lower-level problem. However, there are two issues that need to be addressed when using this approach. First, it is well known that V(x) may not be differentiable in general, even in the case where all defining functions f, [g.sub.i] are continuously differentiable, and hence the problem [(SP).sub.V] is in general a nonsmooth problem. To use the generalized Lagrange multiplier rule of Clarke [8], V(x) is required to be Lipschitz continuous. For this to be true, the lower-level problem is assumed to satisfy the MFCQ at the optimal solution. Secondly, due to the bilevel structure, the nonsmooth MFCQ for the single-level problem [(SP).sub.V] will never be satisfied, and hence weaker constraint qualifications such as the partial calmness condition was suggested by Ye and Zhu [33, 34] as an applicable constraint qualification.
The purpose of this paper is to derive KKT conditions for general bilevel programming problems without convexity assumptions on the lower-level problem, without the assumption that the solution set of the lower-level problem S(x) is a singleton, without the assumption that the lower-level problem satisfies the MFCQ, and without the partial calmness condition. Our approach is to use a new function [psi](x, y) to replace the function f(x, y) - V(x). The resulting single-level problem may be locally equivalent to the BLPP and the function [psi](x, y) is Lipschitz near the optimal solution without any requirements on the MFCQ of the lower-level problem.
2. A new equivalent single-level problem. In order to derive KKT conditions without the...
|
