×

Finding robust global optimal values of bilevel polynomial programs with uncertain linear constraints. (English) Zbl 1370.49017

Summary: This paper studies a bilevel polynomial program involving box data uncertainties in both its linear constraint set and its lower-level optimization problem. We show that the robust global optimal value of the uncertain bilevel polynomial program is the limit of a sequence of values of Lasserre-type hierarchy of semidefinite linear programming relaxations. This is done by first transforming the uncertain bilevel polynomial program into a single-level non-convex polynomial program using a dual characterization of the solution of the lower-level program and then employing the powerful Putinar’s Positivstellensatz of semi-algebraic geometry. We provide a numerical example to show how the robust global optimal value of the uncertain bilevel polynomial program can be calculated by solving a semidefinite programming problem using the MATLAB toolbox YALMIP.

MSC:

49K21 Optimality conditions for problems involving relations other than differential equations
49K99 Optimality conditions
65K10 Numerical optimization and variational techniques
90C22 Semidefinite programming
90C29 Multi-objective and goal programming
90C46 Optimality conditions and duality in mathematical programming

Software:

YALMIP; Matlab
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bard, J.F.: Practical Bilevel Optimization: Algorithms and Applications. Kluwer Academic Publishers, Dordrecht (1998) · Zbl 0943.90078 · doi:10.1007/978-1-4757-2836-1
[2] Colson, B., Marcotte, P., Savard, G.: An overview of bilevel programming. Ann. Oper. Res. 153, 235-256 (2007) · Zbl 1159.90483 · doi:10.1007/s10479-007-0176-2
[3] Dempe, S.: Foundations of Bilevel Programming. Kluwer Academic Publishers, Dordrecht (2002) · Zbl 1038.90097
[4] Dempe, S., Kalashnikov, V., Perez-Valdes, G.A., Kalashnykova, N.: Bilevel Programming Problems: Theory, Algorithms and Application to Energy Networks. Springer, Berlin (2015) · Zbl 1338.90005 · doi:10.1007/978-3-662-45827-3
[5] Gümüs, Z.H., Floudas, C.A.: Global optimization of nonlinear bilevel programming problems. J. Global Optim. 20, 1-31 (2001) · Zbl 0987.90074 · doi:10.1023/A:1011268113791
[6] Dempe, S., Gadhi, N., Zemkoho, A.B.: New optimality conditions for the semivectorial bilevel optimization problem. J. Optim. Theory Appl. 157, 54-74 (2013) · Zbl 1266.90160 · doi:10.1007/s10957-012-0161-z
[7] Ye, J.J., Zhu, D.L.: New necessary optimality conditions for bilevel programs by combining MPEC and the value function approach. SIAM J. Optim. 20, 1885-1905 (2010) · Zbl 1279.90187 · doi:10.1137/080725088
[8] Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust Optimization, Princeton Series Applied Mathematics. Princeton University Press, Princeton (2009) · Zbl 1221.90001
[9] Bertsimas, D., Brown, D.B., Caramanis, C.: Theory and applications of robust optimization. SIAM Rev. 53, 464-501 (2011) · Zbl 1233.90259 · doi:10.1137/080734510
[10] Ben-Tal, A., Nemirovski, A.: Robust optimizationmethodology and applications. ISMP 2000, Part 2 (Atlanta, GA). Math. Program. 92, 453-480 (2002) · Zbl 1007.90047 · doi:10.1007/s101070100286
[11] Ben-Tal, A., Nemirovski, A.: Selected topics in robust convex optimization. Math. Program. 112, 125-158 (2008) · Zbl 1135.90046 · doi:10.1007/s10107-006-0092-2
[12] Gabrel, V., Murat, C., Thiele, A.: Recent advances in robust optimization: an overview. Eur. J. Oper. Res. 235, 471-483 (2014) · Zbl 1305.90390 · doi:10.1016/j.ejor.2013.09.036
[13] Ben-Ayed, O., Blair, C.E.: Computational difficulties of bilevel linear programming. Oper. Res. 38, 556-560 (1990) · Zbl 0708.90052 · doi:10.1287/opre.38.3.556
[14] Putinar, M.: Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42, 203-206 (1993) · Zbl 0796.12002 · doi:10.1512/iumj.1993.42.42045
[15] Jeyakumar, V., Lasserre, J.B., Li, G.: On polynomial optimization over non-compact semi-algebraic sets. J. Optim. Theory Appl. 163, 707-718 (2014) · Zbl 1302.90208 · doi:10.1007/s10957-014-0545-3
[16] Jeyakumar, V., Kim, S., Lee, G.M., Li, G.: Semidefinite programming relaxation methods for global optimization problems with sparse polynomials and semialgebraic feasible sets. J. Global Optim. 65, 175-190 (2016) · Zbl 1369.90136 · doi:10.1007/s10898-015-0356-6
[17] Jeyakumar, V., Lasserre, J.B., Li, G., Pham, T.S.: Convergent semidefinite programming relaxations for global bilevel polynomial optimization problems. SIAM J. Optim. 26, 753-780 (2016) · Zbl 1333.90088 · doi:10.1137/15M1017922
[18] Jeyakumar, V., Vicente-Perez, J.: Dual semidefinite programs without duality gaps for a class of convex minimax programs. J. Optim. Theory Appl. 162, 735-753 (2014) · Zbl 1312.90087 · doi:10.1007/s10957-013-0496-0
[19] Jeyakumar, V., Pham, T.S., Li, G.: Convergence of the Lasserre hierarchy of SDP relaxations for convex polynomial programs without compactness. Oper. Res. Lett. 42(1), 34-40 (2014) · Zbl 1408.90227 · doi:10.1016/j.orl.2013.11.005
[20] Lasserre, J.B.: Moments, Positive Polynomials and Their Applications. Imperial College Press, London (2009) · doi:10.1142/p665
[21] Chuong, T.D., Jeyakumar, V.: A generalized Farkas lemma with a numerical certificate and linear semi-infinite programs with SDP duals. Linear Algebra Appl. 515, 38-52 (2017) · Zbl 1352.90060 · doi:10.1016/j.laa.2016.11.008
[22] Jeyakumar, V., Li, G.: A bilevel Farkas lemma to characterizing global solutions of a class of bilevel polynomial programs. Oper. Res. Lett. 43, 405-410 (2015) · Zbl 1408.90226 · doi:10.1016/j.orl.2015.05.006
[23] Patriksson, M., Wynter, L.: Stochastic mathematical programs with equilibrium constraints. Oper. Res. Lett. 25, 159-167 (1999) · Zbl 0937.90076 · doi:10.1016/S0167-6377(99)00052-8
[24] Budnitzki, A.: The solution approach to linear fuzzy bilevel optimization problems. Optimization 64, 1195-1209 (2015) · Zbl 1311.90197 · doi:10.1080/02331934.2013.848862
[25] Loridan, P., Morgan, J.: Approximate solutions for two-level optimization problems. Trends in mathematical optimization (Irsee 1986), Internat. Schriftenreihe Numer. Math., 84, pp. 181-196. Birkhuser, Basel, (1988) · Zbl 1266.90160
[26] Demmel, J., Nie, J., Powers, V.: Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals. J. Pure Appl. Algebra 209, 189-200 (2007) · Zbl 1106.13028 · doi:10.1016/j.jpaa.2006.05.028
[27] Vinzant, C.: What is a spectrahedron? Not. Am. Math. Soc. 61, 492-494 (2014) · Zbl 1338.52001
[28] Lofberg, J.: YALMIP: A toolbox for modeling and optimization in MATLAB. In: Proceedings of the CACSD Conference, Taipei, Taiwan (2004) · Zbl 1311.90197
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.