Fork me on GitHub

Numeric.js version 1.2 introduced linear programming, ie. solving the problem
$$\min_x c^Tx \text{ such that } Ax \leq b,$$
where \(c,A,b\) are given and \(x\) is the unknown. The algorithm is a logarithmic barrier method. The initial implementation used numeric.uncmin() to solve the barrier problem; the overall algorithm turned out to be very slow. Version 1.2.3 improves this algorithm by embedding the Newton iteration into the main loop of numeric.solveLP() and tuning it appropriately.

The barrier function is:
$$f_\alpha(x) = c^T x + \alpha\left({1 \over 2}x^Tx – \sum_i \log (Ax-b)_i\right),$$
where \(\alpha>0\) is a relaxation parameter. The solution to the linear programming problem is found by letting \(\alpha \to 0^+\). The minimum of \(f_{\alpha}(x)\) is approximated by searching in the Newton search direction. The parameter \(\alpha>0\) is reset at every Newton iteration step.

This new algorithm appears to run about ~100 times faster than the previous one.

September 23, 2012 at 3:04 pm |

2 Responses to “Numeric.js 1.2.3: faster linear programming”

  1. This looks fantastic! Thank you for all the hard work on this awesome library. I hope to be posting an entry soon on a neat project I’m working on, made using Numeric!

Leave a Reply to sloisel