## Algorithm / library for *almost* linear programming?

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

Moderators: phlip, Moderators General, Prelates

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

### Algorithm / library for *almost* linear programming?

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

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

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

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.

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

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

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

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

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

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

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

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

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 12 guests