Maximization in quadratic programming using CGAL

Question

I am using CGAL to solve some quadratic programming problems.

Assume I want to minimize x^2 for x taking values from -oo(-infinity) to +oo. This could be easily solved by doing:

      Program qp (CGAL::SMALLER, false, 0, false, 0);
      qp.set_d(0, 0, 2);

      Solution s = CGAL::solve_quadratic_program(qp, ET());

which of course will return 0 as a result. Now suppose I want to maximize x^2. In order to so, I have to minimize -x^2. But the following does not "work" in CGAL:

      Program qp (CGAL::SMALLER, false, 0, false, 0);
      qp.set_d(0, 0, -2);

      Solution s = CGAL::solve_quadratic_program(qp, ET());

as the now matrix D = [-2] is not positive semidefinite (the API for a quadratic programming problem "asks" for D to be positive semidefinite). By running the above snippet, the wrong result 0 is returned instead of -oo.

What should I do in order to maximize an objective function like x^2 in CGAL?

Answer 1

CGAL's documentation says that your objective function must be minimization of a convex function. You are trying to minimize -x^2, which is not convex - so you cannot do this with CGAL.

Furthermore, in section 10.2.2 of the documentation I've linked, it says that trying to minimize a non-convex function may not even warn you that the problem is non-convex, and instead return a message than optimal solution was found. That is, if you're going to use CGAL for QP make sure it's convex quadratic or you're going to get bad answers.

You might consider a solver that can handle non-convex nonlinear optimization. IPOPT is open source, and will work if your objective function and constraints are twice continuously differentiable. COIN-OR has several solvers (see "Optimization deterministic nonlinear") that might work for you. KNITRO is an excellent commercial solver.