English

运筹学学报 >

2016 , Vol. 20 >Issue 2: 79 - 87

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2016.02.007

运筹学

关于半定规划的一种宽邻域不可行内点算法的注记

展开
  • 1. 重庆师范大学数学科学学院, 重庆 401331; 2. 会东中学，四川会东 615200

收稿日期: 2015-10-26

  网络出版日期: 2016-06-15

基金资助

国家自然科学基金(No. 11431004), 重庆市教委科学技术研究项目(No. KJ1500310)

收起

A note on a wide neighborhood infeasible interior-point algorithm for semidefinite programming

Expand
  • 1. School of Mathematical Sciences, Chongqing Normal University, Chongqing 401331, China; 2. Huidong Middle School, Huidong 615200,  Sichuan, China

Received date: 2015-10-26

  Online published: 2016-06-15

Fold

摘要

针对半定规划的宽邻域不可行内点算法, 将牛顿法和预估校正法进行结合, 构造出适当的迭代方向, 提出一个修正的半定规划宽邻域不可行内点算法, 并在适当的假设条件下, 证明了该算法具有O(\sqrt{n}L)的迭代复杂界．最后利用Matlab编程, 给出了基于KM方向和NT方向的数值实验结果．

关键词： 半定规划; 宽邻域; 不可行内点算法; 数值分析

本文引用格式

杨洋, 罗洪林, 罗慧林 . 关于半定规划的一种宽邻域不可行内点算法的注记[J]. 运筹学学报, 2016 , 20(2) : 79 -87 . DOI: 10.15960/j.cnki.issn.1007-6093.2016.02.007

Abstract

Combing Newton method with predictor-corrector method, a new search direction is applied to a wide neighborhood infeasible-interior point algorithm for solving semidefinite programming． It is shown that this algorithm is a polynomial-time algorithm, which requires that all iterative points are in the neighborhood of the infeasible central path, but does not require the feasibility of the initial and iterative points．Under some mild assumptions, we show that the iteration-complexity bound is O(\sqrt{n}L)．Numerical analysis are also presented in this paper．Preliminary numerical results demonstrate the effectiveness of our method in both KM direction and NT direction．

Key words： semidefinite programming; wide neighborhood; infeasible interior-point algorithm; numerical analysis

参考文献

[1] 艾文宝. 线性规划的邻域跟踪算法 [J]．中国科学, 2004, 34(1): 40-47.
[2] Henry W, Romesh S, Lieven V. Handbook of Semidefinite Programming [M]. Boston: Kluwer Academic Publishers, 1999, 267-306.
[3] Zhang Y． On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming [J]．Optimization, 1998, 8: 365-386．
[4] Zhou G, Toh K C．Polynomiality of an inexact infeasible interior point algorithm for semidefinite programming [R]．Singapore: National University of Singapore, 2004, 261-282.
[5] Alizadeh F, Haeberly J P A, Overton M L．Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results [J]．Optimization, 1998, 8: 746-768．
[6] Monteiro 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．
[7] Nesterov Y E, Todd M J．Self-scaled barriers and interior-point methods for convex programming [J]．Mathematical Operation Research, 1997, 22: 1-42．
[8] 冯增哲, 张西学, 刘建波, 等. 半定规划的一个新的宽邻域非可行内点算法 [J]．运筹学学报, 2014, 18(2): 49-58．
[9] 迟晓妮, 刘三阳, 李炳杰．二次锥规划的一不可行内点算法 [J]．兰州大学学报(自然科学版), 2007, 43(4): 136-139．

 

Options
文章导航

/

〈 〉