On the Copositive Representation of Binary and Continuous Nonconvex Quadratic Programs

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.

Mathematics Subject Classification: Primary: 90C33, 90C20, 90C22; Secondary: 49M37.

Citation: Zhi-Bin Deng, Ye Tian, Cheng Lu, Wen-Xun Xing. Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming. Journal of Industrial and Management Optimization, 2018, 14 (2) : 625-636. doi: 10.3934/jimo.2017064

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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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 $Y$ and a valid lower bound $v$ of problem (DNP).
1. Set $(S, \sigma)=(S_0, \sigma_0)$ and $v=-\infty$. Initialize $Z=0$.
2: for $k=0, 1, ...$ do
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 $Y$ and a valid lower bound $v$ of problem (DNP).
1. Set $(S, \sigma)=(S_0, \sigma_0)$ and $v=-\infty$. Initialize $Z=0$.
2: for $k=0, 1, ...$ do
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 $\mathcal{L}$ to be explored is initialized to contain the root node. Upper bound is set to +1, and lower bound is set to −1.
3: while $\mathcal{L}$ is not empty do
4:Node Selection Step: Select and remove the best-first node from $\mathcal{L}$.
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 $\mathcal{L}$.
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 $\mathcal{L}$ to be explored is initialized to contain the root node. Upper bound is set to +1, and lower bound is set to −1.
3: while $\mathcal{L}$ is not empty do
4:Node Selection Step: Select and remove the best-first node from $\mathcal{L}$.
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 $\mathcal{L}$.
7: end while

Table 1. Computational results of six QPCC instances on MacMPEC

Id	$(m, n, |\mathcal{E}|)$	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	$(m, n, |\mathcal{E}|)$	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

Table 2. Computation results for randomly generated QPCC Instances

$(m, n, |\mathcal{E}|)$	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

$(m, n, |\mathcal{E}|)$	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

Table 3. Computational results for binary quadratic programs from OR-Library

$m=50, ~n=100, ~|\mathcal{E}|=50$
Id	Optimal value	Nodes	{CPU time (sec.)
bqp50-1	$\le-2160$	3564	1800.00
bqp50-2	$-3702$	3063	1570.22
bqp50-3	$-4626$	69	19.53
bqp50-4	$-3544$	767	330.86
bqp50-5	$-4012$	531	226.87
bqp50-6	$-3693$	107	49.31
bqp50-7	$-4520$	605	247.22
bqp50-8	$-4216$	771	363.41
bqp50-9	$-3780$	3849	1692.21
bqp50-10	$\le-3507$	3626	1800.00

$m=50, ~n=100, ~|\mathcal{E}|=50$
Id	Optimal value	Nodes	{CPU time (sec.)
bqp50-1	$\le-2160$	3564	1800.00
bqp50-2	$-3702$	3063	1570.22
bqp50-3	$-4626$	69	19.53
bqp50-4	$-3544$	767	330.86
bqp50-5	$-4012$	531	226.87
bqp50-6	$-3693$	107	49.31
bqp50-7	$-4520$	605	247.22
bqp50-8	$-4216$	771	363.41
bqp50-9	$-3780$	3849	1692.21
bqp50-10	$\le-3507$	3626	1800.00

[1]	Yanqin Bai, Chuanhao Guo. Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems. Journal of Industrial and Management Optimization, 2014, 10 (2) : 543-556. doi: 10.3934/jimo.2014.10.543
[2]	Jing Zhou, Zhibin Deng. A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2087-2102. doi: 10.3934/jimo.2019044
[3]	Lin Zhu, Xinzhen Zhang. Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1505-1517. doi: 10.3934/jimo.2021030
[4]	Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial and Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319
[5]	X. X. Huang, D. Li, Xiaoqi Yang. Convergence of optimal values of quadratic penalty problems for mathematical programs with complementarity constraints. Journal of Industrial and Management Optimization, 2006, 2 (3) : 287-296. doi: 10.3934/jimo.2006.2.287
[6]	Li Jin, Hongying Huang. Differential equation method based on approximate augmented Lagrangian for nonlinear programming. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2267-2281. doi: 10.3934/jimo.2019053
[7]	Lei Guo, Gao-Xi Li, Xinmin Yang. Global convergence of augmented Lagrangian method applied to mathematical program with switching constraints. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022114
[8]	Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial and Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104
[9]	Chunlin Wu, Juyong Zhang, Xue-Cheng Tai. Augmented Lagrangian method for total variation restoration with non-quadratic fidelity. Inverse Problems and Imaging, 2011, 5 (1) : 237-261. doi: 10.3934/ipi.2011.5.237
[10]	Qingsong Duan, Mengwei Xu, Yue Lu, Liwei Zhang. A smoothing augmented Lagrangian method for nonconvex, nonsmooth constrained programs and its applications to bilevel problems. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1241-1261. doi: 10.3934/jimo.2018094
[11]	Z.G. Feng, K.L. Teo, Y. Zhao. Branch and bound method for sensor scheduling in discrete time. Journal of Industrial and Management Optimization, 2005, 1 (4) : 499-512. doi: 10.3934/jimo.2005.1.499
[12]	Yang Li, Yonghong Ren, Yun Wang, Jian Gu. Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved. Journal of Industrial and Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65
[13]	Yang Li, Liwei Zhang. A nonlinear Lagrangian method based on Log-Sigmoid function for nonconvex semidefinite programming. Journal of Industrial and Management Optimization, 2009, 5 (3) : 651-669. doi: 10.3934/jimo.2009.5.651
[14]	Tim Hoheisel, Christian Kanzow, Alexandra Schwartz. Improved convergence properties of the Lin-Fukushima-Regularization method for mathematical programs with complementarity constraints. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 49-60. doi: 10.3934/naco.2011.1.49
[15]	Chunlin Hao, Xinwei Liu. A trust-region filter-SQP method for mathematical programs with linear complementarity constraints. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1041-1055. doi: 10.3934/jimo.2011.7.1041
[16]	Liping Pang, Na Xu, Jian Lv. The inexact log-exponential regularization method for mathematical programs with vertical complementarity constraints. Journal of Industrial and Management Optimization, 2019, 15 (1) : 59-79. doi: 10.3934/jimo.2018032
[17]	Zheng-Hai Huang, Jie Sun. A smoothing Newton algorithm for mathematical programs with complementarity constraints. Journal of Industrial and Management Optimization, 2005, 1 (2) : 153-170. doi: 10.3934/jimo.2005.1.153
[18]	Yong Xia, Yu-Jun Gong, Sheng-Nan Han. A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 185-195. doi: 10.3934/naco.2015.5.185
[19]	Gui-Hua Lin, Masao Fukushima. A class of stochastic mathematical programs with complementarity constraints: reformulations and algorithms. Journal of Industrial and Management Optimization, 2005, 1 (1) : 99-122. doi: 10.3934/jimo.2005.1.99
[20]	Yongchao Liu. Quantitative stability analysis of stochastic mathematical programs with vertical complementarity constraints. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 451-460. doi: 10.3934/naco.2018028

orrwhict1950.blogspot.com

Source: https://www.aimsciences.org/article/doi/10.3934/jimo.2017064

Share this post