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

发布时间：2018-10-31 14:24

【摘要】：本学位论文研究一类特殊的非线性半定规划问题,即凸二次半定规划(简记为CQSDP).这类问题在经济、金融、工程设计、控制论等领域有着广泛的应用.因此,研究凸二次半定规划问题的求解算法在理论和应用方面都有重要的意义.本学位论文提出了凸二次半定规划问题的一个基于势函数的原始对偶势下降内点算法和一个长步原始对偶路径跟踪算法.首先,根据线性半定规划原始对偶势下降内点法的思想,基于仿射缩放(affine-scaling)方向和Nesterov Todd-scaling(NT-scaling)方向以及势函数,建立了 CQSDP 的一个原始对偶势下降内点算法.该算法具有以下特点:使用原始对偶affine-scaling 方向作为搜索方向且迭代点落在中心路径附近时,势函数有充分的下降性;当迭代点远离中心路径时使用NT-scaling方向作为搜索方向也保证了势函数的充分下降性;算法至多迭代O(√nln1/ε)可得到一个ε-最优解.其次,借鉴线性半定规划长步原始对偶路径跟踪法的思想,引入原始对偶对数障碍函数,采用NT方向作为搜索方向,提出了凸二次半定规划的长步原始对偶路径跟踪算法.该算法具有以下特点:对数障碍函数有充分的下降性;当迭代点落在中心路径附近时步长1被接受;算法至多迭代O(n|lnε|)次后可得到一个ε-最优解.最后,对本学位论文提出的两个算法进行了初步的数值测试,数值结果表明这两个算法是可行并且有效的.
[Abstract]:In this dissertation, we study a class of special nonlinear semidefinite programming problems, namely convex quadratic semidefinite programming (abbreviated as CQSDP). Such problems are widely used in the fields of economy, finance, engineering design, cybernetics and so on. Therefore, it is very important to study the algorithm of convex quadratic semidefinite programming in theory and application. In this paper, we propose a potential function based original dual potential descent interior point algorithm and a long step original dual path tracking algorithm for convex quadratic semidefinite programming. Firstly, according to the idea of original dual potential descent interior point method of linear semidefinite programming, based on affine scaling (affine-scaling) direction, Nesterov Todd-scaling (NT-scaling) direction and potential function, an original dual potential descent interior point algorithm for CQSDP is established. The algorithm has the following characteristics: when the original dual affine-scaling direction is used as the search direction and the iterative point falls near the center path, the potential function has sufficient descent; When the iteration point is far from the center path, the NT-scaling direction is used as the search direction, and the sufficient descent of the potential function is also ensured, and the algorithm can obtain an 蔚 -optimal solution at most by iterating O (nln1/ 蔚). Secondly, based on the idea of long step original dual path tracking for linear semidefinite programming, the original dual logarithmic obstacle function is introduced, and the NT direction is used as the search direction, and a long step original dual path tracking algorithm for convex quadratic semidefinite programming is proposed. The algorithm has the following characteristics: the logarithmic barrier function has sufficient descent, the step size 1 is accepted when the iterative point falls near the central path, and the algorithm can obtain an 蔚 -optimal solution after iterating at most the O (n ln 蔚 times. Finally, the numerical results of the two algorithms proposed in this dissertation show that the two algorithms are feasible and effective.
【学位授予单位】：广西大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O221

【参考文献】