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

A Nonmonotonic Trust Region Algorithm for Solving Semidefinite Programming

提出一种求解半定规划的非单调信赖域算法。利用推广至矩阵域的光滑Fischer-Burmeister函数,转化半定规划的最优性条件,改写半定规划的中心路径,得到与其等价的无约束优化问题的非线性可微光滑方程组,在求解信赖域子问题时,利用当前迭代点的一阶梯度信息,给出信赖域半径的选取机制。仿真结果表明,与经典的内点算法相比,对于一般规模(n,m≤30)的半定规划问题,该算法的运行速度较快。对于大规模的半定规划问题(n,m>30),该算法更适合处理Norm min、Lovasz这2类问题。

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.