Article Contents
Article Contents

# Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming

• * Corresponding author: Cheng Lu
• 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:

•  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

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

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

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

Tables(5)