论文部分内容阅读
该文研究互补与混合互补问题的新算法.建立了互补和混合互补问题的一类新La-grange乘子法理论框架,该方法通过引入与互补和混合互补问题等价的非光滑方程组的向量Lagrange函数,构造了一类新的含乘子的处处光滑价值函数,通过简便易行的乘子修正新手段,克服了问题固有的非光滑性困难,为此类问题的数值求解提供了新途径.基此提出了若干求解互补和混合互补问题的新算法.在较目前常用条件更弱的假定下,证明了算法的全局收敛性和局部超线性或二次收敛率.对MCPLIB库及其它大量算例且较其它文献更多初始点的广泛数值实验,表明该方法具有与理论分析一致的高效可靠、令人满意的实算性能,特别对一些典型算例具有优于以往算法的突出数值表现.1.对线性互补问题,首次得到一种乘子固定时具有分片二次凸性质的光滑价值函数,它在光滑条件下完好保持了原问题的线性性质,基此提出了Lagrange乘子法.(i)在P<,0>-矩阵且解集非空有界的弱条件下得到算法的全局收敛性;(ii)在P-矩阵且无须严格互补条件下得到有限步收敛性,且方法避免了采用混杂开关技术或在Newton步之外增加修正步等额外耗费计算量的附加步骤,每次迭代只需求解一次Newton方程.2.对非线性互补问题,利用所构造价值函数具有的特殊非线性最小二乘结构,成功实现了具有一般意义的构造Newton方程时仅利用价值函数的一阶导数且无须计算相应残量函数Jacobi矩阵乘积的Newton法.文中给出了形式不同的两种Newton方程,同时提出了两种计算量少、易于实现的乘子修正策略,并将其纳入了一个统一模式.在P<,0>-函数且解集非空有界的条件下得到算法的全局收敛性,在R-正则条件下得到超线性或二次收敛率,其中全局收敛性条件弱于目前常用条件:单调函数且有严格可行点或P<,0>+R<,0>-函数.3.对于混合互补问题,以中间值函数为桥梁,给出了混合互补问题的Lagrange乘子法.在P<,0>-函数和可行域有界的条件下证明了相应算法的全局收敛性,在R-正则条件下得到了相应算法的超线性或二次收敛率.4.对于互补和混合互补问题,通过消去乘子的技巧性工作,分别构造了新的不含任何参数的一类光滑价值函数,它们结构简单,在P<,0>-函数情形便可保证其稳定点是互补问题之解,不仅具备类似著名Fischer-Burmeister函数的良好微分性质,且强制性方面更优,同时对线性问题也保持了其线性性质.特别对混合互补问题,据作者所知,该价值函数是迄今形式最为简单的光滑价值函数.基此构造的互补和混合互补问题的算法,均具备在前述条件或比其更弱条件下的全局收敛性、局部超线性或二次收敛率以及在线性情形下的有限步收敛性.