×

zbMATH — the first resource for mathematics

Optimizing a polyhedral-semidefinite relaxation of completely positive programs. (English) Zbl 1190.90135
Summary: It has recently been shown [the author, Math. Program. 120, No. 2 (A), 479–495 (2009; Zbl 1180.90234)] that a large class of NP-hard nonconvex quadratic programs (NQPs) can be modeled as so-called completely positive programs, i.e., the minimization of a linear function over the convex cone of completely positive matrices subject to linear constraints. Such convex programs are NP-hard in general. A basic tractable relaxation is gotten by approximating the completely positive matrices with doubly nonnegative matrices, i.e., matrices which are both nonnegative and positive semidefinite, resulting in a doubly nonnegative program (DNP). Optimizing a DNP, while polynomial, is expensive in practice for interior-point methods. In this paper, we propose a practically efficient decomposition technique, which approximately solves the DNPs while simultaneously producing lower bounds on the original NQP. We illustrate the effectiveness of our approach for solving the basic relaxation of box-constrained NQPs (BoxQPs) and the quadratic assignment problem. For one quadratic assignment instance, a best-known lower bound is obtained. We also incorporate the lower bounds within a branch-and-bound scheme for solving BoxQPs and the quadratic multiple knapsack problem. In particular, to the best of our knowledge, the resulting algorithm for globally solving BoxQPs is the most efficient to date.

MSC:
90C26 Nonconvex programming, global optimization
90C05 Linear programming
90C22 Semidefinite programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anderson E., Bai Z., Bischof C., Blackford S., Demmel J., Dongarra J., Du Croz J., Greenbaum A., Hammarling S., McKenney A., Sorensen D.: LAPACK Users’ Guide. Society for Industrial and Applied Mathematics, Philadelphia (1999)
[2] Anstreicher K.M.: Recent advances in the solution of quadratic assignment problems. Math. Program. (Ser. B) 97(1–2), 27–42 (2003) · Zbl 1035.90067
[3] Berman A., Rothblum U.G.: A note on the computation of the CP-rank. Linear Algebra Appl. 419, 1–7 (2006) · Zbl 1105.65038
[4] Bomze I.M., de Klerk E.: Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Glob. Optim. 24(2), 163–185 (2002) Dedicated to Professor Naum Z. Shor on his 65th birthday · Zbl 1047.90038
[5] Bomze I.M., Dür M., de Klerk E., Roos C., Quist A.J., Terlaky T.: On copositive programming and standard quadratic optimization problems. J. Glob. Optim. 18(4), 301–320 (2000) GO’99 Firenze · Zbl 0970.90057
[6] Burer S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120, 479–495 (2009) · Zbl 1180.90234
[7] Burer S., Vandenbussche D.: Solving lift-and-project relaxations of binary integer programs. SIAM J. Optim. 16(3), 493–512 (2006) · Zbl 1113.90100
[8] Burer S., Vandenbussche D.: Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound. Comput. Optim. Appl. 43(2), 181–195 (2009) · Zbl 1170.90522
[9] Burkard R.E., Karisch S., Rendl F.: QAPLIB–a quadratic assignment problem library. Eur. J. Oper. Res. 55, 115–119 (1991) · Zbl 0729.90993
[10] Caprara A., Pisinger D., Toth P.: Exact solution of the quadratic knapsack problem. Inf. J. Comput. 11(2), 125–137 (1999) Combinatorial optimization and network flows · Zbl 1034.90521
[11] de Klerk E., Pasechnik D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12(4), 875–892 (2002) · Zbl 1035.90058
[12] de Klerk E., Sotirov R.: Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem. Math. Program. 122(2 Ser. A), 225–246 (2010) · Zbl 1184.90120
[13] Helmberg C., Rendl F., Weismantel R.: A semidefinite programming approach to the quadratic knapsack problem. J. Comb. Optim. 4(2), 197–215 (2000) · Zbl 0970.90075
[14] ILOG, Inc.: ILOG CPLEX 9.0, User Manual (2003)
[15] Jansson C., Chaykin D., Keil C.: Rigorous error bounds for the optimal value in semidefinite programming. SIAM J. Numer. Anal. 46(1), 180–200 (2007) · Zbl 1167.90009
[16] Moreau J.-J.: Décomposition orthogonale d’un espace hilbertien selon deux cônes mutuellement polaires. C. R. Acad. Sci. Paris 255, 238–240 (1962) · Zbl 0109.08105
[17] Murty K.G., Kabadi S.N.: Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39(2), 117–129 (1987) · Zbl 0637.90078
[18] Parrilo, P.: Structured semidefinite programs and semi-algebraic geometry methods in robustness and optimization. PhD thesis, California Institute of Technology (2000)
[19] Pisinger D.: The quadratic knapsack problem–a survey. Discret. Appl. Math. 155(5), 623–648 (2007) · Zbl 1143.90028
[20] Pisinger D., Rasmussen A., Sandvik R.: Solution of large-sized quadratic knapsack problems through aggressive reduction. Inf. J. Comput. 19(2), 280–290 (2007) · Zbl 1241.90119
[21] Povh J., Rendl F.: Copositive and semidefinite relaxations of the quadratic assignment problem. Discret. Optim. 6(3), 231–241 (2009) · Zbl 1167.90597
[22] Povh J., Rendl F., Wiegele A.: A boundary point method to solve semidefinite programs. Computing 78(3), 277–286 (2006) · Zbl 1275.90055
[23] QAPLIB. http://www.seas.upenn.edu/qaplib/
[24] Sahinidis N.V.: BARON: a general purpose global optimization software package. J. Glob. Optim. 8, 201–205 (1996) · Zbl 0856.90104
[25] Sarac, T., Sipahioglu, A.: A genetic algorithm for the quadratic multiple knapsack problem. In: Advances in Brain, Vision, and Artificial Intelligence, vol. 4729 of Lecture Notes in Computer Science, pp. 490–498. Springer, Heidelberg (2007)
[26] Sturm J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11/12(1–4), 625–653 (1999) · Zbl 0973.90526
[27] Vandenbussche D., Nemhauser G.: A branch-and-cut algorithm for nonconvex quadratic programs with box constraints. Math. Program. 102(3), 559–575 (2005) · Zbl 1137.90010
[28] Wen Z., Goldfarb D., Yin W.: Alternating Direction Augmented Lagrangian Methods for Semidefinite Programming. Manuscript, Department of Industrial Engineering and Operations Research, Columbia University, New York (2009) · Zbl 1206.90088
[29] Zhao Q., Karisch S., Rendl F., Wolkowicz H.: Semidefinite programming relaxations for the quadratic assignment problem. J. Comb. Optim. 2, 71–109 (1998) · Zbl 0904.90145
[30] Zhao, X., Sun, D., Toh, K.: A Newton-CG augmented Lagrangian method for semidefinite programming. Preprint, National University of Singapore, Singapore, Mar (2008). To appear in SIAM Journal on Optimization · Zbl 1213.90175
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.