论文部分内容阅读
本文对几类数学规划问题,包括混合互补、多胞体约束变分不等式、非线性规划和非线性半无限规划,构造了几个新的光滑化同伦方法.与已有的同伦方法相比,这些新的同伦方法有的能在更弱的条件下证明全局收敛性,有的全局收敛性条件相同但具有更高的计算效率.第一章,简要介绍变分不等式、非线性规划、半无限规划的背景和已有的相关算法,特别是同伦方法.第二章研究求解混合互补问题的基于Robinson法方程的光滑化同伦方法.证明了:若光滑化投影算子除具备一致逼近性、可行性和二阶光滑性这几个一般光滑化算子都满足的条件之外,还具备一个特殊的逼近性质,则在混合互补问题没有无穷远解的假设条件下,光滑化Robinson法算子满足锐角条件,进而可以证明:对几乎所有的初始点,同伦路径存在并收敛.我们通过数值例子说明,在没有无穷远解的假设条件下,常用的其它的等价非光滑方程的光滑化算子可能不满足锐角条件,对应的光滑化同伦路径不收敛.我们证明:Chen-Harker-Kanzow-Smale光滑化投影算子具备这个特殊的逼近性质,光滑化Robinson(?)去算子满足锐角条件,进而给出求解混合互补问题的一个具体可行的光滑化同伦方法.该方法和已有的基于KKT系统的内点同伦方法一样在很弱的条件下具有全局收敛性,但有更高的计算效率.对混合互补问题测试集MCPLIB的数值计算结果显示了该方法的可行性、鲁棒性和有效性.第三章,对到多胞体集合上的投影算子,构造了一种具备一致逼近性、可行性、二阶光滑性和一个特殊的逼近性质的光滑化算子,并用它构造了一个求解多胞体约束变分不等式问题的基于Robinson法方程的光滑化同伦方法.在变分不等式问题没有无穷远解的假设条件下,证明了:对几乎所有的初始点,同伦路径存在并收敛.所用的光滑化投影算子在投影算子的非光滑点的某一邻域内需要通过求解一个非线性方程组来计算,而在其它点处仅需要通过求解一个系数矩阵变化不多的线性方程组来计算.该方法和已有的基于KKT系统的内点同伦方法一样在很弱的条件下具有全局收敛性,但有更高的计算效率.初步的数值实验结果显示了该方法的可行性、鲁棒性和有效性.第四章,对具有非常多个不等式约束的非线性规划问题,构造了一种平整化凝聚约束函数,给出了一种平整化凝聚约束同伦方法和平整化凝聚动约束同伦方法.在可行集有界且内部非空、边界正则性和可行集满足法锥条件的假设条件下,证明了:对几乎所有的位于可行集内部的初始点,平整化凝聚约束同伦路径存在并收敛.平整化凝聚动约束同伦不要求可行集满足法锥条件,只需它能通过正则光滑形变变成凸集或满足法锥条件的集合即可.另外,它不要求初始点在可行集内部,可以在整个空间中随机选取.由于平整化凝聚(动)约束函数仅与函数值接近0的约束函数相关并且在区域内距边界较远的点处是常值函数,因此仅需要对少量的约束函数的梯度和Hesse矩阵进行赋值甚至不需要计算任何约束函数的梯度和Hesse矩阵,因而算法具有很高的计算效率.第五章给出了求解非线性半无限规划问题的离散化平整凝聚动约束同伦方法.首先构造半无限动约束,并通过一种自适应的离散化策略将问题转化为一系列具有有限个约束的子问题,同时,也得到了半无限动约束的离散化,进而利用平整化凝聚动约束同伦方法对离散子问题进行求解.在动约束区域有界且内部非空、边界正则和初始动约束区域满足法锥条件的假设条件下,证明在离散网格尺寸足够小时,离散动约束也满足同样的条件,进而证明了同伦路径的存在性和收敛性及离散化同伦方法的收敛性.数值试验表明该方法具有较好的稳定性和较高的计算效率.第六章研究了求解一般非线性规划问题的区域扩张同伦方法.将每个等式约束转化为两个不等式约束,然后通过构造特殊的动约束同伦来求解该问题.用这种方法构造满足收敛条件的动约束同伦,能解决已有的求解含等式约束问题的同伦方法很难解决的问题.