3
$\begingroup$

For a hobby project I need to solve a series of quadratic programming problems each with

  • about 500 variables
  • about 1000 constraints, each of the form $x_i-x_j\le c_{ij}$
  • the objective function is the sum of about 300 terms of the form $w_{ij}^2(x_i-x_j+d_{ij})^2$
  • about a third of the variables are ignored by the objective function, and are just there to help organize the constraints.

I imagine there must be off-the-shelf solvers that can do this, but I'm quite new to this area, and the list of solvers at Wikipedia is not really helpful in terms of selecting which one to look into. Could someone help point me towards a good choice, please?

I'm looking for something that is free and with not too much of a learning curve just to put a problem into it and get a solution. Needing to write some glue code in C/C++, Java, Perl or the like is not a showstopper, however.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Do you have any other requirements/restrictions? The gold standard QP solvers are CPLEX and Gurobi, which are commercial, but have free academic licenses. For open source solvers, IPOPT is a good general purpose nonlinear programming solver; I'd have to look around at open source QP solvers to refresh my memory. (Edit: CVXOPT is also a fine choice of open source solver, if you know Python.) $\endgroup$ – Geoff Oxberry Apr 22 '14 at 19:48
  • $\begingroup$ @Geoff: Which kind of requirements/restrictions are you envisaging? Unfortunately, since I'm not in academia those commercial solvers are not an option. $\endgroup$ – hmakholm left over Monica Apr 22 '14 at 20:51
3
$\begingroup$

cvxopt (for python) does QP, and can take advantage of sparsity (you can provide a custom KKT solver specific to your problem). An example of a custom solver is https://groups.google.com/forum/#!topic/cvxopt/W8kd3LHPwwA

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I suppose I could learn enough Python to write a wrapper that reads the problem from stdin ... but are you saying I'd have to "provide a custom KKT solver" in order to get it to handle my problem size? I don't even know what that is. $\endgroup$ – hmakholm left over Monica Apr 23 '14 at 10:04
  • $\begingroup$ Re. KKT, I found this at Wikipedia. Once I evaluate the gradients, those conditions seem to reduce to exactly the problem I had before I reformulated it as a QP problem in the hope of getting some off-the-shelf software to solve it for me. If I have to provide a custom solver for the KKT formulation of my problem, it would look like Cvxopt wouldn't actually provide any value over just using that custom solver directly? $\endgroup$ – hmakholm left over Monica Apr 23 '14 at 10:31
  • $\begingroup$ See the cvxopt documentation ( cvxopt.org/userguide/coneprog.html ) for a description of the problem. From your description, the QP problem will require solving a linear equation with a 1500x1500 matrix, so storage shouldn't be a problem. If you don't take advantage of sparsity, solving a dense matrix system takes O(N^3) time, which should take a few tenths of a second on a normal PC. You could reduce that to O(number of nonzero entries) with a custom solver, which may not be worth the extra complexity. $\endgroup$ – Ronaldo Carpio Apr 23 '14 at 11:02
  • $\begingroup$ I'm using it now, works like a charm. Thank you! $\endgroup$ – hmakholm left over Monica Apr 25 '14 at 22:27

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.