×

A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems. (English) Zbl 1342.90123

Summary: We propose an efficient computational method for linearly constrained quadratic optimization problems (QOPs) with complementarity constraints based on their Lagrangian and doubly nonnegative (DNN) relaxation and first-order algorithms. The simplified Lagrangian-completely positive programming (CPP) relaxation of such QOPs proposed by Arima, Kim, and Kojima in 2012 takes one of the simplest forms, an unconstrained conic linear optimization problem with a single Lagrangian parameter in a CPP matrix variable with its upper-left element fixed to 1. Replacing the CPP matrix variable by a DNN matrix variable, we derive the Lagrangian-DNN relaxation, and establish the equivalence between the optimal value of the DNN relaxation of the original QOP and that of the Lagrangian-DNN relaxation. We then propose an efficient numerical method for the Lagrangian-DNN relaxation using a bisection method combined with the proximal alternating direction multiplier and the accelerated proximal gradient methods. Numerical results on binary QOPs, quadratic multiple knapsack problems, maximum stable set problems, and quadratic assignment problems illustrate the superior performance of the proposed method for attaining tight lower bounds in shorter computational time.

MSC:

90C20 Quadratic programming
90C25 Convex programming
90C26 Nonconvex programming, global optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arima, N., Kim, S., Kojima, M.: A quadratically constrained quadratic optimization model for completely positive cone programming. SIAM J. Optim. 23, 2320-2340 (2013) · Zbl 1304.90152 · doi:10.1137/120890636
[2] Arima, N., Kim, S., Kojima, M.: Simplified copositive and Lagrangian relaxations for linearly constrained quadratic optimization problems in continuous and binary variables. Pac. J. Optim. 10, 437-451 (2013) · Zbl 1327.90161
[3] Arima, N., Kim, S., Kojima, M.: Extension of completely positive cone relaxation to polynomial optimization, Research report B-471, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Tokyo, Feb 2013 · Zbl 1336.90068
[4] Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183-202 (2009) · Zbl 1175.94009 · doi:10.1137/080716542
[5] Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999) · Zbl 1015.90077
[6] BIQMAC Library. http://www.biqmac.uni-klu.ac.at/biqmaclib.html · Zbl 1206.90088
[7] Borcher, B.: CSDP, a C library for semidefinite programming. Optim. Methods Softw. 11, 613-623 (1999) · Zbl 0973.90524 · doi:10.1080/10556789908805765
[8] 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
[9] Burer, S.: On the copositive representation of binary and continuous non-convex quadratic programs. Math. Program. 120, 479-495 (2009) · Zbl 1180.90234 · doi:10.1007/s10107-008-0223-z
[10] Burer, S.: Optimizating a polyhedral-semidefinite relaxation of completely positive programs. Math. Program. Comput. 2, 1-19 (2010) · Zbl 1190.90135 · doi:10.1007/s12532-010-0010-8
[11] Chen, C., He, B., Ye, Y., Yuan X.: The direct extension of admm for multi-block convex minimization problems is not necessarily convergent. Math. Program. (2015, to appear) · Zbl 1332.90193
[12] 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
[13] Dickinson, P.J.C., Eichfelder, G., Povh, J.: Erratum to: “On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets” [Optim. Letters, 2012]. Optimization Online (2012). http://www.optimization-online.org/DB_HTML/2012/09/3598.html · Zbl 1298.90063
[14] DIMACS, Second DIMACS Challenge, Test instances available at: http://dimacs.rutgers.edu/Challenges/ · Zbl 0973.90524
[15] Dür, M., Still, G.: Interior points of the completely positive cone. Electron. J. Linear Algebra 17, 28-33 (2008) · Zbl 1151.15019
[16] Eichfelder, G., Povh, J.: On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets. Optim. Lett. (2012). doi:10.1007/s11590-012-0450-3 · Zbl 1280.90114 · doi:10.1007/s11590-012-0450-3
[17] Fazel, M., Pong, Ti. K., Sun, D., Tseng, P.: Hankel matrix rank minimization with applications to system identification and realization. SIAM J. Matrix Anal. A 34, 946-977 (2013) · Zbl 1302.90127
[18] Fujisawa, K., Fukuda, M., Kobayashi, K., Kojima, M., Nakata, K., Nakata, M., Yamashita, M.: SDPA (semidefinite programming algorithm) user’s manual—version 7.05. Research report B-448, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Tokyo (2008) · Zbl 1167.90009
[19] Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite element approximations. Comput. Math. Appl. 2, 17-40 (1976) · Zbl 0352.65034 · doi:10.1016/0898-1221(76)90003-1
[20] Ge, D., Ye. Y.: On doubly positive semidefinite programming relaxations. Optimization Online (2010). http://www.optimization-online.org/DB_HTML/2010/08/2709.html · Zbl 1413.90197
[21] Jansson, C., Keil, C.: Rigorous error bounds for the optimal value in semidefinite programming. SIAM J. Numer. Anal. 46, 188-200 (2007) · Zbl 1167.90009
[22] Glowinski, R., Marroco, A.: Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité, d’une classe de problèmes de Dirichlet non linéares. Revue Francaise d’Automatique, Informatique et Recherche Opérationelle 9(R-2), 41-76 (1975) · Zbl 0368.65053
[23] Moreau, J.J.: Décomposition orthogonale d’un espace hilbertien selon deux cones mutuellement polaires. C. R. Acad. Sci. 255, 238-240 (1962) · Zbl 0109.08105
[24] Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and non-linear programming. Math. Program. 39, 117-129 (1987) · Zbl 0637.90078 · doi:10.1007/BF02592948
[25] Nesterov, Y.E., Nemirovskii, A.: Interior Point Methods for Convex Programming. SIAM, Philadelphia (1994) · Zbl 0824.90112 · doi:10.1137/1.9781611970791
[26] Povh, J., Rendl, F.: Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete Optim. 6, 231-224 (2009) · Zbl 1167.90597 · doi:10.1016/j.disopt.2009.01.002
[27] Quadratic assignment problems. http://www.seas.upenn.edu/qaplib · Zbl 0607.90026
[28] Rendl, F., Rinaldi, G., Wiegele, A.: Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math. Program. 121, 307-335 (2010) · Zbl 1184.90118 · doi:10.1007/s10107-008-0235-8
[29] 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)
[30] Sloane, N.: Challenge problems: independent sets in graphs. http://neilsloane.com/doc/graphs.html · Zbl 0352.65034
[31] Strum, J.F.: SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11 & 12, 625-653 (1999) · Zbl 0973.90526 · doi:10.1080/10556789908805766
[32] Toh, K., Todd, M.J., Tütüntü, R.H.: SDPT3—a MATLAB software package for semidefinite programming. Optim. Methods Softw. 11 & 12, 545-581 (1999) · Zbl 0997.90060 · doi:10.1080/10556789908805762
[33] Tucker, A.W.: Dual systems of homogeneous linear relations. In: Kuhn, Tucker (eds.) Linear Inequalities and Related Systems, Annals of Mathematics Studies, No. 38. Princeton University Press, Princeton (1956) · Zbl 0072.37503
[34] Wen, Z., Goldfarb, D., Yin, W.: Alternating direction augmented Lagrangian methods for semidefinite programming. Math. Program. Comput. 2, 203-230 (2010) · Zbl 1206.90088 · doi:10.1007/s12532-010-0017-1
[35] Sun, D.F., Toh, K.C., Yang, L.Q.: A convergent proximal alternating direction method of multipliers for conic programming with 4-block constraints (2014). arXiv:1404.5378 · Zbl 1328.90083
[36] Yoshise, A., Matsukawa, Y.: On optimization over the doubly nonnegative cone. In: Proceedings of 2010 IEEE Multi-conference on Systems and Control, pp. 13-19 (2010)
[37] Zhao, X.Y., Sun, D.F., Toh, K.C.: A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20, 1737-1765 (2010) · Zbl 1213.90175 · doi:10.1137/080718206
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.