Algorithm / library for *almost* linear programming?

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3035
Joined: Sat May 09, 2009 11:55 pm UTC

Algorithm / library for *almost* linear programming?

Postby Qaanol » Wed Sep 07, 2016 6:59 pm UTC

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.
wee free kings

User avatar
Zamfir
I built a novelty castle, the irony was lost on some.
Posts: 7302
Joined: Wed Aug 27, 2008 2:43 pm UTC
Location: Nederland

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

Postby Zamfir » Sat Sep 10, 2016 10:08 am UTC

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.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3035
Joined: Sat May 09, 2009 11:55 pm UTC

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

Postby Qaanol » Mon Sep 12, 2016 6:10 pm UTC

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?
wee free kings

User avatar
Zamfir
I built a novelty castle, the irony was lost on some.
Posts: 7302
Joined: Wed Aug 27, 2008 2:43 pm UTC
Location: Nederland

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

Postby Zamfir » Tue Sep 13, 2016 7:00 am UTC

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

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3035
Joined: Sat May 09, 2009 11:55 pm UTC

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

Postby Qaanol » Tue Nov 01, 2016 6:09 am UTC

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.
wee free kings


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 5 guests