On the asymptotic behavior of the projective rescaling algorithm for linear programming (Q750290): Difference between revisions

This paper extends some of the results of \textit{N. Megiddo} and the author [``Boundary behavior of interior point algorithms in linear programming'', Res. Rep. RJ 5319(54679), IBM Almaden Res. Center, San José/CA 1986; see also Math. Oper. Res. 14, No.1, 97-146 (1989; Zbl 0675.90050)] to include the case of the projective rescaling vector field and a discrete version which is one of Karmarkar's algorithms [see \textit{N. Karmarkar}, Combinatorica 4, 373-395 (1984; Zbl 0557.90065)]. First it is shown that under nondegeneracy conditions every interior orbit of the projective rescaling vector field is tangent to the inverse of the reduced cost vector at the optimal vertex. This is accomplished by showing that for a nondegenerate problem in Karmarkar standard form, the linear and projective rescaling vector fields agree through quadratic terms; then the results of Megiddo and Shub apply. Using the quadratic expression for a nondegenerate problem in Karmarkar standard form, the asymptotic rate of approach of the discrete algorithm to the optimum is shown to be 1-\(\alpha\gamma\) for all starting points in a cone around the central trajectory and near the optimum. Here, \[ 0<\alpha \leq \frac{1}{\sqrt{m((m-n)/n)}+\gamma (n-m)/n)}, \] where \[ \begin{pmatrix} A\\ e^ T \end{pmatrix} x= \begin{pmatrix} 0\\ 1 \end{pmatrix}\in R^{m-1}\times R=R^ m, \] \(\begin{pmatrix} A\\ e^ T \end{pmatrix}\) an \(m\times n\) matrix and \(x\geq 0\) define the polytope, and \(\gamma\) is a fixed constant. Thus the domains where the asymptotic rates of approach have been determined for the algorithms of \textit{N. Karmarkar} [loc. cit.], \textit{E. R. Barnes} [Math. Program. 36, 174-182 (1986; Zbl 0626.90052)], and \textit{J. Renegar} [ibid., Ser. A 40, No.1, 59-93 (1988; Zbl 0654.90050)] are essentially the same and the best possible rate for Karmarkar's is also essentially the same as the proven rates for the other two. See also Megiddo and the author [loc. cit.]. Finally, we end the paper with some open problems concerning Karmarkar's algorithm. Jeff Lagarias, in work in progress which was reported on at Columbia University, has a result which also implies that all orbits of the projective rescaling vector field are tangent at the optimum.