论文部分内容阅读
本文研究非线性互补问题及非光滑凸极小化问题的数值算法。对于非线性互补问题,提出几种基于半光滑方程组的算法。对于非光滑凸函数极小化问题,基于正则化技术,提出求解问题的一类共轭梯度型算法和谱梯度方法。建立这几种算法的全局收敛性,并通过数值试验对所提出的算法进行数值检验。结果表明本文提出的算法具有很好的实用性。 在第二章,首先导出一个与非线性互补问题等价的半光滑方程组,称之为几乎光滑方程组。该方程组具有很好性质:它在方程组的解集之外的任何点都连续可微。而且,它在解集合中的任一点半光滑。特别地,如果解集是单点集,则该函数是基本的强几乎光滑的。该方程组较已有非线性互补问题等价的半光滑方程组具有更好的光滑性。同时保留已有半光滑方程组的许多好的性质如水平集的有界性、局部/全局误差界等.在此基础上我们提出求解非线性互补问题的一种牛顿法,并证明算法的全局收敛性和超线性收敛性.数值试验结果表明所提出的算法很有效。 在第三章,提出求解非线性互补问题的一种光滑化牛顿法和一种同伦光滑化方法。首先构造一种非线性互补问题的新的光滑化函数。与已有的光滑化函数不同,首先构造绝对值函数的导数的光滑化函数,进而导出绝对值函数的光滑化函数。该函数具有Jacobian相容性。基于此光滑化函数,提出一个光滑化牛顿法和同伦光滑化方法来解非线性互补问题。在适当的条件下,分别证明两种算法的全局收敛性和超线性收敛性。还证明了当同伦光滑化算法用于解线性互补问题时,经过有限步迭代后,算法终止于问题的解。 在第四章,研究用无导数算法解对称互补问题。先将求解互补问题转化为求解与其等价的非光滑方程组,在此基础上将最近提出的两种修正PRP共轭梯度法的思想加以改进,应用于解非光滑方程组,所提出的方法是无导数的,但算法产生的点列使得方程组的模函数值序列单调递减,因而算法是一种下降算法。在较弱的条件下分别证明两种算法的全局收敛性。数值结果表明算法有效。 在第五章,借助Moreau-Yosida正则化,首先将求解非光滑凸函数极小化问题转化为求解光滑凸函数极小化问题。利用Moreau-Yosida正则化的近似函数值、近似梯度值而不是其精确值,提出一类共轭梯度型算法,先研究这类算法的共同性质,再着重研究三种具体的共轭梯度型算法。在较弱的条件下,分别证明这三种算法都具有全局收敛性。与已有算法相比,本文算法易于实现,且可用于解大规模问题。 在第六章,充分利用Moreau-Yosida正则化的内在性质,首先将求解非光滑问题转化为求解光滑凸函数极小化问题。然后提出一种易于实现的谱共轭梯度法来解非光滑凸极小化问题。算法利用Moreau-Yosida正则化的近似函数值、近似梯度值而不是其精确值。在较弱的条件下,证明算法的全局收敛性。