A line search trust-region algorithm with nonmonotone adaptive radius for a system of nonlinear equations

In this paper, a trust-region procedure is proposed for the solution of nonlinear equations. The proposed approach takes advantages of an effective adaptive trust-region radius and a nonmonotone strategy by combining both of them appropriately. It is believed that selecting an appropriate adaptive radius based on a suitable nonmonotone strategy can improve the efficiency and robustness of the trust-region frameworks as well as decrease the computational cost of the algorithm by decreasing the required number subproblems that must be solved. The global convergence and the local Q-quadratic convergence rate of the proposed approach are proved. Preliminary numerical results of the proposed algorithm are also reported which indicate the promising behavior of the new procedure for solving the nonlinear system.     

一种非单调滤子信赖域算法解线性不等式约束优化

本文给出了一种新的多维滤子算法结合非单调信赖域策略解线性约束优化.目标函数及其投影梯度的分量组成了新的多维滤子，并且与信赖域半径有关.当信赖域半径充分小时，新的滤子能接受试探点，避免算法无限循环.非单调信赖域策略保证了新算法的整体收敛性.目前为止，多维滤子算法局部收敛性分析仍然没有解决，在合理假设下，我们分析了新算法的局部超线性收敛性.数值结果验证了算法的有效性.     

An efficient nonmonotone trust-region method for unconstrained optimization

The monotone trust-region methods are well-known techniques for solving unconstrained optimization problems. While it is known that the nonmonotone strategies not only can improve the likelihood of finding the global optimum but also can improve the numerical performance of approaches, the traditional nonmonotone strategy contains some disadvantages. In order to overcome to these drawbacks, we introduce a variant nonmonotone strategy and incorporate it into trust-region framework to construct more reliable approach. The new nonmonotone strategy is a convex combination of the maximum of function value of some prior successful iterates and the current function value. It is proved that the proposed algorithm possesses global convergence to first-order and second-order stationary points under some classical assumptions. Preliminary numerical experiments indicate that the new approach is considerably promising for solving unconstrained optimization problems.     

A trust-region approach with novel filter adaptive radius for system of nonlinear equations

This work introduces a version of filter technique to produce an adaptive radius and then adds it into trust-region algorithm. This method uses advantages of the functions norm’s necessary information in order to produce a smaller radius of trust-region close to the optimizer and also a larger radius of trust-region far away from the optimizer using advantages of the filter technique (Fatemi and Mahdavi-Amiri, Comput. Optim. Appl. 52(1), 239–266 2012). Under some ordinary conditions, the global convergence of the proposed approach is proved. Numerical results are also presented.     

A new adaptive trust-region method for system of nonlinear equations

This study presents a new trust-region procedure to solve a system of nonlinear equations in several variables. The proposed approach combines an effective adaptive trust-region radius with a nonmonotone strategy, because it is believed that this combination can improve the efficiency and robustness of the trust-region framework. Indeed, it decreases the computational cost of the algorithm by decreasing the required number of subproblems to be solved. The global and the quadratic convergence of the proposed approach is proved without any nondegeneracy assumption of the exact Jacobian. Preliminary numerical results indicate the promising behavior of the new procedure to solve systems of nonlinear equations.     

A nonmonotone trust-region line search method for large-scale unconstrained optimization

We consider an efficient trust-region framework which employs a new nonmonotone line search technique for unconstrained optimization problems. Unlike the traditional nonmonotone trust-region method, our proposed algorithm avoids resolving the subproblem whenever a trial step is rejected. Instead, it performs a nonmonotone Armijo-type line search in direction of the rejected trial step to construct a new point. Theoretical analysis indicates that the new approach preserves the global convergence to the first-order critical points under classical assumptions. Moreover, superlinear and quadratic convergence are established under suitable conditions. Numerical experiments show the efficiency and effectiveness of the proposed approach for solving unconstrained optimization problems.     

Non-monotone trust region methods for nonlinear equality constrained optimization without a penalty function

 We propose and analyze a class of penalty-function-free nonmonotone trust-region methods for nonlinear equality constrained optimization problems. The algorithmic framework yields global convergence without using a merit function and allows nonmonotonicity independently for both, the constraint violation and the value of the Lagrangian function. Similar to the Byrd–Omojokun class of algorithms, each step is composed of a quasi-normal and a tangential step. Both steps are required to satisfy a decrease condition for their respective trust-region subproblems. The proposed mechanism for accepting steps combines nonmonotone decrease conditions on the constraint violation and/or the Lagrangian function, which leads to a flexibility and acceptance behavior comparable to filter-based methods. We establish the global convergence of the method. Furthermore, transition to quadratic local convergence is proved. Numerical tests are presented that confirm the robustness and efficiency of the approach. Received: December 14, 2000 / Accepted: August 30, 2001 Published online: September 27, 2002 Key words. nonmonotone trust-region methods – sequential quadratic programming – penalty function – global convergence – equality constraints – local convergence – large-scale optimization Mathematics Subject Classification (2000): 65K05, 90C30     

求解极小极大问题的非单调过滤算法

提出一种改进的求解极小极大问题的信赖域滤子方法,利用SQP子问题来求一个试探步,尾服用滤子来衡量是否接受试探步,避免了罚函数的使用;并且借用已有文献的思想, 使用了Lagrange函数作为效益函数和非单调技术,在适当的条件下,分析了算法的全局和局部收敛性,并进行了数值实验.     

Nonmonotone Self-adaptive Levenberg–Marquardt Approach for Solving Systems of Nonlinear Equations

The well-known Levenberg–Marquardt method is used extensively to solve systems of nonlinear equations. An extension of the Levenberg–Marquardt method based on new nonmonotone technique is described. To decrease the total number of iterations, this method allows the sequence of objective function values to be nonmonotone, especially in the case where the objective function is ill-conditioned. Moreover, the parameter of Levenberg–Marquardt is produced according to the new nonmonotone strategy to use the advantages of the faster convergence of the Gauss–Newton method whenever iterates are near the optimizer, and the robustness of the steepest descent method in the case in which iterates are far away from the optimizer. The global and quadratic convergence of the proposed method is established. The results of numerical experiments are reported.     

A nonmonotone trust-region method of conic model for unconstrained optimization

In this paper, we present a nonmonotone trust-region method of conic model for unconstrained optimization. The new method combines a new trust-region subproblem of conic model proposed in [Y. Ji, S.J. Qu, Y.J. Wang, H.M. Li, A conic trust-region method for optimization with nonlinear equality and inequality 4 constrains via active-set strategy, Appl. Math. Comput. 183 (2006) 217–231] with a nonmonotone technique for solving unconstrained optimization. The local and global convergence properties are proved under reasonable assumptions. Numerical experiments are conducted to compare this method with the method of [Y. Ji, S.J. Qu, Y.J. Wang, H.M. Li, A conic trust-region method for optimization with nonlinear equality and inequality 4 constrains via active-set strategy, Appl. Math. Comput. 183 (2006) 217–231].     

A BFGS trust-region method with a new nonmonotone technique for nonlinear equations

In this paper, we consider a trust-region method for solving nonlinear equations which employs a new nonmonotone technique. A strong nonmonotone strategy and a weaker nonmonotone strategy can be obtained by choosing the parameter adaptively. Thus, the disadvantages of the traditional nonmonotone strategy can be avoided. It does not need to compute the Jacobian matrix at every iteration, so that the workload and time are decreased. Theoretical analysis indicates that the new algorithm preserves the global convergence under classical assumptions. Moreover, superlinear and quadratic convergence are established under suitable conditions. Numerical experiments show the efficiency and effectiveness of the proposed method for solving nonlinear equations.     

A new nonmonotone trust-region method of conic model for solving unconstrained optimization

In this paper, we present a new nonmonotone trust-region method of conic model for solving unconstrained optimization problems. Both the local and global convergence properties are analyzed under reasonable assumptions. Numerical experiments are conducted to compare this method with some existed ones which indicate that the new method is efficient.     

一个解非线性方程组新的非单调自适应信赖域法

本文利用函数平均权重的非单调技术以及自适应信赖域方法,提出一个解非线性方程组的非单调自适应信赖域法.并在适当假设条件下,讨论了算法的全局收敛性.数值试验表明了算法是有效的.     

Nonmonotone Trust-Region Method for Nonlinear Programming with General Constraints and Simple Bounds

In this paper, we propose a nonmonotone trust-region algorithm for the solution of optimization problems with general nonlinear equality constraints and simple bounds. Under a constant rank assumption on the gradients of the active constraints, we analyze the global convergence of the proposed algorithm.     

一类新拟牛顿非单调信赖域算法

提出了一类新的求解无约束最优化问题的新拟牛顿非单调信赖域算法.采用加权的r_k用以调整信赖域半径,在适当的条件下,证明了算法的全局收敛性.数值结果表明算法的有效性.     

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.     

Global Convergence of Algorithms with Nonmonotone Line Search Strategy in Unconstrained Optimization

In this paper we state some nonmonotone line search strategies for unconstrained optimization algorithms. Abstracting from the concrete line search strategy we prove two general convergence results. Using this theory we can show the global convergence of the BFGS method with nonmonotone line search strategy. In contrast to some former results about nonmonotone line search strategies, both our convergence results and their proofs are natural generalizations of known results for the monotone case.     

New zero-finders for trust-region computations

Trust-region methods are among the most popular schemes for determining a local minimum of a nonlinear function in several variables. These methods approximate the nonlinear function by a quadratic polynomial, and a trust-region radius determines the size of the sphere in which the quadratic approximation of the nonlinear function is deemed to be accurate. The trust-region radius has to be computed repeatedly during the minimization process. Each trust-region radius is computed by determining a zero of a nonlinear function ψ(x). This is often done with Newton’s method or a variation thereof. These methods give quadratic convergence of the computed approximations of the trust-region radius. This paper describes a cubically convergent zero-finder that is based on the observation that the second derivative \(\psi ^{\prime \prime }(x)\) can be evaluated inexpensively when the first derivative \(\psi ^{\prime }(x)\) is known. Computed examples illustrate the performance of the zero-finder proposed.     

A Globally Convergent Trust-Region Method for Large-Scale Symmetric Nonlinear Systems

This study presents a novel adaptive trust-region method for solving symmetric nonlinear systems of equations. The new method uses a derivative-free quasi-Newton formula in place of the exact Jacobian. The global convergence and local quadratic convergence of the new method are established without the nondegeneracy assumption of the exact Jacobian. Using the compact limited memory BFGS, we adapt a version of the new method for solving large-scale problems and develop the dogleg scheme for solving the associated trust-region subproblems. The sufficient decrease condition for the adapted dogleg scheme is established. While the efficiency of the present trust-region approach can be improved by using adaptive radius techniques, utilizing the compact limited memory BFGS adjusts this approach to handle large-scale symmetric nonlinear systems of equations. Preliminary numerical results for both medium- and large-scale problems are reported.     

Multiplier convergence in trust-region methods with application to convergence of decomposition methods for MPECs

We study piecewise decomposition methods for mathematical programs with equilibrium constraints (MPECs) for which all constraint functions are linear. At each iteration of a decomposition method, one step of a nonlinear programming scheme is applied to one piece of the MPEC to obtain the next iterate. Our goal is to understand global convergence to B-stationary points of these methods when the embedded nonlinear programming solver is a trust-region scheme, and the selection of pieces is determined using multipliers generated by solving the trust-region subproblem. To this end we study global convergence of a linear trust-region scheme for linearly-constrained NLPs that we call a trust-search method. The trust-search has two features that are critical to global convergence of decomposition methods for MPECs: a robustness property with respect to switching pieces, and a multiplier convergence result that appears to be quite new for trust-region methods. These combine to clarify and strengthen global convergence of decomposition methods without resorting either to additional conditions such as eventual inactivity of the trust-region constraint, or more complex methods that require a separate subproblem for multiplier estimation.