New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation
Tóm tắt
We consider a quadratic program with a few negative eigenvalues (QP-r-NE) subject to linear and convex quadratic constraints that covers many applications and is known to be NP-hard even with one negative eigenvalue (QP1NE). In this paper, we first introduce a new global algorithm (ADMBB), which integrates several simple optimization techniques such as alternative direction method, and branch-and-bound, to find a globally optimal solution to the underlying QP within a pre-specified
$$\epsilon $$
-tolerance. We establish the convergence of the ADMBB algorithm and estimate its complexity. Second, we develop a global search algorithm (GSA) for QP1NE that can locate an optimal solution to QP1NE within
$$\epsilon $$
-tolerance and estimate the worst-case complexity bound of the GSA. Preliminary numerical results demonstrate that the ADMBB algorithm can effectively find a global optimal solution to large-scale QP-r-NE instances when
$$r\le 10$$
, and the GSA outperforms the ADMBB for most of the tested QP1NE instances. The software reviewed as part of this submission was given the DOI (digital object identifier)
https://doi.org/10.5281/zenodo.1344739
.
Tài liệu tham khảo
Anjos, M .F., Lasserre, J .B.: Handbook of Semidefinite, Conic and Polynomial Optimization: Theory, Algorithms, Software and Applications. International Series in Operational Research and Management Science, p. 166. Springer, Berlin (2001)
Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1–122 (2010)
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)
Burer, S., Vandenbussche, D.: A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math. Program. 113(2), 259–282 (2008)
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)
Cambini, R., Salvi, F.: A branch and reduce approach for solving a class of low rank d.c. programs. J. Comput. Appl. Math. 233, 492–501 (2009)
Cambini, R., Salvi, F.: Solving a class of low rank d.c. programs via a branch and bound approach: a computational experience. Oper. Res. Lett. 38(5), 354–357 (2010)
Cambini, R., Sodini, C.: A finite algorithm for a particular d.c. quadratic programming problem. Ann. Oper. Res. 117(1), 33–49 (2002)
Chen, J., Burer, S.: Globally solving nonconvex quadratic programming problems via completely positive programming. Math. Program. Comput. 4, 33–52 (2012)
Floudas, C .A., Visweswaran, V.: Quadratic optimization. In: Horst, R., Pardalos, P.M. (eds.) Handbook of Global Optimization, pp. 217–270. Kluwer Academic Publishers, Boston (1994)
Gorski, J., Pfeuffer, F., Klamroth, K.: Biconvex sets and optimization with biconvex functions: a survey and extensions. Math. Methods Oper. Res. 66, 373–407 (2007)
Gould, N .I .M., Toint, P .L.: Numerical methods for large-scale non-convex quadratic programming. In: Siddiqi, A.H., Kocvara, M. (eds.) Trends in Industrial and Applied Mathematics. Applied Optimization, vol. 72, pp. 149–179. Springer, Boston (2002)
Goyal, V., Genc-Kaya, L., Ravi, R.: An FPTAS for minimizing the product of two non-negative linear cost functions. Math. Program. 126, 401–405 (2011)
Horst, R., Thoai, N.V.: DC programming: overview. J. Optim. Theory Appl. 103(1), 1–43 (1999)
IBM ILOG CPLEX. IBM ILOG CPLEX 12.3 User’s Manual for CPLEX, 89 (2011)
Kim, S., Kojima, M.: Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations. Comput. Optim. Appl. 26, 143–154 (2003)
Kojima, M., Tunçel, L.: Cones of matrices and successive convex relaxations of nonconvex sets. SIAM J. Optim. 10, 750–778 (2000)
Kojima, M., Tunçel, L.: Discretization and localization in successive convex relaxation methods for nonconvex quadratic optimization. Math. Program. 89(1), 79–111 (2000)
Konno, H.: A cutting plane algorithm for solving bilinear programs. Math. Program. 11, 14–27 (1976)
Lasserre, J.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796–817 (2001)
Laurent, M.: A comparison of the sherali-adams, lovász-schrijver, and lasserre relaxations for 0–1 programming. Math. Oper. Res. 28(3), 470–496 (2003)
Le Thi, H.A., Pham, T.: Dinh. Solving a class of linearly constrained indefinite quadratic problems by D.C. algorithms. J. Glob. Optim. 11, 253–285 (1997)
Le Thi, H.A., Pham Dinh, T.: A branch and bound method via d.c. optimization algorithms and ellipsoidal technique for box constrained nonconvex quadratic problems. J. Glob. Optim. 13, 171–206 (1998)
Le Thi, H.A.: An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints. Math. Program. Ser. A 87(3), 401–426 (2000)
Loridan, P.: Necessary conditions for \(\epsilon \)-optimality. Math. Program. Stud. 19, 140–152 (1982)
Lovász, L., Schrijver, A.: Cones of matrices and set-functions and 0–1 optimization. SIAM J. Optim. 2(1), 166–190 (1991)
Matsui, T.: NP-hardness of linear multiplicative programming and related problems. J. Glob. Optim. 9(2), 113–119 (1996)
Nie, J.: Optimality conditions and finite convergence of lasserre’s hierarchy. Math. Program. 146(1–2), 97–121 (2014)
Palacios-Gomez, F., Lasdon, L., Enquist, M.: Nonlinear optimization by successive linear programming. Manag. Sci. 28(10), 1106–1120 (1982)
Pardalos, P.M., Rodgers, G.: Computational aspects of a branch and bound algorithm for quadratic zero-one programming. Computing 45, 131–144 (1990)
Pardalos, P.M.: Global optimization algorithms for linearly constrained indefinite quadratic problems. Comput. Math. Appl. 21, 87–97 (1991)
Pardalos, P.M., Schnitger, G.: Checking local optimality in constrained quadratic programming is NP-hard. Oper. Res. Lett. 7(1), 33–35 (1988)
Pardalos, P.M., Vavasis, S.A.: Quadratic programming with one negative eigenvalue is NP-hard. J. Glob. Optim. 1, 15–22 (1991)
Peng, J., Zhu, T.: A nonlinear semidefinite programming approch for the worst-case linear optimization under uncertainties. Math. Program. 152(1), 593–614 (2015)
Pham Dinh, T., Le Thi, H. A.: Recent advances in DC programming and DCA. In: Transactions on Computational Intelligence XIII, pp. 1–37. Springer, Berlin (2014)
Sahinidis, N.V.: BARON: a general purpose global optimization software package. J. Glob. Optim. 8, 201–205 (1996)
Saxena, A., Bonami, P., Lee, J.: Convex relaxation of non-convex mixed integer quadratically constrained programs: extended formulations. Math. Program. Ser. B 124, 383–411 (2010)
Saxena, A., Bonami, P., Lee, J.: Convex relaxation of nonconvex mixed integer quadratically constrained programs: projected formulations. Math. Program. Ser. A 130, 359–413 (2011)
Sherali, H., Adams, W.: A hierarchy of relaxation between the continuous and convex hull representations. SIAM J. Discret. Math. 3, 411–430 (1990)
Sherali, H.D., Tuncbilek, C.H.: A reformulation-convexification approach for solving nonconvex quadratic programming problems. J. Global Optim. 7(1), 1–31 (1995)
Vandenbussche, D., Nemhauser, G.: A branch-and-cut algorithm for nonconvex quadratic programming with box constraints. Math. Program. 102, 559–575 (2005)
Vandenbussche, D., Nemhauser, G.: A polyhedral study of nonconvex quadratic programs with box constraints. Math. Program. 102(3), 531–557 (2005)
Vavasis, S.A.: Approximation algorithms for indefinite quadratic programming. Math. Program. 57, 279–311 (1992)
Visweswaran, V., Floudas, C.: New properties and computational improvement of the GOP algorithm for problems with quadratic objective function and constraints. J. Glob. Optim. 3(3), 439–462 (1993)
Wolkowicz, H., Saigal, R., Vandenberghe, L.: Handbook of Semidefinite Programming. Kluwer Academic Publishers, Boston (2000)
Ye, Y.: On the complexity of approximating a KKT point of quadratic programming. Math. Program. 80, 195–211 (1998)
Zhang, S.: Quadratic maximization and semidefinite relaxation. Math. Program. 87, 453–465 (2000)
Zhang, Y.J., So, A.M.-C.: Optimal spectrum sharing in MIMO cognitive radio networks via semidefinite programming. IEEE J. Sel. Areas Commun. 29, 362–373 (2011)