作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 人工智能及识别技术 • 上一篇    下一篇

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

高雷阜,于冬梅,张兴涛   

  1. (辽宁工程技术大学数学与系统科学研究所,辽宁 阜新 123000)
  • 收稿日期:2012-09-03 出版日期:2013-09-15 发布日期:2013-09-13
  • 作者简介:高雷阜(1963-),男,教授、博士生导师,主研方向:仿生计算,智能控制;于冬梅,博士研究生;张兴涛,硕士
  • 基金资助:
    辽宁省教育厅青年基金资助项目(L2012105);教育部高等学校博士学科点专项科研基金资助项目(20102121110002)

A Nonmonotonic Trust Region Algorithm for Solving Semidefinite Programming

GAO Lei-fu, YU Dong-mei, ZHANG Xing-tao   

  1. (Institute of Mathematics and Systems Science, Liaoning Technical University, Fuxin 123000, China)
  • Received:2012-09-03 Online:2013-09-15 Published:2013-09-13

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

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

Abstract: 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.

Key words: Semidefinite Programming(SDP), trust region algorithm, nonmonotonic strategy, interior algorithm, Fischer-Burmeister function, unconstrained optimization problem

中图分类号: