论文部分内容阅读
梯度算法是求解最优化问题的一类重要方法。算法选取目标函数的负梯度方向作为搜索方向,并且常依据目标函数的梯度来确定搜索步长。梯度算法对最优化算法理论研究很有意义,同时仍然被应用于许多实际问题。传统的梯度算法以Cauchy在1847年提出的最速下降法为代表,其迭代格式简单直接,易于理解。理论上能够证明算法具有线性收敛速度,然而在实际计算中,最速下降法往往随着问题条件数的增大而变得非常缓慢。
1988年Barzilai和Borwein提出的两点步长梯度法为梯度算法开辟了新的研究方向。大量的实际计算表明,这一算法(以下简称BB算法)的效率远高于Cauchy的最速下降法,其计算表现在某些情况下甚至可以接近共轭梯度算法。此后,许多研究者提出了各种不同的BB类型梯度方法,其中大多BB类型梯度方法与BB方法一样是非单调的,即并不能保证目标函数值或梯度模在每一个迭代步均下降。最近,Yuan与Dai研究了一类具有单调性质的梯度方法,它与Cauchy的最速下降法一样保证目标函数值在每一步单调下降,但计算表现明显改善,并且一般好于BB算法。
虽然BB类型梯度算法继承了最速下降法迭代格式的简单性,而且数值效果很好,但足在理论研究方面,由于算法的非单调特征显著,其的收敛分析较为困难。目前最好的收敛结果足对任意维正定二次函数,BB类型梯度算法R-线性收敛。但在理论分析中所得到的收敛速度远不能准确反映算法的实际计算表现。
本文的主要目的是在理论上对BB类型梯度算法的收敛性质做一些探索,并针对两类特殊的问题研究如何结合与运用BB类型梯度算法。在第二章中,我们对一类BB类型梯度方法作了深入的收敛性分析,并证明这类算法具有m步Q-线性收敛的性质,其中m与具体算法有关。这一结果强于已有的BB类型梯度方法R-线性收敛结果,因此可望能够比后者更好地反映算法的计算表现。
在第三中我们将推广BB梯度算法求解线性鞍点问题,并提出了预条件的不精确BB算法。为此,我们首先研究了在梯度不精确情况下的BB梯度算法,证明了当梯度的误差被控制某一个范围时BB算法对于任意维对称正定的极小化二次问题仍然R-线性收敛。在此基础上,我们借鉴Uzawa方法的思路,将线性鞍点问题转换为带有内迭代的正定二次问题,引入预条件子,并使用不精确BB算法进行求解,从而提出了预条件的不精确BB算法。由于该算法迭代方向和迭代步长的计算均很简单,因此较其他梯度算法以及共轭梯度算法,每一步的计算量都比较小,并且计算表现远好于传统的定常梯度迭代方法。由于梯度的计算可以不精确地进行,该算法在求解鞍点问题时也可以进一步减小内迭代的计算量。
在第四章中,我们研究使用BB类型投影梯度算法等求解有序单纯形约束的最优化问题。投影梯度算法在每一步需通过求解点到可行域的投影的子问题以得到新的一步迭代点和判定算法是否中止。因此是否能有效地求解这一子问题与投影算法的效率密切相关。我们针对有序单纯形约束,在已有的原始可行方法以及对偶可行方法的基础上提出一种可以从任意积极集出发求解投影子问题的快速原始-对偶积极集方法。由于投影梯度算法在求解过程中需要反复求解一系列相似的投影子问题,而新的原始-对偶方法可以充分利用前一次子问题求解时所给出的信息,因此这一方法当使用在投影梯度算法中时可以比原有的方法节省大量的计算。
最后一章是对已有工作的总结以及对未来的展望。