# Numeric.js 1.2.3: faster linear programming

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 comments
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!

Looking forward to it!