COMPUTING KARMARKAR＇S PROJECTIONS QUICKLY BY USING MATRIX FACTORIZATION

in this paper we compute Karmarkar‘s projections quickly using MoorePenrose g-inverse and matrix factorization. So the computation work of (A^T D^2 A)^-1 is decreased.     

A standard form variant,and safeguarded linesearch,for the modified Karmarkar algorithm

In his original analysis of the projective algorithm for linear programming, Karmarkar proposed a modified method which improved the worst-case arithmetic complexity of the original algorithm by a factor of . Karmarkar's analysis of the improvement is based on a primal-dual formulation, and requires that small steps be taken on each iteration. However, in practice the original algorithm can be easily applied to standard form problems, and is considerably improved by performing a linesearch on each iteration, generally leading to much larger steps. We show here that by incorporating a simple safeguard, a linesearch may be performed in the modified algorithm while retaining the complexity improvement over the original algorithm. We then show that the modified algorithm, with safeguarded linesearch, can be applied directly to a standard form linear program with unknown optimal objective value. The resulting algorithm enjoys a complexity advantage over standard form variants of the original algorithm.     

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).     

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.     

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.     

A relaxed version of Karmarkar's method

A relaxed version of Karmarkar's method is developed. This method is proved to have the same polynomial time complexity as Karmarkar's method and its efficient implementation using inexact projections is discussed. Computational results obtained using a preliminary implementation of the method are presented which indicate that the method is practicable.This research was supported in part by NSF Grants CDR 84-21402 and DMS-85-12277 and ONR Contract N00014-87-K-0214.     

Karmarkar's algorithm with improved steps

We define a function of the interior of the feasible region of Karmarkar's canonical linear program with the property that its supremum is bounded above by one, if and only if the optimal value of the linear program is zero. We use this function to obtain data-dependent steps for Karmarkar's algorithm. The corresponding reduction in the potential function improves upon the data-independent reduction derived by Padberg. We analyze the general step and consider its potential practical advantages.     

Exploiting special structure in Karmarkar's linear programming algorithm

We propose methods to take advantage of specially-structured constraints in a variant of Karmarkar's projective algorithm for standard form linear programming problems. We can use these constraints to generate improved bounds on the optimal value of the problem and also to compute the necessary projections more efficiently, while maintaining the theoretical bound on the algorithm's performance. It is shown how various upper-bounding constraints can be handled implicitly in this way. Unfortunately, the situation for network constraints appears less favorable.Research supported in part by National Science Foundation Grant ECS-8602534, ONR Contract N00014-87-K-0212 and the US Army Research Office through the Mathematical Sciences Institute of Cornell University.     

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.     

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.     

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.     

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.     

An O(n 3 L) primal—dual potential reduction algorithm for solving convex quadratic programs

In this paper we combine partial updating and an adaptation of Anstreicher's safeguarded linesearch of the primal—dual potential function with Kojima, Mizuno and Yoshise's potential reduction algorithm for the linear complementarity problem to obtain an O(n ³ L) algorithm for convex quadratic programming. Our modified algorithm is a long step method that requires at most O( L) steps.This research was supported in part by ONR Contract N-00014-87-K0214, NSF Grants DMS-85-12277 and DMS-91-06195.     

一种新的线性规划多项式时间算法

本文给出了一种新的线性规划多项式时间算法。在此算法中，每步可沿一族方向中的一个进行线性搜索，同时，还使用了开关策略，从而大大减少了求逆矩阵的次数，最后，证明了算法经Ｏ（ｎＬ）次迭代结束。     

A “build-down” scheme for linear programming

We propose a build-down scheme for Karmarkar's algorithm and the simplex method for linear programming. The scheme starts with an optimal basis candidate set including all columns of the constraint matrix, then constructs a dual ellipsoid containing all optimal dual solutions. A pricing rule is developed for checking whether or not a dual hyperplane corresponding to a column intersects the containing ellipsoid. If the dual hyperplane has no intersection with the ellipsoid, its corresponding column will not appear in any of the optimal bases, and can be eliminated from. As these methods iterate, is eventually built-down to a set that contains only the optimal basic columns.     

On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method

Interest in linear programming has been intensified recently by Karmarkar’s publication in 1984 of an algorithm that is claimed to be much faster than the simplex method for practical problems. We review classical barrier-function methods for nonlinear programming based on applying a logarithmic transformation to inequality constraints. For the special case of linear programming, the transformed problem can be solved by a “projected Newton barrier” method. This method is shown to be equivalent to Karmarkar’s projective method for a particular choice of the barrier parameter. We then present details of a specific barrier algorithm and its practical implementation. Numerical results are given for several non-trivial test problems, and the implications for future developments in linear programming are discussed. The research of the Stanford authors was supported by the U.S. Department of Energy Contract DE-AA03-76SF00326, PA No. DE-AS03-76ER72018; National Science Foundation Grants DCR-8413211 and ECS-8312142; the Office of Naval Research Contract N00014-85-K-0343; and the U.S. Army Research Office Contract DAAG29-84-K-0156. The research of J.A. Tomlin was supported by Ketron, Inc. and the Office of Naval Research Contract N00014-85-C-0338.     

Interior-Point Solver for Large-Scale Quadratic Programming Problems with Bound Constraints

In this paper, we present an interior-point algorithm for large and sparse convex quadratic programming problems with bound constraints. The algorithm is based on the potential reduction method and the use of iterative techniques to solve the linear system arising at each iteration. The global convergence properties of the potential reduction method are reassessed in order to take into account the inexact solution of the inner system. We describe the iterative solver, based on the conjugate gradient method with a limited-memory incomplete Cholesky factorization as preconditioner. Furthermore, we discuss some adaptive strategies for the fill-in and accuracy requirements that we use in solving the linear systems in order to avoid unnecessary inner iterations when the iterates are far from the solution. Finally, we present the results of numerical experiments carried out to verify the effectiveness of the proposed strategies. We consider randomly generated sparse problems without a special structure. Also, we compare the proposed algorithm with the MOSEK solver. Research partially supported by the MIUR FIRB Project RBNE01WBBB “Large-Scale Nonlinear Optimization.”     

An infeasible-interior-point algorithm using projections onto a convex set

We present a new class of primal-dual infeasible-interior-point methods for solving linear programs. Unlike other infeasible-interior-point algorithms, the iterates generated by our methods lie in general position in the positive orthant of ² and are not restricted to some linear manifold. Our methods comprise the following features: At each step, a projection is used to recenter the variables to the domainx _i s _i . The projections are separable into two-dimensional orthogonal projections on a convex set, and thus they are seasy to implement. The use of orthogonal projections allows that a full Newton step can be taken at each iteration, even if the result violates the nonnegativity condition. We prove that a short step version of our method converges in polynomial time.Research performed while visiting the Institut für Angewandte Mathematik, University of Würzburg, D-87074 Würzburg, Germany, as a Research Fellow of the Alexander von Humboldt Foundation.