Long steps in an O(n 3 L) algorithm for linear programming

We consider partial updating in Ye's affine potential reduction algorithm for linear programming. We show that using a Goldstein—Armijo rule to safeguard a linesearch of the potential function during primal steps is sufficient to control the number of updates. We also generalize the dual step construction to apply with partial updating. The result is the first O(n ³ L) algorithm for linear programming whose steps are not constrained by the need to remain approximately centered. The fact that the algorithm has a rigorous primal-only initialization actually reduces the complexity to less than O(m ^1.5 n ^1.5 L).     

Computing Karmarkar projections quickly

The paper presents a numerical method for computing the projections for Karmarkar's new algorithm for linear programming. The method is simple to implement, fully exploits sparsity, and appears in limited experimentation to have good stability properties. Preliminary numerical experience indicates that the method promises advantages over methods that refactor a matrix at every iteration.Research sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF under Grant AFOSR-86-0170. The US Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon.This work was initiated while the author was at the Graduate School of Administration, University of California, Davis, Davis, California.     

A variant of Karmarkar's linear programming algorithm for problems in standard form

This paper presents a variant of Karmarkar's linear programming algorithm that works directly with problems expressed in standard form and requires no a priori knowledge of the optimal objective function value. Rather, it uses a variation on Todd and Burrell's approach to compute ever better bounds on the optimal value, and it can be run as a prima-dual algorithm that produces sequences of primal and dual feasible solutions whose objective function values convege to this value. The only restrictive assumption is that the feasible region is bounded with a nonempty interior; compactness of the feasible region can be relaxed to compactness of the (nonempty) set of optimal solutions.     

A variable-metric variant of the Karmarkar algorithm for linear programming

The most time-consuming part of the Karmarkar algorithm for linear programming is the projection of a vector onto the nullspace of a matrix that changes at each iteration. We present a variant of the Karmarkar algorithm that uses standard variable-metric techniques in an innovative way to approximate this projection. In limited tests, this modification greatly reduces the number of matrix factorizations needed for the solution of linear programming problems. Research sponsored by DOE DE-AS05-82ER13016, ARO DAAG-29-83-K-0035, AFOSR 85-0243. Research sponsored by ARO DAAG-29-83-K-0035, AFOSR 85-0243, Shell Development Company.     

Strict monotonicity and improved complexity in the standard form projective algorithm for linear programming

In a recent paper, Shaw and Goldfarb show that a version of the standard form projective algorithm can achieve step complexity, as opposed to the O(nL) step complexity originally demonstrated for the algorithm. The analysis of Shaw and Goldfarb shows that the algorithm, using a constant, fixed steplength, approximately follows the central trajectory. In this paper we show that simple modifications of the projective algorithm obtain the same complexity improvement, while permitting a linesearch of the potential function on each step. An essential component is the addition of a single constraint, motivated by Shaw and Goldfarb's analysis, which makes the standard form algorithm strictly monotone in the true objective.This paper was written while the author was a research fellow at the Center for Operations Research and Econometrics, Université Catholique de Louvain, Louvain-la-Neuve, Belgium. Research supported by CORE, and the Center for Advanced Studies, University of Iowa.     

A combined phase I-phase II projective algorithm for linear programming

We devise a projective algorithm which explicitly considers the constraint that an artificial variable be zero at the solution. Inclusion of such a constraint allows the algorithm to be applied to a (possibly infeasible) standard form linear program, without the addition of any bigM terms or conversion to a primal-dual problem.     

Modifying the forrest-tomlin and saunders updates for linear programming problems with variable upper bounds

The author previously described a modification of the simplex method to handle variable upper bounds implicitly. This method can easily be used when the representation of the basis inverse (e.g. a triangular decomposition of the basis) is maintained as a dense matrix in core, but appears to cause difficulties for large problems where secondary storage and packed matrices may be employed. Here we show how the Forrest-Tomlin and Saunders updating schemes, which are designed for such large problems, can be adapted.Research supported in part by a fellowship from the Alfred P. Sloan Foundation and by NSF Grant ECS82-15361.     

Modifying the forrest-Tomlin and saunders updates for linear programming problems with variable upper bounds

The author previously described a modification of the simplex method to handle variable upper bounds implicitly. This method can easily be used when the representation of the basis inverse (e.g. a triangular decomposition of the basis) is maintained as a dense matrix in core, but appears to cause difficulties for large problems where secondary storage and packed matrices may be employed. Here we show how the Fonest—Tomlin and Saunders updating schemes, which are designed for such large problems, can be adapted. Research supported in part by a fellowship from the Alfred P. Sloan Foundation and by NSF Grant ECS82-15361.     

Containing and shrinking ellipsoids in the path-following algorithm

We describe a new potential function and a sequence of ellipsoids in the path-following algorithm for convex quadratic programming. Each ellipsoid in the sequence contains all of the optimal primal and dual slack vectors. Furthermore, the volumes of the ellipsoids shrink at the ratio , in comparison to 2^–(1) in Karmarkar's algorithm and 2^–(1/n) in the ellipsoid method. We also show how to use these ellipsoids to identify the optimal basis in the course of the algorithm for linear programming.Research supported by The U.S. Army Research Office through The Mathematical Sciences Institute of Cornell University when the author was visiting at Cornell.Research supported in part by National Science Foundation Grant ECS-8602534 and Office of Naval Research Contract N00014-87-K-0212.     

On motivating the Mitchell-Todd modification of Karmarkar's algorithm for LP problems with free variables

In this note, we first observe that the Morshedi-Tapia interpretation of the Karmarkar algorithm naturally offers an extension of the Karmarkar subproblem scaling to problems with free variables. We then note that this extended scaling is precisely the scaling suggested by Mitchell and Todd for problems with free variables. Mitchell and Todd gave no motivation for or justification of this extended scaling.This research was sponsored by NSF Cooperative Agreement No. CCR-88-09615, AFOSR Grant 89-0363, DOE Grant DEFG05-86-ER25017, ARO Grant 9DAAL03-90-G-0093, and COLCIENCIAS CO: 1106-05-307-93.     

An implementation of Karmarkar's algorithm for linear programming

This paper describes the implementation of power series dual affine scaling variants of Karmarkar's algorithm for linear programming. Based on a continuous version of Karmarkar's algorithm, two variants resulting from first and second order approximations of the continuous trajectory are implemented and tested. Linear programs are expressed in an inequality form, which allows for the inexact computation of the algorithm's direction of improvement, resulting in a significant computational advantage. Implementation issues particular to this family of algorithms, such as treatment of dense columns, are discussed. The code is tested on several standard linear programming problems and compares favorably with the simplex codeMinos 4.0.     

A variation on Karmarkar’s algorithm for solving linear programming problems

The algorithm described here is a variation on Karmarkar’s algorithm for linear programming. It has several advantages over Karmarkar’s original algorithm. In the first place, it applies to the standard form of a linear programming problem and produces a monotone decreasing sequence of values of the objective function. The minimum value of the objective function does not have to be known in advance. Secondly, in the absence of degeneracy, the algorithm converges to an optimal basic feasible solution with the nonbasic variables converging monotonically to zero. This makes it possible to identify an optimal basis before the algorithm converges.     

Rank-one techniques in log-barrier function methods for linear programming

This short paper presents a primal interior-point method for linear programming. The method can be viewed as a modification of the methods developed in Refs. 1–6. In each iteration, it computes an approximately projected Newton direction and needsO(n ^2.5) arithmetic operations to make the log-barrier function significantly decrease. It requires iterations, so that the total complexity isO(n ³ L).This research was supported by the Natural Science Foundation of China and the Tian Yuan Foundation for Mathematics. We are also very grateful to the referees for the many constructive comments and corrections useful for revising this paper.     

Karmarkar's linear programming algorithm and Newton's method

This paper describes a full-dimensional version of Karmarkar's linear programming algorithm, theprojective scaling algorithm, which is defined for any linear program in ⁿ having a bounded, full-dimensional polytope of feasible solutions. If such a linear program hasm inequality constraints, then it is equivalent under an injective affine mappingJ: ^{n m} to Karmarkar's original algorithm for a linear program in ^m havingm—n equality constraints andm inequality constraints. Karmarkar's original algorithm minimizes a potential functiong(x), and the projective scaling algorithm is equivalent to that version of Karmarkar's algorithm whose step size minimizes the potential function in the step direction.The projective scaling algorithm is shown to be a global Newton method for minimizing a logarithmic barrier function in a suitable coordinate system. The new coordinate system is obtained from the original coordinate system by a fixed projective transformationy = (x) which maps the hyperplaneH _opt ={x:c, x =c ₀} specified by the optimal value of the objective function to the hyperplane at infinity. The feasible solution set is mapped under to anunbounded polytope. Letf _LB(y) denote the logarithmic barrier function associated to them inequality constraints in the new coordinate system. It coincides up to an additive constant with Karmarkar's potential function in the new coordinate system. Theglobal Newton method iterate y ^* for a strictly convex functionf(y) defined on a suitable convex domain is that pointy ^* that minimizesf(y) on the search ray {y+ v _N(y): 0} wherev _N(y) =–(² f(y))^–1(f(y)) is the Newton's method vector. If {x ^(k)} are a set of projective scaling algorithm iterates in the original coordinate system andy ^(k) =(x ^(k)) then {y ^(k)} are a set of global Newton method iterates forf _LB(y) and conversely.Karmarkar's algorithm with step size chosen to minimize the potential function is known to converge at least at a linear rate. It is shown (by example) that this algorithm does not have a superlinear convergence rate.     

A rank-one algorithm for unconstrained function minimization

A rank-one algorithm is presented for unconstrained function minimization. The algorithm is a modified version of Davidon's variance algorithm and incorporates a limited line search. It is shown that the algorithm is a descent algorithm; for quadratic forms, it exhibits finite convergence, in certain cases. Numerical studies indicate that it is considerably superior to both the Davidon-Fletcher-Powell algorithm and the conjugate-gradient algorithm.     

A primal projective interior point method for linear programming

We present a new projective interior point method for linear programming with unknown optimal value. This algorithm requires only that an interior feasible point be provided. It generates a strictly decreasing sequence of objective values and within polynomial time, either determines an optimal solution, or proves that the problem is unbounded. We also analyze the asymptotic convergence rate of our method and discuss its relationship to other polynomial time projective interior point methods and the affine scaling method.This research was supported in part by NSF Grants DMS-85-12277 and CDR-84-21402 and ONR Contract N00014-87-K0214.     

Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming

This paper presents a “standard form” variant of Karmarkar's algorithm for linear programming. The tecniques of using duality and cutting objective are combined in this variant to maintain polynomial-time complexity and to bypass the difficulties found in Karmarkar's original algorithm. The variant works with problems in standard form and simultaneously generates sequences of primal and dual feasible solutions whose objective function values converge to the unknown optimal value. Some computational results are also reported.     

A polynomial-time algorithm for a class of linear complementarity problems

Given ann × n matrixM and ann-dimensional vectorq, the problem of findingn-dimensional vectorsx andy satisfyingy = Mx + q, x 0,y 0,x _i y _i = 0 (i = 1, 2,,n) is known as a linear complementarity problem. Under the assumption thatM is positive semidefinite, this paper presents an algorithm that solves the problem in O(n ³ L) arithmetic operations by tracing the path of centers,{(x, y) S: x _i y _i = (i = 1, 2,,n) for some > 0} of the feasible regionS = {(x, y) 0:y = Mx + q}, whereL denotes the size of the input data of the problem.     

A reduced-gradient variant of Karmarkar's algorithm and null-space projections

This paper discusses the relationship between Karmarkar's new method for linear programming and the traditional simplex method. It is shown how null-space Karmarkar projections can be done using a basis matrix to compute the projections in the null space. Preliminary computational evidence shows that problems exist in the choice of a basis matrix, but that, given a basis, very inexact and computationally efficient projections are computationally sound.     

A modified layered-step interior-point algorithm for linear programming

The layered-step interior-point algorithm was introduced by Vavasis and Ye. The algorithm accelerates the path following interior-point algorithm and its arithmetic complexity depends only on the coefficient matrixA. The main drawback of the algorithm is the use of an unknown big constant in computing the search direction and to initiate the algorithm. We propose a modified layered-step interior-point algorithm which does not use the big constant in computing the search direction. The constant is required only for initialization when a well-centered feasible solution is not available, and it is not required if an upper bound on the norm of a primal—dual optimal solution is known in advance. The complexity of the simplified algorithm is the same as that of Vavasis and Ye. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Research supported in part by ONR contract N00014-94-C-0007 and the Grant-in-Aid for Scientific Research (C) 08680478 and the Grant-in-Aid for Encouragement of Young Scientists (A) 08780227 of the Ministry of Science, Education and Culture of Japan. This research was partially done while S. Mizuno and T. Tsuchiya were visiting IBM Almaden Research Center in the summer of 1995.