Numeric Javascript v1.2: Linear Programming
Numeric Javascript v1.2 adds linear programming (function numeric.solveLP()).
IN> x = numeric.solveLP([1,1], /* minimize [1,1]*x */
[[-1,0],[0,-1],[-1,-2]], /* matrix of inequalities */
[0,0,-3] /* right-hand-side of inequalities */
);
numeric.trunc(x.solution,1e-12);
OUT> [0,1.5]
Click here to see this example in the Workshop.
The function numeric.solveLP(c,A,b) uses a logarithmic barrier method. In order to solve the linear problem
$$\min c^Tx \text{ such that } Ax \leq b,$$
we define the “barrier function”
$$F_a(x) = c^Tx – a\sum_i \log(b-Ax)_i,$$
where \(a>0\) is a parameter. For a given value of \(a\), we minimize \(F_a(x)\) using numeric.uncmin(), obtaining the solution \(x_a\); this value of \(x = x_a\) is an approximate solution to the linear program. The function numeric.solveLP() minimizes \(F_a(x)\) for smaller and smaller values of \(a \to 0^+\) until convergence is attained.
The function numeric.solveLP(c,A,b,Aeq,beq) is able to solve a linear program with equality and inequality constraints:
$$\min c^Tx \text{ such that } Ax \leq b \text{ and } A_{eq} x = b_{eq}.$$