- Research
- Open access
- Published:
The models of bilevel programming with lower level second-order cone programs
Journal of Inequalities and Applications volume 2014, Article number: 168 (2014)
Abstract
Robust optimization is an effective method for dealing with the optimization problems under uncertainty. When there is uncertainty in the lower level optimization problem of a bilevel programming, it can be formulated by a robust optimization method as a bilevel programming problem with lower level second-order cone program (SOCBLP). In this paper, we present the mathematical models of the SOCBLP, and we give some basic concepts, such as constraint region, inducible region, and optimal solution. It is illustrated that the SOCBLP is generally a nonconvex and nondifferentiable optimization problem, whose feasible set may be not connected in some cases and the constraint region is generally not polyhedral. Finally under suitable conditions we propose the optimality conditions for several models of the SOCBLP in the optimistic case.
MSC:90C30.
1 Introduction
Bilevel programming (BLP) problems are hierarchical ones-optimization problems having a second (parametric) optimization problem as part of their constraints [1, 2]. Second-order cone programming (SOCP) problems are convex optimization problems in which a linear function is minimized over the intersection of an affine linear manifold with the Cartesian product of second-order cones [3–6]. In the development of mathematical programming, linear programming (LP) is extended to second-order cone programming (SOCP), linear complementarity problems (LCP) and nonlinear complementarity problems (NLCP) [7] are extended to second-order cone complementarity problems (SOCCP) [8], and mathematical programming with complementarity constraints (MPCC) [9] is extended to mathematical programming with second-order cone complementarity constraints (SOCMPCC) [10]. However, there have been rare works about extending BLP to bilevel programming with lower level second-order cone program (SOCBLP).
In real world, we often face uncertainty. Uncertainty makes the optimal solution of the deterministic BLP become feasible but not optimal, or infeasible. Robust optimization is an effective method for dealing with the optimization problems under uncertainty. When there is uncertainty in the lower level optimization problem of a bilevel programming [1], it can be formulated by a robust optimization method as a bilevel programming problem having second-order cone programming [2] as its lower level problem, i.e., a bilevel programming problem with lower level second-order cone programs (SOCBLP).
In spite of its significance, there have been rare works to deal with SOCBLP or related problems. In 2007, Ejiri [11] reformulates a nonlinear SOCBLP as a mathematical program with second-order cone complementarity constraints (SOCMPCC), and he proposes a smoothing method which has the global convergence property to a Clarke- (C-) stationary point of the SOCMPCC under suitable assumptions. In 2011, Yan and Fukushima [12] extend the results and the smoothing method to mathematical programming with symmetric cone complementarity constraints. Jiang [13] studies the optimality conditions for optimization problems with second-order cone equilibrium constraints, the Aubin property of the second-order cone complementarity set and the smoothing methods for solving inverse linear programming problems and inverse linear second-order cone programming problems. Wu et al. [14] study the necessary optimality conditions and the second-order sufficient conditions, and they present a smoothing method for mathematical programs governed by second-order cone constrained generalized equations. Ding et al. [15] derive explicit expressions for the strong-, Mordukhovich-, and Clarke- (S-, M- and C-) stationary conditions and give constraint qualifications under which a local solution of mathematical programs with semidefinite cone complementarity constraints is a S-, M- and C-stationary point. Zhang et al. [10] first introduce B-stationary, C-stationary, M-stationary, S-stationary point, SOCMPCC-linear independence constraint qualification, second-order cone upper level strict complementarity condition at a feasible point of a SOCMPCC problem and discuss the convergence properties of a smoothing approach for solving SOCMPCCs.
In this paper, we consider bilevel programming problems with lower level second-order cone programs (SOCBLP). For , , and , the SOCBLP problem is given by
where , , , , , , , and . Here
with is the Cartesian product of second-order cones. , is the second-order cone (SOC) of dimension defined by
where refers to the Euclidean norm. Then the interior and boundary of the SOC , , can be defined as
Thus it is easy to verify that the SOC is self-dual, that is,
Obviously, if , we have and therefore the SOCBLP problem (1) becomes the classical linear bilevel programming problem (BLP) in [1].
Remark The formulation of the SOCBLP (1) with the quotation marks is used to express the uncertainty in case of non-uniquely determined lower level optimal solutions.
In this paper, we aim to establish the mathematical models of the SOCBLP, study the characteristics of the feasible set, and we propose the optimality conditions of the SOCBLP problems in the optimistic case.
The organization of this paper is as follows. In Section 2, we review some preliminaries including the Euclidean Jordan algebra and the generalized differential calculus of Mordukhovich. We give some basic concepts and illustrate the characteristics of the SOCBLP in Section 3. The constraint qualification and optimality condition for the SOCBLP are studied in Section 4. The optimality conditions for the several models of the SOCBLP in the optimistic case are proposed in Section 5. Finally some conclusions are given in Section 6.
2 Preliminaries
First, we introduce the spectral factorization of vectors in associated with the SOC , which is an important character of Jordan algebra [16].
For any , its spectral factorization [16] is defined as
Here , are the spectral values given by
and , are the associated spectral vectors given by
with being any vector satisfying .
Lemma 2.1 [3]
Suppose that and with satisfies . Then for all , either (i) ; or (ii) ; or (iii) there exists such that .
Let be the metric projection of z onto the SOC and , for any . Then
Now, we introduce some notions of the generalized differential calculus of Mordukhovich [17].
Give a closed set and a point , we denote by the Fréchet (regular) normal cone to A at , defined by
The limiting (Mordukhovich) normal cone to A at , denoted , is defined by
where ‘lim sup’ is the Painlevé-Kuratowski outer limit of sets [18]. If A is convex, then amounts to the classic normal cone in the sense of convex analysis.
Let be a multifunction with its graph, denoted by , being closed and . The multifunction , defined by
is called limiting (Mordukhovich) coderivative of S at [17]. If S happens to be single-valued, we usually write . If S is continuously differentiable, then amounts to the adjoint Jacobian of S at .
Suppose that and satisfies either (i) ; or (ii) ; or (iii) . Then is a continuously differentiable function in a neighborhood of z, and
Moreover, we have
-
(1)
if , we have ;
-
(2)
if , we have ;
-
(3)
if , we have
For any with , the matrix-valued mapping is defined by
Then we obtain the following property of the matrix .
Lemma 2.3 For any with , the matrix is nonsingular and is singular.
Proof It is not difficult to show the results hold by direct calculations. □
3 Concepts and characteristics of feasible set
In this section, we give some basic concepts of the SOCBLP, such as constraint region, inducible region, and optimal solution. Then it is illustrated that the SOCBLP is generally a nonconvex and nondifferentiable optimization problem, whose feasible set may be not connected in some cases and the constraint region is generally not polyhedral for .
3.1 Basic concepts
Definition 3.1
-
(1)
Constraint region of the SOCBLP problem:
-
(2)
Feasible set for the follower for each fixed :
-
(3)
Projection of S onto the leader’s decision space:
-
(4)
Follower’s rational reaction set for :
where .
-
(5)
Inducible region:
For simplicity, unless specified we make the following assumptions throughout this paper.
Assumption 3.1
-
(1)
S is nonempty and compact.
-
(2)
For decisions taken by the leader, the follower has some room to respond, i.e., .
-
(3)
The feasible set (i.e., inducible region IR) of the SOCBLP is connected.
The rational reaction set defines the response, while the inducible region IR represents the set over which the leader may optimize his objective. Thus the SOCBLP problem (1) can be written as
Definition 3.2 A feasible point to the SOCBLP problem (1) is a local optimal solution provided that there exists such that
A local optimal solution is a global one, if ε can be chosen arbitrarily large.
When the lower level problem has more than one solution, the leader has no knowledge about the real choice of the follower. He will be hard to evaluate his objective function value before he is aware of the follower’s real choice. In this paper, we assume that the leader is able to influence the follower to select in each case the solution of the lower level problem which is the best one for the leader. This results in the optimistic SOCBLP problem:
where . Unless specified, we assume that , in the following analysis.
3.2 Characteristics of feasible set
It is well known that the BLP problem is usually nonconvex, nondifferentiable and its feasible set may be not connected in some cases. To detect if these are valid in SOCBLP, we discuss the characteristics of the feasible set of SOCBLP in this subsection.
Example 3.1 Consider the following SOCBLP problem with , , and :
Figure 1 illustrates the feasible set of this example. The optimal solution of the lower level problem is
with . On this set, the upper level objective function is to be minimized:
The global optimal solutions are found at the points
which are depicted by the thick line in Figure 1, with an optimal function value of 12.
From Example 3.1, even in its simple case of functions, SOCBLP is a nonconvex and nondifferentiable optimization problem. Thus, it is possible that there exist local optimal solutions or stationary solutions for SOCBLPs. Furthermore, the optimal solutions of the lower level problem may be not unique in some cases.
Example 3.2 Consider the following SOCBLP problem with , , and :
The optimal solution of the lower level problem is
with . However, only for the upper level constraint holds, and therefore the feasible set is not connected, which is depicted in Figure 2. Hence the global optimal solutions are found at
which are the points on the thick line in Figure 2, with an optimal function value of 6.
It should be noted that if the inequality is moved into the lower level problem, the feasible set of the SOCBLP is again connected, and it is equal to all the points with ,
By Example 3.2, we can see that the feasible set of the SOCBLP may be not connected especially when the upper level constraints depend on the lower level optimal solution. Furthermore, the position of constraints is not arbitrary, whose changes may affect the feasible set of the problem. Therefore, it is necessary to point out that the solutions of the SOCBLP strongly depend on the order of play.
Example 3.3 Consider the following SOCBLP problem with , , and :
Similarly to Example 3.1, the optimal solution of the lower level problem is
with . The global optimal solution of this problem is found at points
with an optimal function value is 12.
From Example 3.3, unlike linear BLP, the constraint region of the SOCBLP with is usually not polyhedral and its inducible region is not made up of a piecewise linear equality constraint comprised of supporting hyperplanes of S. In theory, the second-order cone with is a closed convex cone, but not a polyhedron, which is greatly different from the linear BLP.
Stated briefly, the SOCBLP has the following characteristics:
-
(i)
it is generally a nonconvex and nondifferentiable optimization problem;
-
(ii)
its feasible set may be not connected especially when the upper level constraints depend on the lower level optimal solution, and its constraint region is generally not polyhedral for ;
-
(iii)
its solutions strongly depend on the order of play, since the changes of the position of constraints could generally affect the feasible set of the problem.
Therefore, compared to many mathematical programming problems, it is difficult for us to study the theories and algorithms of the SOCBLP.
4 Optimality conditions
In this section, the SOCBLP problem (1) in the optimistic case is reformulated as a single level optimization problem by using the Karush-Kuhn-Tucker (KKT) conditions for the lower level problem. And the necessary optimality conditions for problem (1) are given under the strict complementarity and linear independence constraint qualification assumptions.
For any fixed , the Lagrange function of the lower level problem in (1) is defined by
and the set of the Lagrange multipliers corresponding to the point is denoted by
Definition 4.1 The generalized slater condition is satisfied at for the SOCBLP problem (1) if there exists a such that holds.
By replacing the lower level problem in (1) with its KKT conditions, we reformulate the SOCBLP problem (1) as the following mathematical programming problem with second-order cone complementarity constraints and linear complementarity constraints:
Remark Problem (4) is more complicated than usual mathematical programs with second-order cone complementarity constraints (SOCMPCC). In usual SOCMPCC, there exist only second-order cone complementarity constraints and equality constraints in some cases. However, in problem (4) there are also inequality constraints and linear complementarity constraints.
By extending Theorem 2.1 in [21] about BLP and MPCC, we obtain the following results as regards the SOCBLP problem (1) and problem (4).
Theorem 4.1 Let be a global (resp. local) optimal solution of the SOCBLP problem (1) and assume that the generalized slater condition is satisfied at . Then, for each , the point is a global (resp. local) optimal solution of problem (4).
Proof Since if and only if , the results of the theorem obviously hold. □
Next we discuss the necessary optimality conditions for problem (4).
By Proposition 6 in [22], we obtain
and
Here stands for the Euclidean inner product, which is defined by for any two vectors x and s in . Then problem (4) is equivalent to the following optimization problem:
where , and is defined by
Theorem 4.2 [18]
Suppose that is a local optimal solution of (5). If the constraint qualification
holds, there exists such that
By Theorem 4.2, we discuss the optimality conditions for problem (1).
Suppose that is a feasible point to problem (5). Then there exists a partition of such that
By Lemma 2.1, we define three index subsets of S as
There also exists a partition of such that
We define two index subsets of S as
We are now in a position to present some assumptions.
(A1) The linear independence constraint qualification holds, i.e., the matrix is of full rank in row with , and is of full rank in column, where and , .
(A2) The componentwise strict complementarity condition holds at , i.e.,
or in other words, .
(A3) The componentwise strict complementarity condition holds at , i.e.,
or, in other words, .
Lemma 4.3 If assumptions (A1), (A2), and (A3) hold, then the constraint qualification (7) hold.
Proof Suppose that there exists , such that and , where
Then we have
Since is of full rank in row by the assumption (A1), it follows from (9) that
From assumption (A3), the second inclusion in (10) is equivalent to
i.e.,
The last relation implies that
From (11) and (12), we have
From the assumption (A2), the third inclusion in (10) is equivalent to
i.e.,
The last relation together with Lemma 2.2 implies that
Then it follows from (11) and (14) that
Since is of full rank in column by the assumption (A1), we have from (11), (13), and (15) that , and , . Then it follows from (11), (13), and (15) that . This completes the proof. □
From Theorem 4.1, Theorem 4.2, and Lemma 4.3, we obtain the following optimality conditions for the SOCBLP problem (1).
Theorem 4.4 Let be a local optimal solution of the SOCBLP problem (1) and assume that the generalized slater condition given by Definition 4.1 is satisfied at . If assumptions (A1), (A2), and (A3) hold, then for each , there exist , , , and such that
with
Proof It follows from Theorem 4.1 that is a local optimal solution of (5). Since assumptions (A1), (A2), and (A3) hold, we have from Theorem 4.2 and Lemma 4.3
Then there exists such that
The first inclusion in (18) implies
From assumption (A3), the second inclusion in (18) is equivalent to
i.e.,
The last relation implies that
From the assumption (A2), the third inclusion in (18) is equivalent to
i.e.,
The last relation together with Lemma 2.2 implies that
Therefore, combing (17), (18), (19), and the feasibility of implies equation (16) holds. This completes the proof. □
Remark Theorem 4.4 shows that under the strict complementarity conditions and linear independence constraint qualifications, a local optimal solution is a M-stationary point which is introduced for mathematical programming governed by second-order cone constrained generalized equations in [14].
5 Extensions
In this section, we consider the optimality conditions for the following three common models of the SOCBLP in the optimistic case,
where with is the Cartesian product of second-order cones in problem (22). Here problem (20) is an extension of the bilevel programming problem proposed by Dempe [2], problem (21) is the case that equality constraints always hold in problem (1), and problem (22) is closely connected with problem (1) which will be seen in Section 5.3.
5.1 Optimality conditions for problem (20)
In this subsection, we discuss the optimization conditions for problem (20) under strict complementarity and linear independence constraint qualification assumptions.
For any fixed , the Lagrange function of the lower level problem in (20) is defined by
and the set of the Lagrange multipliers corresponding to the point is denoted by
Definition 5.1 The generalized slater condition is satisfied at for the SOCBLP problem (20) if there exists a such that holds.
Theorem 5.1 Let be a global (resp. local) optimal solution of the SOCBLP problem (20) and assume that the generalized slater condition given by Definition 5.1 is satisfied at . Then, for each , the point is a global (resp. local) optimal solution of problem
It is easy to see that problem (23) is equivalent to the following optimization problem:
where and is defined by
Then similarly to Lemma 4.3 and Theorem 4.4, we obtain the optimality conditions for problem (20).
Lemma 5.2 Suppose that is a local optimal solution of (24). If assumptions (A1), (A2), and (A3) hold, then the following constraint qualification holds:
Theorem 5.3 Let be a local optimal solution of the SOCBLP problem (20) and assume that the generalized slater condition given by Definition 5.1 is satisfied at . If assumptions (A1), (A2), and (A3) hold, then for each , there exist , , , and such that
with
5.2 Optimality conditions for problem (21)
In this subsection, we reformulate problem (21) as a single level optimization problem, and then we discuss its optimization conditions under strict complementarity and linear independence constraint qualification assumptions.
For any fixed , we define the Lagrange function of the lower level problem in (21) by
and the set of the Lagrange multipliers corresponding to the point by
Definition 5.2 The generalized slater condition is satisfied at for the SOCBLP problem (21) if is of full rank in row and there exists a such that holds.
Theorem 5.4 Let be a global (resp. local) optimal solution of the SOCBLP problem (21) and assume that the generalized slater condition given by Definition 5.2 is satisfied at . Then, for each , the point is a global (resp. local) optimal solution of problem
It is not difficult to see that problem (25) is equivalent to the following optimization problem:
where and is defined by
Now we give the following assumption.
(A4) The linear independence constraint qualification holds, i.e., the matrix is of full rank in row with , and is of full rank in column, where and .
Then similarly to Lemma 4.3 and Theorem 4.4, we obtain the optimality conditions for problem (21).
Lemma 5.5 Suppose that is a local optimal solution of (26). If assumptions (A2) and (A4) hold, then the following constraint qualification holds:
Theorem 5.6 Let be a local optimal solution of the SOCBLP problem (21) and assume that the generalized slater condition given by Definition 5.2 is satisfied at . If assumptions (A2) and (A4) hold, then for each , there exist , , and such that
with
5.3 Optimality conditions for problem (22)
In this subsection, we discuss the optimization conditions for problem (22) under suitable conditions.
For any fixed , the Lagrange function of the lower level problem in (22) is defined by
and the set of the Lagrange multipliers corresponding to the point is denoted by
Definition 5.3 The generalized slater condition is satisfied at for the SOCBLP problem (22) if there exists a such that holds.
Theorem 5.7 Let be a global (resp. local) optimal solution of the SOCBLP problem (22) and assume that the generalized slater condition given by Definition 5.3 is satisfied at . Then, for each , the point is a global (resp. local) optimal solution of
Since (27) has a similar form to the form (4) of problem (1), we could study the optimality conditions for problem (22) in the similar way to problem (1).
It is easy to see that problem (27) is equivalent to the following optimization problem:
where and is defined by
Suppose that is a feasible point to problem (28). Then there exists a partition of such that
We define two index subsets of as
There also exists a partition of such that
By Lemma 2.1, we define three index subsets of as
Now we present the following assumptions.
(A5) The linear independence constraint qualification holds, i.e., the matrix is of full rank in row with , and is of full rank in column, where and .
(A6) The componentwise strict complementarity condition holds at , i.e.,
or, in other words, .
(A7) The componentwise strict complementarity condition holds at , i.e.,
or in other words, .
By using Lemma 2.3 and the proof of Lemma 4.3 and Theorem 4.4, we obtain the following optimality conditions for the SOCBLP problem (22).
Lemma 5.8 Suppose that is a local optimal solution of (28). If assumptions (A5), (A6), and (A7) hold, then the following constraint qualification holds:
Theorem 5.9 Let be a local optimal solution of the SOCBLP problem (22) and assume that the generalized slater condition given by Definition 5.3 is satisfied at . If assumptions (A5), (A6), and (A7) hold, then for each , there exist , , , and such that
with
6 Conclusions
In this paper, we discuss the models and theories of the SOCBLP. Firstly, we give some basic concepts of the SOCBLP, such as constraint region, inducible region and optimal solution. Then some examples illustrate that the SOCBLP is generally a nonconvex and nondifferentiable optimization problem, whose feasible set may be not connected in some cases and constraint region is generally not polyhedral for . Finally, the SOCBLP in the optimistic case is reformulated as a single level optimization problem by using the KKT conditions for the lower level problem. The necessary optimality conditions for several models of the SOCBLP are given under the strict complementarity and linear independence constraint qualification assumptions.
References
Bard JF: Practical Bilevel Programming. Kluwer Academic, Dordrecht; 1998.
Dempe S: Foundations of Bilevel Programming. Kluwer Academic, New York; 2002.
Alizadeh F, Goldfarb D: Second-order cone programming. Math. Program. 2003, 95: 3-51. 10.1007/s10107-002-0339-5
Tang JY, He GP, Dong L, Fang L: A new one-step smoothing Newton method for second-order cone programming. Appl. Math. 2012, 57: 311-331. 10.1007/s10492-012-0019-6
Li YM, Wang XT, Wei DY: A new class of smoothing complementarity functions over symmetric cones. Commun. Nonlinear Sci. Numer. Simul. 2010, 15: 3299-3305. 10.1016/j.cnsns.2009.12.006
Wang GQ, Bai YQ: A new full Nesterov-Todd step primal-dual path-following interior-point algorithm for symmetric optimization. J. Optim. Theory Appl. 2012, 154: 966-985. 10.1007/s10957-012-0013-x
Che HT: A smoothing and regularization predictor-corrector method for nonlinear inequalities. J. Inequal. Appl. 2012., 2012: Article ID 214
Fang L, Han C: A new one-step smoothing Newton method for the second-order cone complementarity problem. Math. Methods Appl. Sci. 2011, 34: 347-359. 10.1002/mma.1366
Liu X, Sun J: Generalized stationary points and an interior point method for mathematical programs with equilibrium constraints. Math. Program. 2004, 101: 231-261.
Zhang Y, Zhang LW, Wu J: Convergence properties of a smoothing approach for mathematical programs with second-order cone complementarity constraints. Set-Valued Anal. 2011, 19: 609-646. 10.1007/s11228-011-0190-z
Ejiri, T: A smoothing method for mathematical programs with second-order cone complementarity constraints. Master thesis, Kyoto University (2007)
Yan T, Fukushima M: Smoothing method for mathematical programs with symmetric cone complementarity constraints. Optimization 2011, 60: 113-128. 10.1080/02331934.2010.541458
Jiang, Y: Optimization problems with second-order cone equilibrium constraints. PhD thesis, Dalian University of Technology (2011)
Wu J, Zhang LW, Zhang Y: A smoothing Newton method for mathematical programs governed by second-order cone constrained generalized equations. J. Glob. Optim. 2013, 55: 359-385. 10.1007/s10898-012-9880-9
Ding C, Sun D, Ye J: First order optimality conditions for mathematical programs with semidefinite cone complementarity constraints. Math. Program. 2014. 10.1007/s10107-013-0735-z
Faraut U, Korányi A: Analysis on Symmetric Cones. Oxford University Press, New York; 1994.
Mordukhovich BS: Variational Analysis and Generalized Differentiation I: Basic Theory. Springer, Berlin; 2006.
Rockafellar RT, Wets RJ-B: Variational Analysis. Springer, Berlin; 1998.
Liu YJ, Zhang LW: Convergence analysis of the augmented Lagrangian method for nonlinear second-order cone optimization problems. Nonlinear Anal. 2007, 67: 1359-1373. 10.1016/j.na.2006.07.022
Outrata JV, Sun D: On the coderivative of the projection operator onto the second-order cone. Set-Valued Anal. 2008, 16: 999-1014. 10.1007/s11228-008-0092-x
Dempe S, Dutta J: Is bilevel programming a special case of a mathematical programming with complementarity constraints? Math. Program. 2012, 131: 37-48. 10.1007/s10107-010-0342-1
Gowda MS, Sznajder R, Tao J: Some P-properties for linear transformations on Euclidean Jordan algebras. Linear Algebra Appl. 2004, 393: 203-232.
Acknowledgements
This research is supported by the National Natural Science Foundation of China (Nos. 71171150, 11161001, 71161001) and China Postdoctoral Science Foundation of China (No. 2012M511651). The authors are grateful to the editor and the anonymous referees for their valuable comments, which have greatly improved the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Competing interests
The authors declare that they have no competing interests.
Authors’ contributions
All authors contributed equally to this paper. They read and approved the final manuscript.
Authors’ original submitted files for images
Below are the links to the authors’ original submitted files for images.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 2.0 International License ( https://creativecommons.org/licenses/by/2.0 ), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
About this article
Cite this article
Chi, X., Wan, Z. & Hao, Z. The models of bilevel programming with lower level second-order cone programs. J Inequal Appl 2014, 168 (2014). https://doi.org/10.1186/1029-242X-2014-168
Received:
Accepted:
Published:
DOI: https://doi.org/10.1186/1029-242X-2014-168