Globally solving nonconvex quadratic programming problems via completely positive programming

被引：79

作者：

Chen J. ^{[1
]}

Burer S. ^{[2
]}

机构：

[1] Mathematics and Computer Science Division, Argonne National Laboratory, Argonne

[2] Department of Management Sciences, University of Iowa, Iowa City

来源：

Mathematical Programming Computation | 2012年 / 4卷 / 01期

基金：

美国国家科学基金会;

关键词：

Branch-and-bound; Completely positive programming; Copositive programming; Global optimization; Nonconvex quadratic programming; Semidefinite programming;

D O I：

10.1007/s12532-011-0033-9

中图分类号：

学科分类号：

摘要：

Nonconvex quadratic programming (QP) is an NP-hard problem that optimizes a general quadratic function over linear constraints. This paper introduces a new global optimization algorithm for this problem, which combines two ideas from the literature-finite branching based on the first-order KKT conditions and polyhedral-semidefinite relaxations of completely positive (or copositive) programs. Through a series of computational experiments comparing the new algorithm with existing codes on a diverse set of test instances, we demonstrate that the new algorithm is an attractive method for globally solving nonconvex QP. © 2011 Springer and Mathematical Optimization Society.

引用

页码：33 / 52

页数：19

共 25 条

[1]

Belotti P., Couenne: A user's manual, (2010)

[2]

Belotti P., Lee J., Liberti L., Margot F., Wachter A., Branching and bounds tightening techniques for non-convex MINLP, Optim. Methods Softw., 24, 4-5, pp. 597-634, (2009)

[3]

Burer S., On the copositive representation of binary and continuous nonconvex quadratic programs, Math. Program., 120, 2, pp. 479-495, (2009)

[4]

Burer S., Optimizing a polyhedral-semidefinite relaxation of completely positive programs, Math. Prog. Comp., 2, 1, pp. 1-19, (2010)

[5]

Burer S., Vandenbussche D., Solving lift-and-project relaxations of binary integer programs, SIAM J. Optim., 16, 3, pp. 726-750, (2006)

[6]

Burer S., Vandenbussche D., A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations, Math. Program., 113, 2 Ser. A, pp. 259-282, (2008)

[7]

Burer S., Vandenbussche D., Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound, Comput. Optim. Appl., 43, 2, pp. 181-195, (2009)

[8]

Celis M.R., Dennis J.E., Tapia R.A., A trust region strategy for nonlinear equality constrained optimization, In: Numerical Optimization, 1984 (Boulder, Colo., 1984), pp. 71-82, (1985)

[9]

Dolan E.D., More J.J., Benchmarking optimization software with performance profiles, Math. Program., 91, 2 Ser. A, pp. 201-213, (2002)

[10]

Globallib: Gamsworld global optimization library

← 1 2 3 →