Properties of the sequential gradient-restoration algorithm (SGRA), part 1: Introduction and comparison with related methods

The sequential gradient-restoration algorithm (SGRA) was developed in the late 1960s for the solution of equality-constrained nonlinear programs and has been successfully implemented by Miele and coworkers on many large-scale problems. The algorithm consists of two major sequentially applied phases. The first is a gradient-type minimization in a subspace tangent to the constraint surface, and the second is a feasibility restoration procedure. In Part 1, the original SGRA algorithm is described and is compared with two other related methods: the gradient projection and the generalized reduced gradient methods. Next, the special case of linear equalities is analyzed. It is shown that, in this case, only the gradient-type minimization phase is needed, and the SGRA becomes identical to the steepest-descent method. Convergence proofs for the nonlinearly constrained case are given in Part 2.Partial support for this work was provided by the Fund for the Promotion of Research at Technion, Israel Institute of Technology, Haifa, Israel.     

Two-Phase Model Algorithm with Global Convergence for Nonlinear Programming

The family of feasible methods for minimization with nonlinear constraints includes the nonlinear projected gradient method, the generalized reduced gradient method (GRG), and many variants of the sequential gradient restoration algorithm (SGRA). Generally speaking, a particular iteration of any of these methods proceeds in two phases. In the restoration phase, feasibility is restored by means of the resolution of an auxiliary nonlinear problem, generally a nonlinear system of equations. In the minimization phase, optimality is improved by means of the consideration of the objective function, or its Lagrangian, on the tangent subspace to the constraints. In this paper, minimal assumptions are stated on the restoration phase and the minimization phase that ensure that the resulting algorithm is globally convergent. The key point is the possibility of comparing two successive nonfeasible iterates by means of a suitable merit function that combines feasibility and optimality. The merit function allows one to work with a high degree of infeasibility at the first iterations of the algorithm. Global convergence is proved and a particular implementation of the model algorithm is described.     

A Dwindling Filter Algorithm with a Modified Subproblem for Nonlinear Inequality Constrained Optimization

The authors propose a dwindling filter algorithm with Zhou＇s modified subprob- lem for nonlinear inequality constrained optimization. The feasibility restoration phase, which is always used in the traditional filter method, is not needed. Under mild conditions, global convergence and local superlinear convergence rates are obtained. Numerical results demonstrate that the new algorithm is effective.     

A feasible filter SQP algorithm with global and local convergence

A feasible sequential quadratic programming (SQP) filter algorithm is proposed for general nonlinear programming. It is based on the modified quadratic programming (QP) subproblem in which each iteration proceeds in two phases. The first phase solves a general convex QP problem which does not require any feasibility restoration phase whose computation may be expensive. And, under some mild conditions, the global convergence is proved. The second phase can make the presented SQP method derive quadratic convergence by employing exact Hessian information.     

Convergence of a Three-Dimensional Dwindling Filter Algorithm Without Feasibility Restoration Phase

In this article, we propose a three-dimensional dwindling filter algorithm for general nonlinear programming. The envelope of the three-dimensional dwindling filter becomes thinner and thinner as the step size approaches zero so that the new filter has more flexibility for the acceptance of the trial step size. Moreover, we show that the feasibility restoration phase, which is always used in traditional filter method, is not needed. The modified limited memory Broyden-Fletcher-Goldfarb-Shanno method is employed in the algorithm, and the update matrices are positive definite when the Lagrangian function is a general convex function. Under mild conditions, the global convergence of the new algorithm is analyzed. The primary numerical experiments are reported to show effectiveness of the proposed algorithm.     

A modified spectral conjugate gradient projection algorithm for total variation image restoration

In this study, a modified spectral conjugate gradient projection method is presented to solve total variation image restoration, which is transferred into the nonlinear constrained optimization with the closed constrained set. The global convergence of the proposed scheme is analyzed. In the end, some numerical results illustrate the efficiency of this method.     

On the optimization of constrained functions: comparison of sequential gradient-restoration algorithm and gradient-projection algorithm

The problem of minimizing a function fnof(x) subject to the nonlinear constraint ?(x) = 0 is considered, where fnof is a scalar, x is an n-vector, and ? is a q-vector, with q < n. The sequential gradient-restoration algorithm (SGRA: Miele, [1, 2]) and the gradient-projection algorithm (GPA: Rosen, [3, 4]) are considered. These algorithms have one common characteristic: they are all composed of the alternate succession of gradient phases and restoration phases. However, they are different in several aspects, namely, (a) problem formulation, (b) structure of the gradient phase, and (c) structure of the restoration phase. First, a critical summary of SGRA and GPA is presented. Then, a comparison is undertaken by considering the speed of convergence and, above all, robustness (that is, the capacity of an algorithm to converge to a solution). The comparison is done through 16 numerical examples. In order to understand the separate effects of characteristics (a), (b), (c), six new experimental algorithms are generated by combining parts of Miele's algorithm with parts of Rosen's algorithm. Thus, the total number of algorithms investigated is eight. The numerical results show that Miele's method is on the average faster than Rosen's method. More importantly, regarding robustness, Miele's method compares favorably with Rosen's method. Through the examples, it is shown that Miele's advantage in robustness is more prominent as the curvature of the constraint increases. While this advantage is due to the combined effect of characteristics (a), (b), (c), it is characteristic (c) that plays the dominant role. Indeed, Miele's restoration provides a better search direction as well as better step-size control than Rosen's restoration.     

A two-stage feasible directions algorithm for nonlinear constrained optimization

We present a feasible directions algorithm, based on Lagrangian concepts, for the solution of the nonlinear programming problem with equality and inequality constraints. At each iteration a descent direction is defined; by modifying it, we obtain a feasible descent direction. The line search procedure assures the global convergence of the method and the feasibility of all the iterates. We prove the global convergence of the algorithm and apply it to the solution of some test problems. Although the present version of the algorithm does not include any second-order information, like quasi-Newton methods, these numerical results exhibit a behavior comparable to that of the best methods known at present for nonlinear programming. Research performed while the author was on a two years appointment at INRIA, Rocquencourt, France, and partially supported by the Brazilian Research Council (CNPq).     

Multiple-Subarc Gradient-Restoration Algorithm, Part 1: Algorithm Structure

Rapid progresses in information and computer technology allow the development of more advanced optimal control algorithms dealing with real-world problems. In this paper, which is Part 1 of a two-part sequence, a multiple-subarc gradient-restoration algorithm (MSGRA) is developed. We note that the original version of the sequential gradient-restoration algorithm (SGRA) was developed by Miele et al. in single-subarc form (SSGRA) during the years 1968–86; it has been applied successfully to solve a large number of optimal control problems of atmospheric and space flight.MSGRA is an extension of SSGRA, the single-subarc gradient-restoration algorithm. The primary reason for MSGRA is to enhance the robustness of gradient-restoration algorithms and also to enlarge the field of applications. Indeed, MSGRA can be applied to optimal control problems involving multiple subsystems as well as discontinuities in the state and control variables at the interface between contiguous subsystems.Two features of MSGRA are increased automation and efficiency. The automation of MSGRA is enhanced via time normalization: the actual time domain is mapped into a normalized time domain such that the normalized time length of each subarc is 1. The efficiency of MSGRA is enhanced by using the method of particular solutions to solve the multipoint boundary-value problems associated with the gradient phase and the restoration phase of the algorithm.In a companion paper [Part 2 (Ref. 2)], MSGRA is applied to compute the optimal trajectory for a multistage launch vehicle design, specifically, a rocket-powered spacecraft ascending from the Earth surface to a low Earth orbit (LEO). Single-stage, double-stage, and triple-stage configurations are considered and compared.     

m步非线性多重分裂Newton法的收敛性

本文讨论了多重分裂算法在求解一类非线性方程组的全局收敛性和单侧收敛性．当用研步Newton法来代替求得每个非线性多重分裂子问题的近似解时，同样给出相应收敛性结论．数值算例证实了算法的有效性．     

An outcome space algorithm for optimization over the weakly efficient set of a multiple objective nonlinear programming problem

This article presents for the first time an algorithm specifically designed for globally minimizing a finite, convex function over the weakly efficient set of a multiple objective nonlinear programming problem (V1) that has both nonlinear objective functions and a convex, nonpolyhedral feasible region. The algorithm uses a branch and bound search in the outcome space of problem (V1), rather than in the decision space of the problem, to find a global optimal solution. Since the dimension of the outcome space is usually much smaller than the dimension of the decision space, often by one or more orders of magnitude, this approach can be expected to considerably shorten the search. In addition, the algorithm can be easily modified to obtain an approximate global optimal weakly efficient solution after a finite number of iterations. Furthermore, all of the subproblems that the algorithm must solve can be easily solved, since they are all convex programming problems. The key, and sometimes quite interesting, convergence properties of the algorithm are proven, and an example problem is solved.     

Wolfe线搜索下新的共轭梯度法的全局收敛性

共轭梯度法是求解无约束优化问题的一种重要的方法.本文提出一族新的共轭梯度法,证明了其在推广的Wolfe非精确线搜索条件下具有全局收敛性.最后对算法进行了数值实验,实验结果验证了该算法的有效性.     

非线性约束条件下的SQP可行方法

本文对非线性规划问题给出了一个具有一步超线性收敛速度的可行方法。由于此算法每步迭代均在可行域内进行，并且每步迭代只需计算一个二次子规划和一个逆矩阵，因而算法具有较好的实用价值。本文还在较弱的条件下证明了算法的全局收敛和一步超线性收敛性。     

一族新的共轭梯度法的全局收敛性

共轭梯度法是求解无约束优化问题的一种重要的方法,尤其适用于大规模优化问题的求解。本文提出一族新的共轭梯度法,证明了其在推广的Wolfe非精确线搜索条件下具有全局收敛性。最后对算法进行了数值试验,试验结果验证了该算法的有效性。     

On the global convergence of an SLP–filter algorithm that takes EQP steps

 A global convergence proof is presented for a class of trust region filter–type methods for nonlinear programming. Such methods are characterized by their use of the dominance concept of multiobjective optimization, instead of a penalty parameter whose adjustment can be problematic. The methods are based on successively solving linear programming subproblems for which effective software is readily available. The methods also permit the use of steps calculated on the basis of an equality constrained quadratic programming model, which enables rapid convergence to take place for problems in which second order information is important. The proof technique is presented in a fairly general context, allowing a range of specific algorithm choices associated with choosing the quadratic model, updating the trust region radius and with feasibility restoration. Received: July 4, 2001 / Accepted: December 19, 2002 Published online: March 21, 2003 Mathematics Subject Classification (2000): 20E28, 20G40, 20C20     

On the superlinear local convergence of a filter-SQP method

Transition to superlinear local convergence is shown for a modified version of the trust-region filter-SQP method for nonlinear programming introduced by Fletcher, Leyffer, and Toint [8]. Hereby, the original trust-region SQP-steps can be used without an additional second order correction. The main modification consists in using the Lagrangian function value instead of the objective function value in the filter together with an appropriate infeasibility measure. Moreover, it is shown that the modified trust-region filter-SQP method has the same global convergence properties as the original algorithm in [8].Mathematics Subject Classification (2000): 90C55, 65K05, 90C30     

Global convergence for a 1-D inverse problem with application to imaging of land mines

A new globally convergent numerical method is developed for a 1-D coefficient inverse problem for a hyperbolic partial differential equation (PDE). The back reflected data are used. A version of the quasi-reversibility method is proposed. A global convergence theorem is proven via a Carleman estimate. The results of numerical experiments are presented.     

信赖域算法的修订算法

为了求得非线性优化问题的最优解,必须从收敛的可能性和收敛速度入手实现有效的计算方法.为此,通过改变作为搜索方向的下降方向,并适当修订信赖范围,在信赖域算法的基础上提出了一种修订的最优化问题的求解方法.计算方法的计算程序虽然有些复杂,但从整体收敛性和计算可行性方面来说是一个有效的方法.     

A kind of nonmonotone filter method for nonlinear complementarity problem

The nonlinear complementarity problem can be reformulated as a nonlinear programming. For solving nonlinear programming, sequential quadratic programming (SQP) type method is very effective. But the QP subproblem may be inconsistent. In this paper, we propose a kind nonmonotone filter method in which the QP subproblem is consistent. By means of nonmonotone filter, this method has no demand on the penalty parameter which is difficult to obtain. Moreover, the restoration phase is not needed any more. Under reasonable conditions, we obtain the global convergence of the algorithm. Some numerical results are presented.