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

A Nonmonotonic Trust Region Algorithm for Solving Semidefinite Programming

作　　者：高雷阜[1] 于冬梅[1] 张兴涛[1] 

机构地区：[1]辽宁工程技术大学数学与系统科学研究所,辽宁阜新123000

出　　处：《计算机工程》2013年第9期233-236,共4页Computer Engineering

基　　金：辽宁省教育厅青年基金资助项目(L2012105);教育部高等学校博士学科点专项科研基金资助项目(20102121110002)

摘　　要：提出一种求解半定规划的非单调信赖域算法。利用推广至矩阵域的光滑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.

关 键 词：半定规划 信赖域算法 非单调策略 内点算法 FISCHER-BURMEISTER函数 无约束优化问题 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]