Maximizing a Strictly Convex Quadratic Function Over a Convex Set

Question

I need to solve a special case of non-convex QCQP (Quadratically Constrained Quadratic Programming) with the general form:

$$ \begin{align} & \max {x^T}{A_o}x \\ & \text{s.t.}\left\{ \begin{matrix} {x^T}{A_i}x+{x^T}{a_i}+{c_i}\le 0 & i=1,\ldots,n \\ x\in L(x) & {} \\ x\ge 0 & {} \\ \end{matrix} \right. \\ \end{align} $$

Where $L(x)$ is a set of linear constraints and $A_o,A_1,\ldots,A_n\succ 0$ (positive definite). It basically involves maximizing a convex quadratic function over a convex set. I know that the solution to this problem takes place at the boundaries of the convex set and that standard methods would lead to a local optimum for such a problem. I need to know that besides from heuristics, are there any solution methods that could globally solve such a problem?

Answer 1

There are numerous deterministic global solvers capable of solving nonconvex quadratically constrained problems, if that is what you are asking. BARON, GloMIQO, BMIBNB in YALMIP, and SCIP are some of the solvers that comes to mind (all of them relying on linear programming based relaxations, branch&bound with bound propagation, cuts, etc.). Another approach is semidefinite relaxations, available in, e.g., Gloptipoly, Sparsepop, and the moment solver in YALMIP.