Homotopy techniques in linear programming (Q1091937)

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.