等式约束优化的组合信赖域与拟牛顿算法

本文对等式约束问题提出了一个种组合信赖域与拟牛顿算法。该算法的特点是若Lagrangian函数的近似Ｈessian阵在等式约束Jacobi阵的零空间正定的,则选择拟牛顿算法,否则用信赖域算法,在通常信赖域算法的收敛假设下,该文证明了组合算法的全局收敛性。     

等式约束最小化的信赖域乘子算法

本文通过使用信赖域乘子策略和引入不可微的势函数,讨论了(1)中被合理修正的双边投影拟牛顿方法。分析和叙述了算式约束最小化的信赖域乘子算法,并且证明了算法整体收敛性以及局部超越性收敛速率.     

一类等式约束非线性优化问题的信赖域新算法

提出一类信赖域新算法用于求解等式约束的非线性优化问题,在构造增广拉格朗日函数的基础上,提出了信赖域子问题的求解公式,研究了拉格朗日乘子和罚因子的修正公式,并使用滤子技巧,放松了接受尝试步的条件,证明了算法的收敛性.最后进行了数值试验.     

线性不等式约束的广义非线性互补问题的仿射内点信赖域方法

提供了一种新的非单调内点回代线搜索技术的仿射内点信赖域方法解线性不等式约束的广义非线性互补问题(GCP).基于广义互补问题构成的半光滑方程组的广义Jacobian矩阵,算法使用l_2范数作为半光滑方程组的势函数,形成的信赖域子问题为一个带椭球约束的线性化的二次模型.利用广义牛顿方程计算试探迭代步,通过内点映射回代技术确保迭代点是严格内点,保证了算法的整体收敛性.在合理的条件下,证明了信赖域算法在接近最优点时可转化为广义拟牛顿步,进而具有局部超线性收敛速率.非单调技术将克服高度非线性情况加速收敛进展.最后,数值结果表明了算法的有效性.     

线性不等式约束的广义非线性互补问题的仿射内点信赖域方法

提供了一种新的非单调内点回代线搜索技术的仿射内点信赖域方法解线性不等式约束的广义非线性互补问题(GCP).基于广义互补问题构成的半光滑方程组的广义Jacobian矩阵,算法使用l2范数作为半光滑方程组的势函数,形成的信赖域子问题为一个带椭球约束的线性化的二次模型.利用广义牛顿方程计算试探迭代步,通过内点映射回代技术确保迭代点是严格内点,保证了算法的整体收敛性.在合理的条件下,证明了信赖域算法在接近最优点时可转化为广义拟牛顿步,进而具有局部超线性收敛速率.非单调技术将克服高度非线性情况加速收敛进展.最后,数值结果表明了算法的有效性.     

等式约束最小化的信整域乘子算法

本文通过使用信赖域乘子策略和引入不可微的势函数，讨论了[1]中被合理修正的双边投影拟牛顿方法，分析和叙述了算式约束最小化的信赖域乘子算法，并且证明了算法整体收敛性以及局部超越性收敛速率。     

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

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

一个新的MBFGS信赖域算法

本文研究了无约束最优化问题.利用MBFGS信赖域算法的基本思想,通过对BFGS校正公式的改进,并结合线搜索技术,提出了一种新的MBFGS信赖域算法,拓宽了信赖域算法的适用范围,并在一定条件下证明了该算法的全局收敛性和超线性收敛性.     

基于增广Lagrange函数的约束优化问题的一个信赖域方法

本文提出一个求解不等式约束优化问题的基于指数型增广Lagrange函数的信赖域方法.基于指数型增广Lagrange函数,将传统的增广Lagrange方法的精确求解子问题转化为一个信赖域子问题,从而减少了计算量,并建立相应的信赖域算法.在一定的假设条件下,证明了算法的全局收敛性,并给出相应经典算例的数值实验结果.     

局部误差的有界约束非线性方程组的非单调信赖域算法

本文提供了在没有非奇异假设的条件下,求解有界约束半光滑方程组的投影信赖域算法.基于一个正则化子问题,求得类牛顿步,进而求得投影牛顿步.在合理的假设条件下,证明了算法不仅具有整体收敛性而且保持超线性收敛速率.     

A modified nearly exact method for solving low-rank trust region subproblem

In this paper, we first discuss how the nearly exact (NE) method proposed by Moré and Sorensen [14] for solving trust region (TR) subproblems can be modified to solve large-scale “low-rank” TR subproblems efficiently. Our modified algorithm completely avoids computation of Cholesky factorizations by instead relying primarily on the Sherman–Morrison–Woodbury formula for computing inverses of “diagonal plus low-rank” type matrices. We also implement a specific version of the modified log-barrier (MLB) algorithm proposed by Polyak [17] where the generated log-barrier subproblems are solved by a trust region method. The corresponding direction finding TR subproblems are of the low-rank type and are then solved by our modified NE method. We finally discuss the computational results of our implementation of the MLB method and its comparison with a version of LANCELOT [5] based on a collection extracted from CUTEr [12] of nonlinear programming problems with simple bound constraints.      

结合有效集和多维滤子技术的拟Newton信赖域算法(英文)

针对界约束优化问题,提出一个修正的多维滤子信赖域算法.将滤子技术引入到拟Newton信赖域方法,在每步迭代,Cauchy点用于预测有效集,此时试探步借助于求解一个较小规模的信赖域子问题获得.在一定条件下,本文所提出的修正算法对于凸约束优化问题全局收敛.数值试验验证了新算法的实际运行结果.     

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.     

Numerical experiments with an inexact Jacobian trust-region algorithm

We present the adaptation and implementation of a composite-step trust region algorithm, developed in (Walther, SIAM J. Optim. 19(1):307–325, 2008), that incorporates the approximation of the Jacobian of the equality constraints with a specialized quasi-Newton method. The forming and/or factoring of the exact Jacobian in each optimization step is avoided. Hence, the presented approach is especially well suited for equality constrained optimization problems where the Jacobian of the constraints is dense.     

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

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

Numerical experiments with variations of the Gauss-Newton algorithm for nonlinear least squares

In this paper, the classical Gauss-Newton method for the unconstrained least squares problem is modified by introducing a quasi-Newton approximation to the second-order term of the Hessian. Various quasi-Newton formulas are considered, and numerical experiments show that most of them are more efficient on large residual problems than the Gauss-Newton method and a general purpose minimization algorithm based upon the BFGS formula. A particular quasi-Newton formula is shown numerically to be superior. Further improvements are obtained by using a line search that exploits the special form of the function.     

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

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

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.     

On the use of the energy norm in trust-region and adaptive cubic regularization subproblems

We propose a multi-time scale quasi-Newton based smoothed functional (QN-SF) algorithm for stochastic optimization both with and without inequality constraints. The algorithm combines the smoothed functional (SF) scheme for estimating the gradient with the quasi-Newton method to solve the optimization problem. Newton algorithms typically update the Hessian at each instant and subsequently (a) project them to the space of positive definite and symmetric matrices, and (b) invert the projected Hessian. The latter operation is computationally expensive. In order to save computational effort, we propose in this paper a quasi-Newton SF (QN-SF) algorithm based on the Broyden-Fletcher-Goldfarb-Shanno (BFGS) update rule. In Bhatnagar (ACM TModel Comput S. 18(1): 27–62, 2007), a Jacobi variant of Newton SF (JN-SF) was proposed and implemented to save computational effort. We compare our QN-SF algorithm with gradient SF (G-SF) and JN-SF algorithms on two different problems – first on a simple stochastic function minimization problem and the other on a problem of optimal routing in a queueing network. We observe from the experiments that the QN-SF algorithm performs significantly better than both G-SF and JN-SF algorithms on both the problem settings. Next we extend the QN-SF algorithm to the case of constrained optimization. In this case too, the QN-SF algorithm performs much better than the JN-SF algorithm. Finally we present the proof of convergence for the QN-SF algorithm in both unconstrained and constrained settings.