Quadratic factorization heuristics for copositive programming. (English) Zbl 1219.90134

Bomze, Immanuel M.; Jarre, Florian; Rendl, Franz

Math. Program. Comput. 3, No. 1, 37-57 (2011).

Summary: Copositive optimization problems are particular conic programs: optimize linear forms over the copositive cone subject to linear constraints. Every quadratic program with linear constraints can be formulated as a copositive program, even if some of the variables are binary. So this is an NP-hard problem class. While most methods try to approximate the copositive cone from within, we propose a method which approximates this cone from outside. This is achieved by passing to the dual problem, where the feasible set is an affine subspace intersected with the cone of completely positive matrices, and this cone is approximated from within. We consider feasible descent directions in the completely positive cone, and regularized strictly convex subproblems. In essence, we replace the intractable completely positive cone with a nonnegative cone, at the cost of a series of nonconvex quadratic subproblems. Proper adjustment of the regularization parameter results in short steps for the nonconvex quadratic programs. This suggests to approximate their solution by standard linearization techniques. Preliminary numerical results on three different classes of test problems are quite promising.

MSC:

90C27

Combinatorial optimization

Keywords:

combinatorial optimization; copositive programs; clique number

Software:

DIMACS; Matlab

References:

[1]	Berman A., Shaked-Monderer N.: Completely positive matrices. World Scientific, Singapore (2003) · Zbl 1030.15022
[2]	Bomze I.M., Dür M., de Klerk E., Quist A., Roos C., Terlaky T.: On copositive programming and standard quadratic optimization problems. J. Glob. Optim. 18, 301–320 (2000) · Zbl 0970.90057 · doi:10.1023/A:1026583532263
[3]	Bomze, I.M., Eichfelder, G.: Copositivity detection by difference-of-convex decomposition and omega-subdivision. Available at http://www.optimization-online.org/DB_HTML/2010/01/2523.html (2010) · Zbl 1267.65060
[4]	Bomze I.M., Frommlet F., Locatelli M.: Gap, cosum, and product properties of the {\(\theta\)}’ bound on the clique number. Optimization 59, 1041–1051 (2010) · Zbl 1214.05102 · doi:10.1080/02331930903395634
[5]	Bomze I.M., Jarre F.: A note on Burer’s copositive representation of mixed-binary QPs. Optim. Lett. 4, 465–472 (2010) · Zbl 1200.90134 · doi:10.1007/s11590-010-0174-1
[6]	Bundfuss S., Dür M.: Algorithmic Copositivity Detection by Simplicial Partition. Linear Algebra Appl. 428, 1511–1523 (2008) · Zbl 1138.15007 · doi:10.1016/j.laa.2007.09.035
[7]	Bundfuss S., Dür M.: An Adaptive Linear Approximation Algorithm for Copositive Programs. SIAM J. Optim. 20, 30–53 (2009) · Zbl 1187.90187 · doi:10.1137/070711815
[8]	Burer S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120, 479–495 (2009) · Zbl 1180.90234 · doi:10.1007/s10107-008-0223-z
[9]	de Klerk E., Pasechnik D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12, 875–892 (2002) · Zbl 1035.90058 · doi:10.1137/S1052623401383248
[10]	Dickinson P.J.C.: An improved characterization of the interior of the completely positive cone. Electron. J. Linear Algebra 20, 723–729 (2010) · Zbl 1217.15019
[11]	DIMACS implementation challenges. Available at ftp://dimacs.rutgers.edu/pub/challenge/graph
[12]	Dür M., Still G.: Interior points of the completely positive cone. Electron. J. Linear Algebra 17, 48–53 (2008) · Zbl 1151.15019
[13]	Dukanovic I., Rendl F.: Copositive programming motivated bounds on the stability and chromatic numbers. Math. Program. 121, 249–268 (2010) · Zbl 1194.90109 · doi:10.1007/s10107-008-0233-x
[14]	Johnson C.R., Reams R.: Constructing copositive matrices from interior matrices. Electron. J. Linear Algebra 17, 9–20 (2008) · Zbl 1143.15023
[15]	Knuth D.E.: The sandwich theorem. Electron. J. Comb. 22, 1–48 (1994) · Zbl 0810.05065
[16]	Lovász L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory IT–25, 1–7 (1979) · Zbl 0395.94021 · doi:10.1109/TIT.1979.1055985
[17]	McEliece R.J., Rodemich E.R., Rumsey H.C.: The Lovász’ bound and some generalizations. J. Comb. Inf. Syst. Sci. 3, 134–152 (1978) · Zbl 0408.05031
[18]	Nesterov Y., Nemirovski A.: Interior point polynomial algorithms in convex programming. SIAM Publications, Philadelphia (1994) · Zbl 0824.90112
[19]	Parrilo, P.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD thesis, California Institute of Technology, USA (2000)
[20]	Povh J., Rendl F.: Copositive and semidefinite relaxations of the quadratic assignment problem. Discret. Optim. 6, 231–241 (2009) · Zbl 1167.90597 · doi:10.1016/j.disopt.2009.01.002
[21]	Schrijver A.: A comparison of the Delsarte and Lovasz bounds. IEEE Trans. Inf. Theory IT–25, 425–429 (1979) · Zbl 0444.94009 · doi:10.1109/TIT.1979.1056072
[22]	Vandenbussche D., Nemhauser G.: A branch-and-cut algorithm for nonconvex quadratic programs with box constraints. Math. Program. 102, 559–575 (2005) · Zbl 1137.90010 · doi:10.1007/s10107-004-0550-7