对称锥互补问题若干内点算法的复杂性研究

摘要

上世纪60年代以来大量的理论和实践结果表明,内点算法是解决优化问题,互补问题最有效的方法之一.本论文旨在研究几类对称锥线性互补问题(包括非单调线性互补问题,半定互补问题和非单调对称锥线性互补问题）中的有效内点算法,讨论它们的算法复杂性和实际计算效果.
　　本文首先给出基于宽邻域的三个非单调线性互补问题的预估-矫正内点算法,其中前两个是Mehrotra型算法,“保障”策略的实施使得算法具有多项式收敛性.相对第一个算法,第二个算法中通过设计新的中心参数更新方案不仅简化了复杂性分析,保证了Mehrotra型算法的多项式收敛性,而且也具有更好的实际计算效果.通过证明一些重要的引理,前两种算法对于可行的初始点,都具有O((1+κ)nL)算法复杂性.接着,通过线性互补问题以及一个不可行的初始点,构造出线性互补问题的扰动问题,提出了线性互补问题的二阶不可行预估-矫正内点算法.在求解该扰动问题的过程中,算法产生的迭代点对于扰动问题始终是严格可行的,对于原问题却始终不可行.该算法采用1-范数宽邻域,并对矫正步搜索方向进行修正.最终证明该算法具有O((1+κ)nL)的算法复杂性,这和目前为止最好的不可行内点算法复杂性一致,数值结果验证了算法具有很好的实际计算效果.进一步,把该算法推广到半定线性互补问题,得到了与线性互补问题一致的算法复杂性结果.
　　接着深入研究了两个不可行的对称锥线性互补问题预估-矫正内点算法. Mehrotra型内点算法的特点是在计算矫正方向时用到预估方向的乘积.在严格可行解存在的假设下,通过对预估方向乘积赋予不同的权重修正矫正方向,提出Cartesian-P*(κ)对称锥线性互补问题的Mehrotra型内点算法,此算法始于不可行的初始点.为了在每一步迭代中可行性残量与互补间隙有相同的减小率,该算法采用不同于传统矫正步的计算方法.基于NT尺度,该算法具有算法复杂性O((1+κ)r2 logε-1.数值试验也验证了算法是有效的.接着,在解集非空有界的条件下,给出第二个预估-矫正不可行内点算法.该算法通过一正定的不可行点,构造Cartesian-P*(κ)对称锥线性互补问题的扰动问题,通过求解扰动问题,最终得到原问题的解.基于NT尺度该算法具有O((1+κ)r2 logε-1的算法复杂性.
　　最后研究了Cartesian-P*(κ)对称锥水平线性互补问题的中心路径理论.虽然具有不同形式的标准线性互补问题和水平线性互补问题是等价的,但对于对称锥线性互补问题而言却是未决问题.在中心路径理论的基础上设计了一种不可行内点算法,该算法采用中心路径附近的点作为目标点计算矫正方向,同时利用对称邻域加强迭代的中心性.基于NT尺度,该算法具有O((1+κ)r3/2 logε-1的多项式复杂性.数值试验也验证了算法是有效的.

目录

封面

声明

中文摘要

英文摘要

符号对照表

缩略语对照表

目录

第一章 绪论

1.1对称锥线性互补问题的研究背景及意义

1.2对称锥线性互补问题及其内点算法简介

1.3 预备知识

1.4 本文的主要和安排

1.5 本文的创新点

第二章 线性互补问题预估-矫正内点算法

2.1 引言

2.2 非单调线性互补问题的Mehrotra型预估-矫正内点算法

2.3 二阶不可行预估-矫正内点算法

2.4 小结

第三章 半定互补问题预估-矫正内点算法

3.1引言

3.2初始讨论与算法

3.3算法的复杂度分析

3.4 数值结果

3.5 本章小结

第四章 对称锥线性互补问题预估-矫正内点算法

4.1 引言

4.2 对称锥线性互补问题的Mehrotra型内点算法

4.3 二阶Mehrotra型预估-矫正算法

4.4 小结

第五章 对称锥水平线性互补问题内点算法

5.1 引言

5.2 Cartesian-P*(κ)对称锥水平线性互补问题

5.3 中心路径

5.4初步讨论与算法

5.5 小结

第六章 结论和展望

6.1 研究结论

6.2 研究展望

参考文献

致谢

作者简介

1. 基本情况

2. 教育背景

3. 攻读博士学位期间的研究成果