A globally convergent method for nonlinear programming

Recently developed Newton and quasi-Newton methods for nonlinear programming possess only local convergence properties. Adopting the concept of the damped Newton method in unconstrained optimization, we propose a stepsize procedure to maintain the monotone decrease of an exact penalty function. In so doing, the convergence of the method is globalized.This research was supported in part by the National Science Foundation under Grant No. ENG-75-10486.     

A globally convergent primal-dual interior-point filter method for nonlinear programming

In this paper, the filter technique of Fletcher and Leyffer (1997) is used to globalize the primal-dual interior-point algorithm for nonlinear programming, avoiding the use of merit functions and the updating of penalty parameters.The new algorithm decomposes the primal-dual step obtained from the perturbed first-order necessary conditions into a normal and a tangential step, whose sizes are controlled by a trust-region type parameter. Each entry in the filter is a pair of coordinates: one resulting from feasibility and centrality, and associated with the normal step; the other resulting from optimality (complementarity and duality), and related with the tangential step.Global convergence to first-order critical points is proved for the new primal-dual interior-point filter algorithm.Mathematics Subject Classification (1991): 65K05, 90C06, 90C29, 90C30Support for this author was provided by CRPC grant CCR–9120008.Support for this author was provided by CRPC grant CCR–9120008.Support for this author was provided by Centro de Matemática da Universidade de Coimbra, by FCT under grant POCTI/35059/MAT/2000, by the European Union under grant IST-2000-26063, and by Fundaç\ ao Calouste Gulbenkian. The author would also like to thank the IBM T.J. Watson Research Center and the Institute for Mathematics and Its Applications for their local support.     

A globally convergent method for solving nonlinear equations without the differentiability condition

We give a general iterative method which computes the maximal real rootx _max of a one variable Lipschitzian function in a given interval. The method generates a monotonically decreasing sequence which converges towardsx _max or demonstrates the non-existence of a real root in the considered interval. We show that the method is globally convergent and locally linearly convergent. We also compute the number of iterations needed to reach the given accuracy.     

A minimax optimal control problem

A control system x=f(t,x,u) is considered, and a cost functional ess supT ₀tT ₁ G(t, x(t),u(t)) is to be minimized. Necessary conditions for optimality (maximum principle and transversality conditions) are derived. It is also shown that an optimal control is optimal for the corresponding problem on a subinterval of [T ₀,T ₁], if a certain controllability condition is satisfied.     

Optimal feedback control laws using nonlinear programming

A procedure of parametrizing feedback controls when solving the optimal control problem using nonlinear programming is considered. The maximum principle is utilized to determine the forms of the parametrized feedback control. Applications are demonstrated by numerical examples.     

A globally convergent interior point algorithm for non-convex nonlinear programming

In this paper, a new algorithm for tracing the combined homotopy path of the non-convex nonlinear programming problem is proposed. The algorithm is based on the techniques of β$\beta$-cone neighborhood and a combined homotopy interior point method. The residual control criteria, which ensures that the obtained iterative points are interior points, is given by the condition that ensures the β$\beta$-cone neighborhood to be included in the interior part of the feasible region. The global convergence and polynomial complexity are established under some hypotheses.     

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.     

Minimax Control for a Class of Linear Systems Subject to Disturbances<Superscript>1</Superscript>

A class of linear dynamical control systems subject to uncertain but bounded disturbances is considered. The bounds imposed on the disturbances depend on the control magnitude and grow with the control. This situation occurs if the disturbances are due to the inaccuracy of the control implementation and often takes place in engineering applications such as transportation, aerospace, and robotic systems. Under certain assumptions, the minimax control problem is formulated and solved. Explicit expressions for the optimal control (both open-loop and feedback) are obtained that provide the minimax to the given performance index for arbitrary but bounded disturbances. Examples are given. ¹This work was supported by the Russian Foundation for Basic Research (Project 05-01-00647) and the Grant for Russian Scientific Schools (NSh 1627.2003.1).     

Convergence of the control parameterization Ritz method for nonlinear optimal control problems

This paper studies the local convergence properties of the control parameterization Ritz method in which the control variable is approximated over a finite-dimensional subspace. The nonlinear free-endpoint optimal control problem is considered, and error bounds are derived for both the cost functional and state-control convergence. Explicit error bounds are obtained for the particular case of approximations over spline spaces. On specializing the general results to the linear-quadratic regulator problem, global convergence results are obtained. Computational results supporting the theoretically derived error bounds are presented.This research was supported by the University Grants Committee of New Zealand.     

A feasible SQP method for nonlinear programming

In this paper, a new SQP algorithm is presented to solve the general nonlinear programs with mixed equality and inequality constraints. Quoted from P. Spellucci (see [9]), this method maybe be named sequential equality constrained quadratic programming (SECQP) algorithm. Per single iteration, based on an active set strategy ( see [9]), this SECQP algorithm requires only to solve equality constrained quadratic programming subproblems or system of linear equations. The theoretical analysis shows that global and superlinear convergence can be induced under some suitable conditions.     

A filter inexact-restoration method for nonlinear programming

A new iterative algorithm based on the inexact-restoration (IR) approach combined with the filter strategy to solve nonlinear constrained optimization problems is presented. The high level algorithm is suggested by Gonzaga et al. (SIAM J. Optim. 14:646–669, 2003) but not yet implement—the internal algorithms are not proposed. The filter, a new concept introduced by Fletcher and Leyffer (Math. Program. Ser. A 91:239–269, 2002), replaces the merit function avoiding the penalty parameter estimation and the difficulties related to the nondifferentiability. In the IR approach two independent phases are performed in each iteration, the feasibility and the optimality phases. The line search filter is combined with the first one phase to generate a “more feasible” point, and then it is used in the optimality phase to reach an “optimal” point. Numerical experiences with a collection of AMPL problems and a performance comparison with IPOPT are provided.      

A homotopy method for nonlinear semidefinite programming

In this paper, for solving the nonlinear semidefinite programming problem, a homotopy is constructed by using the parameterized matrix inequality constraint. Existence of a smooth path determined by the homotopy equation, which starts from almost everywhere and converges to a Karush–Kuhn–Tucker point, is proven under mild conditions. A predictor-corrector algorithm is given for numerically tracing the smooth path. Numerical tests with nonlinear semidefinite programming formulations of several control design problems with the data contained in COMPl _e ib are done. Numerical results show that the proposed algorithm is feasible and applicable.     

A gradient projection-multiplier method for nonlinear programming

This paper describes a gradient projection-multiplier method for solving the general nonlinear programming problem. The algorithm poses a sequence of unconstrained optimization problems which are solved using a new projection-like formula to define the search directions. The unconstrained minimization of the augmented objective function determines points where the gradient of the Lagrangian function is zero. Points satisfying the constraints are located by applying an unconstrained algorithm to a penalty function. New estimates of the Lagrange multipliers and basis constraints are made at points satisfying either a Lagrangian condition or a constraint satisfaction condition. The penalty weight is increased only to prevent cycling. The numerical effectiveness of the algorithm is demonstrated on a set of test problems.The author gratefully acknowledges the helpful suggestions of W. H. Ailor, J. L. Searcy, and D. A. Schermerhorn during the preparation of this paper. The author would also like to thank D. M. Himmelblau for supplying a number of interesting test problems.     

Direct training method for a continuous-time nonlinear optimal feedback controller

The solutions of most nonlinear optimal control problems are given in the form of open-loop optimal control which is computed from a given fixed initial condition. Optimal feedback control can in principle be obtained by solving the corresponding Hamilton-Jacobi-Bellman dynamic programming equation, though in general this is a difficult task. We propose a practical and effective alternative for constructing an approximate optimal feedback controller in the form of a feedforward neural network, and we justify this choice by several reasons. The controller is capable of approximately minimizing an arbitrary performance index for a nonlinear dynamical system for initial conditions arising from a nontrivial bounded subset of the state space. A direct training algorithm is proposed and several illustrative examples are given.This research was carried out with the support of a grant from the Australian Research Council.We thank the anonymous reviewers for their helpful comments.     

A smooth method for the finite minimax problem

We consider unconstrained minimax problems where the objective function is the maximum of a finite number of smooth functions. We prove that, under usual assumptions, it is possible to construct a continuously differentiable function, whose minimizers yield the minimizers of the max function and the corresponding minimum values. On this basis, we can define implementable algorithms for the solution of the minimax problem, which are globally convergent at a superlinear convergence rate. Preliminary numerical results are reported.This research was partially supported by the National Research Program on Metodi di ottimizzazione per le decisioni, Ministero dell'Università e della Ricerca Scientifica e Tecnologica, Italy.     

A nonlinear augmented Lagrangian for constrained minimax problems

A novel smooth nonlinear augmented Lagrangian for solving minimax problems with inequality constraints, is proposed in this paper, which has the positive properties that the classical Lagrangian and the penalty function fail to possess. The corresponding algorithm mainly consists of minimizing the nonlinear augmented Lagrangian function and updating the Lagrange multipliers and controlling parameter. It is demonstrated that the algorithm converges Q-superlinearly when the controlling parameter is less than a threshold under the mild conditions. Furthermore, the condition number of the Hessian of the nonlinear augmented Lagrangian function is studied, which is very important for the efficiency of the algorithm. The theoretical results are validated further by the preliminary numerical experiments for several testing problems reported at last, which show that the nonlinear augmented Lagrangian is promising.     

A computational method for a class of optimal relaxed control problems

In the present paper, we propose a computational scheme for solving a class of optimal relaxed control problems, using the concept of control parametrization. Furthermore, some important convergence properties of the proposed computational scheme are investigated. For illustration, a numerical example is also included.     

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.     

A globally convergent derivative-free method for solving large-scale nonlinear monotone equations

In this paper, we propose two derivative-free iterative methods for solving nonlinear monotone equations, which combines two modified HS methods with the projection method in Solodov and Svaiter (1998) [5]. The proposed methods can be applied to solve nonsmooth equations. They are suitable to large-scale equations due to their lower storage requirement. Under mild conditions, we show that the proposed methods are globally convergent. The reported numerical results show that the methods are efficient.