Approximate solution of the trust region problem by minimization over two-dimensional subspaces

The trust region problem, minimization of a quadratic function subject to a spherical trust region constraint, occurs in many optimization algorithms. In a previous paper, the authors introduced an inexpensive approximate solution technique for this problem that involves the solution of a two-dimensional trust region problem. They showed that using this approximation in an unconstrained optimization algorithm leads to the same theoretical global and local convergence properties as are obtained using the exact solution to the trust region problem. This paper reports computational results showing that the two-dimensional minimization approach gives nearly optimal reductions in then-dimension quadratic model over a wide range of test cases. We also show that there is very little difference, in efficiency and reliability, between using the approximate or exact trust region step in solving standard test problems for unconstrained optimization. These results may encourage the application of similar approximate trust region techniques in other contexts.Research supported by ARO contract DAAG 29-84-K-0140, NSF grant DCR-8403483, and NSF cooperative agreement DCR-8420944.     

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.     

Nonmonotone adaptive trust region method

In this paper, we propose a nonmonotone adaptive trust region method for unconstrained optimization problems. This method can produce an adaptive trust region radius automatically at each iteration and allow the functional value of iterates to increase within finite iterations and finally decrease after such finite iterations. This nonmonotone approach and adaptive trust region radius can reduce the number of solving trust region subproblems when reaching the same precision. The global convergence and convergence rate of this method are analyzed under some mild conditions. Numerical results show that the proposed method is effective in practical computation.     

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…     

On the Computation of Optimal Static Output Feedback Controllers for Discrete-Time Systems

In this article, we consider the static output feedback problem for discrete-time systems when complete set of state variables is not available. It has been reported that quasi-Newton methods have substandard performance on this problem. A structured quasi-Newton method with trust region globalization is analyzed and studied for solving this problem. Moreover, the classical Anderson-Moore method is enhanced by using the trust region mechanism to ensure global convergence instead of the line search technique. The algorithms are tested numerically on test problems of engineering applications.     

A new modified nonmonotone adaptive trust region method for unconstrained optimization

In this paper, we present an adaptive trust region method for solving unconstrained optimization problems which combines nonmonotone technique with a new update rule for the trust region radius. At each iteration, our method can adjust the trust region radius of related subproblem. We construct a new ratio to adjust the next trust region radius which is different from the ratio in the traditional trust region methods. The global and superlinear convergence results of the method are established under reasonable assumptions. Numerical results show that the new method is efficient for unconstrained optimization problems.     

A feasible direction method for image restoration

In this work, a feasible direction method is proposed for computing the regularized solution of image restoration problems by simply using an estimate of the noise present on the data. The problem is formulated as an optimization problem with one quadratic constraint. The proposed method computes a feasible search direction by inexactly solving a trust region subproblem with the truncated Conjugate Gradient method of Steihaug. The trust region radius is adjusted to maintain feasibility and a line-search globalization strategy is employed. The global convergence of the method is proved. The results of image denoising and deblurring are presented in order to illustrate the effectiveness and efficiency of the proposed method.     

A new trust region method with adaptive radius

In this paper we develop a new trust region method with adaptive radius for unconstrained optimization problems. The new method can adjust the trust region radius automatically at each iteration and possibly reduces the number of solving subproblems. We investigate the global convergence and convergence rate of this new method under some mild conditions. Theoretical analysis and numerical results show that the new adaptive trust region radius is available and reasonable and the resultant trust region method is efficient in solving practical optimization problems. The work was supported in part by NSF grant CNS-0521142, USA.     

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.     

非线性最小二乘问题的信赖域方法

本文提出一个新的非线性最小二乘的信赖域方法,在该方法中每个信赖域子问题只需要一次求解,而且每次迭代的一维搜索步长因子是给定的,避开一维搜索的环节,大大地提高了算法效率.文中证明了在一定的条件下算法的全局收敛性.     

A new adaptive trust region algorithm for optimization problems

It is well known that trust region methods are very effective for optimization problems. In this article, a new adaptive trust region method is presented for solving unconstrained optimization problems. The proposed method combines a modified secant equation with the BFGS updated formula and an adaptive trust region radius, where the new trust region radius makes use of not only the function information but also the gradient information. Under suitable conditions, global convergence is proved, and we demonstrate the local superlinear convergence of the proposed method. The numerical results indicate that the proposed method is very efficient.     

A nonmonotonic trust region algorithm for a class of semi-infinite minimax programming

Based on the discretization methods for solving semi-infinite programming problems, this paper presents a new nonmonotonic trust region algorithm for a class of semi-infinite minimax programming problem. Under some mild assumptions, the global convergence of the proposed algorithm is given. Numerical tests are reported that show the efficiency of the proposed method.     

A globally convergent trust region algorithm for optimization with general constraints and simple bounds

1.IntroductionInthispaper,weconsiderthefollowingnonlinearprogr~ngproblemwherec(x)=(c,(x),c2(2),',We(.))',i(x)andci(x)(i=1,2,',m)arerealfunctions*ThisworkissupPOrtedbytheNationalNaturalScienceFOundationofChinaandtheManagement,DecisionandinformationSystemLab,theChineseAcademyofSciences.definedinD={xEReIISx5u}.Weassumethath相似文献   

An algorithm for solving new trust region subproblem with conic model

The new trust region subproblem with the conic model was proposed in 2005, and was divided into three different cases. The first two cases can be converted into a quadratic model or a convex problem with quadratic constraints, while the third one is a nonconvex problem. In this paper, first we analyze the nonconvex problem, and reduce it to two convex problems. Then we discuss some dual properties of these problems and give an algorithm for solving them. At last, we present an algorithm for solving the new trust region subproblem with the conic model and report some numerical examples to illustrate the efficiency of the algorithm.     

An improved trust region method for unconstrained optimization

In this paper,we propose an improved trust region method for solving unconstrained optimization problems.Different with traditional trust region methods,our algorithm does not resolve the subproblem within the trust region centered at the current iteration point,but within an improved one centered at some point located in the direction of the negative gradient,while the current iteration point is on the boundary set.We prove the global convergence properties of the new improved trust region algorithm and give the computational results which demonstrate the effectiveness of our algorithm.     

解无约束优化问题的一个新的带线搜索的信赖域算法

在传统信赖域方法的基础上, 提出了求解无约束最优化问题的一个新的带线搜索的信赖域算法. 该算法采用大步长 Armijo 线搜索技术获得迭代步长, 克服了每次迭代求解信赖域子问题时计算量较大的缺点, 因而适用于求解大型的优化问题. 在适当的条件下, 我们证明了算法的全局收敛性. 数值实验结果表明本文所提出的算法是有效的.     

广义几何规划的压缩共轭梯度路径非单调信赖域算法(英文)

In this paper,on the basis of making full use of the characteristics of unconstrained generalized geometric programming（GGP）,we establish a nonmonotonic trust region algorithm via the conjugate path for solving unconstrained GGP problem.A new type of condensation problem is presented,then a particular conjugate path is constructed for the problem,along which we get the approximate solution of the problem by nonmonotonic trust region algorithm,and further prove that the algorithm has global convergence and quadratic convergence properties.     

A new simple model trust-region method with generalized Barzilai-Borwein parameter for large-scale optimization

In this paper a new trust region method with simple model for solving large-scale unconstrained nonlinear optimization is proposed. By employing the generalized weak quasi-Newton equations, we derive several schemes to construct variants of scalar matrices as the Hessian approximation used in the trust region subproblem. Under some reasonable conditions, global convergence of the proposed algorithm is established in the trust region framework. The numerical experiments on solving the test problems with dimensions from 50 to 20,000 in the CUTEr library are reported to show efficiency of the algorithm.     

A modified SLP algorithm and its global convergence

This paper concerns a filter technique and its application to the trust region method for nonlinear programming (NLP) problems. We used our filter trust region algorithm to solve NLP problems with equality and inequality constraints, instead of solving NLP problems with just inequality constraints, as was introduced by Fletcher et al. [R. Fletcher, S. Leyffer, Ph.L. Toint, On the global converge of an SLP-filter algorithm, Report NA/183, Department of Mathematics, Dundee University, Dundee, Scotland, 1999]. We incorporate this filter technique into the traditional trust region method such that the new algorithm possesses nonmonotonicity. Unlike the tradition trust region method, our algorithm performs a nonmonotone filter technique to find a new iteration point if a trial step is not accepted. Under mild conditions, we prove that the algorithm is globally convergent.     

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.