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