Abstract:
Nonconvex quadratic programming (QP) is a fundamental problem in global optimization. The simplest nonconvex QP problems are posed over feasible regions in R^n such as the regular simplex, the hypercube and the hypersphere. We describe recent results that provide exact convex programming representations for some of these cases, including the simplex for n \le 4 and the hypercube for n \le 3. For the case of the hypercube, computational results show that the same methodology that provides an exact representation in low dimensions often gives tight bounds in higher dimensions. Optimization of a nonconvex quadratic objective over the hypersphere is often referred to as the trust-region subproblem (TRS) and is well-known to be equivalent to a convex programming problem. We show that extensions of TRS involving the addition of one linear constraint or two parallel linear constraints can also be posed as convex programming problems. The same methodology used to obtain these representations also obtains strong bounds for the two-trust region-subproblem (TTRS) that adds a second ellipsoidal constraint to TRS.

References:

K.M. Anstreicher and S. Burer. Computable representations for convex hulls of low-dimensional quadratic forms. Math. Prog. B 124:33-43, 2010.
S. Burer and K.M. Anstreicher. Second-order-cone constraints for extended trust-region subproblems. Working paper, Dept. of Management Sciences, University of Iowa, March 2011.
S.Burer and A.N. Letchford. On nonconvex quadratic programming with box constraints. SIAM J. Optim. 20:1073-1089, 2009.
J.J. More and D.C. Sorensen. Computing a trust region step. SIAM J. Sci. Statist. Comput. 4:553-572, 1983.
F. Rendl and H. Wolkowicz. A semidefinite framework for trust region subproblems with applications to large scale minimization. Math. Prog. B 77:273-299, 1997.
J.F. Sturm and S. Zhang. On cones of nonnegative quadratic functions. Math. Oper. Res. 28:246-267, 2003.
Y. Ye. A new complexity result on minimization of a quadratic function with a sphere constraint. In C. Floudas and P. Pardalos, eds., Recent Advances in Global Optimization, Princeton University Press, Princeton NJ, 1992.
Y. Ye and S. Zhang. New results on quadratic minimization. SIAM J. Optim. 14:245-267, 2003.
Y. Yuan. On a subproblem of trust region algorithms for constrained optimization. Math. Prog. 47:53-63, 1990.