SDP的Mehrotra型预估-校正内点算法及其拓展

摘要

内点算法作为求解线性规划的最有效算法之一，除具有多项式复杂性外，还具有良好的实际计算效果．自第一个求解线性规划的具有实用性的多项算法，即Kamakar算法发表以来，经国内外众多学者多年的努力，对内点算法的相关研究已取得了显著成果．求解线性规划的内点算法已被成功推广到求解半定规划(SDP)、凸规划、互补问题(LCP)、锥优化问题等．如今，内点算法已被成功地、广泛地应用于求解实际问题。
　　本文主要研究了Mehrotra型预估-校正算法，将其推广到SDP和单调LCP，导出了相应算法的多项式复杂性，通过数值实验证明了算法的可行性与有效性。
　　本文共分五章，第一章介绍了相关基础知识、算法模型、研究背景及现状和本文的基本符号约定；第二章提出了SDP的二阶Mehrotra型预估-校正算法，给出了算法的复杂性证明；第三章介绍了一个基于新的参数校正策略求解SDP的Mehrotra型内点算法，证明了相应的多项式复杂性，并用数值实验表明了算法的可行性与有效性；第四章我们为单调LCP提出了一个基于新的参数校正策略的Mehrotra型预估-校正算法，并得到了算法的迭代复杂界；第五章对全文进行了总结与展望。

目录

封面

声明

中文摘要

英文摘要

目录

引言

1 绪论

1.1 基本概念与算法模型

1.2内点算法产生的背景

1.3 国内外研究现状分析

1.4 基本符号约定

2 SDP的二阶Mehrotra型预估-校正算法

2.1 算法描述

2.2 算法的复杂性分析

2.3 小结

3 SDP的基于新的参数校正策略的Mehrotra型预估-校正算法

3.1 算法描述

3.2 障碍参数的选取方案

3.3 算法的复杂性分析

3.4 数值实验

3.5 小结

4 单调LCP基于新的参数校正策略的Mehrotra型内点算法

4.1 预备知识

4.2 新的参数校正策略

4.3算法的复杂性分析

4.4 小结

5总结与展望

参考文献

后记

附录：攻读硕士学位期间发表的学术论著