CGAL users discussion list

[Oren Ben-Kiki <>]

I am writing a program that needs to solve many related quadratic minimization problems with linear constraints. Essentially the program constructs an initial (sparse) problem and incrementally adds new variables and constraints to it, calling CGAL::solve_quadratic_program at each step. The expected number of steps is large (thousands of solver calls).

If it matters, my problem is of the form minimize(sum w_i * x_i^2), where w_i >= 0, subject to x_i >= 0, and some linear constraints A * X </<=/=/>/>= B (where A is very sparse). The size of the problem starts small and scales up to hundreds, possibly thousands of variables and constraints.

I'm still at early stages of implementing the program so I don't have reliable profiling data yet, but I expect it to spend most of its time in the solver, so speeding it up would be crucial for performance.

Each next step's solution values for most of the variables shared with the previous step, would be identical or very close to the previous solution's values. It would therefore seems useful to provide an initial guess for these variables, to speed up computing the new solution.

Looking at the API I don't see a way to provide such an initial guess. Searching found https://stackoverflow.com/questions/43380565/give-an-initial-guess-to-the-quadratic-programming-solver-of-cgal which has gone unanswered for 5 years, which doesn't look promising...

So, I guess there is no way to provide such an initial guess? Is this something that can be faked somehow? Is there some alternative approach I could use?

In addition - I love the fact CGAL allows me to specify iterators to provide the very sparse matrix A, since writing my own iterator makes it easy to describe an A' = extension of A without copying all the data of A.

However... does the internal solver benefit at all from sparseness? The iterator API hints that the solver treats the problem as dense (that is, the iterators return every element, even the zero ones, instead of returning the next non-zero element). Unless the solver does something smart with the returned zero values?

So, would I be better off using a sparse solver instead?

Looking around I saw IPOPT which is a more general NPL solver, but seems to benefit directly from sparseness, and allows for an initial guess. But it seems there's no easy way to "extend" an existing problem with additional variables and constraints. Also, being a general NPL solver, it probably will be less efficient for simple QP problems than a dedicated QP solver...?

I don't suppose there's such a thing as a:
A. Dedicated QP solver,
B. Which allows providing one's own iterators (to allow extending problem instances),
C. Benefits from sparseness,

D. Allows specifying an initial guess,

E. Is open-source...

So I have to give up _some_ of the above. CGAL seems fails C and D; IOPT fails A and B. I have no idea which would be more important for the actual performance (other than implementing both and measuring, which is a non-trivial amount of work).

Any advice would be appreciated!

Thanks,

Oren Ben-Kiki