-
Previous Article
Solving normalized stationary points of a class of equilibrium problem with equilibrium constraints
- JIMO Home
- This Issue
-
Next Article
D.C. programming approach for solving an applied ore-processing problem
Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming
1. | School of Economics and Management, University of Chinese Academy of Sciences, Key Laboratory of Big Data Mining and Knowledge Management, Chinese Academy of Sciences, Beijing 100190, China |
2. | School of Business Administration, Southwestern University of Finance and Economics, Chengdu 611130, China |
3. | School of Economics and Management, North China Electric Power University, Beijing 102206, China |
4. | Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China |
Quadratic programs with complementarity constraints (QPCC) are NP-hard due to the nonconvexity of complementarity relation between the pairs of nonnegative variables. Most of the existing solvers are capable of solving QPCC by finding stationary solutions, which are not able to be verified as global or local optimal ones. In this paper, we aim to globally solve QPCC by a branch-and-bound algorithm, in which the doubly nonnegative (DNN) relaxation in each node is efficiently solved via an augmented Lagrangian method. The method is practically efficient due to the fact that the augmented Lagrangian function can be decomposed into two easy-to-solve subproblems. Computational results demonstrate the effectiveness of the proposed algorithm, with a particular highlight in only a few nodes for some instances.
References:
[1] |
L. Bai, J. E. Mitchell and J.-S. Pang,
On convex quadratic programs with linear complementarity constraints, Computational Optimization and Applications, 54 (2013), 517-554.
doi: 10.1007/s10589-012-9497-4. |
[2] |
J. Beasley, OR-Library: distributing test problems by electronic mail, Journal of the Operational Research Society, 41 (1990), 1069-1072. Google Scholar |
[3] |
A. Billionnet, S. Elloumi and M.-C. Plateau,
Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method, Discrete Applied Mathematics, 157 (2009), 1185-1197.
doi: 10.1016/j.dam.2007.12.007. |
[4] |
S. Burer,
On the copositive representation of binary and continuous nonconvex quadratic programs, Mathematical Programming, 120 (2009), 479-495.
doi: 10.1007/s10107-008-0223-z. |
[5] |
S. Burer,
Optimizing a polyhedral-semidefinite relaxation of completely positive programs, Mathematical Programming Computation, 2 (2010), 1-19.
doi: 10.1007/s12532-010-0010-8. |
[6] |
Y.-L. Chang, J.-S. Chen and J. Wu,
Proximal point algorithm for nonlinear complementarity problem based on the generalized fischer-burmeister merit function, Journal of Industrial and Management Optimization, 9 (2013), 153-169.
doi: 10.3934/jimo.2013.9.153. |
[7] |
P. J. Dickinson and L. Gijben,
On the computational complexity of membership problems for the completely positive cone and its dual, Computational Optimization and Applications, 57 (2014), 403-415.
doi: 10.1007/s10589-013-9594-z. |
[8] |
M. C. Ferris and J. S. Pang,
Engineering and economic applications of complementarity problems, SIAM Review, 39 (1997), 669-713.
doi: 10.1137/S0036144595285963. |
[9] |
C. Hao and X. Liu,
A trust-region filter-sqp method for mathematical programs with linear complementarity constraints, Journal of Industrial and Management Optimization, 7 (2011), 1041-1055.
doi: 10.3934/jimo.2011.7.1041. |
[10] |
T. Hoheisel, C. Kanzow and A. Schwartz,
Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints, Mathematical Programming, 137 (2013), 257-288.
doi: 10.1007/s10107-011-0488-5. |
[11] |
J. Hu, J. E. Mitchell, J.-S. Pang, K. P. Bennett and G. Kunapuli,
On the global solution of linear programs with linear complementarity constraints, SIAM Journal on Optimization, 19 (2008), 445-471.
doi: 10.1137/07068463x. |
[12] |
X. X. Huang, D. Li and X. Q. Yang,
Convergence of optimal values of quadratic penalty problems for mathematical programs with complementarity constraints, Journal of Industrial and Management Optimization, 2 (2006), 287-296.
doi: 10.3934/jimo.2006.2.287. |
[13] |
H. Jiang and D. Ralph,
QPECgen, a MATLAB generator for mathematical programs with quadratic objectives and affine variational inequality constraints, Computational Optimization and Applications, 13 (1999), 25-59.
doi: 10.1023/A:1008696504163. |
[14] |
J. J. Júdice and A. Faustino, The linear-quadratic bilevel programming problem, Information Systems and Operational Research, 32 (1994), 87-98. Google Scholar |
[15] |
S. Kim, M. Kojima and K.-C. Toh,
A lagrangian-dnn relaxation: A fast method for computing tight lower bounds for a class of quadratic optimization problems, Mathematical Programming, 156 (2016), 161-187.
doi: 10.1007/s10107-015-0874-5. |
[16] |
S. Leyffer, MacMPEC: AMPL collection of mathematical problems with equilibrium constraints, 2015, URL http://wiki.mcs.anl.gov/leyffer/index.php/MacMPEC. Google Scholar |
[17] |
C. Lu, W. Xing, S. -C. Fang and Z. Deng, Doubly non-negative relaxation solution based branch-and-bound algorithms for mixed integer quadratic programs, Working paper. Google Scholar |
[18] |
C. Lu and X. Guo,
Convex reformulation for binary quadratic programming problems via average objective value maximization, Optimization Letters, 9 (2015), 523-535.
doi: 10.1007/s11590-014-0768-0. |
[19] |
O. Mangasarian and S. Fromovitz,
The Fritz John necessary optimality conditions in the presence of equality and inequality constraints, Journal of Mathematical Analysis and Applications, 17 (1967), 37-47.
doi: 10.1016/0022-247X(67)90163-1. |
[20] |
P. Pardalom and S. Jha,
Complexity of uniqueness and local search in quadratic 0-1 programming, Operations Research Letters, 11 (1992), 119-123.
doi: 10.1016/0167-6377(92)90043-3. |
[21] |
T. Rockafellar,
Convex Analysis, Princeton University Press, Princeton, N. J., 1970. |
[22] |
J. Sun and S. Zhang,
A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs, European Journal of Operational Research, 207 (2010), 1210-1220.
doi: 10.1016/j.ejor.2010.07.020. |
[23] |
Z. Wen, D. Goldfarb and W. Yin,
Alternating direction augmented lagrangian methods for semidefinite programming, Mathematical Programming Computation, 2 (2010), 203-230.
doi: 10.1007/s12532-010-0017-1. |
[24] |
X.-Y. Zhao, D.-F. Sun and K.-C. Toh,
A Newton-CG augmented Lagrangian method for semidefinite programming, SIAM Journal on Optimizaton, 20 (2010), 1737-1765.
doi: 10.1137/080718206. |
[25] |
J. Zhou, S.-C. Fang and W. Xing,
Conic approximation to quadratic optimization with linear complementarity constraints, Computational Optimization and Applications, 66 (2017), 92-122.
doi: 10.1007/s10589-016-9855-8. |
show all references
References:
[1] |
L. Bai, J. E. Mitchell and J.-S. Pang,
On convex quadratic programs with linear complementarity constraints, Computational Optimization and Applications, 54 (2013), 517-554.
doi: 10.1007/s10589-012-9497-4. |
[2] |
J. Beasley, OR-Library: distributing test problems by electronic mail, Journal of the Operational Research Society, 41 (1990), 1069-1072. Google Scholar |
[3] |
A. Billionnet, S. Elloumi and M.-C. Plateau,
Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method, Discrete Applied Mathematics, 157 (2009), 1185-1197.
doi: 10.1016/j.dam.2007.12.007. |
[4] |
S. Burer,
On the copositive representation of binary and continuous nonconvex quadratic programs, Mathematical Programming, 120 (2009), 479-495.
doi: 10.1007/s10107-008-0223-z. |
[5] |
S. Burer,
Optimizing a polyhedral-semidefinite relaxation of completely positive programs, Mathematical Programming Computation, 2 (2010), 1-19.
doi: 10.1007/s12532-010-0010-8. |
[6] |
Y.-L. Chang, J.-S. Chen and J. Wu,
Proximal point algorithm for nonlinear complementarity problem based on the generalized fischer-burmeister merit function, Journal of Industrial and Management Optimization, 9 (2013), 153-169.
doi: 10.3934/jimo.2013.9.153. |
[7] |
P. J. Dickinson and L. Gijben,
On the computational complexity of membership problems for the completely positive cone and its dual, Computational Optimization and Applications, 57 (2014), 403-415.
doi: 10.1007/s10589-013-9594-z. |
[8] |
M. C. Ferris and J. S. Pang,
Engineering and economic applications of complementarity problems, SIAM Review, 39 (1997), 669-713.
doi: 10.1137/S0036144595285963. |
[9] |
C. Hao and X. Liu,
A trust-region filter-sqp method for mathematical programs with linear complementarity constraints, Journal of Industrial and Management Optimization, 7 (2011), 1041-1055.
doi: 10.3934/jimo.2011.7.1041. |
[10] |
T. Hoheisel, C. Kanzow and A. Schwartz,
Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints, Mathematical Programming, 137 (2013), 257-288.
doi: 10.1007/s10107-011-0488-5. |
[11] |
J. Hu, J. E. Mitchell, J.-S. Pang, K. P. Bennett and G. Kunapuli,
On the global solution of linear programs with linear complementarity constraints, SIAM Journal on Optimization, 19 (2008), 445-471.
doi: 10.1137/07068463x. |
[12] |
X. X. Huang, D. Li and X. Q. Yang,
Convergence of optimal values of quadratic penalty problems for mathematical programs with complementarity constraints, Journal of Industrial and Management Optimization, 2 (2006), 287-296.
doi: 10.3934/jimo.2006.2.287. |
[13] |
H. Jiang and D. Ralph,
QPECgen, a MATLAB generator for mathematical programs with quadratic objectives and affine variational inequality constraints, Computational Optimization and Applications, 13 (1999), 25-59.
doi: 10.1023/A:1008696504163. |
[14] |
J. J. Júdice and A. Faustino, The linear-quadratic bilevel programming problem, Information Systems and Operational Research, 32 (1994), 87-98. Google Scholar |
[15] |
S. Kim, M. Kojima and K.-C. Toh,
A lagrangian-dnn relaxation: A fast method for computing tight lower bounds for a class of quadratic optimization problems, Mathematical Programming, 156 (2016), 161-187.
doi: 10.1007/s10107-015-0874-5. |
[16] |
S. Leyffer, MacMPEC: AMPL collection of mathematical problems with equilibrium constraints, 2015, URL http://wiki.mcs.anl.gov/leyffer/index.php/MacMPEC. Google Scholar |
[17] |
C. Lu, W. Xing, S. -C. Fang and Z. Deng, Doubly non-negative relaxation solution based branch-and-bound algorithms for mixed integer quadratic programs, Working paper. Google Scholar |
[18] |
C. Lu and X. Guo,
Convex reformulation for binary quadratic programming problems via average objective value maximization, Optimization Letters, 9 (2015), 523-535.
doi: 10.1007/s11590-014-0768-0. |
[19] |
O. Mangasarian and S. Fromovitz,
The Fritz John necessary optimality conditions in the presence of equality and inequality constraints, Journal of Mathematical Analysis and Applications, 17 (1967), 37-47.
doi: 10.1016/0022-247X(67)90163-1. |
[20] |
P. Pardalom and S. Jha,
Complexity of uniqueness and local search in quadratic 0-1 programming, Operations Research Letters, 11 (1992), 119-123.
doi: 10.1016/0167-6377(92)90043-3. |
[21] |
T. Rockafellar,
Convex Analysis, Princeton University Press, Princeton, N. J., 1970. |
[22] |
J. Sun and S. Zhang,
A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs, European Journal of Operational Research, 207 (2010), 1210-1220.
doi: 10.1016/j.ejor.2010.07.020. |
[23] |
Z. Wen, D. Goldfarb and W. Yin,
Alternating direction augmented lagrangian methods for semidefinite programming, Mathematical Programming Computation, 2 (2010), 203-230.
doi: 10.1007/s12532-010-0017-1. |
[24] |
X.-Y. Zhao, D.-F. Sun and K.-C. Toh,
A Newton-CG augmented Lagrangian method for semidefinite programming, SIAM Journal on Optimizaton, 20 (2010), 1737-1765.
doi: 10.1137/080718206. |
[25] |
J. Zhou, S.-C. Fang and W. Xing,
Conic approximation to quadratic optimization with linear complementarity constraints, Computational Optimization and Applications, 66 (2017), 92-122.
doi: 10.1007/s10589-016-9855-8. |
Output: An approximate solution |
1. Set |
2: for |
3: Solve problem (Y-Block) to get Y. |
4: Solve problem (Z-Block to get Z. |
5: Update S according to (5). |
6: Update v by optimizing problem (Y-Block) with Z = 0 and σ = 0. |
7: Update σ if necessary. |
8: STOP, if termination criteria are met. |
9: end for |
Output: An approximate solution |
1. Set |
2: for |
3: Solve problem (Y-Block) to get Y. |
4: Solve problem (Z-Block to get Z. |
5: Update S according to (5). |
6: Update v by optimizing problem (Y-Block) with Z = 0 and σ = 0. |
7: Update σ if necessary. |
8: STOP, if termination criteria are met. |
9: end for |
Algorithm 2 A Branch-and-Bound Algorithm for Globally Solving Problem (QPCC) |
Input: Data (Q; q; A; b; E). |
Output: A global solution of (QPCC). |
1: Preprocessing Step: Calculate the upper bound for variable x. |
2: Initialization Step: The list |
3: while |
4: Node Selection Step: Select and remove the best-first node from |
5: Bounding Step: Solve the relaxation problem of the node by Algorithm 1. Update upper and lower bound if possible. If the node is not fathomed, go to the next step. |
6: Branching Step: Branch the node on the most violated complementarity constraint, generate two children nodes and add them to the list |
7: end while |
Algorithm 2 A Branch-and-Bound Algorithm for Globally Solving Problem (QPCC) |
Input: Data (Q; q; A; b; E). |
Output: A global solution of (QPCC). |
1: Preprocessing Step: Calculate the upper bound for variable x. |
2: Initialization Step: The list |
3: while |
4: Node Selection Step: Select and remove the best-first node from |
5: Bounding Step: Solve the relaxation problem of the node by Algorithm 1. Update upper and lower bound if possible. If the node is not fathomed, go to the next step. |
6: Branching Step: Branch the node on the most violated complementarity constraint, generate two children nodes and add them to the list |
7: end while |
Id | | nodes | time (sec.) |
bilevel2 | (29, 13, 12) | 13 | 4.86 |
bilevel2m | (9, 21, 8) | 5 | 1.74 |
flp4-1 | (60,190, 80) | 3 | 8.41 |
flp4-2 | (110,270,110) | 1 | 15.21 |
flp4-3 | (170,380,140) | 1 | 30.03 |
flp4-4 | (250,550,200) | 1 | 67.71 |
Id | | nodes | time (sec.) |
bilevel2 | (29, 13, 12) | 13 | 4.86 |
bilevel2m | (9, 21, 8) | 5 | 1.74 |
flp4-1 | (60,190, 80) | 3 | 8.41 |
flp4-2 | (110,270,110) | 1 | 15.21 |
flp4-3 | (170,380,140) | 1 | 30.03 |
flp4-4 | (250,550,200) | 1 | 67.71 |
Ave. nodes | Ave. CPU time (sec.) | |
(4, 12, 3) | 3 | 1.21 |
(15, 45, 10) | 5 | 9.43 |
(25, 55, 20) | 26 | 65.21 |
(30,100, 40) | 121 | 310.66 |
Ave. nodes | Ave. CPU time (sec.) | |
(4, 12, 3) | 3 | 1.21 |
(15, 45, 10) | 5 | 9.43 |
(25, 55, 20) | 26 | 65.21 |
(30,100, 40) | 121 | 310.66 |
Id | Optimal value | Nodes | {CPU time (sec.) |
bqp50-1 | | 3564 | 1800.00 |
bqp50-2 | | 3063 | 1570.22 |
bqp50-3 | | 69 | 19.53 |
bqp50-4 | | 767 | 330.86 |
bqp50-5 | | 531 | 226.87 |
bqp50-6 | | 107 | 49.31 |
bqp50-7 | | 605 | 247.22 |
bqp50-8 | | 771 | 363.41 |
bqp50-9 | | 3849 | 1692.21 |
bqp50-10 | | 3626 | 1800.00 |
Id | Optimal value | Nodes | {CPU time (sec.) |
bqp50-1 | | 3564 | 1800.00 |
bqp50-2 | | 3063 | 1570.22 |
bqp50-3 | | 69 | 19.53 |
bqp50-4 | | 767 | 330.86 |
bqp50-5 | | 531 | 226.87 |
bqp50-6 | | 107 | 49.31 |
bqp50-7 | | 605 | 247.22 |
bqp50-8 | | 771 | 363.41 |
bqp50-9 | | 3849 | 1692.21 |
bqp50-10 | | 3626 | 1800.00 |
[1] |
Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017 |
[2] |
Yuri Chekanov, Felix Schlenk. Notes on monotone Lagrangian twist tori. Electronic Research Announcements, 2010, 17: 104-121. doi: 10.3934/era.2010.17.104 |
[3] |
David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002 |
[4] |
Alberto Bressan, Ke Han, Franco Rampazzo. On the control of non holonomic systems by active constraints. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3329-3353. doi: 10.3934/dcds.2013.33.3329 |
[5] |
Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141 |
[6] |
Marcelo Messias. Periodic perturbation of quadratic systems with two infinite heteroclinic cycles. Discrete & Continuous Dynamical Systems - A, 2012, 32 (5) : 1881-1899. doi: 10.3934/dcds.2012.32.1881 |
[7] |
Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023 |
[8] |
Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 |
[9] |
Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271 |
[10] |
Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327 |
[11] |
Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006 |
[12] |
Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018 |
[13] |
Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002 |
[14] |
Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263 |
[15] |
Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149 |
[16] |
Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83 |
[17] |
Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069 |
[18] |
Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056 |
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]