一种求解半定规划的非单调信赖域算法

摘要

A nonmonotonic trust region algorithm for solving Semidefinite Programming(SDP) is proposed in this paper. The equivalent smoothing equations of the optimal condition are obtained by exploiting the Fischer-Burmeister function that is extended to the matrix domain, and the center of the path of SDP is rewritten. The algorithm makes full use of first-order gradient information of the current iteration point to solve the trust region subproblem, and a new trust region radius selection mechanism is proposed. Simulation results show that the algorithm runs faster than the classical interior point algorithm for general scale semidefinite programming problems(n, m≤30), for large-scale semidefinite programming problem(n, m>30) the algorithm is suitable for handling Norm min, Lovasz these two kinds of problems.%提出一种求解半定规划的非单调信赖域算法。利用推广至矩阵域的光滑Fischer-Burmeister函数，转化半定规划的最优性条件，改写半定规划的中心路径，得到与其等价的无约束优化问题的非线性可微光滑方程组，在求解信赖域子问题时，利用当前迭代点的一阶梯度信息，给出信赖域半径的选取机制。仿真结果表明，与经典的内点算法相比，对于一般规模(n, m≤30)的半定规划问题，该算法的运行速度较快。对于大规模的半定规划问题(n, m＞30)，该算法更适合处理Norm min、Lovasz这2类问题。