论文部分内容阅读
本文对互补问题与半定规划问题的数值解法进行了研究。主要研究内容及结果如下:
⑴提出无约束最优化共轭梯度法参数βκ修正的两种新形式.与经典共轭梯度法的区别是新方法中体现了函数值下降量信息,提出这两种方法的改进形式,证明了这四种方法的全局收敛性.数值实验表明了算法的有效性。
⑵提出求解大规模非线性互补问题(NCP(F))的共轭梯度法。(i)利用Fischer-Burmeister NCP-函数,将NCP(F)转化为非线性方程组,基此提出PRP-型共轭梯度法。算法的突出特点是在不需要额外假设及线搜索的辅助下满足充分下降条件,在F是连续可微P0+R0函数且F(x)在水平集上全局Lipschitz连续条件下,算法全局收敛;(ii)利用光滑Fischer-Burmeister函数,将NCP(F)转化为光滑非线性方程组,基此对大规模非线性互补问题提出光滑PRP-型共轭梯度法。算法执行一步需进行两个Armijo线性搜索既确保光滑参数μ的非负性又极小化由光滑Fischer-Burmeister函数所形成的光滑价值函数。在F为P0+R0连续可微函数时,算法全局收敛.数值实验表明了这两种算法的数值有效性。
⑶提出半定规划的半定互补解法.首先考虑一类特殊的半定规划问题(即在对偶问题中加入约束条件y≥0),将其最优性条件等价转化为半定互补问题(SDCP),藉此提出预估-校正光滑牛顿法,证明了牛顿方向的存在性、迭代点列的有界性及算法的全局收敛性。在解点处广义导数可逆的假设下得到算法的超线性收敛率。然后推广这一思想,将标准半定规划的最优性条件转化为广义半定互补问题(GSDCP),提出预估-校正光滑牛顿法。该方法是非线性互补问题(NCP(F))算法的推广。同样证明了牛顿方向的存在性、迭代点列的有界性及算法的全局收敛性。在解点处广义导数可逆的假设下得到算法的二次收敛率。不需要任何对称化技巧,此二方法自动产生对称搜索方向。
⑷提出半定规划的非内点连续化方法。该方法是求解半定互补问题(SDCP)算法的推广。证明了牛顿方向的存在性.在中心路径邻域有界的假设下得到迭代点列的有界性,进而证明了算法的全局收敛性.在解点处广义导数可逆的假设下算法局部二次收敛.给出了数值实验结果。
⑸提出半定规划的PRP+共轭梯度法.基于Fischer-Burmeister SDCP-函数,对SDP的最优性条件提出一梯度具有全局Lipschitz连续性的价值函数,从而将半定规划转化为无约束优化问题,进而用PRP+共轭梯度法求解。为得到PRP+共轭梯度法的收敛性同时使函数值在每次迭代中有所下降,提出一Armijo-型线搜索。