Local Convergence of the Affine-Scaling Interior-Point Algorithm for Nonlinear Programming

This paper addresses the local convergence properties of the affine-scaling interior-point algorithm for nonlinear programming. The analysis of local convergence is developed in terms of parameters that control the interior-point scheme and the size of the residual of the linear system that provides the step direction. The analysis follows the classical theory for quasi-Newton methods and addresses q-linear, q-superlinear, and q-quadratic rates of convergence.     

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.     

A Simple Primal-Dual Feasible Interior-Point Method for Nonlinear Programming with Monotone Descent

We propose and analyze a primal-dual interior point method of the feasible type, with the additional property that the objective function decreases at each iteration. A distinctive feature of the method is the use of different barrier parameter values for each constraint, with the purpose of better steering the constructed sequence away from non-KKT stationary points. Assets of the proposed scheme include relative simplicity of the algorithm and of the convergence analysis, strong global and local convergence properties, and good performance in preliminary tests. In addition, the initial point is allowed to lie on the boundary of the feasible set.     

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.     

Quadratic Convergence of a Primal-Dual Interior Point Method for Degenerate Nonlinear Optimization Problems

Recently studies of numerical methods for degenerate nonlinear optimization problems have been attracted much attention. Several authors have discussed convergence properties without the linear independence constraint qualification and/or the strict complementarity condition. In this paper, we are concerned with quadratic convergence property of a primal-dual interior point method, in which Newton’s method is applied to the barrier KKT conditions. We assume that the second order sufficient condition and the linear independence of gradients of equality constraints hold at the solution, and that there exists a solution that satisfies the strict complementarity condition, and that multiplier iterates generated by our method for inequality constraints are uniformly bounded, which relaxes the linear independence constraint qualification. Uniform boundedness of multiplier iterates is satisfied if the Mangasarian-Fromovitz constraint qualification is assumed, for example. By using the stability theorem by Hager and Gowda (1999), and Wright (2001), the distance from the current point to the solution set is related to the residual of the KKT conditions.By controlling a barrier parameter and adopting a suitable line search procedure, we prove the quadratic convergence of the proposed algorithm.     

求解非凸半定规划的一个非线性Lagrange算法及其收敛性分析

本文提出了一个求解非凸半定规划的非线性Lagrange算法,当二阶充分条件以及严格互补条件成立时,证明了这一算法的收敛性定理.收敛结果表明,当惩罚参数小于某个阀值时,算法是局部收敛的;此外,还给出了解的一个依赖于惩罚参数的误差界.     

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     

Interior-Point Algorithms for Semidefinite Programming Based on a Nonlinear Formulation

Recently in Burer et al. (Mathematical Programming A, submitted), the authors of this paper introduced a nonlinear transformation to convert the positive definiteness constraint on an n × n matrix-valued function of a certain form into the positivity constraint on n scalar variables while keeping the number of variables unchanged. Based on this transformation, they proposed a first-order interior-point algorithm for solving a special class of linear semidefinite programs. In this paper, we extend this approach and apply the transformation to general linear semidefinite programs, producing nonlinear programs that have not only the n positivity constraints, but also n additional nonlinear inequality constraints. Despite this complication, the transformed problems still retain most of the desirable properties. We propose first-order and second-order interior-point algorithms for this type of nonlinear program and establish their global convergence. Computational results demonstrating the effectiveness of the first-order method are also presented.     

Local Convergence of the Interior-Point Newton Method for General Nonlinear Programming

In this paper, a formulation for an interior-point Newton method of general nonlinear programming problems is presented. The formulation uses the Coleman-Li scaling matrix. The local convergence and the q-quadratic rate of convergence for the method are established under the standard assumptions of the Newton method for general nonlinear programming.     

Primal-Dual Newton-Type Interior-Point Method for Topology Optimization

We consider the problem of minimization of energy dissipation in a conductive electromagnetic medium with a fixed geometry and a priori given lower and upper bounds for the conductivity. The nonlinear optimization problem is analyzed by using the primal-dual Newton interior-point method. The elliptic differential equation for the electric potential is considered as an equality constraint. Transforming iterations for the null space decomposition of the condensed primal-dual system are applied to find the search direction. The numerical experiments treat two-dimensional isotropic systems.     

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.     

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.     

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.     

Stabilization of Interior-Point Methods for Linear Programming

The paper studies numerical stability problems arising in the application of interior-point methods to primal degenerate linear programs. A stabilization procedure based on Gaussian elimination is proposed and it is shown that it stabilizes all path following methods, original and modified Dikin's method, Karmarkar's method, etc.     

Superlinear Convergence of a Stabilized SQP Method to a Degenerate Solution

We describe a slight modification of the well-known sequential quadratic programming method for nonlinear programming that attains superlinear convergence to a primal-dual solution even when the Jacobian of the active constraints is rank deficient at the solution. We show that rapid convergence occurs even in the presence of the roundoff errors that are introduced when the algorithm is implemented in floating-point arithmetic.     

Global Convergence of the Newton Interior-Point Method for Nonlinear Programming

The aim of this paper is to show that the theorem on the global convergence of the Newton interior–point (IP) method presented in Ref. 1 can be proved under weaker assumptions. Indeed, we assume the boundedness of the sequences of multipliers related to nontrivial constraints, instead of the hypothesis that the gradients of the inequality constraints corresponding to slack variables not bounded away from zero are linearly independent. By numerical examples, we show that, in the implementation of the Newton IP method, loss of boundedness in the iteration sequence of the multipliers detects when the algorithm does not converge from the chosen starting point.     

非线性整规划的连续化

本文讨论了非线性整规划问题的连续化途径．结论是可以将无约束和有约束的非线性整规划全局解问题化为非线性连续规划问题求解．     

Dynamic Programming Method for Constrained Discrete-Time Optimal Control

A dynamic programming method is presented for solving constrained, discrete-time, optimal control problems. The method is based on an efficient algorithm for solving the subproblems of sequential quadratic programming. By using an interior-point method to accommodate inequality constraints, a modification of an existing algorithm for equality constrained problems can be used iteratively to solve the subproblems. Two test problems and two application problems are presented. The application examples include a rest-to-rest maneuver of a flexible structure and a constrained brachistochrone problem.     

On the Convergence of a Trust-Region Method for Solving Constrained Nonlinear Equations with Degenerate Solutions

This paper presents a trust-region method for solving the constrained nonlinear equation F(x) = 0, x , where R ⁿ is a nonempty and closed convex set, F is defined on the open set containing and is continuously differentiable. The iterates generated by the method are feasible. The method is globally and quadratically convergent under local error bounded assumption on F. The results obtained are extensions of the work of Yamashita Fukushima (Ref. 1) and Fan Yuan (Ref. 2) for unconstrained nonlinear equations. Numerical results show that the new algorithm works quite well.     

A Trust-Region Method for Nonlinear Bilevel Programming: Algorithm and Computational Experience

We consider the approximation of nonlinear bilevel mathematical programs by solvable programs of the same type, i.e., bilevel programs involving linear approximations of the upper-level objective and all constraint-defining functions, as well as a quadratic approximation of the lower-level objective. We describe the main features of the algorithm and the resulting software. Numerical experiments tend to confirm the promising behavior of the method.