论文部分内容阅读
大规模最优化问题广泛见于经济计划、工程设计、生产管理、国防和航空航天等重要领域.由于具有所需存储量少、迭代简单和数值效果好等优点,梯度型算法已经成为解大规模无约束优化问题的重要算法,并且在图像处理、压缩感知、人脸识别、文本分类和机器学习等领域得到了广泛的应用.众所周知,步长对梯度法的数值性能有至关重要的影响.因此,研究梯度法的步长,提出有效的梯度法,具有重要的理论意义和应用价值.本文在现有理论和算法基础上,从新的角度观察BB算法,针对梯度法,提出一类新的步长—近似最优步长,把基于近似最优步长的梯度法称为近似最优梯度法.值得注意的是,最速下降法、修正的最速下降法、BB算法、修正的BB算法和固定步长的梯度法都是近似最优梯度法.本文主要研究解凸二次极小化问题的近似最优梯度法,将近似最优梯度法推广到一般无约束优化领域,设计几类解一般无约束优化问题的近似最优梯度法,最后将近似最优梯度法及其思想应用到共轭梯度法中.主要工作和创新成果如下:1.针对梯度法,提出一类新的步长—近似最优步长.利用最近三次迭代的信息构造标量矩阵,使用拟牛顿公式进行更新,构造目标函数在迭代点的二次近似模型,计算近似最优步长,提出一种解凸二次极小化问题的近似最优梯度法,建立其全局收敛性,并证明近似最优梯度法具有R-线性收敛速度.数值结果表明,针对几类常用的测试问题,近似最优梯度法的数值性能远远优于一些著名的梯度法.2.将解凸二次极小化问题的近似最优梯度法推广到一般无约束优化领域,提出几类解无约束优化问题的近似最优梯度法:(1)构造目标函数在迭代点的二次近似模型,计算近似最优步长,研究其重要性质.特别地,针对非负曲率情形,设计了一种简单有效的初始步长确定策略.结合非单调Armijo型线搜索,提出一种基于二次模型的近似最优梯度法,并建立算法的全局收敛性.数值实验验证了近似最优梯度法的有效性.(2)利用三种BFGS公式对标量矩阵进行更新,构造目标函数在迭代点处修正的二次近似模型,计算近似最优步长并研究其重要性质.特别地.针对非负曲率情形,构造特殊的二次近似模型产生步长.结合非单调Armijo型线搜索,提出三种基于修正的二次模型的近似最优梯度法,并在较弱的条件下建立其全局收敛性.数值实验验证了近似最优梯度法的有效性.(3)根据函数在迭代点的性质,分别构造目标函数在迭代点的张量近似模型和二次近似模型,建立各近似模型的使用准则,计算近似最优步长.结合非单调Armijo型线搜索,提出一种基于锥模型和二次模型的近似最优梯度法,并在较弱条件下建立了算法的全局收敛性.数值实验验证了近似最优梯度法的有效性.(4)根据函数在迭代点的性质,分别构造目标函数在迭代点的锥近似模型和二次近似模型,建立各近似模型的使用准则,计算近似最优步长.结合非单调Armijo型线搜索,提出一种基于锥模型和二次模型的近似最优梯度法(GM_AOS(cone)),并建立其全局收敛性.数值结果表明,对Andrei给出的测试集,GM_AOS(cone)的数值性能优于著名的共轭梯度软件CGOPT,且能与著名的有限内存CG软件CG_DESCENT(6.0)相媲美,对CUTEst测试集,GM_AOS(cone)的数值性能能与CGOPT和CG_DESCENT(5.0)相媲美.3.根据目标函数在迭代点的性质,利用近似最优梯度法的思想与线性共轭梯度法的性质,构造目标函数在二维子空间上的二次近似模型,极小化近似模型得到新的搜索方向,研究其重要性质,提出新的初始步长确定策略.设计Generalized Wolfe型线搜索,提出一种解无约束优化问题的Barzilai-Borwein子空间极小化共轭梯度法(SMCG_BB),在较弱条件下建立其全局收敛性,并证明SMCG_BB具有R-线性收敛速度.数值结果表明,针对CUTEst测试集和Andrei设计的测试集,SMCG_BB比著名的CG软件CGOPT和CG_DESCENT(5.3)更具竞争力.近似最优步长的重要特征是它充分利用了函数二阶或更高阶的信息.在近似最优梯度法求解过程中,近似最优步长在大多数情况下直接满足非单调Armijo线搜索条件,从而无需启动线搜索.因此,近似最优步长极大地减少了计算成本,有效地提高近似最优梯度法的效率.近似最优梯度法是一类新的梯度法,它的搜索方向是容易计算且所需存储量少的负梯度方向,使用的线搜索是非常简单且容易找到步长的非单调Armijo型线搜索,更重要的是它具有非常出色的数值效果.我们认为,近似最优梯度法将成为大规模无约束优化中具有较强竞争力的优化方法,并将在很多实际领域得到广泛的应用.