# 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}.$$

September 6, 2012 at 6:35 pm |