Superlinear convergence of infeasible-interior-point methods for linear programming

At present the interior-point methods of choice are primal—dual infeasible-interior-point methods, where the iterates are kept positive, but allowed to be infeasible. In practice, these methods have demonstrated superior computational performance. From a theoretical point of view, however, they have not been as thoroughly studied as their counterparts — feasible-interior-point methods, where the iterates are required to be strictly feasible. Recently, Kojima et al., Zhang, Mizuno and Potra studied the global convergence of algorithms in the primal—dual infeasible-interior-point framework. In this paper, we continue to study this framework, and in particular we study the local convergence properties of algorithms in this framework. We construct parameter selections that lead toQ-superlinear convergence for a merit function andR-superlinear convergence for the iteration sequence, both at rate 1 + where can be arbitrarily close to one.Research supported in part by NSF DMS-9102761 and DOE DE-FG05-91ER25100.Corresponding author.     

The s-monotone index selection rules for pivot algorithms of linear programming

In this paper we introduce the concept of s-monotone index selection rule for linear programming problems. We show that several known anti-cycling pivot rules like the minimal index, Last-In–First-Out and the most-often-selected-variable pivot rules are s-monotone index selection rules. Furthermore, we show a possible way to define new s-monotone pivot rules. We prove that several known algorithms like the primal (dual) simplex, MBU-simplex algorithms and criss-cross algorithm with s-monotone pivot rules are finite methods.     

Complete characterizations of stable Farkas’ lemma and cone-convex programming duality

We establish necessary and sufficient conditions for a stable Farkas’ lemma. We then derive necessary and sufficient conditions for a stable duality of a cone-convex optimization problem, where strong duality holds for each linear perturbation of a given convex objective function. As an application, we obtain stable duality results for convex semi-definite programs and convex second-order cone programs. The authors are grateful to the referees for their valuable suggestions and helpful detailed comments which have contributed to the final preparation of the paper. The first author was supported by the Australian Research Council Linkage Program. The second author was supported by the Basic Research Program of KOSEF (Grant No. R01-2006-000-10211-0).     

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.     

Parametric linear programming and anti-cycling pivoting rules

The traditional perturbation (or lexicographic) methods for resolving degeneracy in linear programming impose decision rules that eliminate ties in the simplex ratio rule and, therefore, restrict the choice of exiting basic variables. Bland's combinatorial pivoting rule also restricts the choice of exiting variables. Using ideas from parametric linear programming, we develop anticycling pivoting rules that do not limit the choice of exiting variables beyond the simplex ratio rule. That is, any variable that ties for the ratio rule can leave the basis. A similar approach gives pivoting rules for the dual simplex method that do not restrict the choice of entering variables.Supported in part by grant ECS-83-6224 from the Systems Theory and Operations Research Division of the National Science Foundation.Supported in part by Presidential Young Investigator grant 8451517-ECS of the National Science Foundation.     

Interior-point algorithms for semi-infinite programming

In order to study the behavior of interior-point methods on very large-scale linear programming problems, we consider the application of such methods to continuous semi-infinite linear programming problems in both primal and dual form. By considering different discretizations of such problems we are led to a certain invariance property for (finite-dimensional) interior-point methods. We find that while many methods are invariant, several, including all those with the currently best complexity bound, are not. We then devise natural extensions of invariant methods to the semi-infinite case. Our motivation comes from our belief that for a method to work well on large-scale linear programming problems, it should be effective on fine discretizations of a semi-infinite problem and it should have a natural extension to the limiting semi-infinite case.Research supported in part by NSF, AFORS and ONR through NSF grant DMS-8920550.     

Optimal stopping,exponential utility,and linear programming

This paper uses linear programming to compute an optimal policy for a stopping problem whose utility function is exponential. This is done by transforming the problem into an equivalent one having additive utility and nonnegative (not necessarily substochastic) transition matrices.Research was supported by NSF Grant ENG 76-15599.     

An iterative approach to solve multiobjective linear fractional programming problems

This paper suggests an iterative parametric approach for solving multiobjective linear fractional programming (MOLFP) problems which only uses linear programming to obtain efficient solutions and always converges to an efficient solution. A numerical example shows that this approach performs better than some existing algorithms. Randomly generated MOLFP problems are also solved to demonstrate the performance of new introduced algorithm.     

Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming

We propose to compute the search direction at each interior-point iteration for a linear program via a reduced augmented system that typically has a much smaller dimension than the original augmented system. This reduced system is potentially less susceptible to the ill-conditioning effect of the elements in the (1,1) block of the augmented matrix. A preconditioner is then designed by approximating the block structure of the inverse of the transformed matrix to further improve the spectral properties of the transformed system. The resulting preconditioned system is likely to become better conditioned toward the end of the interior-point algorithm. Capitalizing on the special spectral properties of the transformed matrix, we further proposed a two-phase iterative algorithm that starts by solving the normal equations with PCG in each IPM iteration, and then switches to solve the preconditioned reduced augmented system with symmetric quasi-minimal residual (SQMR) method when it is advantageous to do so. The experimental results have demonstrated that our proposed method is competitive with direct methods in solving large-scale LP problems and a set of highly degenerate LP problems. Research supported in parts by NUS Research Grant R146-000-076-112 and SMA IUP Research Grant.     

A unified approach to infeasible-interior-point algorithms via geometrical linear complementarity problems

There are many interior-point algorithms for LP (linear programming), QP (quadratic programming), and LCPs (linear complementarity problems). While the algebraic definitions of these problems are different from each other, we show that they are all of the same general form when we define the problems geometrically. We derive some basic properties related to such geometrical (monotone) LCPs and based on these properties, we propose and analyze a simple infeasible-interior-point algorithm for solving geometrical LCPs. The algorithm can solve any instance of the above classes without making any assumptions on the problem. It features global convergence, polynomial-time convergence if there is a solution that is smaller than the initial point, and quadratic convergence if there is a strictly complementary solution.This research was performed while the first author was visiting the Institute of Applied Mathematics and Statistics, Würzburg University as a Research Fellow of the Alexander von Humboldt Foundation.     

Neighborhood-following algorithms for linear programming

In this paper, we present neighborhood-following algorithms for linear programming. When the neighborhood is a wide neighborhood, our algorithms are wide neighborhood primal-dual interior point algorithms. If the neighborhood degenerates into the central path, our algorithms also degenerate into path-following algorithms. We prove that our algorithms maintain the O(n~(1/2)L)-iteration complexity still, while the classical wide neighborhood primal-dual interior point algorithms have only the O(nL)-iteration complexity. We also proved that the algorithms are quadratic convergence if the optimal vertex is nondegenerate. Finally, we show some computational results of our algorithms.     

Checking solvability of systems of interval linear equations and inequalities via mixed integer programming

This paper deals with the problems of checking strong solvability and feasibility of linear interval equations, checking weak solvability of linear interval equations and inequalities, and finding control solutions of linear interval equations. These problems are known to be NP$\mathit{NP}$-hard. We use some recently developed characterizations in combination with classical arguments to show that these problems can be equivalently stated as optimization tasks and provide the corresponding linear mixed 0–1 programming formulations.     

Theorems of the alternative for conic integer programming

Farkas’ Lemma is a foundational result in linear programming, with implications in duality, optimality conditions, and stochastic and bilevel programming. Its generalizations are known as theorems of the alternative. There exist theorems of the alternative for integer programming and conic programming. We present theorems of the alternative for conic integer programming. We provide a nested procedure to construct a function that characterizes feasibility over right-hand sides and can determine which statement in a theorem of the alternative holds.     

Pivot rules for linear programming: A survey on recent theoretical developments

The purpose of this paper is to discuss the various pivot rules of the simplex method and its variants that have been developed in the last two decades, starting from the appearance of the minimal index rule of Bland. We are mainly concerned with finiteness properties of simplex type pivot rules. Well known classical results concerning the simplex method are not considered in this survey, but the connection between the new pivot methods and the classical ones, if there is any, is discussed.In this paper we discuss three classes of recently developed pivot rules for linear programming. The first and largest class is the class of essentially combinatorial pivot rules including minimal index type rules and recursive rules. These rules only use labeling and signs of the variables. The second class contains those pivot rules which can actually be considered as variants or generalizations or specializations of Lemke's method, and so they are closely related to parametric programming. The last class has the common feature that the rules all have close connections to certain interior point methods. Finally, we mention some open problems for future research.On leave from the Eötvös University, Budapest, and partially supported by OTKA No. 2115.     

Polynomiality of infeasible-interior-point algorithms for linear programming

Kojima, Megiddo, and Mizuno investigate an infeasible-interior-point algorithm for solving a primal—dual pair of linear programming problems and they demonstrate its global convergence. Their algorithm finds approximate optimal solutions of the pair if both problems have interior points, and they detect infeasibility when the sequence of iterates diverges. Zhang proves polynomial-time convergence of an infeasible-interior-point algorithm under the assumption that both primal and dual problems have feasible points. In this paper, we show that a modification of the Kojima—Megiddo—Mizuno algorithm solves the pair of problems in polynomial time without assuming the existence of the LP solution. Furthermore, we develop anO(nL)-iteration complexity result for a variant of the algorithm.The original title was Polynomiality of the Kojima—Megiddo—Mizuno infeasible-interior-point algorithm for linear programming.Research performed while visiting Cornell University (April 1992 – January 1993) as an Overseas Research Scholar of the Ministry of Science, Education and Culture of Japan.     

Primal—dual methods for linear programming

Many interior-point methods for linear programming are based on the properties of the logarithmic barrier function. After a preliminary discussion of the convergence of the (primal) projected Newton barrier method, three types of barrier method are analyzed. These methods may be categorized as primal, dual and primal—dual, and may be derived from the application of Newton's method to different variants of the same system of nonlinear equations. A fourth variant of the same equations leads to a new primal—dual method.In each of the methods discussed, convergence is demonstrated without the need for a nondegeneracy assumption or a transformation that makes the provision of a feasible point trivial. In particular, convergence is established for a primal—dual algorithm that allows a different step in the primal and dual variables and does not require primal and dual feasibility.Finally, a new method for treating free variables is proposed.Presented at the Second Asilomar Workshop on Progress in Mathematical Programming, February 1990, Asilomar, CA, United StatesThe material contained in this paper is based upon research supported by the National Science Foundation Grant DDM-9204208 and the Office of Naval Research Grant N00014-90-J-1242.     

Volumetric path following algorithms for linear programming

We consider the construction of small step path following algorithms using volumetric, and mixed volumetric-logarithmic, barriers. We establish quadratic convergence of a volumetric centering measure using pure Newton steps, enabling us to use relatively standard proof techniques for several subsequently needed results. Using a mixed volumetric-logarithmic barrier we obtain an O(n ^1/4 m ^1/4 L) iteration algorithm for linear programs withn variables andm inequality constraints, providing an alternative derivation for results first obtained by Vaidya and Atkinson. In addition, we show that the same iteration complexity can be attained while holding the work per iteration to O(n ² m), as opposed to O(nm ²), operations, by avoiding use of the true Hessian of the volumetric barrier. Our analysis also provides a simplified proof of self-concordancy of the volumetric and mixed volumetric-logarithmic barriers, originally due to Nesterov and Nemirovskii. This paper was first presented at the 1994 Faculty Research Seminar “Optimization in Theory and Practice”, at the University of Iowa Center for Advanced Studies.     

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.     

Intelligent gradient search in linear programming

The simplex algorithm is still the best known and most frequently used way to solve LP problems. Khachian has suggested a method to solve these problems in polynomial time. The average behaviour of his method, however, is still inferior to the modern simplex based LP codes. A new gradient based approach which also has polynomial worst-case behaviour has been suggested by Karmarkar. This method was modified, programmed and compared with other available LP codes. It is shown that the numerical efficiency of Karmarkar's method compares favourably with other LP codes, particularly for problems with high numbers of variables and few constraints.