Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
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.
