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…     

非单调技术预条件弧线路径信赖域解无约束优化

本文提供修正近似信赖域类型路经三类预条件弧线路径方法解无约束最优化问题.使用对称矩阵的稳定Bunch-Parlett易于形成信赖域子问题的弧线路径,使用单位下三角矩阵作为最优路径和修正梯度路径的预条件因子.运用预条件因子改进Hessian矩阵特征值分布加速预条件共轭梯度路径收敛速度.基于沿着三类路径信赖域子问题产生试探步,将信赖域策略与非单调线搜索技术相结合作为新的回代步.理论分析证明在合理条件下所提供的算法是整体收敛性,并且具有局部超线性收敛速率,数值结果表明算法的有效性.     

线性不等式约束优化的弧线路径信赖域算法

提供了弧线路径结合仿射内点信赖域策略的非单调回代算法解线性不等式约束的优化问题.基于仿射投影的信赖域子问题获得新的搜索方向,采用弧线路径的近似信赖域和线搜索结合技术得到回代步,获得新的步长.通过证明所提供的弧线路径具有一系列良好性质,从而在合理的条件下,证明所提供的算法不仅具有整体收敛性,而且保持算法的局部超线性收敛速率.数值测试表明了算法的有效性与可靠性.     

INTERIOR POINT PROJECTED REDUCED HESSIAN METHOD WITH TRUST REGION STRATEGY FOR NONLINEAR CONSTRAINED OPTIMIZATION

§1　IntroductionIn this paper we analyze an interior point scaling projected reduced Hessian methodwith trust region strategy for solving the nonlinear equality constrained optimizationproblem with nonnegative constraints on variables:min　f(x)s.t.　c(x) =0 (1.1)x≥0where f∶Rn→R is the smooth nonlinear function,notnecessarily convex and c(x)∶Rn→Rm(m≤n) is the vector nonlinear function.There are quite a few articles proposing localsequential quadratic programming reduced Hessian methods…     

An adaptive trust region method and its convergence

In this paper, a new trust region subproblem is proposed. The trust radius in the new subproblem adjusts itself adaptively. As a result, an adaptive trust region method is constructed based on the new trust region subproblem. The local and global convergence results of the adaptive trust region method are proved. Numerical results indicate that the new method is very efficient.     

An interior affine scaling projective algorithm for nonlinear equality and linear inequality constrained optimization

In this paper, we propose a new nonmonotonic interior point backtracking strategy to modify the reduced projective affine scaling trust region algorithm for solving optimization subject to nonlinear equality and linear inequality constraints. The general full trust region subproblem for solving the nonlinear equality and linear inequality constrained optimization is decomposed to a pair of trust region subproblems in horizontal and vertical subspaces of linearize equality constraints and extended affine scaling equality constraints. The horizontal subproblem in the proposed algorithm is defined by minimizing a quadratic projective reduced Hessian function subject only to an ellipsoidal trust region constraint in a null subspace of the tangential space, while the vertical subproblem is also defined by the least squares subproblem subject only to an ellipsoidal trust region constraint. By introducing the Fletcher's penalty function as the merit function, trust region strategy with interior point backtracking technique will switch to strictly feasible interior point step generated by a component direction of the two trust region subproblems. The global convergence of the proposed algorithm while maintaining fast local convergence rate of the proposed algorithm are established under some reasonable conditions. A nonmonotonic criterion should bring about speeding up the convergence progress in some high nonlinear function conditioned cases.     

信赖域策略的内点投影既约Hessian方法解非线性约束优化

A interior point scaling projected reduced Hessian method with combination of nonmonotonic backtracking technique and trust region strategy for nonlinear equality constrained optimization with nonegative constraint on variables is proposed. In order to deal with large problems,a pair of trust region subproblems in horizontal and vertical subspaces is used to replace the general full trust region subproblem. The horizontal trust region subproblem in the algorithm is only a general trust region subproblem while the vertical trust region subproblem is defined by a parameter size of the vertical direction subject only to an ellipsoidal constraint. Both trust region strategy and line search technique at each iteration switch to obtaining a backtracking step generated by the two trust region subproblems. By adopting the l1 penalty function as the merit function, the global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions. A nonmonotonic criterion and the second order correction step are used to overcome Maratos effect and speed up the convergence progress in some ill-conditioned cases.     

A trust region and affine scaling interior point method for nonconvex minimization with linear inequality constraints

A trust region and affine scaling interior point method (TRAM) is proposed for a general nonlinear minimization with linear inequality constraints [8]. In the proposed approach, a Newton step is derived from the complementarity conditions. Based on this Newton step, a trust region subproblem is formed, and the original objective function is monotonically decreased. Explicit sufficient decrease conditions are proposed for satisfying the first order and second order necessary conditions.?The objective of this paper is to establish global and local convergence properties of the proposed trust region and affine scaling interior point method. It is shown that the proposed explicit decrease conditions are sufficient for satisfy complementarity, dual feasibility and second order necessary conditions respectively. It is also established that a trust region solution is asymptotically in the interior of the proposed trust region subproblem and a properly damped trust region step can achieve quadratic convergence. Received: January 29, 1999 / Accepted: November 22, 1999?Published online February 23, 2000     

The convergence of subspace trust region methods

The trust region method is an effective approach for solving optimization problems due to its robustness and strong convergence. However, the subproblem in the trust region method is difficult or time-consuming to solve in practical computation, especially in large-scale problems. In this paper we consider a new class of trust region methods, specifically subspace trust region methods. The subproblem in these methods has an adequate initial trust region radius and can be solved in a simple subspace. It is easier to solve than the original subproblem because the dimension of the subproblem in the subspace is reduced substantially. We investigate the global convergence and convergence rate of these methods.     

Combining trust region and linesearch algorithm for equality constrained optimization

In this paper, a combining trust region and line search algorithm for equality constrained optimization is proposed. At each iteration, we only need to solve the trust region subproblem once, when the trust region trial step can not be accepted, we switch to line search to obtain the next iteration. Hence, the difficulty of repeated solving trust region subproblem in an iterate is avoided. In order to allow the direction of negative curvature, we add second correction step in trust region step and employ nommonotone technique in line search. The global convergence and local superlinearly rate are established under certain assumptions. Some numerical examples are given to illustrate the efficiency of the proposed algorithm.     

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.     

AN INTERIOR TRUST REGION ALGORITHM FOR NONLINEAR MINIMIZATION WITH LINEAR CONSTRAINTS

AbstractAn interior trust-region-based algorithm for linearly constrained minimization problems is proposed and analyzed. This algorithm is similar to trust region algorithms for unconstrained minimization: a trust region subproblem on a subspace is solved in each iteration. We establish that the proposed algorithm has convergence properties analogous to those of the trust region algorithms for unconstrained minimization. Namely, every limit point of the generated sequence satisfies the Krush-Kuhn-Tucker (KKT) conditions and at least one limit point satisfies second order necessary optimality conditions. In addition, if one limit point is a strong local minimizer and the Hessian is Lipschitz continuous in a neighborhood of that point, then the generated sequence converges globally to that point in the rate of at least 2-step quadratic. We are mainly concerned with the theoretical properties of the algorithm in this paper. Implementation issues and adaptation to large-scale problems will be addressed in a     

A ROBUST TRUST REGION ALGORITHM FOR SOLVING GENERAL NONLINEAR PROGRAMMING

1. Introductioncrust region methods are iterative. As a strategy of globalization, the trust region approach was introduced into solving unconstrained optimization and proved to be efficient androbust. An excellent survey was given by Mor6(1983). The associated research with trustregion methods for unconstrained optimization can be found in Fletcher(1980), Powell(1975),Sorensen(1981), Shultz, Schnabel and Byrd(1985), Yuan(1985). The solution of the trust region subproblem is still an activ…     

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

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

A NEW TRUST-REGION ALGORITHM FOR FINITE MINIMAX PROBLEM

In this paper, a new trust region algorithm for minimax optimization problems is proposed, which solves only one quadratic subproblem based on a new approximation model at each iteration. The approach is different from the traditional algorithms that usually require to solve two quadratic subproblems. Moreover, to avoid Maratos effect, the nonmonotone strategy is employed. The analysis shows that, under standard conditions, the algorithm has global and superlinear convergence. Preliminary numerical experiments are conducted to show the efficiency of the new method.     

A Dual Algorithm for Minimizing a Quadratic Function with Two Quadratic Constraints

In this paper, we present a dual algorithm for minimizing a convex quadratic function with two quadratic constraints. Such a minimization problem is a subproblem that appears in some trust region algorithms for general nonlinear programming. Some theoretical properties of the dual problem are given. Global convergence of the algorithm is proved and a local superlinear convergence result is presented. Numerical examples are also provided.     

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

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

无约束非光滑优化问题信赖域算法的收敛条件

1 引言 考虑下列无约束非光滑优化问题 minf(x),(1) x∈R~n,其中f为R~n上的局部Lipschitz函数,本文将‖·‖_2简记为‖·‖.记下列信赖域子问题为S∪B(x,△). min m(x,s)=φ(x,s)+1/2s~TBs, 其中φ:R~(2m)→R为f的迭代函数。 对于无约束非光滑优化问题(1),[11],[13],[3]、[4]和[5]分别在特殊的条件下给出了信赖域算法用以求解(1)的收敛性结果。最近,[10]、[2]和[6]在不同的假设条件下分别给出了信赖域算法求解无约束非光滑优化问题的一般模型,并在子问题的目标函数满足局部一致有界性条件时证明了算法模型的整体收敛性。在目标函数满足某种正则性条件时,[11]和[9]给出了当信赖域子问题的目标函数中二次项不满足一致有界性条件时的收敛性结果.本文则在目标函数仅为局部Lipschitz函数时得到了和[8]、[11]、[9]相同的收敛性结果。     

A new nonmonotone adaptive trust region method based on simple quadratic models

Based on simple quadratic models of the trust region subproblem, we combine the trust region method with the nonmonotone and adaptive techniques to propose a new nonmonotone adaptive trust region algorithm for unconstrained optimization. Unlike traditional trust region method, our trust region subproblem is very simple by using a new scale approximation of the minimizing function??s Hessian. The new method needs less memory capacitance and computational complexity. 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 unconstrained problems.     

A trust region algorithm with adaptive cubic regularization methods for nonsmooth convex minimization

By using the Moreau-Yosida regularization and proximal method, a new trust region algorithm is proposed for nonsmooth convex minimization. A cubic subproblem with adaptive parameter is solved at each iteration. The global convergence and Q-superlinear convergence are established under some suitable conditions. The overall iteration bound of the proposed algorithm is discussed. Preliminary numerical experience is reported.