Interior-point methods for nonconvex nonlinear programming: orderings and higher-order methods

The paper extends prior work by the authors on loqo, an interior point algorithm for nonconvex nonlinear programming. The specific topics covered include primal versus dual orderings and higher order methods, which attempt to use each factorization of the Hessian matrix more than once to improve computational efficiency. Results show that unlike linear and convex quadratic programming, higher order corrections to the central trajectory are not useful for nonconvex nonlinear programming, but that a variant of Mehrotra’s predictor-corrector algorithm can definitely improve performance. Received: May 3, 1999 / Accepted: January 24, 2000?Published online March 15, 2000     

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.     

Interior-point ℓ 2-penalty methods for nonlinear programming with strong global convergence properties

We propose two line search primal-dual interior-point methods for nonlinear programming that approximately solve a sequence of equality constrained barrier subproblems. To solve each subproblem, our methods apply a modified Newton method and use an ℓ₂-exact penalty function to attain feasibility. Our methods have strong global convergence properties under standard assumptions. Specifically, if the penalty parameter remains bounded, any limit point of the iterate sequence is either a Karush-Kuhn-Tucker (KKT) point of the barrier subproblem, or a Fritz-John (FJ) point of the original problem that fails to satisfy the Mangasarian-Fromovitz constraint qualification (MFCQ); if the penalty parameter tends to infinity, there is a limit point that is either an infeasible FJ point of the inequality constrained feasibility problem (an infeasible stationary point of the infeasibility measure if slack variables are added) or a FJ point of the original problem at which the MFCQ fails to hold. Numerical results are given that illustrate these outcomes. Research supported by the Presidential Fellowship of Columbia University. Research supported in part by NSF Grant DMS 01-04282, DOE Grant DE-FG02-92EQ25126 and DNR Grant N00014-03-0514.     

A spline smoothing homotopy method for nonconvex nonlinear programming

Homotopy methods are globally convergent under weak conditions and robust; however, the efficiency of a homotopy method is closely related with the construction of the homotopy map and the path tracing algorithm. Different homotopies may behave very different in performance even though they are all theoretically convergent. In this paper, a spline smoothing homotopy method for nonconvex nonlinear programming is developed using cubic spline to smooth the max function of the constraints of nonlinear programming. Some properties of spline smoothing function are discussed and the global convergence of spline smoothing homotopy under the weak normal cone condition is proven. The spline smoothing technique uses a smooth constraint instead of m constraints and acts also as an active set technique. So the spline smoothing homotopy method is more efficient than previous homotopy methods like combined homotopy interior point method, aggregate constraint homotopy method and other probability one homotopy methods. Numerical tests with the comparisons to some other methods show that the new method is very efficient for nonlinear programming with large number of complicated constraints.     

An Interior-Point Algorithm for Nonconvex Nonlinear Programming

The paper describes an interior-point algorithm for nonconvex nonlinear programming which is a direct extension of interior-point methods for linear and quadratic programming. Major modifications include a merit function and an altered search direction to ensure that a descent direction for the merit function is obtained. Preliminary numerical testing indicates that the method is robust. Further, numerical comparisons with MINOS and LANCELOT show that the method is efficient, and has the promise of greatly reducing solution times on at least some classes of models.     

Interior-Point Methods for Nonconvex Nonlinear Programming: Filter Methods and Merit Functions

Recently, Fletcher and Leyffer proposed using filter methods instead of a merit function to control steplengths in a sequential quadratic programming algorithm. In this paper, we analyze possible ways to implement a filter-based approach in an interior-point algorithm. Extensive numerical testing shows that such an approach is more efficient than using a merit function alone.     

Interior-point methods for nonlinear complementarity problems

We present a potential reduction interior-point algorithm for monotone nonlinear complementarity problems. At each iteration, one has to compute an approximate solution of a nonlinear system such that a certain accuracy requirement is satisfied. For problems satisfying a scaled Lipschitz condition, this requirement is satisfied by the approximate solution obtained by applying one Newton step to that nonlinear system. We discuss the global and local convergence rates of the algorithm, convergence toward a maximal complementarity solution, a criterion for switching from the interior-point algorithm to a pure Newton method, and the complexity of the resulting hybrid algorithm.This research was supported in part by NSF Grant DDM-89-22636.The authors would like to thank Rongqin Sheng and three anonymous referees for their comments leading to a better presentation of the results.     

Interior-point methods for nonconvex nonlinear programming: cubic regularization

In this paper, we present a primal-dual interior-point method for solving nonlinear programming problems. It employs a Levenberg-Marquardt (LM) perturbation to the Karush-Kuhn-Tucker (KKT) matrix to handle indefinite Hessians and a line search to obtain sufficient descent at each iteration. We show that the LM perturbation is equivalent to replacing the Newton step by a cubic regularization step with an appropriately chosen regularization parameter. This equivalence allows us to use the favorable theoretical results of Griewank (The modification of Newton’s method for unconstrained optimization by bounding cubic terms, 1981), Nesterov and Polyak (Math. Program., Ser. A 108:177–205, 2006), Cartis et al. (Math. Program., Ser. A 127:245–295, 2011; Math. Program., Ser. A 130:295–319, 2011), but its application at every iteration of the algorithm, as proposed by these papers, is computationally expensive. We propose a hybrid method: use a Newton direction with a line search on iterations with positive definite Hessians and a cubic step, found using a sufficiently large LM perturbation to guarantee a steplength of 1, otherwise. Numerical results are provided on a large library of problems to illustrate the robustness and efficiency of the proposed approach on both unconstrained and constrained problems.     

Interior-point methods: An old and new approach to nonlinear programming

In this paper we discuss the main concepts of structural optimization, a field of nonlinear programming, which was formed by the intensive development of modern interior-point schemes.     

Outer approximation algorithms for separable nonconvex mixed-integer nonlinear programs

A rigorous decomposition approach to solve separable mixed-integer nonlinear programs where the participating functions are nonconvex is presented. The proposed algorithms consist of solving an alternating sequence of Relaxed Master Problems (mixed-integer linear program) and two nonlinear programming problems (NLPs). A sequence of valid nondecreasing lower bounds and upper bounds is generated by the algorithms which converge in a finite number of iterations. A Primal Bounding Problem is introduced, which is a convex NLP solved at each iteration to derive valid outer approximations of the nonconvex functions in the continuous space. Two decomposition algorithms are presented in this work. On finite termination, the first yields the global solution to the original nonconvex MINLP and the second finds a rigorous bound to the global solution. Convergence and optimality properties, and refinement of the algorithms for efficient implementation are presented. Finally, numerical results are compared with currently available algorithms for example problems, illuminating the potential benefits of the proposed algorithm.     

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.     

A semistrong sufficiency condition for optimality in nonconvex programming and its connection to the perturbation problem

What happens when a nonconvex program, having a local solutionx ⁰ at which the gradients of the binding constraints are linearly independent, but without strict complementarity hypothesis, is perturbed? Under a relatively weak second-order assumption (some nonnegative second-order terms are supposed to be strictly positive), the perturbed problem has, in the neighborhood ofx ⁰, a finite number of local minima, situated on curves that are connected to some pseudo-solutions of the tangent quadratic problem.     

Interior-point methods for convex programming

This work is concerned with generalized convex programming problems, where the objective function and also the constraints belong to a certain class of convex functions. It examines the relationship of two basic conditions used in interior-point methods for generalized convex programming—self-concordance and a relative Lipschitz condition—and gives a short and simple complexity analysis of an interior-point method for generalized convex programming. In generalizing ellipsoidal approximations for the feasible set, it also allows a geometrical interpretation of the analysis.This work was supported by a research grant from the Deutsche Forschungsgemeinschaft, and in part by the U.S. National Science Foundation Grant DDM-8715153 and the Office of Naval Research Grant N00014-90-J-1242.On leave from the Institut für Angewandte Mathematik, University of Würzburg, Am Hubland, W-8700 Würzburg, Federal Republic of Germany.     

Test examples for nonlinear programming codes

The increasing importance of nonlinear programming software requires an enlarged set of test examples. The purpose of this note is to point out how an interested mathematical programmer could obtain computer programs of more than 120 constrained nonlinear programming problems which have been used in the past to test and compare optimization codes.     

Duality for nonconvex absolute value programming and a characterization of linear max-min programs

In this paper a dual problem for nonconvex linear programs with absolute value functionals is constructed by means of a max-min problem involving bivalent variables. A relationship between the classical linear max-min problem and a linear program with absolute value functionals is developed. This program is then used to compute the duality gap between some max-min and min-max linear problems.     

A local convergence property of primal-dual methods for nonlinear programming

We prove a new local convergence property of some primal-dual methods for solving nonlinear optimization problems. We consider a standard interior point approach, for which the complementarity conditions of the original primal-dual system are perturbed by a parameter driven to zero during the iterations. The sequence of iterates is generated by a linearization of the perturbed system and by applying the fraction to the boundary rule to maintain strict feasibility of the iterates with respect to the nonnegativity constraints. The analysis of the rate of convergence is carried out by considering an arbitrary sequence of perturbation parameters converging to zero. We first show that, once an iterate belongs to a neighbourhood of convergence of the Newton method applied to the original system, then the whole sequence of iterates converges to the solution. In addition, if the perturbation parameters converge to zero with a rate of convergence at most superlinear, then the sequence of iterates becomes asymptotically tangent to the central trajectory in a natural way. We give an example showing that this property can be false when the perturbation parameter goes to zero quadratically.      

Feasible direction method for large-scale nonconvex programs: Decomposition approach

In this paper, we propose a feasible-direction method for large-scale nonconvex programs, where the gradient projection on a linear subspace defined by the active constraints of the original problem is determined by dual decomposition. Results are extended for dynamical problems which include distributed delays and constraints both in state and control variables. The approach is compared with other feasible-direction approaches, and the method is applied to a power generation problem. Some computational results are included.This work was supported by the Conselho Nacional de Desenvolvimento Cientifico e Tecnologico, Brasilia, Brasil, and by the Fundaçao de Amparo a Pesquisa do Estado de Sao Paulo, Sao Paulo, Brazil.On leave from UNICAMP, Campinas, Brazil.     

Algorithms for parametric nonconvex programming

In this paper, we consider a general family of nonconvex programming problems. All of the objective functions of the problems in this family are identical, but their feasibility regions depend upon a parameter . This family of problems is called a parametric nonconvex program (PNP). Solving (PNP) means finding an optimal solution for every program in the family. A prototype branch-and-bound algorithm is presented for solving (PNP). By modifying a prototype algorithm for solving a single nonconvex program, this algorithm solves (PNP) in one branch-and-bound search. To implement the algorithm, certain compact partitions and underestimating functions must be formed in an appropriate manner. We present an algorithm for solving a particular (PNP) which implements the prototype algorithm by forming compact partitions and underestimating functions based upon rules given by Falk and Soland. The programs in this (PNP) have the same concave objective function, but their feasibility regions are described by linear constraints with differing right-hand sides. Computational experience with this algorithm is reported for various problems.The author would like to thank Professors R. M. Soland, T. L. Morin, and P. L. Yu for their helpful comments. Thanks also go to two anonymous reviewers for their useful comments concerning an earlier version of this paper.     

On filter-successive linearization methods for nonlinear semidefinite programming

In this paper we present a filter-successive linearization method with trust region for solutions of nonlinear semidefinite programming. Such a method is based on the concept of filter for nonlinear programming introduced by Fletcher and Leyffer in 2002. We describe the new algorithm and prove its global convergence under weaker assumptions. Some numerical results are reported and show that the new method is potentially effcient.     

A general class of branch-and-bound methods in global optimization with some new approaches for concave minimization

Based on a review of existing algorithms, a general branch-and-bound concept in global optimization is presented. A sufficient and necessary convergence condition is established, and a broad class of realizations is derived that include existing and several new approaches for concave minimization problems.