4
$\begingroup$

I have a C++ program/model that in some parts already use IPOPT (with ADOL-C and ColPack) to solve some pretty large non linear problems.

Now in an other part of the program I need to solve a large amount (tens of thousand) of small quadratic problems.

I'd like to have your suggestion if you think it should be more efficient to use again IPOPT, that it is very good for large generic non-linear problems but it seems it takes too much to initialise or if you think it should be better to use a specialized quadratic programming solver that is particularly fast for small problems (and in that case a name would be appreciated).

For completeness my quadratic problem is:

min: sum_i sum_j a_i,j x_i x_j
sub
sum_i x_i = 1
x_i >= 0
sum_i x_i b_i = c

with i=j ~ 10

Problems are independent.

$\endgroup$
4
$\begingroup$

If your problems are small, you could try a simple solver with dense data structures and use stack allocation (old Fortran codes). IPOPT uses sparse data structures and indeed, it takes a relatively long time to initialize IPOPT if your problems are small. Old Fortran codes with stack allocation are surprisingly fast if you have small problems.

If the license is not an issue for you, you could look at the Harwell Subroutine Library. I belive VEO2 Minimize a quadratic function, linear constraints is likely to be good for you.

Another appealing option is the MNHL subroutine: general optimization, requiring gradient and Hessian, linear constraints from PORT3.

Interfacing C++ and Fortran codes is painful and boring but really not a rocket science. I believe these old Fortran codes are likely to be fast enough for your application. (Take it from someone who loves C++.)

If performance is an issue, I wouldn't use automatic differentiation on your quadratic program. Instead, I would hand-code the derivatives.


My I ask: What is your application? How do you get that many small quadratic programs?

$\endgroup$
  • $\begingroup$ It's a portfolio-optimisation of forest resources problem that it is embedded in a more general forest model (where I already use IPOPT for a single large market-level optimisation) but here I need it to be run for each economic agent in the model. Just for reference, for these small convex quadratic optimisations I ended up using quadprog++ (quadprog.sourceforge.net) which implements the Goldfarb-Idnani active-set dual method and it has only an optional dependency on uBoost. I can run 10.000 small problems in less than 8 seconds on a i7 laptop. Thank you. $\endgroup$ – Antonello Jan 23 '14 at 13:27
  • $\begingroup$ @Antonello Ah, you have a strictly convex quadratic program. Well, then it is different. In any case, even if my answer didn't help much, I am glad you have found an appropriate solver. $\endgroup$ – Ali Jan 23 '14 at 13:32

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.