idea of Ye allows algorithms that can greedily take bigger steps and still the
worst-case analysis applies. (In practical implementations one takes bigger
steps than the complexity analyses allow.) Ye has since shown that those
ideas extend to "projective" algorithms. In another direction, in early 1988
the linear programming community in the West discovered that the affine
scaling algorithm was proposed in 1967 by the Soviet mathematician I. I.
Dikin, and that he published a proof of convergence for it in 1974. R. J.
Vanderbei and J. C. Lagarias give an expose of Dikin's proof of convergence,
which applies under the assumption of primal nondegeneracy. One of the
difficulties of interior-point methods is that they require linear programs to
be transformed to a form that comes with an initial interior feasible solu-
tion. The paper of
Lustig presents a new method for obtaining an initial
feasible point for a linear program and its dual. E. Barnes discusses another
method for obtaining a feasible starting point for the affine scaling algorithm
and gives a convergence result for this algorithm. The paper of K. Anstre-
icher considers ellipsoids containing dual optimal solutions for a projective
scaling interior point method in the case of primal degeneracy. M. ASiC,
V. KovaEeviC-VujEic, and M. RadosavljeviC-Nikoli analyze the asymptotic
behavior of Karmarkar's algorithm, obtaining results valid for degenerate lin-
ear programs. They also propose a rounding method to go from an interior
feasible point to the exact optimal solution.
Section 3 presents results on the trajetories determined by "infinitesimal"
versions of the affine scaling and projective scaling algorithms. The paper of
C. Witzgall, P. Boggs, and P. Domich and the paper of I. Adler and R. Mon-
teiro both prove that limiting behavior exists for affine scaling trajectories.
Their results apply even to degenerate linear programs, including cases where
the convergence of the affine scaling algorithm has not yet been proved. The
paper of R. C. Monteiro analyzes the boundary behavior of projective scaling
Section 4 presents results for nonlinear programming problems. F. Jarre,
G. Sonnevend, and J. Stoer give a polynomial-time interior point method for
solving convex quadratic programming problems having convex quadratic
constraints. B. Kalantari studies the problem of finding a zero of a quadratic
form over a simplex, a problem which is NP-complete in general. He gives
a "projective" algorithm for finding a local minimum of a certain potential
function, which gives a polynomial-time algorithm for solving certain convex
quadratic programs including linear programming. S. Mehrotra and J. Sun
present an interior-point method for smooth convex programming. A. Gold-
stein gives a criterion specifying a quadratic convergence region when using
Newton's method to find a zero of a nonlinear function.
Section 5 presents results for integer programming and multi-objective pro-
gramming. The paper of N. Karmarkar gives an interior-point approach to
solving 0-1 integer programming problems. Such problems, which are NP-
complete in general, are converted to nonconvex quadratic programs on a
Previous Page Next Page