具有O(n^(1/2)L)复杂度的Mehrotra型预估-校正内点算法
A Mehrotra-type Predictor-corrector Interior-point Algorithm with O (n^(1/2)L) Complexity
摘要
基于中心路径的大邻域,提出了一种新的二阶预估-校正内点算法求解半定线性互补问题,并证明了该算法具有目前最好的多项式复杂度O(n^(1/2)L).
A new second order predictor-corrector algorithm for solving the semidefinite linear complementary problem is presented. And it is proved that the algorithm has the best polynomial complexity O（√nL）.
出处
《新乡学院学报》
2013年第3期161-164,167,共5页
Journal of Xinxiang University
基金
国家自然科学基金项目(61072144)
关键词
线性互补问题
内点算法
预估
校正算法
多项式复杂度
linear complementary problems
interior-point algorithm
predictor-corrector algorithm
polynomialcomplexity
参考文献10
-
1KOJIMA M, SHINDOHZ S, HARA S. Interior-point Methods for the Monotone Semidefinite Linear Complementarity Problem in Symmetric Matrices[J]. SIAM J OPTIM, 1997, 7(1): 86-125.
-
2GOWDA M S, SONG Y. On Semidefinite Linear Complementarity Problem[J]. Math Program, 2000, 88: 575-587.
-
3MEHROTRA S. On the Implementation of a Primal-dual Interior Point Method[J]. SIAM J Optim, 1992, 2(4): 575-601.
-
4HUNG P, YE Y. An Asymptotical O( nL)-iteration Path-following Linear Programming Algorithm that Use Wide Neighborhood[J]. SIAM J Optim, 1996, 6(2): 570-586.
-
5AI W, ZHANG S, An O(.：nL)-iteration Primal-dual Path-following Method, Based on Wide Neighborhoods and Large Updates, for Monotone LCP[J]. SIAM J Optim, 2005, 16(2): 400-417.
-
6LIU C, LIU H, CONG W. An O(：nL) Iteration Primal-dual Second-order Corrector Algorithm for Linear Programming [J]. Optimization Letters, 2011, 5(4): 729-743.
-
7ZHANG Y. On Extending Some Primal-dual Interior-point Algorithms from Linear Programming to Semidefinite Programming[J]. SIAM J Optim, 1998, 8(2): 365-386.
-
8TODD M J, TOH K C. TUTUNCU R H. On the Nesterov-todd Direction in Semidefinite Programming[J]. SIAM J Optim, 1998, 8(3): 769-796.
-
9LI Y, TERLAKY T. A New Class of Large Neighborhood Path-following Interior Point Algorithms for Semidefinite Optimization with O(nL) -iteration Complexity[J]. SIAM J Optim, 2010, 20(6): 2853-2875.
-
10MONTEIRO R D C, ZHANG Y. A Unified Analysis for a Class of Long-step Primal-dual Path-following Interior-point ：lgorithms for Semidefinite Programming[J]. Math Program, 1998, 81(3): 281-299.
-
1杨喜美,张因奎,裴永刚.求解线性规划的宽邻域不可行内点算法[J].西南大学学报（自然科学版）,2017,39(1):92-98.
-
2杨喜美,刘红卫,刘长河.弧搜索内点算法[J].吉林大学学报（理学版）,2014,52(4):693-697. 被引量：1
-
3刘新泽,刘红卫,刘长河.P_*(κ)线性互补问题的预估-校正内点算法[J].吉林大学学报（理学版）,2013,51(5):789-794.
-
4刘新泽,李玉婷.P_*(κ)线性互补问题的预估-校正内点算法[J].内蒙古师范大学学报（自然科学汉文版）,2013,42(4):375-379.
-
5刘新泽,郭晓永.半定互补问题的Mehrotra型预估-校正内点算法[J].西南大学学报（自然科学版）,2013,35(7):73-78.
-
6杨喜美,刘红卫,张因奎.带有新的迭代格式的内点算法[J].应用数学和力学,2014,35(9):1063-1070. 被引量：1
-
7杨喜美,张因奎,裴永刚.求解P_*(κ)-水平线性互补问题的核函数内点算法[J].河南师范大学学报（自然科学版）,2016,44(5):1-7. 被引量：1
-
8黄雷,李洪波.四维Minkowski空间上零括号代数的复括号和复差分表示[J].中国科学（A辑）,2008,38(7):750-760.
-
9张伟.基于多项式逼近的学习式搜索[J].辽宁大学学报（自然科学版）,1995,22(A00):113-116.
-
10王双成,冷翠平,刘凤霞.无向马尔科夫毯分类器与集成[J].系统工程与电子技术,2008,30(7):1333-1338.
