半定规划的一种非精确不可行内点法  

An Inexact Infeasible Interior Point Algorithm for Semidefinite Programming

作　　者：王淑华[1] 刘三阳[1] 穆学文[1] 迟晓妮[1] 

机构地区：[1]西安电子科技大学应用数学系,西安陕西710071

出　　处：《应用数学》2004年第S1期93-97,共5页Mathematica Applicata

基　　金：陕西省自然科学基金资助项目 (2 0 0 1SL0 5 )

摘　　要：本文给出了求解半定规划的一种基于KM方向的非精确不可行内点法 ,分析了其收敛性 ,结果表明 ,该算法最多可以在O(n2 ln( 1 /ε) )步内求出半定规划的一个ε 近似解 ,与YZhang所提出的精确不可行内点法有相同的界 .Based on an inexact version of the KM direction,a primal-dual inexact infeasible interior point algorithm for semidefinite programming problems (SDP) is proposed.Furthermore,its convergent bound is given.Under a mild assumption on the inexactness,we show that the algorithm can find an ε-approximate solution for an SDP in O(n2 ln (1/ε)) iterations.This bound is the same as that of the exact infeasible interior point algorithms proposed by Y Zhang.

关 键 词：半定规划 不可行内点法 非精确搜索方向 KM方向 多项式复杂性 

分 类 号：O221.7[理学—运筹学与控制论]