An SQP method for general nonlinear programs using only equality constrained subproblems

In this paper we describe a new version of a sequential equality constrained quadratic programming method for general nonlinear programs with mixed equality and inequality constraints. Compared with an older version [P. Spellucci, Han's method without solving QP, in: A. Auslender, W. Oettli, J. Stoer (Eds), Optimization and Optimal Control, Lecture Notes in Control and Information Sciences, vol. 30, Springer, Berlin, 1981, pp. 123–141.] it is much simpler to implement and allows any kind of changes of the working set in every step. Our method relies on a strong regularity condition. As far as it is applicable the new approach is superior to conventional SQP-methods, as demonstrated by extensive numcrical tests. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

A trust region SQP algorithm for mixed-integer nonlinear programming

We propose a modified sequential quadratic programming method for solving mixed-integer nonlinear programming problems. Under the assumption that integer variables have a smooth influence on the model functions, i.e., that function values do not change drastically when in- or decrementing an integer value, successive quadratic approximations are applied. The algorithm is stabilized by a trust region method with Yuan’s second order corrections. It is not assumed that the mixed-integer program is relaxable or, in other words, function values are evaluated only at integer points. The Hessian of the Lagrangian function is approximated by a quasi-Newton update formula subject to the continuous and integer variables. Numerical results are presented for a set of 80 mixed-integer test problems taken from the literature. The surprising result is that the number of function evaluations, the most important performance criterion in practice, is less than the number of function calls needed for solving the corresponding relaxed problem without integer variables.     

Integrating SQP and Branch-and-Bound for Mixed Integer Nonlinear Programming

This paper considers the solution of Mixed Integer Nonlinear Programming (MINLP) problems. Classical methods for the solution of MINLP problems decompose the problem by separating the nonlinear part from the integer part. This approach is largely due to the existence of packaged software for solving Nonlinear Programming (NLP) and Mixed Integer Linear Programming problems.In contrast, an integrated approach to solving MINLP problems is considered here. This new algorithm is based on branch-and-bound, but does not require the NLP problem at each node to be solved to optimality. Instead, branching is allowed after each iteration of the NLP solver. In this way, the nonlinear part of the MINLP problem is solved whilst searching the tree. The nonlinear solver that is considered in this paper is a Sequential Quadratic Programming solver.A numerical comparison of the new method with nonlinear branch-and-bound is presented and a factor of up to 3 improvement over branch-and-bound is observed.     

等式约束优化一个新的SQP算法

提出了一个处理等式约束优化问题新的SQP算法,该算法通过求解一个增广Lagrange函数的拟Newton方法推导出一个等式约束二次规划子问题,从而获得下降方向．罚因子具有自动调节性,并能避免趋于无穷．为克服Maratos效应采用增广Lagrange函数作为效益函数并结合二阶步校正方法．在适当的条件下,证明算法是全局收敛的,并且具有超线性收敛速度．     

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.     

Using the KKT matrix in an augmented Lagrangian SQP method for sparse constrained optimization

The augmented Lagrangian SQP subroutine OPALQP was originally designed for small-to-medium sized constrained optimization problems in which the main calculation on each iteration, the solution of a quadratic program, involves dense, rather than sparse, matrices. In this paper, we consider some reformulations of OPALQP which are better able to take advantage of sparsity in the objective function and constraints.The modified versions of OPALQP differ from the original in using sparse data structures for the Jacobian matrix of constraints and in replacing the dense quasi-Newton estimate of the inverse Hessian of the Lagrangian by a sparse approximation to the Hessian. We consider a very simple sparse update for estimating ² L and also investigate the benefits of using exact second derivatives, noting in the latter case that safeguards are needed to ensure that a suitable search direction is obtained when ² L is not positive definite on the null space of the active constraints.The authors are grateful to John Reid and Nick Gould of the Rutherford Appleton Laboratory for a number of helpful and interesting discussions. Thanks are also due to Laurence Dixon for comments which led to the clarification of some parts of the paper.This work has been partly supported by a CAPES Research Studentship funded by the Brazilian Government.     

The Lagrange-Newton method for nonlinear optimal control problems

We investigate local convergence of the Lagrange-Newton method for nonlinear optimal control problems subject to control constraints including the situation where the terminal state is fixed. Sufficient conditions for local quadratic convergence of the method based on stability results for the solutions of nonlinear control problems are discussed.     

非线性互补问题的SQP方法

In this paper, the nonlinear complementarity problem is transformed into the least squares problem with nonnegative constraints ,and a SQP algorithm for this reformulation based on a damped Gauss-Newton type method is presented. It is shown that the algorithm is globally and locally superlinearly (quadratically) convergent without the assumption of monotonicity.     

约束优化无罚函数非单调SQP算法

本文研究求解非线性约束优化问题.利用非单调无罚函数方法,提出了一个新的序列二次规划算法.该算法在每次迭代过程中只需求解一个QP子问题和一个线性方程组.在一般条件下,算法具有全局收敛性,数值结果表明,计算量小于单调且含罚函数的传统算法.     

An NE/SQP Method for the Bounded Nonlinear Complementarity Problem

NE/SQP (Refs. 2–3) is a recent algorithm that has proven quite effective for solving the nonlinear complementarity problem (NCP). NE/SQP is robust in the sense that its direction-finding subproblems are always solvable; in addition, the convergence rate of this method is q-quadratic. In this note, we consider a generalized version of NE/SQP, as first described in Ref. 4, which is suitable for the bounded NCP. We extend the work in Ref. 4 by demonstrating a stronger convergence result and present numerical results on test problems.     

A new technique for avoiding the Maratos effect

A well-known difficulty arising in the convergence globalization of Newton-type constrained optimization methods is the Maratos effect, which prevents these methods from achieving a superlinear convergence rate and, in many cases, reduces their general efficiency. For the sequential quadratic programming method with linesearch, a new simple and rather promising technique is proposed to avoid the Maratos effect.     

A Modified SQP Method and Its Global Convergence

The sequential quadratic programming method developed by Wilson, Han andPowell may fail if the quadratic programming subproblems become infeasibleor if the associated sequence of search directions is unbounded. In [1], Hanand Burke give a modification to this method wherein the QP subproblem isaltered in a way which guarantees that the associated constraint region isnonempty and for which a robust convergence theory is established. In thispaper, we give a modification to the QP subproblem and provide a modifiedSQP method. Under some conditions, we prove that the algorithm eitherterminates at a Kuhn–Tucker point within finite steps or generates aninfinite sequence whose every cluster is a Kuhn–Tucker point.Finally, we give some numerical examples.     

An inexact NE/SQP method for solving the nonlinear complementarity problem

In this paper, we present an extension to the NE/SQP method; the latter is a robust algorithm that we proposed for solving the nonlinear complementarity problem in an earlier article. In this extended version of NE/SQP, instead of exactly solving the quadratic program subproblems, approximate solutions are generated via an inexact rule.Under a proper choice for this rule, this inexact method is shown to inherit the same convergence properties of the original NE/SQP method. In addition to developing the convergence theory for the inexact method, we also present numerical results of the algorithm tested on two problems of varying size.     

The Lagrange-Newton method for state constrained optimal control problems

Local convergence of the Lagrange-Newton method for optimization problems with two-norm discrepancy in abstract Banach spaces is investigated. Based on stability analysis of optimization problems with two-norm discrepancy, sufficient conditions for local superlinear convergence are derived. The abstract results are applied to optimal control problems for nonlinear ordinary differential equations subject to control and state constraints.This research was completed while the second author was a visitor at the University of Bayreuth, Germany, supported by grant No. CIPA3510CT920789 from the Commission of the European Communities.     

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 SQP METHOD FOR GENERAL NONLINEAR COMPLEMENTARITY PROBLEMS

§ 1　 IntroductionThe nonlinear complementarity problem(NCP) is to find a pointx∈Rn such thatx Tf(x) =0 ,x≥ 0 ,f(x)≥ 0 ,(1 .1 )where f is a continuously differentiable function from Rninto itself.It is well known thatthe NCP is equivalent to a system of smoothly nonlinear equations with nonnegative con-straintsH (z)∶ =y -f(x)x . y =0 ,s.t. x≥ 0 ,y≥ 0 ,(1 .2 )where z=(x,y) and x y=(x1 y1 ,...,xnyn) T.Based on the above reformulation,many in-terior-point methods are established;see,fo…     

A new technique for generating quadratic programming test problems

This paper describes a new technique for generating convex, strictly concave and indefinite (bilinear or not) quadratic programming problems. These problems have a number of properties that make them useful for test purposes. For example, strictly concave quadratic problems with their global maximum in the interior of the feasible domain and with an exponential number of local minima with distinct function values and indefinite and jointly constrained bilinear problems with nonextreme global minima, can be generated.Unlike most existing methods our construction technique does not require the solution of any subproblems or systems of equations. In addition, the authors know of no other technique for generating jointly constrained bilinear programming problems.Support of this work has been provided by the Instituto Nacional de Investigação Científica de Portugal (INIC) under contract 89/EXA/5 and by the Natural Sciences and Engineering Research Council of Canada operating grant 5671.Much of this paper was completed while this author was on a research sabbatical at the Universidade de Coimbra, Portugal.     

A modified SQP algorithm for minimax problems

In this paper, a modified nonmonotone line search SQP algorithm for nonlinear minimax problems is presented. During each iteration of the proposed algorithm, a main search direction is obtained by solving a reduced quadratic program (QP). In order to avoid the Maratos effect, a correction direction is generated by solving the reduced system of linear equations. Under mild conditions, the global and superlinear convergence can be achieved. Finally, some preliminary numerical results are reported.     

Numerical solution of a nonlinear parabolic control problem by a reduced SQP method

We consider a control problem for a nonlinear diffusion equation with boundary input that occurs when heating ceramic products in a kiln. We interpret this control problem as a constrained optimization problem, and we develop a reduced SQP method that presents for this problem a new and efficient approach of its numerical solution. As opposed to Newton's method for the unconstrained problem, where at each iteration the state must be computed from a set of nonlinear equations,in the proposed algorithm only the linearized state equations need to be solved. Furthermore, by use of a secant update formula, the calculation of exact second derivatives is avoided. In this way the algorithm achieves a substantial decrease in the total cost compared to the implementation of Newton's method in [2]. Our method is practicable with regard to storage requirements, and by choosing an appropriate representation for the null space of the Jacobian of the constraints we are able to exploit the sparsity pattern of the Jacobian in the course of the iteration. We conclude with a presentation of numerical examples that demonstrate the fast two-step superlinear convergence behavior of the method.