Superlinear and quadratic convergence of primal-dual interior-point methods for linear programming revisited

Recently, Zhang, Tapia, and Dennis (Ref. 1) produced a superlinear and quadratic convergence theory for the duality gap sequence in primal-dual interior-point methods for linear programming. In this theory, a basic assumption for superlinear convergence is the convergence of the iteration sequence; and a basic assumption for quadratic convergence is nondegeneracy. Several recent research projects have either used or built on this theory under one or both of the above-mentioned assumptions. In this paper, we remove both assumptions from the Zhang-Tapia-Dennis theory.Dedicated to the Memory of Magnus R. Hestenes, 1906–1991This research was supported in part by NSF Cooperative Agreement CCR-88-09615 and was initiated while the first author was at Rice University as a Visiting Member of the Center for Research in Parallel Computation.The authors thank Yinyu Ye for constructive comments and discussions concerning this material.This author was supported in part by NSF Grant DMS-91-02761 and DOE Grant DE-FG05-91-ER25100.This author was supported in part by AFOSR Grant 89-0363, DOE Grant DE-FG05-86-ER25017, and ARO Grant 9DAAL03-90-G-0093.     

A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming

We present a unified analysis for a class of long-step primal-dual path-following algorithms for semidefinite programming whose search directions are obtained through linearization of the symmetrized equation of the central pathH _P (XS) [PXSP ^–1 + (PXSP ^–1) ^T ]/2 = I, introduced by Zhang. At an iterate (X,S), we choose a scaling matrixP from the class of nonsingular matricesP such thatPXSP ^–1 is symmetric. This class of matrices includes the three well-known choices, namely:P = S ^1/2 andP = X ^–1/2 proposed by Monteiro, and the matrixP corresponding to the Nesterov—Todd direction. We show that within the class of algorithms studied in this paper, the one based on the Nesterov—Todd direction has the lowest possible iteration-complexity bound that can provably be derived from our analysis. More specifically, its iteration-complexity bound is of the same order as that of the corresponding long-step primal-dual path-following algorithm for linear programming introduced by Kojima, Mizuno and Yoshise. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.This author's research is supported in part by the National Science Foundation under grants INT-9600343 and CCR-9700448 and the Office of Naval Research under grant N00014-94-1-0340.This author's research was supported in part by DOE DE-FG02-93ER25171-A001.     

A primal-dual interior-point algorithm for quadratic programming

In this paper we propose a primal-dual interior-point method for large, sparse, quadratic programming problems. The method is based on a reduction presented by Gonzalez-Lima, Wei, and Wolkowicz [14] in order to solve the linear systems arising in the primal-dual methods for linear programming. The main features of this reduction is that it is well defined at the solution set and it preserves sparsity. These properties add robustness and stability to the algorithm and very accurate solutions can be obtained. We describe the method and we consider different reductions using the same framework. We discuss the relationship of our proposals and the one used in the LOQO code. We compare and study the different approaches by performing numerical experimentation using problems from the Maros and Meszaros collection. We also include a brief discussion on the meaning and effect of ill-conditioning when solving linear systems.This work was partially supported by DID-USB (GID-001).     

Exploiting sparsity in primal-dual interior-point methods for semidefinite programming

The Helmberg-Rendl-Vanderbei-Wolkowicz/Kojima-Shindoh-Hara/Monteiro and Nesterov-Todd search directions have been used in many primal-dual interior-point methods for semidefinite programs. This paper proposes an efficient method for computing the two directions when the semidefinite program to be solved is large scale and sparse.     

A clique algorithm for standard quadratic programming

A standard Quadratic Programming problem (StQP) consists in minimizing a (nonconvex) quadratic form over the standard simplex. For solving a StQP we present an exact and a heuristic algorithm, that are based on new theoretical results for quadratic and convex optimization problems. With these results a StQP is reduced to a constrained nonlinear minimum weight clique problem in an associated graph. Such a clique problem, which does not seem to have been studied before, is then solved with an exact and a heuristic algorithm. Some computational experience shows that our algorithms are able to solve StQP problems of at least one order of magnitude larger than those reported in the literature.     

“Cone-free” primal-dual path-following and potential-reduction polynomial time interior-point methods

We present a framework for designing and analyzing primal-dual interior-point methods for convex optimization. We assume that a self-concordant barrier for the convex domain of interest and the Legendre transformation of the barrier are both available to us. We directly apply the theory and techniques of interior-point methods to the given good formulation of the problem (as is, without a conic reformulation) using the very usual primal central path concept and a less usual version of a dual path concept. We show that many of the advantages of the primal-dual interior-point techniques are available to us in this framework and therefore, they are not intrinsically tied to the conic reformulation and the logarithmic homogeneity of the underlying barrier function.Part of the research was done while the author was a Visiting Professor at the University of Waterloo.Research of this author is supported in part by a PREA from Ontario and by a NSERC Discovery Grant. Tel: (519) 888-4567 ext.5598, Fax: (519) 725-5441Mathematics Subject Classification (2000): 90C51, 90C25, 65Y20,90C28, 49D49     

Minimizing an indefinite quadratic function subject to a single indefinite quadratic constraint

In this paper, we consider the problem of minimizing an indefinite quadratic function subject to a single indefinite quadratic constraint. A key difficulty with this problem is its nonconvexity. Using Lagrange duality, we show that under a mild assumption, this problem can be solved by solving a linearly constrained convex univariate minimization problem. Finally, the superior efficiency of the new approach compared to the known semidefinite relaxation and a known approach from the literature is demonstrated by solving several randomly generated test problems.     

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.     

On the convergence of the iteration sequence in primal-dual interior-point methods

Recently, numerous research efforts, most of them concerned with superlinear convergence of the duality gap sequence to zero in the Kojima—Mizuno—Yoshise primal-dual interior-point method for linear programming, have as a primary assumption the convergence of the iteration sequence. Yet, except for the case of nondegeneracy (uniqueness of solution), the convergence of the iteration sequence has been an important open question now for some time. In this work we demonstrate that for general problems, under slightly stronger assumptions than those needed for superlinear convergence of the duality gap sequence (except of course the assumption that the iteration sequence converges), the iteration sequence converges. Hence, we have not only established convergence of the iteration sequence for an important class of problems, but have demonstrated that the assumption that the iteration sequence converges is redundant in many of the above mentioned works.This research was supported in part by NSF Coop. Agr. No. CCR-8809615. A part of this research was performed in June, 1991 while the second and the third authors were at Rice University as visiting members of the Center for Research in Parallel Computation.Corresponding author. Research supported in part by AFOSR 89-0363, DOE DEFG05-86ER25017 and ARO 9DAAL03-90-G-0093.Research supported in part by NSF DMS-9102761 and DOE DE-FG05-91ER25100.Research supported in part by NSF DDM-8922636.     

On the formulation and theory of the Newton interior-point method for nonlinear programming

In this work, we first study in detail the formulation of the primal-dual interior-point method for linear programming. We show that, contrary to popular belief, it cannot be viewed as a damped Newton method applied to the Karush-Kuhn-Tucker conditions for the logarithmic barrier function problem. Next, we extend the formulation to general nonlinear programming, and then validate this extension by demonstrating that this algorithm can be implemented so that it is locally and Q-quadratically convergent under only the standard Newton method assumptions. We also establish a global convergence theory for this algorithm and include promising numerical experimentation.The first two authors were supported in part by NSF Cooperative Agreement No. CCR-8809615, by Grants AFOSR 89-0363, DOE DEFG05-86ER25017, ARO 9DAAL03-90-G-0093, and the REDI Foundation. The fourth author was supported in part by NSF DMS-9102761 and DOE DE-FG02-93ER25171. The authors would like to thank Sandra Santos for painstakingly proofreading an earlier verion of this paper.     

Implementation of warm-start strategies in interior-point methods for linear programming in fixed dimension

We implement several warm-start strategies in interior-point methods for linear programming (LP). We study the situation in which both the original LP instance and the perturbed one have exactly the same dimensions. We consider different types of perturbations of data components of the original instance and different sizes of each type of perturbation. We modify the state-of-the-art interior-point solver PCx in our implementation. We evaluate the effectiveness of each warm-start strategy based on the number of iterations and the computation time in comparison with “cold start” on the NETLIB test suite. Our experiments reveal that each of the warm-start strategies leads to a reduction in the number of interior-point iterations especially for smaller perturbations and for perturbations of fewer data components in comparison with cold start. On the other hand, only one of the warm-start strategies exhibits better performance than cold start in terms of computation time. Based on the insight gained from the computational results, we discuss several potential improvements to enhance the performances of such warm-start strategies. This research was supported in part by NSF through CAREER grant DMI-0237415.     

An exact primal–dual penalty method approach to warmstarting interior-point methods for linear programming

One perceived deficiency of interior-point methods in comparison to active set methods is their inability to efficiently re-optimize by solving closely related problems after a warmstart. In this paper, we investigate the use of a primal–dual penalty approach to overcome this problem. We prove exactness and convergence and show encouraging numerical results on a set of linear and mixed integer programming problems. Research of the first author is sponsored by ONR grant N00014-04-1-0145. Research of the second author is supported by NSF grant DMS-0107450.     

Convex relaxation and Lagrangian decomposition for indefinite integer quadratic programming

We study lower bounding methods for indefinite integer quadratic programming problems. We first construct convex relaxations by D.C. (difference of convex functions) decomposition and linear underestimation. Lagrangian bounds are then derived by applying dual decomposition schemes to separable relaxations. Relationships between the convex relaxation and Lagrangian dual are established. Finally, we prove that the lower bound provided by the convex relaxation coincides with the Lagrangian bound of the orthogonally transformed problem.     

A note on the existence of the Alizadeh-Haeberly-Overton direction for semidefinite programming

This note establishes a new sufficient condition for the existence and uniqueness of the Alizadeh-Haeberly-Overton direction for semidefinite programming. The work of these authors was based on research supported by the National Science Foundation under grants INT-9600343 and CCR-970048 and the Office of Naval Research under grant N00014-94-1-0340.     

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

Numerically stable methods for quadratic programming

Numerically stable algorithms for quadratic programming are discussed. A new algorithm is described for indefinite quadratic programming which utilizes methods for updating positivedefinite factorizations only. Consequently all the updating procedures required are common to algorithms for linearly-constrained optimization. The new algorithm can be used for the positive-definite case without loss of efficiency.     

On affine scaling algorithms for nonconvex quadratic programming

We investigate the use of interior algorithms, especially the affine-scaling algorithm, to solve nonconvex — indefinite or negative definite — quadratic programming (QP) problems. Although the nonconvex QP with a polytope constraint is a hard problem, we show that the problem with an ellipsoidal constraint is easy. When the hard QP is solved by successively solving the easy QP, the sequence of points monotonically converge to a feasible point satisfying both the first and the second order optimality conditions.Research supported in part by NSF Grant DDM-8922636 and the College Summer Grant, College of Business Administration, The University of Iowa.     

Some properties of generalized proximal point methods for quadratic and linear programming

The proximal point method for convex optimization has been extended recently through the use of generalized distances (e.g., Bregman distances) instead of the Euclidean one. One advantage of these extensions is the possibility of eliminating certain constraints (mainly positivity) from the subproblems, transforming an inequality constrained problem into a sequence of unconstrained or equality constrained problems. We consider here methods obtained using a certain class of Bregman functions applied to convex quadratic (including linear) programming, which are of the interior-point type. We prove that the limit of the sequence generated by the method lies in the relative interior of the solution set, and furthermore is the closest optimal solution to the initial point, in the sense of the Bregman distance. These results do not hold for the standard proximal point method, i.e., when the square of the Euclidean norm is used as the Bregman distance.The research leading to this paper was partially supported by CNPq Grant 301280/86.We thank two anonymous referees whose comments and suggestions allowed us to improve our results in a significant way.     

Steplength selection in interior-point methods for quadratic programming

We present a new strategy for choosing primal and dual steplengths in a primal–dual interior-point algorithm for convex quadratic programming. Current implementations often scale steps equally to avoid increases in dual infeasibility between iterations. We propose that this method can be too conservative, while safeguarding an unequally-scaled steplength approach will often require fewer steps toward a solution. Computational results are given.     

Parabolic target space and primal-dual interior-point methods

In this paper we develop new primal-dual interior-point methods for linear programming problems, which are based on the concept of parabolic target space. We show that such schemes work in the infinity-neighborhood of the primal-dual central path. Nevertheless, these methods possess the best known complexity estimate. We demonstrate that the adaptive-step path-following strategies can be naturally incorporated in such schemes.