期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

二次锥规划的不可行内点算法 被引量：2

An infeasible interior point algorithm for the second-order cone programming
下载PDF
导出
摘要 给出二次锥规划的一种不可行内点算法并证明该算法是多项式时间算法.利用本算法需O(n^(1/2)lnε^(-1))次迭代就可找到问题的ε-近似解,其迭代复杂性界与现有的二次锥规划可行内点算法的复杂性界相同. An infeasible interior point algorithm for the second-order cone programming is presented. It is shown that this algorithm is a polynomial-time algorithm which can algorithm can find an ε-approximate solution in O（√nlnε^-1） iterations. The iteration complexity bound is the same as that of the feasible interior point methods available.
作者 迟晓妮 刘三阳 李炳杰
机构地区 西安电子科技大学数学科学系 空军工程大学理学院
出处 《兰州大学学报（自然科学版）》 CAS CSCD 北大核心 2007年第4期136-139,共4页 Journal of Lanzhou University(Natural Sciences)
基金 国家自然科学基金(69972036).
关键词 二次锥规划 不可行内点算法 多项式时间算法 second-order cone programming infeasible interior point algorithm polynomial-time algorithm
分类号 O221.7 [理学—运筹学与控制论]
  • 相关文献

参考文献8

  • 1ALIZADEH F,GOLDFARB D.Second-order cone programming[J].Mathematical Programming,2003,95(1):3-51.
  • 2LOBO M S,VANDENBERGHE L,BOYD S.Applications of second-order cone programming[J].Linear Algebra and Its Applications,1998,284(1-3):193-228.
  • 3KUO Yu-ju,HANS D Mittelmann.Interior point methods for second-order cone programming and operations research applications[J].Computational Optimization and Applications,2004,28(3):255-285.
  • 4MONTEIRO R D C,TSUCHIYA T.Polynomial convergence of primal-dual algorithms for the secondorder cone program based on the MZ-family of directions[J].Mathematical Programming,2000,88(1):61-83.
  • 5MIZUNO S.Polynomiality of infeasible-interiorpoint algorithms for linear programming[J].Mathematical Programming,1994,67(1):109-119.
  • 6MIAO J.Two infeasible-interior-point predictorcorrector algorithms for linear programming[J].SIAM Journal on Optimization,1996,6(3):587-599.
  • 7BERTSIMAS D,LUO X.On the worst complexity of potential reduction algorithms for linear programming[J].Mathematical Programming,1997,77(3):321-333.
  • 8TSUCHIYA T.A convergence analysis of the scalinginvariant primal-dual path-following algorithms for second-order cone programming[J].Optimizatin Methods and Software,1999,11-12:141-182.

同被引文献21

  • 1Monteiro R D C, Zhang Y. A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming [J]. Mathematical Programming, 1998, 81: 281-299.
  • 2Vandenberghe L, Boyd S. A primal-dual potential reduction method for problems involving matrix inequalities [J]. Mathematical Programming, 1995, 69: 205-236.
  • 3Zhang Y. On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming [J]. SIAM Journal on Optimization, 1998, 8: 365-386.
  • 4Nesterov Y E, Nemirovsky A S. Interior Point Methods in Convex Programming: Theory and Applications [M]. Philadelphia PA: SIAM, 1994.
  • 5Ai W B, Zhang S Z. An O(√nL) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone LCP [J]. SIAM Journal on Optimization, 2005, 16: 400-417.
  • 6Feng Z Z, Fang L. A wide neighborhood interior-point method with O(√nL) iteration-complexity bound for semidefinite programming [J]. Optimization, 2010, 59(8): 1235-1246.
  • 7Feng Z Z. A new iteration large update primal-dual interior-point method for second-order cone programming [J]. Numerical Functional Analysis and Optimization, 2012, 33(4): 397-414.
  • 8Alizadeh F, Haeberly J A, Overton N. Primal-dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results [J]. SIAM Journal on Opti- mization, 1998, 8: 746-768.
  • 9Helmberg C, Rendl F, Vanderbei R J, et al. An interior-point method for semidefinite pro- gramming [J]. SIAM Journal on Optimization, 1996, 6: 342-361.
  • 10Kojima M, Shindoh S, Hara S. Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices [J]. SIAM Journal on Optimization, 1997, 7: 86-125.

引证文献2

二级引证文献3

兰州大学学报（自然科学版）
2007年 第4期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部