Fork me on GitHub

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 */
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 |

Leave a Reply