Homotopy techniques in linear programming

The author studies the solution of the linear program using a homotopy technique of nonlinear equation solving that moves through the interior of the polytopy of feasible solutions. The homotopy is defined by a family of programs of the following form: Minimize \(F_ k(x,t)=(1-t)f_ k(x)+t(c^ Tx)\), subject to \(Ax=b\) and \(x\geq 0\), where \(f_ k(x)=(x- x^ k)^ T\), \(D_ k^{-2}(x-x^ k)\), \(Ax^ k=b\), \(x^ k\geq 0\) and \(D=diag[x^ k_ 1,...,x^ k_ n]>0\). The direction from one point to the next point in this algorithm is precisely the local search direction used in the affine variant of Karmarkar's method. Finally, the author believes that the homotopy principle provides a suitable unifying framework for viewing the current algorithmic techniques for solving linear programs and as a means for formulating new algorithms.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Homotopy techniques in linear programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1091937)