Page 1 of 1

Algorithm / library for *almost* linear programming?

Posted: Wed Sep 07, 2016 6:59 pm UTC
by Qaanol
I have a little hobby project where I need to find an optimal strategy for a (symmetric, zero-sum) matrix game. That part is straightforward, I implemented the simplex algorithm as described in §4.5 of this paper (PDF).

However if more than one strategy is optimal, I need to select the optimal strategy which minimizes the sum-of-squares of its components. So I am looking for either an algorithm I can implement or a library I can call into, which solves this in a nice and efficient manner.

This is *just barely* a quadratic programming problem. Everything is convex and all the constraints are linear, so I’m pretty sure I don’t need the full strength / complexity of a general non-linear optimizer, and I’m hoping a more specialized routine will be faster.

I’m coding in Swift, for what it’s worth.

Re: Algorithm / library for *almost* linear programming?

Posted: Sat Sep 10, 2016 10:08 am UTC
by Zamfir
Matlab had a solver for linear least squares minimisation with linear constraints, which sounds like what you looking for. If you don't have Matlab, then scipy has linear least squares with variable bounds as constraints, which might be too restrictive for you.

CVXpy says that it has an 'LS' solver that recognises linear least squares ptoblems with linear constraints and solve them efficiently, but I have never used that.

Otherwise, just go with a quadratic solver with linear constraints(like cvxopt), those should still be much faster than a general nonlinear solver.

Re: Algorithm / library for *almost* linear programming?

Posted: Mon Sep 12, 2016 6:10 pm UTC
by Qaanol
Yeah I can’t use Matlab since I want to be able to distribute my program to other people.

The Python libraries look good, but I don’t know how to call them from Swift without embedding an entire Python interpreter in my project.

From what I’ve read, it looks like an active-set method should do what I want. Can anyone recommend an algorithm or reference paper I can use to build an implementation?

Re: Algorithm / library for *almost* linear programming?

Posted: Tue Sep 13, 2016 7:00 am UTC
by Zamfir
You might look here:
http://plato.asu.edu/sub/nonlsq.html#lsqres

There is a section ""f is quadratic in x; g,h linear (the linearly constrained least squares problem)"

"Toms 587" might be what you're after, that's this: http://dl.acm.org/citation.cfm?id=356010&picked=formats

Re: Algorithm / library for *almost* linear programming?

Posted: Tue Nov 01, 2016 6:09 am UTC
by Qaanol
I ended up implementing the Lemke-Howson algorithm for linear complementarity as described here. That paper describes both the method and how to solve quadratic programs with it.

To move variables in and out of the basis, I adapted the pivoting formulas from here. I also applied a preliminary substitution to eliminate the ∑xi = 1 constraint, so that only inequalities are involved.