Minimizing a negative definite quadratic function with specified bounds

Question

I have the following quadratic program

$$\begin{array}{ll} \text{minimize} & f(x) = \frac{1}{2} x^T D x + c^T x\\ \text{subject to} & x_{\text{lower}} < x < x_{\text{upper}}\end{array}$$

where matrix $D$ is symmetric negative definite!

I have no problems with using symmetric positive definite matrices for $D$. I use JOptimizer's QP-solver for it. But with negative $D$ it doesn't work. (JOptimizer can deal only with convex optimization.)

How can I solve it? Does it have to be a non-convex problem solver? I found Couenne so far, which can handle non-convex MINLPs.

Answer 1

Your problem is a non convex bounds constrained quadratic programming problem. There are lots of software packages that can solve such problems. See the list of solvers at

http://plato.asu.edu/sub/nlores.html#QP-problem

Answer 2

You do realize that there are at least two problems with your goal:

• This is, in general, a problem that can have $2^N$ solutions where $N$ is the number of variables. An example is if you tried to find the solution of $$ \min_{x\in {\mathbb R}^N} \sum_{1\le i\le N} -x_i^2 \\ \text{subject to} \quad -1 \le x_i \le 1. $$ For this problem, every vertex of the hypercube $[-1,1]^N$ is a solution, and there are $2^N$ such vertices. In other words, you have a problem that is combinatorially difficult.

• Your problem is ill-posed: you state your constraints as $$ l_i < x_i < u_i $$ but this is not a closed set and so a minimizer may not exist despite the fact that you have a minimizing sequence of points that converge towards the boundary of your feasible set. You need to formulate your problem on a closed domain by requiring $$ l_i \le x_i \le u_i. $$

Answer 3

Not only is this a non-convex programming problem, it is actually a concave programming problem, i.e., the minimization of a concave function subject to convex constraints. I will assume that you have reformulated to use <= rather than < for the bound constraints.

Because your concave programming problems has a compact constraint region, there must exist at least one global minimum at an extreme point of the constraint region. See, for example, theorem 1.1 on p. 10 of "Global Optimization: Deterministic Approaches" by Reiner Horst, Hoang Tuy. So there must be a global minimum at one of the $2^v$ vertices of the box constituting the constraints, where $n$ is the dimension of $x$.. Therefore, you can solve the problem to global optimality by brute force evaluation of the objective function at all $2^n$ vertices, and choosing the vertex (or vertices) having the lowest value of the objective function. This approach will work fine if $n$ is not too big.

More generally you can solve this to global optimality using CPLEX"s QP solver, with solutiontarget set to 3 (solve to global optimality). If you are content with a locally optimal solution, you can set solutiontarget to 2. BARON can also be usesd to solve this to global optimality. As well, there are many local QP solvers (must accept non-convex problems) which can as well, in addition to some other global solvers.

Note that if you use a general purpose local nonlinear solver to solve this concave QP using a Quasi-Newton Method, and you use BFGS as the choice of Quasi-Newton method, performance may be quite poor, and it may not even succeed. That is because BFGS maintains a positive semi-definite Hessian approximation, and therefore objective function approximation, and that is a quite poor representation, for optimization purposes, of a concave function. However, the SR1 Quasi-Newton method might succeed, because its definiteness can adapt to what it "sees" based on the gradient differences.