Polynomial affine algorithms for linear programming

The method of steepest descent with scaling (affine scaling) applied to the potential functionq logcx — _i=1 ⁿ logx _i solves the linear programming problem in polynomial time forq n. Ifq = n, then the algorithm terminates in no more than O(n ² L) iterations; if q n + withq = O(n) then it takes no more than O(nL) iterations. A modified algorithm using rank-1 updates for matrix inversions achieves respectively O(n ⁴ L) and O(n ^3.5 L) arithmetic computions.     

Interior path following primal-dual algorithms. part I: Linear programming

We describe a primal-dual interior point algorithm for linear programming problems which requires a total of number of iterations, whereL is the input size. Each iteration updates a penalty parameter and finds the Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem. The algorithm is based on the path following idea.     

A polynomial method of approximate centers for linear programming

We present a path-following algorithm for the linear programming problem with a surprisingly simple and elegant proof of its polynomial behaviour. This is done both for the problem in standard form and for its dual problem. We also discuss some implementation strategies.This author completed this work under the support of the research grant No. 1467086 of the Fonds National Suisses de la Recherche Scientifique.     

Global convergence of the affine scaling methods for degenerate linear programming problems

In this paper we show the global convergence of the affine scaling methods without assuming any condition on degeneracy. The behavior of the method near degenerate faces is analyzed in detail on the basis of the equivalence between the affine scaling methods for homogeneous LP problems and Karmarkar's method. It is shown that the step-size 1/8, where the displacement vector is normalized with respect to the distance in the scaled space, is sufficient to guarantee the global convergence of the affine scaling methods.This paper was presented at the International Symposium Interior Point Methods for Linear Programming: Theory and Practice, held on January 18–19, 1990, at the Europa Hotel, Scheveningen, the Netherlands.     

Superlinear primal-dual affine scaling algorithms for LCP

We describe an interior-point algorithm for monotone linear complementarity problems in which primal-dual affine scaling is used to generate the search directions. The algorithm is shown to have global and superlinear convergence with Q-order up to (but not including) two. The technique is shown to be consistent with a potential-reduction algorithm, yielding the first potential-reduction algorithm that is both globally and superlinearly convergent.Corresponding author. The work of this author was based on research supported by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.The work of this author was based on research supported by the National Science Foundation under grant DDM-9109404 and the Office of Naval Research under grant N00014-93-1-0234. This work was done while the author was a faculty member of the Systems and Industrial Engineering Department at the University of Arizona.     

Interior path following primal-dual algorithms. part II: Convex quadratic programming

We describe a primal-dual interior point algorithm for convex quadratic programming problems which requires a total of number of iterations, whereL is the input size. Each iteration updates a penalty parameter and finds an approximate Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem. The algorithm is based on the path following idea. The total number of arithmetic operations is shown to be of the order of O(n ³ L).     

Conical projection algorithms for linear programming

The Linear Programming Problem is manipulated to be stated as a Non-Linear Programming Problem in which Karmarkar's logarithmic potential function is minimized in the positive cone generated by the original feasible set. The resulting problem is then solved by a master algorithm that iteratively rescales the problem and calls an internal unconstrained non-linear programming algorithm. Several different procedures for the internal algorithm are proposed, giving priority either to the reduction of the potential function or of the actual cost. We show that Karmarkar's algorithm is equivalent to this method in the special case in which the internal algorithm is reduced to a single steepest descent iteration. All variants of the new algorithm have the same complexity as Karmarkar's method, but the amount of computation is reduced by the fact that only one projection matrix must be calculated for each call of the internal algorithm.Research partly sponsored by CNPq-Brazilian National Council for Scientific and Technological Development, by National Science Foundation grant ECS-857362, Office of Naval Research contract N00014-86-K-0295, and AFOSR grant 86-0116.On leave from COPPE-Federal University of Rio de Janeiro, Cx. Postal 68511, 21941 Rio de Janeiro, RJ, Brasil.     

An affine scaling algorithm for linear programming problems with inequality constraints

A primal, interior point method is developed for linear programming problems for which the linear objective function is to be maximised over polyhedra that are not necessarily in standard form. This algorithm concurs with the affine scaling method of Dikin when the polyhedron is in standard form, and satisfies the usual conditions imposed for using that method. If the search direction is regarded as a function of the current iterate, then it is shown that this function has a unique, continuous extension to the boundary. In fact, on any given face, this extension is just the value the search direction would have for the problem of maximising the objective function over that face. This extension is exploited to prove convergence. The algorithm presented here can be used to exploit such special constraint structure as bounds, ranges, and free variables without increasing the size of the linear programming problem.This paper is in final form and no version of it will be submitted for publication elsewhere.     

Improved complexity using higher-order correctors for primal-dual Dikin affine scaling

In this paper we show that the primal-dual Dikin affine scaling algorithm for linear programming of Jansen. Roos and Terlaky enhances an asymptotical $O(\sqrt n L)$ complexity by using corrector steps. We also show that the result remains valid when the method is applied to positive semi-definite linear complementarity problems.     

Primal-dual algorithms for linear programming based on the logarithmic barrier method

In this paper, we deal with primal-dual interior point methods for solving the linear programming problem. We present a short-step and a long-step path-following primal-dual method and derive polynomial-time bounds for both methods. The iteration bounds are as usual in the existing literature, namely iterations for the short-step variant andO(nL) for the long-step variant. In the analysis of both variants, we use a new proximity measure, which is closely related to the Euclidean norm of the scaled search direction vectors. The analysis of the long-step method depends strongly on the fact that the usual search directions form a descent direction for the so-called primal-dual logarithmic barrier function.This work was supported by a research grant from Shell, by the Dutch Organization for Scientific Research (NWO) Grant 611-304-028, by the Hungarian National Research Foundation Grant OTKA-2116, and by the Swiss National Foundation for Scientific Research Grant 12-26434.89.     

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

Interior point algorithms for linear programming with inequality constraints

Interior methods for linear programming were designed mainly for problems formulated with equality constraints and non-negative variables. The formulation with inequality constraints has shown to be very convenient for practical implementations, and the translation of methods designed for one formulation into the other is not trivial. This paper relates the geometric features of both representations, shows how to transport data and procedures between them and shows how cones and conical projections can be associated with inequality constraints.     

On the number of iterations of Karmarkar's algorithm for linear programming

Karmarkar's algorithm for linear programming was published in 1984, and it is highly important to both theory and practice. On the practical side some of its variants have been found to be far more efficient than the simplex method on a wide range of very large calculations, while its polynomial time properties are fundamental to research on complexity. These properties depend on the fact that each iteration reduces a potential function by an amount that is bounded away from zero, the bound being independent of all the coefficients that occur. It follows that, under mild conditions on the initial vector of variables, the number of iterations that are needed to achieve a prescribed accuracy in the final value of the linear objective function is at most a multiple ofn, wheren is the number of inequality constraints. By considering a simple example that allowsn to be arbitrarily large, we deduce analytically that the magnitude of this complexity bound is correct. Specifically, we prove that the solution of the example by Karmarkar's original algorithm can require aboutn/20 iterations. Further, we find that the algorithm makes changes to the variables that are closely related to the steps of the simplex method.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.     

A simple proof of a primal affine scaling method

In this paper, we present a simpler proof of the result of Tsuchiya and Muramatsu on the convergence of the primal affine scaling method. We show that the primal sequence generated by the method converges to the interior of the optimum face and the dual sequence to the analytic center of the optimal dual face, when the step size implemented in the procedure is bounded by 2/3. We also prove the optimality of the limit of the primal sequence for a slightly larger step size of 2q/(3q–1), whereq is the number of zero variables in the limit. We show this by proving the dual feasibility of a cluster point of the dual sequence.Partially supported by the grant CCR-9321550 from NSF.     

Updating lower bounds when using Karmarkar's projective algorithm for linear programming

We give two results related to Gonzaga's recent paper showing that lower bounds derived from the Todd-Burrell update can be obtained by solving a one-variable linear programming problem involving the centering direction and the affine direction. We show how these results may be used to update the primal solution when using the dual affine variant of Karmarkar's algorithm. This leads to a dual projective algorithm.This research was partially supported by ONR Grant Number N00014-90-J-1714.     

On lower bound updates in primal potential reduction methods for linear programming

We present a procedure for computing lower bounds for the optimal cost in a linear programming problem. Whenever the procedure succeeds, it finds a dual feasible slack and the associated duality gap. Although no projective transformations or problem restatements are used, the method coincides with the procedures by Todd and Burrell and by de Ghellinck and Vial when these procedures are applicable. The procedure applies directly to affine potential reduction algorithms, and improves on existent techniques for finding lower bounds.     

基于指数型核函数的线性规划原始对偶内点算法

给出线性规划原始对偶内点算法的一个单变量指数型核函数.首先研究了这个指数型核函数的性质以及其对应的障碍函数.其次,基于这个指数型核函数,设计了求解线性规划问题的原始对偶内点算法,得到了目前小步算法最好的理论迭代界.最后,通过数值算例比较了基于指数型核函数的原始对偶内点算法和基于对数型核函数的原始对偶内点算法的计算效果.     

AnO(\sqrt n L) iteration bound primal-dual cone affine scaling algorithm for linear programmingiteration bound primal-dual cone affine scaling algorithm for linear programming

In this paper we introduce a primal-dual affine scaling method. The method uses a search-direction obtained by minimizing the duality gap over a linearly transformed conic section. This direction neither coincides with known primal-dual affine scaling directions (Jansen et al., 1993; Monteiro et al., 1990), nor does it fit in the generic primal-dual method (Kojima et al., 1989). The new method requires main iterations. It is shown that the iterates follow the primal-dual central path in a neighbourhood larger than the conventional neighbourhood. The proximity to the primal-dual central path is measured by trigonometric functions.     

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.