半定规划的非单调信赖域算法研究

Nonmonotone Trust-region Method for Solving Semidefinite Programs

半定规划是线性规划的一种推广,是一个非光滑的凸优化问题。文中利用半定规划的最优性条件将半定规划问题转化为一个非线性可微的方程组,然后将这一方程组转化为一个无约束优化问题。因此求解半定规划问题就转变为求解无约束优化问题,最后用非单调的信赖域算法求解此问题,即避免了重复计算子问题,且降低了运算次数,同时也证明了此算法的收敛性。

As an extension of linear programming, semidefiniting programming is a nonlinear and nonsmooth programming. In this paper semidefiniting programming is transformed into nonlinear differentiable equations, and then into an unconstrained optimization, thus changing the solution of the semidefiniting programming into the solu- tion of the unconstrained optimization, which can be done by nonmonotone trust-region method to avoid repeated sub- problems solving and reduce the number of calculations. Convergence of the algorithm is proved.