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.     

On the Global Convergence of a Modified Augmented Lagrangian Linesearch Interior-Point Newton Method for Nonlinear Programming

We consider a linesearch globalization of the local primal-dual interior-point Newton method for nonlinear programming introduced by El-Bakry, Tapia, Tsuchiya, and Zhang. The linesearch uses a new merit function that incorporates a modification of the standard augmented Lagrangian function and a weak notion of centrality. We establish a global convergence theory and present promising numerical experimentation.     

On the Newton Interior-Point Method for Nonlinear Programming Problems

Interior-point methods have been developed largely for nonlinear programming problems. In this paper, we generalize the global Newton interior-point method introduced in Ref. 1 and we establish a global convergence theory for it, under the same assumptions as those stated in Ref. 1. The generalized algorithm gives the possibility of choosing different descent directions for a merit function so that difficulties due to small steplength for the perturbed Newton direction can be avoided. The particular choice of the perturbation enables us to interpret the generalized method as an inexact Newton method. Also, we suggest a more general criterion for backtracking, which is useful when the perturbed Newton system is not solved exactly. We include numerical experimentation on discrete optimal control problems.     

Numerical Comparisons of Path-Following Strategies for a Primal-Dual Interior-Point Method for Nonlinear Programming

An important research activity in primal-dual interior-point methods for general nonlinear programming is to determine effective path-following strategies and their implementations. The objective of this work is to present numerical comparisons of several path-following strategies for the local interior-point Newton method given by El-Bakry, Tapia, Tsuchiya, and Zhang. We conduct numerical experimentation of nine strategies using two central regions, three notions of proximity measures, and three merit functions to obtain an optimal solution. Six of these strategies are implemented for the first time. The numerical results show that the best path-following strategy is that given by Argáez and Tapia.     

A primal–dual augmented Lagrangian penalty-interior-point filter line search algorithm

Interior-point methods have been shown to be very efficient for large-scale nonlinear programming. The combination with penalty methods increases their robustness due to the regularization of the constraints caused by the penalty term. In this paper a primal–dual penalty-interior-point algorithm is proposed, that is based on an augmented Lagrangian approach with an \(\ell 2\)-exact penalty function. Global convergence is maintained by a combination of a merit function and a filter approach. Unlike the majority of filter methods, no separate feasibility restoration phase is required. The algorithm has been implemented within the solver WORHP to study different penalty and line search options and to compare its numerical performance to two other state-of-the-art nonlinear programming algorithms, the interior-point method IPOPT and the sequential quadratic programming method of WORHP.     

Combining search directions using gradient flows

 The efficient combination of directions is a significant problem in line search methods that either use negative curvature, or wish to include additional information such as the gradient or different approximations to the Newton direction. In this paper we describe a new procedure to combine several of these directions within an interior-point primal-dual algorithm. Basically, we combine in an efficient manner a modified Newton direction with the gradient of a merit function and a direction of negative curvature, if it exists. We also show that the procedure is well-defined, and it has reasonable theoretical properties regarding the rate of convergence of the method. We also present numerical results from an implementation of the proposed algorithm on a set of small test problems from the CUTE collection. Received: November 2000 / Accepted: October 2002 Published online: February 14, 2003 Key Words. negative curvature – primal-dual methods – interior-point methods – nonconvex optimization – line searches Mathematics Subject Classification (1991): 49M37, 65K05, 90C30     

A primal-dual interior-point algorithm for nonlinear least squares constrained problems

This paper extends prior work by the authors on solving nonlinear least squares unconstrained problems using a factorized quasi-Newton technique. With this aim we use a primal-dual interior-point algorithm for nonconvex nonlinear programming. The factorized quasi-Newton technique is now applied to the Hessian of the Lagrangian function for the transformed problem which is based on a logarithmic barrier formulation. We emphasize the importance of establishing and maintaining symmetric quasi-definiteness of the reduced KKT system. The algorithm then tries to choose a step size that reduces a merit function, and to select a penalty parameter that ensures descent directions along the iterative process. Computational results are included for a variety of least squares constrained problems and preliminary numerical testing indicates that the algorithm is robust and efficient in practice.     

A reduction method for semi-infinite programming by means of a global stochastic approach†

We describe a reduction algorithm for solving semi-infinite programming problems. The proposed algorithm uses the simulated annealing method equipped with a function stretching as a multi-local procedure, and a penalty technique for the finite optimization process. An exponential penalty merit function is reduced along each search direction to ensure convergence from any starting point. Our preliminary numerical results seem to show that the algorithm is very promising in practice.     

Infeasible interior-point method for symmetric optimization using a positive-asymptotic barrier

We propose a new primal-dual infeasible interior-point method for symmetric optimization by using Euclidean Jordan algebras. Different kinds of interior-point methods can be obtained by using search directions based on kernel functions. Some search directions can be also determined by applying an algebraic equivalent transformation on the centering equation of the central path. Using this method we introduce a new search direction, which can not be derived from a usual kernel function. For this reason, we use the new notion of positive-asymptotic kernel function which induces the class of corresponding barriers. In general, the main iterations of the infeasible interior-point methods are composed of one feasibility and several centering steps. We prove that in our algorithm it is enough to take only one centering step in a main iteration in order to obtain a well-defined algorithm. Moreover, we conclude that the algorithm finds solution in polynomial time and has the same complexity as the currently best known infeasible interior-point methods. Finally, we give some numerical results.     

Using aspiration levels in an interactive interior multiobjective linear programming algorithm

In this paper, we propose the use of an interior-point linear programming algorithm for multiple objective linear programming (MOLP) problems. At each iteration, a Decision Maker (DM) is asked to specify aspiration levels for the various objectives, and an achievement scalarizing function is applied to project aspiration levels onto the nondominated set. The interior-point algorithm is used to find an interior solution path from a starting solution to a nondominated solution corresponding to the optimum of the achievement scalarizing function. The proposed approach allows the DM to re-specify aspiration levels during the solution process and thus steer the interior solution path toward different areas in objective space. We illustrate the use of the approach with a numerical example.     

SEQUENTIAL QUADRATIC PROGRAMMING METHODS FOR OPTIMAL CONTROL PROBLEMS WITH STATE CONSTRAINTS

A Kind of direct methods is presented for the solution of optimal control problems with state constraints.These methods are sequential quadratic programming methods.At every iteration a quadratic programming which is obtained by quadratic approximation to Lagrangian function and Linear approximations to constraints is solved to get a search direction for a merit function.The merit function is formulated by augmenting the Lagrangian funetion with a penalty term.A line search is carried out along the search direction to determine a step length such that the merit function is decreased.The methods presented in this paper include continuous sequential quadratic programming methods and discreate sequential quadrade programming methods.     

Globally Convergent Interior-Point Algorithm for Nonlinear Programming

This paper presents a primal-dual interior-point algorithm for solving general constrained nonlinear programming problems. The inequality constraints are incorporated into the objective function by means of a logarithmic barrier function. Also, satisfaction of the equality constraints is enforced through the use of an adaptive quadratic penalty function. The penalty parameter is determined using a strategy that ensures a descent property for a merit function. Global convergence of the algorithm is achieved through the monotonic decrease of a merit function. Finally, extensive computational results show that the algorithm can solve large and difficult problems in an efficient and robust way.Communicated by L. C. W. DixonThe research reported in this paper was done while the first author was at Imperial College. The authors gratefully acknowledge constructive comments from Professor L. C. W. Dixon and an anonymous referee. They are also grateful to Dr. Stanislav Zakovic for helpful suggestions and comments. Financial support was provided by EPSRC Grants M16016 and GR/G51377/01.     

A filter interior-point algorithm with projected Hessian updating for nonlinear optimization

Filter approaches, initially presented by Fletcher and Leyffer in 2002, are attractive methods for nonlinear programming. In this paper, we propose an interior-point barrier projected Hessian updating algorithm with line search filter method for nonlinear optimization. The Lagrangian function value instead of the objective function value is used in the filter. The damped BFGS updating is employed to maintain the positive definiteness of the matrices in projected Hessian updating algorithm. The numerical experiments are reported to show the effectiveness of the proposed algorithm.     

An interior-point piecewise linear penalty method for nonlinear programming

We present an interior-point penalty method for nonlinear programming (NLP), where the merit function consists of a piecewise linear penalty function and an ? ₂-penalty function. The piecewise linear penalty function is defined by a set of break points that correspond to pairs of values of the barrier function and the infeasibility measure at a subset of previous iterates and this set is updated at every iteration. The ? ₂-penalty function is a traditional penalty function defined by a single penalty parameter. At every iteration the step direction is computed from a regularized Newton system of the first-order equations of the barrier problem proposed in Chen and Goldfarb (Math Program 108:1?C36, 2006). Iterates are updated using a line search. In particular, a trial point is accepted if it provides a sufficient reduction in either of the penalty functions. We show that the proposed method has the same strong global convergence properties as those established in Chen and Goldfarb (Math Program 108:1?C36, 2006). Moreover, our method enjoys fast local convergence. Specifically, for each fixed small barrier parameter???, iterates in a small neighborhood (roughly within o(??)) of the minimizer of the barrier problem converge Q-quadratically to the minimizer. The overall convergence rate of the iterates to the solution of the nonlinear program is Q-superlinear.     

A new second-order corrector interior-point algorithm for semidefinite programming

In this paper, we propose a second-order corrector interior-point algorithm for semidefinite programming (SDP). This algorithm is based on the wide neighborhood. The complexity bound is O(?nL){O(\sqrt{n}L)} for the Nesterov-Todd direction, which coincides with the best known complexity results for SDP. To our best knowledge, this is the first wide neighborhood second-order corrector algorithm with the same complexity as small neighborhood interior-point methods for SDP. Some numerical results are provided as well.     

Global Convergence Analysis of Line Search Interior-Point Methods for Nonlinear Programming without Regularity Assumptions

As noted by Wächter and Biegler (Ref. 1), a number of interior-point methods for nonlinear programming based on line-search strategy may generate a sequence converging to an infeasible point. We show that, by adopting a suitable merit function, a modified primal-dual equation, and a proper line-search procedure, a class of interior-point methods of line-search type will generate a sequence such that either all the limit points of the sequence are KKT points, or one of the limit points is a Fritz John point, or one of the limit points is an infeasible point that is a stationary point minimizing a function measuring the extent of violation to the constraint system. The analysis does not depend on the regularity assumptions on the problem. Instead, it uses a set of satisfiable conditions on the algorithm implementation to derive the desired convergence property.Communicated by Z. Q. LuoThis research was partially supported by Grant R-314-000-026/042/057-112 of National University of Singapore and Singapore-MIT Alliance. We thank Professor Khoo Boo Cheong, Cochair of the High Performance Computation Program of Singapore-MIT Alliance, for his support     

A primal-dual interior-point method for linear programming based on a weighted barrier function

One motivation for the standard primal-dual direction used in interior-point methods is that it can be obtained by solving a least-squares problem. In this paper, we propose a primal-dual interior-point method derived through a modified least-squares problem. The direction used is equivalent to the Newton direction for a weighted barrier function method with the weights determined by the current primal-dual iterate. We demonstrate that the Newton direction for the usual, unweighted barrier function method can be derived through a weighted modified least-squares problem. The algorithm requires a polynomial number of iterations. It enjoys quadratic convergence if the optimal vertex is nondegenerate.The research of the second author was supported in part by ONR Grants N00014-90-J-1714 and N00014-94-1-0391.     

Generalized stationary points and an interior-point method for mathematical programs with equilibrium constraints

Generalized stationary points of the mathematical program with equilibrium constraints (MPEC) are studied to better describe the limit points produced by interior point methods for MPEC. A primal-dual interior-point method is then proposed, which solves a sequence of relaxed barrier problems derived from MPEC. Global convergence results are deduced under fairly general conditions other than strict complementarity or the linear independence constraint qualification for MPEC (MPEC-LICQ). It is shown that every limit point of the generated sequence is a strong stationary point of MPEC if the penalty parameter of the merit function is bounded. Otherwise, a point with certain stationarity can be obtained. Preliminary numerical results are reported, which include a case analyzed by Leyffer for which the penalty interior-point algorithm failed to find a stationary point.Mathematics Subject Classification (1991):90C30, 90C33, 90C55, 49M37, 65K10     

An Interior-Point Algorithm for Nonlinear Minimax Problems

We present a primal-dual interior-point method for constrained nonlinear, discrete minimax problems where the objective functions and constraints are not necessarily convex. The algorithm uses two merit functions to ensure progress toward the points satisfying the first-order optimality conditions of the original problem. Convergence properties are described and numerical results provided.