Interior-point methods for nonconvex nonlinear programming: regularization and warmstarts

In this paper, we investigate the use of an exact primal-dual penalty approach within the framework of an interior-point method for nonconvex nonlinear programming. This approach provides regularization and relaxation, which can aid in solving ill-behaved problems and in warmstarting the algorithm. We present details of our implementation within the loqo algorithm and provide extensive numerical results on the CUTEr test set and on warmstarting in the context of quadratic, nonlinear, mixed integer nonlinear, and goal programming. 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.     

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.     

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.     

Presolving in linear programming

Most modern linear programming solvers analyze the LP problem before submitting it to optimization. Some examples are the solvers WHIZARD (Tomlin and Welch, 1983), OB1 (Lustig et al., 1994), OSL (Forrest and Tomlin, 1992), Sciconic (1990) and CPLEX (Bixby, 1994). The purpose of the presolve phase is to reduce the problem size and to discover whether the problem is unbounded or infeasible.In this paper we present a comprehensive survey of presolve methods. Moreover, we discuss the restoration procedure in detail, i.e., the procedure that undoes the presolve.Computational results on the NETLIB problems (Gay, 1985) are reported to illustrate the efficiency of the presolve methods.This author was supported by a Danish SNF Research studentship.     

An interior-point method for semi-infinite programming problems

This work examines the generalization of a certain interior-point method, namely the method of analytic centers, to semi-infinite linear programming problems. We define an analytic center for these problems and an appropriate norm to examine Newton's method for computing this center. A simple algorithm of order zero is constructed and a convergence proof for that algorithm is given. Finally, we describe a more practical implementation of a predictor-corrector method and give some numerical results. In particular we concentrate on practical integration rules that take care of the specific structure of the integrals.     

An interior semi-infinite programming method

In this paper, a new method for semi-infinite programming problems with convex constraints is presented. The method generates a sequence of feasible points whose cluster points are solutions of the original problem. No maximization over the index set is required. Some computational results are also presented.This work was partly supported by Republicka Zajednica za Nauku Socijalisticke Republike Srbije. The authors are indebted to Professor R. A. Tapia for encouraging the approach taken in this research.     

Sufficient conditions for total ill-posedness in linear semi-infinite optimization

This paper deals with the so-called total ill-posedness of linear optimization problems with an arbitrary (possibly infinite) number of constraints. We say that the nominal problem is totally ill-posed if it exhibits the highest unstability in the sense that arbitrarily small perturbations of the problem’s coefficients may provide both, consistent (with feasible solutions) and inconsistent problems, as well as bounded (with finite optimal value) and unbounded problems, and also solvable (with optimal solutions) and unsolvable problems. In this paper we provide sufficient conditions for the total ill-posedness property exclusively in terms of the coefficients of the nominal problem.     

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.     

Second order optimality conditions for generalized semi-infinite programming problems

We consider generalized semi-infinite programming problems. Second order necessary and sufficient conditionsfor local optimality are given. The conditions are derived under assumptions such that the feasible set can be described by means of a finite number of optimal value functions. Since we do not require a strict complementary condition for the local reduction these functions are only of class C¹ A sufficient condition for optimality is proven under much weaker assumptions.     

A one-phase algorithm for semi-infinite linear programming

We present an algorithm for solving a large class of semi-infinite linear programming problems. This algorithm has several advantages: it handles feasibility and optimality together; it has very weak restrictions on the constraints; it allows cuts that are not near the most violated cut; and it solves the primal and the dual problems simultaneously. We prove the convergence of this algorithm in two steps. First, we show that the algorithm can find an-optimal solution after finitely many iterations. Then, we use this result to show that it can find an optimal solution in the limit. We also estimate how good an-optimal solution is compared to an optimal solution and give an upper bound on the total number of iterations needed for finding an-optimal solution under some assumptions. This algorithm is generalized to solve a class of nonlinear semi-infinite programming problems. Applications to convex programming are discussed.     

A globally convergent method for semi-infinite linear programming

This paper presents a globally convergent method for solving a general semi-infinite linear programming problem. Some important features of this method include: It can solve a semi-infinite linear program having an unbounded feasible region. It requires an inexact solution to a nonlinear subproblem at each iteration. It allows unbounded index sets and nondifferentiable constraints. The amount of work at each iteration k does not increase with k.     

Directional derivatives for the value-function in semi-infinite programming

For the problemP(λ): Maximizec ^T z subject toz∈Z(λ), whereZ(λ) is defined by an in general infinite set of linear inequalities, it is shown that the value-function has directional derivatives at every point such thatP( ) and its dual are both superconsistent. To compute these directional derivatives a min-max-formula, well-known in convex programming, is derived. In addition, it is shown that derivatives can be obtained more easily by a limit-process using only convergent selections of solutions ofP(λ _n ), λ _n → and their duals.     

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.     

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.     

An interior point algorithm for semi-infinite linear programming

We consider the generalization of a variant of Karmarkar's algorithm to semi-infinite programming. The extension of interior point methods to infinite-dimensional linear programming is discussed and an algorithm is derived. An implementation of the algorithm for a class of semi-infinite linear programs is described and the results of a number of test problems are given. We pay particular attention to the problem of Chebyshev approximation. Some further results are given for an implementation of the algorithm applied to a discretization of the semi-infinite linear program, and a convergence proof is given in this case.     

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.     

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.     

Semi-infinite programming

A semi-infinite programming problem is an optimization problem in which finitely many variables appear in infinitely many constraints. This model naturally arises in an abundant number of applications in different fields of mathematics, economics and engineering. The paper, which intends to make a compromise between an introduction and a survey, treats the theoretical basis, numerical methods, applications and historical background of the field.     

Application of general semi-infinite programming to lapidary cutting problems

We consider a volume maximization problem arising in gemstone cutting industry. The problem is formulated as a general semi-infinite program (GSIP) and solved using an interior-point method developed by Stein [O. Stein, Bi-level Strategies in Semi-infinite Programming, Kluwer Academic Publishers, Boston, 2003]. It is shown, that the convexity assumption needed for the convergence of the algorithm can be satisfied by appropriate modelling. Clustering techniques are used to reduce the number of container constraints, which is necessary to make the subproblems practically tractable. An iterative process consisting of GSIP optimization and adaptive refinement steps is then employed to obtain an optimal solution which is also feasible for the original problem. Some numerical results based on real-world data are also presented.     

Nonsmooth semi-infinite programming problems with mixed constraints

We consider a nonsmooth semi-infinite programming problem with a feasible set defined by inequality and equality constraints and a set constraint. First, we study some alternative theorems which involve linear and sublinear functions and a convex set and we propose several generalizations of them. Then, alternative theorems are applied to obtain, under different constraint qualifications, several necessary optimality conditions in the type of Fritz-John and Karush-Kuhn-Tucker.