A filter trust-region algorithm for unconstrained optimization with strong global convergence properties

We present a new filter trust-region approach for solving unconstrained nonlinear optimization problems making use of the filter technique introduced by Fletcher and Leyffer to generate non-monotone iterations. We also use the concept of a multidimensional filter used by Gould et?al. (SIAM J. Optim. 15(1):17?C38, 2004) and introduce a new filter criterion showing good properties. Moreover, we introduce a new technique for reducing the size of the filter. For the algorithm, we present two different convergence analyses. First, we show that at least one of the limit points of the sequence of the iterates is first-order critical. Second, we prove the stronger property that all the limit points are first-order critical for a modified version of our algorithm. We also show that, under suitable conditions, all the limit points are second-order critical. Finally, we compare our algorithm with a natural trust-region algorithm and the filter trust-region algorithm of Gould et al. on the CUTEr unconstrained test problems Gould et?al. in ACM Trans. Math. Softw. 29(4):373?C394, 2003. Numerical results demonstrate the efficiency and robustness of our proposed algorithms.     

基于简单二次函数模型的非单调信赖域算法

基于简单二次函数模型,结合非单调技术,建立了一个新的求解无约束最优化问题的非单调信赖域算法,并证明了算法的全局收敛性及超线性收敛性.数值例子表明算法是有效性的,适合求解大规模问题.     

新非单调线搜索规则的Lampariello修正对角稀疏拟牛顿算法

本文设计了求解无约束最优化问题的新的非单调线搜索规则的Lampariello修正对角稀疏拟牛顿算法.新的步长规则类似于Grippo非单调线搜索规则并包含Grippo非单调线搜索规则作为特例.新的步长规则在每一次线搜索时得到一个相对于Grippo非单调线搜索规则的较大步长,同时保证算法的全局收敛性.数值例子表明算法是有效的,适合求解大规模问题.     

A new non-monotone self-adaptive trust region method for unconstrained optimization

In this paper, based on a simple model of trust region sub-problem, we combine the trust region method with the non-monotone and self-adaptive techniques to propose a new non-monotone self-adaptive trust region algorithm for unconstrained optimization. By use of the simple model, the new method needs less memory capacitance, computational complexity and CPU time. The convergence results of the method are proved under certain conditions. Numerical results show that the new method is effective and attractive for large-scale optimization problems.     

凸约束优化的非单调信赖域算法的收敛性

本文对凸约束优化问题提出一类新的非单调信赖域算法，在二次模型Hesse矩阵{Bk}一致有界条件下，证明了算法具有强收敛性；在{Bk}线性增长的条件下，证明了算法具有弱收敛性；这推广了现有约束或凸约束优化问题的各种信赖域算法，改进了收敛性结果。     

基于信赖域技术的非单调超记忆梯度算法

基于信赖域技术和修正拟牛顿方程,结合Zhang H.C.非单调策略,设计了新的求解无约束最优化问题的非单调超记忆梯度算法,分析了算法的收敛性和收敛速度.数值实验表明算法是有效的,适于求解大规模问题.     

一类带非单调线搜索的信赖域算法

通过将非单调Wolfe线搜索技术与传统的信赖域算法相结合,我们提出了一类新的求解无约束最优化问题的信赖域算法.新算法在每一迭代步只需求解一次信赖域子问题,而且在每一迭代步Hesse阵的近似都满足拟牛顿条件并保持正定传递.在一定条件下,证明了算法的全局收敛性和强收敛性.数值试验表明新算法继承了非单调技术的优点,对于求解某...     

一种求解非线性互补问题的filter内点算法

利用Armijio条件和信赖域方法,构造新的价值函数.首次将内点算法与filter技术结合起来,提出一种求解非线性互补问题的新算法,即filter内点算法.在主算法中使用Armijio型线搜索求取步长,在修复算法中使用信赖域方法进行适当控制以保证算法的收敛性.文章还讨论了算法的全局收敛性.最后用数值实验表明了该方法是有效的.     

Local convergence of filter methods for equality constrained non-linear programming

In Gonzaga et al. [A globally convergent filter method for nonlinear programming, SIAM J. Optimiz. 14 (2003), pp. 646–669] we discuss general conditions to ensure global convergence of inexact restoration filter algorithms for non-linear programming. In this article we show how to avoid the Maratos effect by means of a second-order correction. The algorithms are based on feasibility and optimality phases, which can be either independent or not. The optimality phase differs from the original one only when a full Newton step for the tangential minimization of the Lagrangian is efficient but not acceptable by the filter method. In this case a second-order corrector step tries to produce an acceptable point keeping the efficiency of the rejected step. The resulting point is tested by trust region criteria. Under the usual hypotheses, the algorithm inherits the quadratic convergence properties of the feasibility and optimality phases. This article includes a comparison between classical Sequential Quadratic Programming (SQP) and Inexact Restoration (IR) iterations, showing that both methods share the same asymptotic convergence properties.     

A filter method for nonlinear semidefinite programming with global convergence

In this study, a new filter algorithm is presented for solving the nonlinear semidefinite programming. This algorithm is inspired by the classical sequential quadratic programming method. Unlike the traditional filter methods, the sufficient descent is ensured by changing the step size instead of the trust region radius. Under some suitable conditions, the global convergence is obtained. In the end, some numerical experiments are given to show that the algorithm is effective.     

一个锥模型的自适应信赖域算法及其收敛性

本文研究了无约束最优化问题的基于锥模型的自适应信赖域算法.利用理论分析得到一个新的自适应信赖域半径.算法在每步迭代中以变化的速率、当前迭代点的信息以及水平向量信息调节信赖域半径的大小.从理论上证明了新算法的全局收敛性和Q-二阶收敛性.用数值试验验证了新算法的有效性.推广了已有的自适应信赖域算法的可行性和有效性.     

一个新的BFGS信赖域算法

本文对于无约束最优化问题提出了一个新的BFGS信赖域算法.利用BFGS方法和信赖域方法,提出了改进的BFGS信赖域方法.推广了文献[3,5]中的两种算法,得到一个新的BFGS信赖域算法,在适当条件下证明了算法的全局收敛性.     

CURVILINEAR PATHS AND TRUST REGION METHODS WITH NONMONOTONIC BACK TRACKING TECHNIQUE FOR UNCONSTRAINED OPTIMIZATION

1. Illtroductioncrust region method is a well-accepted technique in nonlinear optindzation to assure globalconvergence. One of the adVantages of the model is that it does not require the objectivefunction to be convex. Many differellt versions have been suggested in using trust regiontechnique. For each iteration, suppose a current iterate point, a local quadratic model of thefunction and a trust region with center at the point and a certain radius are given. A point thatminimizes the model f…     

求解变量带简单界约束的非线性规划问题的信赖域方法

1．引言。本文考虑下述变量带简单界约束的非线性规划问题：问题（1．1）不仅是实际应用中出现的简单的约束最优化问题，而且相当一部分最优化问题可以把变量限制在有意义的区间内181．因此，无论在理论方面还是在实际应用方面，都有必要研究此种问题．给出简便而且有效的算法．有些文章提出了一些特殊的方法．如011和［2］．14］及16］提出了一类信赖域方法，它们都借助于某种辅助点，证明了算法的全局收敛性．在收敛速度的分析方面，除要求在＊－T点满足严格互补松弛外，它们还要求另一个条件，即在每次迭代中，辅助点的有效约束必须在尝…     

凸约束优化问题的带记忆模型信赖域算法

本文我们考虑求解凸约束优化问题的信赖域方法 .与传统的方法不同 ,我们信赖域子问题的逼近模型中包括过去迭代点的信息 ,该模型使我们可以从更全局的角度来求得信赖域试探步 ,从而避免了传统信赖域方法中试探步的求取完全依赖于当前点的信息而过于局部化的困难 .全局收敛性的获得是依靠非单调技术来保证的     

An effective adaptive trust region algorithm for nonsmooth minimization

In this paper, an adaptive trust region algorithm that uses Moreau–Yosida regularization is proposed for solving nonsmooth unconstrained optimization problems. The proposed algorithm combines a modified secant equation with the BFGS update formula and an adaptive trust region radius, and the new trust region radius utilizes not only the function information but also the gradient information. The global convergence and the local superlinear convergence of the proposed algorithm are proven under suitable conditions. Finally, the preliminary results from comparing the proposed algorithm with some existing algorithms using numerical experiments reveal that the proposed algorithm is quite promising for solving nonsmooth unconstrained optimization problems.     

一个新锥模型信赖域算法

1引言本文考虑的无约束最优化问题为(?)f(x),(1.1)其中f(x)为连续可微函数.解此问题的很多算法一般都采用二次函数模型去逼近f(x) ([10],[15]).对于一些非二次性态强、曲率变化剧烈的函数,用二次函数模型去逼近可能效果不好,因此Davidon于1980年首次提出了解无约束优化问题的锥模型方法.锥模型是二次模型的推广,比二次函数具有更多的自由度,因此期望能够更充分地逼近原函数.对于一些在极小点附近很不对称,或曲率变化剧烈的函数,或在某个区域内变化大的函数,全部或部分用锥模型去逼近的效果可能好于用二次模型去逼近.     

仿射内点既约投影Hessian算法解非线性约束优化

本文结合非单调内点回代技术,提供了新的仿射信赖域方法解含有非负变量约束和非线性等式约束的优化问题.为求解大规模问题,采用等式约束的Jacobian矩阵的QR分解和两块校正的双边既约Hessian矩阵投影,将问题分解成零空间和值空间两个信赖域子问题.零空间的子问题为通常二次目标函数只带椭球约束的信赖域子问题,而值空间的子问题使用满足信赖域约束参数的值空间投影向量方向.通过引入Fletcher罚函数作为势函数,将由两个子问题结合信赖域策略构成的合成方向,并使用非单调线搜索技术回代于可接受的非负约束内点步长.在合理的条件下,算法具有整体收敛性且两块校正的双边既约Hessian投影法将保持超线性收敛速率.非单调技术将克服高度非线性情况,加快收敛进展.     

On filter-successive linearization methods for nonlinear semidefinite programming

In this paper we present a filter-successive linearization method with trust region for solutions of nonlinear semidefinite programming. Such a method is based on the concept of filter for nonlinear programming introduced by Fletcher and Leyffer in 2002. We describe the new algorithm and prove its global convergence under weaker assumptions. Some numerical results are reported and show that the new method is potentially effcient.     

A Nonmonotone Trust Region Method for Nonlinear Programming with Simple Bound Constraints

In this paper we propose a nonmonotone trust region algorithm for optimization with simple bound constraints. Under mild conditions, we prove the global convergence of the algorithm. For the monotone case it is also proved that the correct active set can be identified in a finite number of iterations if the strict complementarity slackness condition holds, and so the proposed algorithm reduces finally to an unconstrained minimization method in a finite number of iterations, allowing a fast asymptotic rate of convergence. Numerical experiments show that the method is efficient. Accepted 5 September 2000. Online publication 4 December 2000.