A New Nonmonotonic Trust Region Algorithm for A Class of Unconstraied Nonsmooth Optimization

This paper preasents a new trust region algorithm for solving a class of composite nonsmooth optimizations.It is distinguished by the fact that this method does not enforce strict monotonicity of the objective function values at successive itereates and that this method extends the existing results for this type of nonlinear optimization with smooth ,or piecewis somooth,or convex objective functions or their composition It is pyoved that this algorithm is globally convergent under certain conditions.Finally,some numerical results for several optimization problems are reported which show that the nonmonotonic trust region method is competitive with the usual trust region method.     

一类约束非光滑优化的非单调信赖域算法

提出了求解一类带一般凸约束的复合非光滑优化的信赖域算法 .和通常的信赖域方法不同的是 :该方法在每一步迭代时不是迫使目标函数严格单调递减 ,而是采用非单调策略 .由于光滑函数、逐段光滑函数、凸函数以及它们的复合都是局部Lipschitz函数 ,故本文所提方法是已有的处理同类型问题 ,包括带界约束的非线性最优化问题的方法的一般化 ,从而使得信赖域方法的适用范围扩大了 .同时 ,在一定条件下 ,该算法还是整体收敛的 .数值实验结果表明 :从计算的角度来看 ,非单调策略对高度非线性优化问题的求解非常有效     

一种解无约束优化问题的新的非单调自适应信赖域方法

本文提出了一种解无约束优化问题的新的非单调自适应信赖域方法.这种方法借助于目标函数的海赛矩阵的近似数量矩阵来确定信赖域半径.在通常的条件下,给出了新算法的全局收敛性以及局部超线性收敛的结果,数值试验验证了新的非单调方法的有效性.     

一类拟牛顿非单调信赖域算法及其收敛性

本文提出了一类求解无约束最优化问题的非单调信赖域算法.将非单调Wolfe线搜索技术与信赖域算法相结合,使得新算-法不仅不需重解子问题,而且在每步迭代都满足拟牛顿方程同时保证目标函数的近似Hasse阵Bk的正定性.在适当的条件下,证明了此算法的全局收敛性.数值结果表明该算法的有效性.     

A nonmonotone trust region method with new inexact line search for unconstrained optimization

In this paper, a new nonmonotone inexact line search rule is proposed and applied to the trust region method for unconstrained optimization problems. In our line search rule, the current nonmonotone term is a convex combination of the previous nonmonotone term and the current objective function value, instead of the current objective function value . We can obtain a larger stepsize in each line search procedure and possess nonmonotonicity when incorporating the nonmonotone term into the trust region method. Unlike the traditional trust region method, the algorithm avoids resolving the subproblem if a trial step is not accepted. Under suitable conditions, global convergence is established. Numerical results show that the new method is effective for solving unconstrained optimization problems.     

A trust region algorithm for minimization of locally Lipschitzian functions

The classical trust region algorithm for smooth nonlinear programs is extended to the nonsmooth case where the objective function is only locally Lipschitzian. At each iteration, an objective function that carries both first and second order information is minimized over a trust region. The term that carries the first order information is an iteration function that may not explicitly depend on subgradients or directional derivatives. We prove that the algorithm is globally convergent. This convergence result extends the result of Powell for minimization of smooth functions, the result of Yuan for minimization of composite convex functions, and the result of Dennis, Li and Tapia for minimization of regular functions. In addition, compared with the recent model of Pang, Han and Rangaraj for minimization of locally Lipschitzian functions using a line search, this algorithm has the same convergence property without assuming positive definiteness and uniform boundedness of the second order term. Applications of the algorithm to various nonsmooth optimization problems are discussed.This author's work was supported in part by the Australian Research Council.This author's work was carried out while he was visiting the Department of Applied Mathematics at the University of New South Wales.     

求解非光滑凸规划的一种混合束方法

提出一种求解非光滑凸规划问题的混合束方法. 该方法通过对目标函数增加迫近项, 且对可行域增加信赖域约束进行迭代, 做为迫近束方法与信赖域束方法的有机结合, 混合束方法自动在二者之间切换, 收敛性分析表明该方法具有全局收敛性. 最后的数值算例验证了算法的有效性．     

A Line Search and Trust Region Algorithm with Trust Region Radius Converging to Zero

In this paper, we present a new line search and trust region algorithm for unconstrained optimization problem with the trust region radius converging to zero. The new trust region algorithm performs a backtracking line search from the failed, point instead of resolving the subproblem when the trial step results in an increase in the objective function. We show that the algorithm preserves the convergence properties of the traditional trust region algorithms. Numerical results are also given.     

A trust region method for solving linearly constrained locally Lipschitz optimization problems

In this paper, we present a nonsmooth trust region method for solving linearly constrained optimization problems with a locally Lipschitz objective function. Using the approximation of the steepest descent direction, a quadratic approximation of the objective function is constructed. The null space technique is applied to handle the constraints of the quadratic subproblem. Next, the CG-Steihaug method is applied to solve the new approximation quadratic model with only the trust region constraint. Finally, the convergence of presented algorithm is proved. This algorithm is implemented in the MATLAB environment and the numerical results are reported.     

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.     

A trust region method for minimization of nonsmooth functions with linear constraints

We introduce a trust region algorithm for minimization of nonsmooth functions with linear constraints. At each iteration, the objective function is approximated by a model function that satisfies a set of assumptions stated recently by Qi and Sun in the context of unconstrained nonsmooth optimization. The trust region iteration begins with the resolution of an “easy problem”, as in recent works of Martínez and Santos and Friedlander, Martínez and Santos, for smooth constrained optimization. In practical implementations we use the infinity norm for defining the trust region, which fits well with the domain of the problem. We prove global convergence and report numerical experiments related to a parameter estimation problem. Supported by FAPESP (Grant 90/3724-6), FINEP and FAEP-UNICAMP. Supported by FAPESP (Grant 90/3724-6 and grant 93/1515-9).     

A model-hybrid approach for unconstrained optimization problems

In this paper, we propose a model-hybrid approach for nonlinear optimization that employs both trust region method and quasi-Newton method, which can avoid possibly resolve the trust region subproblem if the trial step is not acceptable. In particular, unlike the traditional trust region methods, the new approach does not use a single approximate model from beginning to the end, but instead employs quadratic model or conic model at every iteration adaptively. We show that the new algorithm preserves the strong convergence properties of trust region methods. Numerical results are also presented.     

一类新的非单调信赖域算法

提出了一类带线性搜索的非单调信赖域算法.算法将非单调Armijo线性搜索技术与信赖域方法相结合,使算法不需重解子问题.而且由于采用了MBFGS校正公式,使矩阵Bk能较好地逼近目标函数的Hesse矩阵并保持正定传递.在较弱的条件下,证明了算法的全局收敛性.数值结果表明算法是有效的.     

Constrained optimization involving expensive function evaluations: A sequential approach

This paper presents a new sequential method for constrained nonlinear optimization problems. The principal characteristics of these problems are very time consuming function evaluations and the absence of derivative information. Such problems are common in design optimization, where time consuming function evaluations are carried out by simulation tools (e.g., FEM, CFD). Classical optimization methods, based on derivatives, are not applicable because often derivative information is not available and is too expensive to approximate through finite differencing.The algorithm first creates an experimental design. In the design points the underlying functions are evaluated. Local linear approximations of the real model are obtained with help of weighted regression techniques. The approximating model is then optimized within a trust region to find the best feasible objective improving point. This trust region moves along the most promising direction, which is determined on the basis of the evaluated objective values and constraint violations combined in a filter criterion. If the geometry of the points that determine the local approximations becomes bad, i.e. the points are located in such a way that they result in a bad approximation of the actual model, then we evaluate a geometry improving instead of an objective improving point. In each iteration a new local linear approximation is built, and either a new point is evaluated (objective or geometry improving) or the trust region is decreased. Convergence of the algorithm is guided by the size of this trust region. The focus of the approach is on getting good solutions with a limited number of function evaluations.     

An ODE-Based Trust Region Filter Algorithm for Unconstrained Optimization

In this article, an ODE-based trust region filter algorithm for unconstrained optimization is proposed. It can be regarded as a combination of trust region and filter techniques with ODE-based methods. Unlike the existing trust-region-filter methods and ODE-based methods, a distinct feature of this method is that at each iteration, a reduced linear system is solved to obtain a trial step, thus avoiding solving a trust region subproblem. Under some standard assumptions, it is proven that the algorithm is globally convergent. Preliminary numerical results show that the new algorithm is efficient for large scale problems.     

A hybrid trust region algorithm for unconstrained optimization

This paper presents a hybrid trust region algorithm for unconstrained optimization problems. It can be regarded as a combination of ODE-based methods, line search and trust region techniques. A feature of the proposed method is that at each iteration, a system of linear equations is solved only once to obtain a trial step. Further, when the trial step is not accepted, the method performs an inexact line search along it instead of resolving a new linear system. Under reasonable assumptions, the algorithm is proven to be globally and superlinearly convergent. Numerical results are also reported that show the efficiency of this proposed method.     

带有固定步长的非单调自适应信赖域算法

提出了求解无约束优化问题带有固定步长的非单调自适应信赖域算法.信赖域半径的修正采用自适应技术,算法在试探步不被接受时,采用固定步长寻找下一迭代点.并在适当的条件下,证明算法具有全局收敛性和超线性收敛性.初步的数值试验表明算法对高维问题具有较好的效果.     

一种改进的无约束非光滑优化问题的信赖域算法

本文提出了一种新的求解无约束非光滑优化问题的信赖域算法,并证明了该算法的迭代点列的任何聚点都是的问题的稳定点。     

A parallel descent algorithm for convex programming

In this paper, we propose a parallel decomposition algorithm for solving a class of convex optimization problems, which is broad enough to contain ordinary convex programming problems with a strongly convex objective function. The algorithm is a variant of the trust region method applied to the Fenchel dual of the given problem. We prove global convergence of the algorithm and report some computational experience with the proposed algorithm on the Connection Machine Model CM-5.     

Global Convergence of a Nonmonotone Trust Region Algorithm with Memory for Unconstrained Optimization

In this paper, we consider a trust region algorithm for unconstrained optimization problems. Unlike the traditional memoryless trust region methods, our trust region model includes memory of the past iteration, which makes the algorithm less myopic in the sense that its behavior is not completely dominated by the local nature of the objective function, but rather by a more global view. The global convergence is established by using a nonmonotone technique. The numerical tests are also given to show the efficiency of our proposed method.