3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It is pretty special case of target function and restrictions. In most cases ( for example: 0 ≤xi≤1) we will get the single solution. $\endgroup$ – vadim Oct 27 '16 at 15:18
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ thank you! If anyone has experience with such (free) solvers in Java, I'll be interested to know. $\endgroup$ – colorblind Feb 2 '14 at 18:58
3
$\begingroup$

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. $$

$\endgroup$
  • $\begingroup$ to 2) thanks, I didn't understand this so far. $\endgroup$ – colorblind Feb 3 '14 at 1:28
  • $\begingroup$ to p2) I thought in practice floating point arithmetic would take care of it and didn't take it serious enough. to p1) Given your example, one of the solutions would be enough for me, e.g. [1,1]. If the algorithm could stop after finding the first solution, what I don't expect, it would be fine. For me it just has to be a correct solution within the specified bounds, I don't need all solutions. But you probably meant that the solver itself would have problems if there are too many solutions. $\endgroup$ – colorblind Feb 3 '14 at 2:54
  • 2
    $\begingroup$ On 2: In floating point arithmetic it makes no difference whether you compare with or without equality, but from a mathematical point of view it determines whether there is a solution or not. $\endgroup$ – Wolfgang Bangerth Feb 3 '14 at 15:25
  • 1
    $\begingroup$ On 1: Brian already pointed at a list of packages. I'm sure they will all not have trouble finding at least one solution. The point I was just making is that there are many (very many, indeed) solutions and if you wanted to have the global minimizer then you're going to be in trouble. If, as you say, you don't care which minimum you find, then I don't see a problem. $\endgroup$ – Wolfgang Bangerth Feb 3 '14 at 15:26
1
$\begingroup$

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.

$\endgroup$

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.