凸二次半定规划两个原始对偶内点算法

摘要

本学位论文研究一类特殊的非线性半定规划问题，即凸二次半定规划(简记为CQSDP).这类问题在经济、金融、工程设计、控制论等领域有着广泛的应用.因此，研究凸二次半定规划问题的求解算法在理论和应用方面都有重要的意义.
　　本学位论文提出了凸二次半定规划问题的一个基于势函数的原始对偶势下降内点算法和一个长步原始对偶路径跟踪算法.首先，根据线性半定规划原始对偶势下降内点法的思想，基于仿射缩放(affine-scaling)方向和Nesterov Todd-scaling(NT-scaling)方向以及势函数，建立了CQSDP的一个原始对偶势下降内点算法.该算法具有以下特点:使用原始对偶affine-scaling方向作为搜索方向且迭代点落在中心路径附近时，势函数有充分的下降性;当迭代点远离中心路径时使用NT-scaling方向作为搜索方向也保证了势函数的充分下降性;算法至多迭代O（√nln1/ε）可得到一个ε-最优解.
　　其次，借鉴线性半定规划长步原始对偶路径跟踪法的思想，引入原始对偶对数障碍函数，采用NT方向作为搜索方向，提出了凸二次半定规划的长步原始对偶路径跟踪算法.该算法具有以下特点:对数障碍函数有充分的下降性;当迭代点落在中心路径附近时步长1被接受;算法至多迭代O(n|lnε|)次后可得到一个ε-最优解.
　　最后，对本学位论文提出的两个算法进行了初步的数值测试，数值结果表明这两个算法是可行并且有效的.

目录

声明

摘要

符号说明

第1章 绪论

1．1 研究背景及意义

1．2 国内外研究现状

1．3 本文研究内容与结构

第2章 预备知识

2．1 基本概念

2．2 基本结论

2．3 本章小节

第3章 凸二次半定规划一个原始对偶势下降内点算法

3．1 势函数以及中心路径测量函数

3．2 仿射缩放(affine-scaling)方向及其性质

3．3 势函数Ψ(X，Z)在affine-scaling方向上的下降性

3．4 Nesterov-Todd(NT)-scaling方向及中心化迭代步

3．5 势函数Ψ(X，Z)在NT-scaling方向上的下降性

3．6 势下降内点算法及其多项式时间复杂性

3．7 本章小结

第4章 凸二次半定规划一个长步原始对偶路径跟踪算法

4．1 NT方向及其性质

4．2 长步原始对偶路径跟踪算法

4．3 算法的多项式时间复杂性分析

4．4 本章小结

第5章 数值试验

5．1 数值算例

5．2 参数选取及终止准则

5．3 搜索方向及矩阵对称Kronecker积的计算

5．4 数值试验结果

5．5 本章小结

结论与展望

参考文献

致谢

攻读硕士学位期间概况