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.

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

**Moderators:** phlip, Moderators General, Prelates

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

wee free kings

- Zamfir
- I built a novelty castle, the irony was lost on some.
**Posts:**7458**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.

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?

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?

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:**7458**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

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?

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 ∑x

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 ∑x

_{i}= 1 constraint, so that only inequalities are involved.wee free kings

### Who is online

Users browsing this forum: No registered users and 5 guests