预处理的校正梯度路径信赖域算法

Preconditioned modified gradient path trust region algorithm.

信赖域算法是最优化中广泛使用的一种方法.在迭代的每一步都要解信赖域子问题,在众多解子问题的方法中,校正梯度路径算法利用系统的特征值和特征向量在整个维数空间求出子问题的解.虽然这个方法较吸引人,但现有的校正梯度路径算法不太可行,因为在每一步迭代中它要求整个特征系统的计算或者矩阵的重复分解.提出了一种预处理的校正梯度信赖域算法.该算法在一步迭代中仅通过对对称矩阵进行一次Bunch-Parlett分解就在全空间中求出子问题的解,再用单位下三角矩阵因子去标度问题的变量,预处理的校正梯度路径由此形成.算法在通常使用的条件下有好的收敛性,对各种模型的优化问题的计算结果也显示出算法的高效性.

Trust region algorithm is a kind of method that is widely used in optimization. It solves a trust region subproblem at each iteration. Among the methods solving the subproblem, the modified gradient path algorithm obtains the solution to the subproblem in full-dimensional space by using the eigenvalues and eigenvectors of the system. Although the idea is attractive, the existing modified gradient path method seems impractical because it requires either the calculation of the full eigensystem of a matrix or repeated factorizations of matrices at each iteration. A preeonditioned modified gradient path trust region algorithm is proposed. The algorithm finds a solution to the subproblem in full-dimensional space by just one Bunch-Parlett factorization for symmetric matrices at each iteration and by using the resulting unit lower triangular factor to scale the variables in the problem. A preconditioned modified gradient path can then be formed easily. The algorithm has good convergence properties under commonly used conditions. Computational results for different scale optimization problems are presented, which shows that the algorithm is effective.