2
$\begingroup$

In which problem category can I put a quadratic programming problem with only continuous values whereas the matrix A should be symmetric but needs not to be positive semi-definite?

minimize/maximize x' * A * x
whereas
lowerbound <= x <= upperbound

Can I reformulate it as a Mixed Integer Problem for example? Or is there some algorithm or method that can cope with this problem?

$\endgroup$
3
$\begingroup$

Like WolfgangBangerth says, it is a quadratic program. Without loss of generality, I will assume that you are minimizing your quadratic form. (If you are maximizing your quadratic form, replace that problem with minimizing the negative of your quadratic form, and what I say will still apply; where I refer to $A$ below, replace with $-A$.)

If $A$ is positive semi-definite, your program is convex, so any optimizer that converges to a local minimum will converge to a global minimum, because the two sets of minima coincide for convex programs. Furthermore, this can be accomplished in polynomial time, and can exploit the quadratic structure of your problem, so it will be fast in practice.

If $A$ has at least one negative eigenvalue, your problem is nonconvex. This statement is true no matter what your box constraints are, because the Hessian matrix of your quadratic form will be $2A$, since $A$ is symmetric. This constant Hessian matrix implies that the convexity properties of your objective function will be the same everywhere. For the case where $A$ has at least one negative eigenvalue, the problem is known to be $\mathcal{NP}$-hard.

As far as I'm aware, most methods for quadratic programming (or more generally, nonlinear programming) converge to local optima. If local optima suffice for your application, then any standard method -- active set SQP being one common approach to small- or medium-sized problems -- will work. On the other hand, if you wish to solve your nonconvex optimization problem to global optimality, then you should select another approach. Usually, a convex optimization method is augmented by methods for branching and bounding to solve nonconvex problems deterministically; this class of algorithms is slower than algorithms for convex optimization, but has the advantage of returning a global optimum instead of a local one. Libraries that will solve nonconvex problems deterministically to global optimality include BARON and LINDOGlobal, which can be accessed as part of GAMS. If you do not have a copy of GAMS, you can submit a GAMS job through the NEOS server. You could also use a nondeterministic global optimization method, if you prefer.

For examples of algorithms more tailored to nonconvex quadratic programs, see Globally solving nonconvex quadratic programs via completely positive programming, A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations, and Globally solving box-constrained quadratic programs with semidefinite-based finite branch-and-bound. These algorithms are much more tailored to your particular problem, but it looks like you'll need to roll your own implementation, which is why I suggest off-the-shelf libraries first.

$\endgroup$
  • $\begingroup$ It does look like Sam Burer leads the charge on these specific kinds of problems (your last link above). $\endgroup$ – Michael Grant Mar 7 '14 at 14:47
2
$\begingroup$

There is no need for $A$ to be positive definite. All you need is that your constraints cut off that part of the domain where the objective function becomes negative. For example, the problem $$ \min x_1^2 - x_2^2 $$ subject to constraints $-1\le x_2\le 1$ has a perfectly good solution (in fact, it has two). The only problem you have is that in general your problem may not be convex at the solution, so a straight up Newton method will not work. However, there are plenty of modifications to Newton's method that allow it to continue working even in situations like yours.

The method to use such cases is the active set SQP method. Take a look at the book by Nocedal and Wright on Numerical Optimization.

$\endgroup$
  • $\begingroup$ I'm not clear on what you mean by "All you need is that your constraints cut off that part of the domain where the objective function becomes negative." In your example, there are an infinite number of points where the objective is negative. (The set $\{(x_{1} = 0, x_{2}): -1 \leq x_{2} \leq 1\}$, for instance.) Furthermore, the Hessian of the OP's objective function will be constant, so if it has any negative eigenvalues, the objective will be nonconvex over the entire feasible set, regardless of what that feasible set is. $\endgroup$ – Geoff Oxberry Mar 7 '14 at 3:36
  • $\begingroup$ Right. What I meant is that there are sectors of the solution space where the objective function will go to $-\infty$ as we move away from the origin. The constraints must be so that they terminate these sectors for there to be a minimizer of the problem. I spoke inaccurately when I said "becomes negative". What I meant to say was "becomes more and more negative and tends to $-\infty$". $\endgroup$ – Wolfgang Bangerth Mar 7 '14 at 3:47
0
$\begingroup$

I would suggest that Wolfgang's and Geoff's answers are more general than necessary. This is a quadratic program with box constraints, and this problem has been the subject of a fair amount of specific study. For instance, here is a PDF of "On Nonconvex Quadratic Programming with Box Constraints" by S. Burer and A. Letchford. I would suggest that's the perfect place to start, and the bibliography therein will provide more direction if needed.

$\endgroup$
  • $\begingroup$ I agree that there are more specific solutions. I wish the authors of those algorithms had posted permissively-licensed implementations of their algorithms online. I've opted to post algorithms papers instead of the theory paper you posted, because I think that algorithms papers will be more immediately useful. I think the general library recommendations are most immediately useful to someone under severe time constraints; these aren't the most efficient algorithms, and one could do better with a more tailored solution if time and resources are available. $\endgroup$ – Geoff Oxberry Mar 7 '14 at 6:53
  • $\begingroup$ Fair enough, and I appreciate your edits! $\endgroup$ – Michael Grant Mar 7 '14 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.