research-article

A Lagrange Multiplier Expression Method for Bilevel Polynomial Optimization

Authors:

Suhan ZhongAuthors Info & Claims

SIAM Journal on Optimization, Volume 31, Issue 3

Pages 2368 - 2395

https://doi.org/10.1137/20M1352375

Published: 01 January 2021 Publication History

Abstract

This paper studies bilevel polynomial optimization. We propose a method to solve it globally by using polynomial optimization relaxations. Each relaxation is obtained from the Karush--Kuhn--Tucker (KKT) conditions for the lower level optimization and the exchange technique for semi-infinite programming. For KKT conditions, Lagrange multipliers are represented as polynomial or rational functions. The Moment--sum-of-squares relaxations are used to solve the polynomial optimization relaxations. Under some general assumptions, we prove the convergence of the algorithm for solving bilevel polynomial optimization problems. Numerical experiments are presented to show the efficiency of the method.

References

[1]

A. A. Ahmadi and A. Majumdar, DSOS and SDSOS optimization: More tractable alternatives to sum of squares and semidefinite optimization, SIAM J. Appl. Algebra Geom., 3 (2019), pp. 193--230.

[2]

G. Allende and G. Still, Solving bilevel programs with the KKT-approach, Math. Program., 138 (2013), pp. 309--332.

[3]

K. Bai and J.J. Ye, Directional necessary optimality conditions for bilevel programs, Math. Oper. Res., to appear.

[4]

J. Bard, Practical Bilevel Optimization: Algorithms and Applications, Kluwer Academic, Dordrecht, Netherlands, 1998.

[5]

A. Ben-Tal and C. Blair, Computational difficulties of bilevel linear programming, Oper. Res., 38 (1990), pp. 556--560.

[6]

D. Bertsekas, Nonlinear Programming, 2nd ed., Athena Scientific, Belmont, MA, 1995.

[7]

M. Bjørndal and K. Jørnsten, The deregulated electricity market viewed as a bilevel programming problem, J. Global Optim., 33 (2005), pp. 465--475.

[8]

G. Boglárka and K. Kovács, Solving a Huff-like Stackelberg location problem on networks, J. Global Optim., 64 (2016), pp. 233--247.

[9]

G. Bouza Allende and G. Still, Solving bilevel programs with the KKT-approach, Math. Program., 138 (2013), pp. 309--332.

[10]

T. Chuong, V. Jeyakumar, and G. Li, A new bounded degree hierarchy with SOCP relaxations for global polynomial optimization and conic convex semi-algebraic programs, J. Global Optim., 75 (2019), pp. 885--919.

[11]

F. H. Clarke, Optimization and Nonsmooth Analysis,Classics Appl. Math. 5, SIAM, Philadelphia, 1990.

[12]

B. Colson, P. Marcotte, and G. Savard, An overview of bilevel optimization, Ann. Oper. Res., 153 (2007), pp. 235--256.

[13]

S. Dempe, Bilevel optimization: Theory, algorithms and applications, preprint, optimization online 2018-11, 2018.

[14]

S. Dempe and J. Dutta, Is bilevel programming a special case of a mathematical program with complementarity constraints?, Math. Program., 131 (2012), pp. 37--48.

[15]

S. Dempe and S. Franke, Solution algorithm for an optimistic linear Stackelberg problem, Comput. Oper. Res., 41 (2014), pp. 277--281.

[16]

S. Dempe, V. Kalashnikov, G. Pérez-Valdés, and N. Kalashnykova, Bilevel Programming Problems, Energy Syst., Springer, Berlin, 2015.

[17]

S. Dempe and A. Zemkoho, Bilevel Optimization: Advances and Next Challenges, Springer Optim. Appl. 161, Springer, Cham, Switzerland, 2020.

[18]

L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil, Bilevel programming for hyperparameter optimization, in International Conference on Machine Learning, Curran Associates, Red Hook, NY, (2018), pp. 1563--1572.

[19]

J. Gauvin and F. Dubeau, Differential properties of the marginal function in mathematical programming, in Optimality and Stability in Mathematical Programming, Math. Program. Stud., 19, Springer, Berlin, 1982, pp. 101--119.

[20]

L. Guo, G. Lin, J.J. Ye, and J. Zhang, Sensitivity analysis of the value function for parametric mathematical programs with equilibrium constraints, SIAM J. Optim., 24 (2014), pp. 1206--1237.

[21]

D. Henrion, J. Lasserre, and J. Lofberg, GloptiPoly 3: Moments, optimization and semidefinite programming, Optim. Methods Softw., 24 (2009), pp. 761--779.

[22]

R. Hettich and K. O. Kortanek, Semi-infinite programming: Theory, methods, and applications, SIAM Rev., 35 (1993), pp. 380--429.

[23]

V. Jeyakumar, J. B. Lasserre, G. Li, and T. S. Pham, Convergent semidefinite programming relaxations for global bilevel polynomial optimization problems, SIAM J. Optim., 26 (2016), pp. 753--780.

[24]

H. Th. Jongen, P. Jonker, and F. Twilt, Critical sets in parametric optimization, Math. Program., 34 (1986), pp. 333--353.

[25]

G. Kunapuli, K. Bennett, J. Hu, and J-S. Pang, Classification model selection via bilevel programming, Optim. Methods Softw., 23 (2008), pp. 475--489.

[26]

L. Lampariello and S. Sagratella, A bridge between bilevel programs and Nash games, J. Optim. Theory Appl., 174 (2017), pp. 613--635.

[27]

J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11 (2001), pp. 796--817.

[28]

J. Lasserre, Moments, Positive Polynomials and Their Applications, Optim. Ser. 1, Imperial College Press, London, 2009.

[29]

J. B. Lasserre, K. Toh, and S. Yang, A bounded degree SOS hierarchy for polynomial optimization, EURO J. Comput. Optim., 5 (2017), pp. 87--117.

[30]

M. Laurent, Optimization over polynomials: Selected topics, Proceedings of the International Congress of Mathematicians, Kyung Moon, Seoul, 2014.

[31]

G. Lin, M. Xu, and J. Ye, On solving simple bilevel programs with a nonconvex lower level program, Math. Program., 144 (2014), pp. 277--305.

[32]

R. Liu, P. Mu, X. Yuan, S. Zeng, and J. Zhang, A generic first-order algorithmic framework for bi-level programming beyond lower-level singleton, International Conference on Machine Learning, 2020, Proceedings of the 37th International Conference on Machine Learning, PMLR, 119 (2020), pp. 6305--6315.

[33]

J. Lofberg, YALMIP: A toolbox for modeling and optimization in MATLAB, in 2004 IEEE International Conference on Robotics and Automation (IEEE Cat. No. 04CH37508), IEEE, Piscataway, NJ, 2004.

[34]

Z. Luo, J. Pang, and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge, 1996.

[35]

A. Megretski, SPOT (Systems polynomial optimization tools) Manual, http://web.mit.edu/ameg/www/images/spot_manual.pdf (2010).

[36]

J. Mirrlees, The theory of moral hazard and unobservable behaviour: Part I, Rev. Eco. Stud., 66 (1999), pp. 3--22.

[37]

A. Mitsos, P. Lemonidis, and P.I. Barton, Global solution of bilevel programs with a nonconvex inner program, J. Global Optim., 42 (2008), pp. 475--513.

[38]

L. Muu and N. Quy, A global optimization method for solving convex quadratic bilevel programming problems, J. Global Optim., 26 (2003), pp. 199--219.

[39]

J. Nie, Certifying convergence of Lasserre's hierarchy via flat truncation, Math. Program., 1422 (2013), pp. 485--510.

[40]

J. Nie, Optimality conditions and finite convergence of Lasserre's hierarchy, Math. Program., 146 (2014), pp. 97--121.

[41]

J. Nie, Tight relaxations for polynomial optimization and Lagrange multiplier expressions, Math. Program., 178 (2019), pp. 1--37.

[42]

J. Nie, L. Wang, and J.J. Ye, Bilevel polynomial programs and semidefinite relaxation methods, SIAM J. Optim., 27 (2017), pp. 1728--1757.

[43]

J. Outrata, On the numerical solution of a class of Stackelberg problems, Z. Oper. Resear., 34 (1990), pp. 255--277.

[44]

J. V. Outrata, On optimization problems with variational inequality constraints, SIAM J. Optim., 4 (1994), pp. 340--357.

[45]

J. Outrata, M. Kocvara, and J. Zowe, Nonsmooth Approach to Optimization Problems with Equilibrium Constraints: Theory, Applications and Numerical Results, Kluwer Academic, Boston, 1998.

[46]

M. Putinar, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J., 42 (1993), pp. 969--984.

[47]

K. Shimizu and E. Aiyoshi, A new computational method for Stackelberg and min-max problems by use of a penalty method, IEEE Trans. Automat. Control, 26 (1981), pp. 460--466.

[48]

K. Shimizu, Y. Ishizuka, and J. Bard, Nondifferentiable and Two-level Mathematical Programming, Kluwer Academic, Boston, 1997.

[49]

J. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11 (1999), pp. 625--653.

[50]

M. Xu and J.J. Ye, A smoothing augmented Lagrangian method for solving simple bilevel programs, Comput. Optim. Appl., 59 (2014), pp. 353--377.

[51]

M. Xu and J.J. Ye, Relaxed constant positive linear dependence constraint qualification and its application to bilevel programs, J. Global Optim., 78 (2020), pp. 181--205.

[52]

M. Xu, J.J. Ye, and L. Zhang, Smoothing augmented Lagrangian method for solving nonsmooth and nonconvex constrained optimization problems, J. Global Optim., 62 (2014), pp. 675--694.

[53]

M. Xu, J.J. Ye, and L. Zhang, Smoothing SQP methods for solving degenerate nonsmooth constrained optimization problems with applications to bilevel programs, SIAM J. Optim., 25 (2015), pp. 1388--1410.

[54]

J.J. Ye, Constraint qualifications and optimality conditions in bilevel optimization, in Bilevel Optimization: Advances and Next Challenges, Springer Optim. Appl. 161, Springer, Cham, Switzerland, 2020.

[55]

J.J. Ye and D. Zhu, Optimality conditions for bilevel programming problems, Optimization, 33 (1995), pp. 9--27.

[56]

J.J. Ye and D. Zhu, New necessary optimality conditions for bilevel programs by combining the MPEC and value function approaches, SIAM J. Optim., 20 (2010), pp. 1885--1905.

[57]

J.J. Ye, D.L. Zhu, and Q.J. Zhu, Exact penalization and necessary optimality conditions for generalized bilevel programming problems, SIAM J. Optim., 7 (1997), pp. 481--507.

Cited By

Zhao WZhou G(2024)Hausdorff distance between convex semialgebraic setsJournal of Global Optimization10.1007/s10898-023-01313-988:2(409-429)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s10898-023-01313-9
Ye JYuan XZeng SZhang J(2022)Difference of convex algorithms for bilevel programs with applications in hyperparameter selectionMathematical Programming: Series A and B10.1007/s10107-022-01888-3198:2(1583-1616)Online publication date: 16-Sep-2022
https://dl.acm.org/doi/10.1007/s10107-022-01888-3
Nie JTang X(2021)Convex generalized Nash equilibrium problems and polynomial optimizationMathematical Programming: Series A and B10.1007/s10107-021-01739-7198:2(1485-1518)Online publication date: 7-Dec-2021
https://dl.acm.org/doi/10.1007/s10107-021-01739-7

Recommendations

The adaptive convexification algorithm for semi-infinite programming with arbitrary index sets

A numerical solution method for semi-infinite optimization problems with arbitrary, not necessarily box-shaped, index sets is presented. Following the ideas of Floudas and Stein (SIAM J Optim 18:1187---1208, 2007), convex relaxations of the lower level ...
Bilevel Polynomial Programs and Semidefinite Relaxation Methods

A bilevel program is an optimization problem whose constraints involve the solution set to another optimization problem parameterized by upper level variables. This paper studies bilevel polynomial programs (BPPs), i.e., all the functions are polynomials. We ...
Convergent Semidefinite Programming Relaxations for Global Bilevel Polynomial Optimization Problems

In this paper, we consider a bilevel polynomial optimization problem where the objective and the constraint functions of both the upper-and the lower-level problems are polynomials. We present methods for finding its global minimizers and global minimum ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Optimization

SIAM Journal on Optimization Volume 31, Issue 3

DOI:10.1137/sjope8.31.3

Issue’s Table of Contents

© 2021, Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 2021

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhao WZhou G(2024)Hausdorff distance between convex semialgebraic setsJournal of Global Optimization10.1007/s10898-023-01313-988:2(409-429)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s10898-023-01313-9
Ye JYuan XZeng SZhang J(2022)Difference of convex algorithms for bilevel programs with applications in hyperparameter selectionMathematical Programming: Series A and B10.1007/s10107-022-01888-3198:2(1583-1616)Online publication date: 16-Sep-2022
https://dl.acm.org/doi/10.1007/s10107-022-01888-3
Nie JTang X(2021)Convex generalized Nash equilibrium problems and polynomial optimizationMathematical Programming: Series A and B10.1007/s10107-021-01739-7198:2(1485-1518)Online publication date: 7-Dec-2021
https://dl.acm.org/doi/10.1007/s10107-021-01739-7

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents