April  2018, 14(2): 625-636. doi: 10.3934/jimo.2017064

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

* Corresponding author: Cheng Lu

Received  August 2016 Revised  April 2017 Published  June 2017

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.

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 & Management Optimization, 2018, 14 (2) : 625-636. doi: 10.3934/jimo.2017064
References:
[1]

L. BaiJ. 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.  Google Scholar

[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. BillionnetS. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

Y.-L. ChangJ.-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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[10]

T. HoheiselC. 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.  Google Scholar

[11]

J. HuJ. E. MitchellJ.-S. PangK. 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.  Google Scholar

[12]

X. X. HuangD. 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.  Google Scholar

[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.  Google Scholar

[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. KimM. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[21]

T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, N. J., 1970.  Google Scholar

[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.  Google Scholar

[23]

Z. WenD. 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.  Google Scholar

[24]

X.-Y. ZhaoD.-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.  Google Scholar

[25]

J. ZhouS.-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.  Google Scholar

show all references

References:
[1]

L. BaiJ. 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.  Google Scholar

[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. BillionnetS. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

Y.-L. ChangJ.-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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[10]

T. HoheiselC. 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.  Google Scholar

[11]

J. HuJ. E. MitchellJ.-S. PangK. 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.  Google Scholar

[12]

X. X. HuangD. 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.  Google Scholar

[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.  Google Scholar

[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. KimM. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[21]

T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, N. J., 1970.  Google Scholar

[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.  Google Scholar

[23]

Z. WenD. 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.  Google Scholar

[24]

X.-Y. ZhaoD.-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.  Google Scholar

[25]

J. ZhouS.-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.  Google Scholar

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}|)$nodestime (sec.)
bilevel2(29, 13, 12)134.86
bilevel2m(9, 21, 8)51.74
flp4-1(60,190, 80)38.41
flp4-2(110,270,110)115.21
flp4-3(170,380,140)130.03
flp4-4(250,550,200)167.71
Id $(m, n, |\mathcal{E}|)$nodestime (sec.)
bilevel2(29, 13, 12)134.86
bilevel2m(9, 21, 8)51.74
flp4-1(60,190, 80)38.41
flp4-2(110,270,110)115.21
flp4-3(170,380,140)130.03
flp4-4(250,550,200)167.71
Table 2.  Computation results for randomly generated QPCC Instances
$(m, n, |\mathcal{E}|)$Ave. nodesAve. CPU time (sec.)
(4, 12, 3)31.21
(15, 45, 10)59.43
(25, 55, 20)2665.21
(30,100, 40)121310.66
$(m, n, |\mathcal{E}|)$Ave. nodesAve. CPU time (sec.)
(4, 12, 3)31.21
(15, 45, 10)59.43
(25, 55, 20)2665.21
(30,100, 40)121310.66
Table 3.  Computational results for binary quadratic programs from OR-Library
$m=50, ~n=100, ~|\mathcal{E}|=50$
IdOptimal valueNodes{CPU time (sec.)
bqp50-1 $\le-2160$35641800.00
bqp50-2 $-3702$30631570.22
bqp50-3 $-4626$6919.53
bqp50-4 $-3544$767330.86
bqp50-5 $-4012$531226.87
bqp50-6 $-3693$10749.31
bqp50-7 $-4520$605247.22
bqp50-8 $-4216$771363.41
bqp50-9 $-3780$38491692.21
bqp50-10 $\le-3507$36261800.00
$m=50, ~n=100, ~|\mathcal{E}|=50$
IdOptimal valueNodes{CPU time (sec.)
bqp50-1 $\le-2160$35641800.00
bqp50-2 $-3702$30631570.22
bqp50-3 $-4626$6919.53
bqp50-4 $-3544$767330.86
bqp50-5 $-4012$531226.87
bqp50-6 $-3693$10749.31
bqp50-7 $-4520$605247.22
bqp50-8 $-4216$771363.41
bqp50-9 $-3780$38491692.21
bqp50-10 $\le-3507$36261800.00
[1]

Xuemei Chen, Julia Dobrosotskaya. Inpainting via sparse recovery with directional constraints. Mathematical Foundations of Computing, 2020, 3 (4) : 229-247. doi: 10.3934/mfc.2020025

[2]

Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020374

[3]

Knut Hüper, Irina Markina, Fátima Silva Leite. A Lagrangian approach to extremal curves on Stiefel manifolds. Journal of Geometric Mechanics, 2020  doi: 10.3934/jgm.2020031

[4]

Javier Fernández, Cora Tori, Marcela Zuccalli. Lagrangian reduction of nonholonomic discrete mechanical systems by stages. Journal of Geometric Mechanics, 2020, 12 (4) : 607-639. doi: 10.3934/jgm.2020029

[5]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

[6]

Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169

[7]

Christopher S. Goodrich, Benjamin Lyons, Mihaela T. Velcsov. Analytical and numerical monotonicity results for discrete fractional sequential differences with negative lower bound. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020269

[8]

Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015

[9]

Gongbao Li, Tao Yang. Improved Sobolev inequalities involving weighted Morrey norms and the existence of nontrivial solutions to doubly critical elliptic systems involving fractional Laplacian and Hardy terms. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020469

[10]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013

[11]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019

[12]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076

[13]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078

[14]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462

[15]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250

[16]

Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120

[17]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319

[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

[19]

Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351

[20]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (117)
  • HTML views (652)
  • Cited by (0)

Other articles
by authors

[Back to Top]