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 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.     

采用不定Dogleg路径的非单调自适应信赖域算法解无约束极小化(英文)

In this paper, we combine the nonmonotone and adaptive techniques with trust region method for unconstrained minimization problems. We set a new ratio of the actual descent and predicted descent. Then, instead of the monotone sequence, the nonmonotone sequence of function values are employed. With the adaptive technique, the radius of trust region △k can be adjusted automatically to improve the efficiency of trust region methods. By means of the Bunch-Parlett factorization, we construct a method with indefinite dogleg path for solving the trust region subproblem which can handle the indefinite approximate Hessian Bk. The convergence properties of the algorithm are established. Finally, detailed numerical results are reported to show that our algorithm is efficient.     

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 nonmonotone adaptive trust region method for unconstrained optimization based on conic model

In this paper, we present a nonmonotone adaptive trust region method for unconstrained optimization based on conic model. The new method combines nonmonotone technique and a new way to determine trust region radius at each iteration. The local and global convergence properties are proved under reasonable assumptions. Numerical experiments show that our algorithm is effective.     

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 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.     

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.     

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

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

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

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

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.     

A non-monotone trust region algorithm for unconstrained optimization with dynamic reference iteration updates using filter

We present a non-monotone trust region algorithm for unconstrained optimization. Using the filter technique of Fletcher and Leyffer, we introduce a new filter acceptance criterion and use it to define reference iterations dynamically. In contrast with the early filter criteria, the new criterion ensures that the size of the filter is finite. We also show a correlation between problem dimension and the filter size. We prove the global convergence of the proposed algorithm to first- and second-order critical points under suitable assumptions. It is significant that the global convergence analysis does not require the common assumption of monotonicity of the sequence of objective function values in reference iterations, as assumed by the standard non-monotone trust region algorithms. Numerical experiments on the CUTEr problems indicate that the new algorithm is competitive compared to some representative non-monotone trust region algorithms.     

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.     

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.     

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 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 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.     

A linear-time algorithm for the trust region subproblem based on hidden convexity

We present a linear-time approximation scheme for solving the trust region subproblem (TRS). It employs Nesterov’s accelerated gradient descent algorithm to solve a convex programming reformulation of (TRS). The total time complexity is less than that of the recent linear-time algorithm. The algorithm is further extended to the two-sided trust region subproblem.     

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

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

Exploring trust region method for the solution of logit-based stochastic user equilibrium problem

In this research paper, we explored using the trust region method to solve the logit-based SUE problem. We proposed a modified trust region Newton (MTRN) algorithm for this problem. When solving the trust region SUE subproblem, we showed that applying the well-known Steihaug-Toint method is inappropriate, since it may make the convergence rate of the major iteration very slow in the early stage of the computation. To overcome this drawback, a modified Steihaug-Toint method was proposed. We proved the convergence of our MTRN algorithm and showed its convergence rate is superlinear.