A New Second-Order Mehrotra-Type Predictor-Corrector Algorithm for SDO

被引：0

作者：

HUANG Fangyan ^{[1
]}

ZHANG Mingwang ^{[1
]}

HUANG Zhengwei ^{[2
]}

机构：

[1] College of Science,China Three Gorges University

[2] College of Economics and Management,China Three Gorges University

来源：

WuhanUniversityJournalofNaturalSciences | 2016年 / 21卷 / 02期

关键词：

Mehrotra-type algorithm; predictor-corrector methods; semidefinite optimization;

D O I：

暂无

中图分类号：

O224 [最优化的数学理论];

学科分类号：

070105 ; 1201 ;

摘要：

In Zhang's recent works,a second-order Mehrotra-type predictor-corrector algorithm for linear optimization was extended to semidefinite optimization and derived that the algorithm for semidefinite optimization had O(n3/2log（X0）T·S0/ε) iteration complexity based on the NT direction as Newton search direction. In this paper, we extend the second-order Mehrotra-type predictor-corrector algorithm for linear optimization to semidefinite optimization and discuss the polynomial convergence of the algorithm by modifying the corrector direction and new iterates. It is proved that the iteration complexity is reduced to O(n3/2log（X0）T·S0/ε), which coincides with the currently best iteration bound of Mehrotra-type predictor-corrector algorithm for semidefinite optimization.

引用

页码：99 / 109

页数：11

共 6 条

[1]

A SECOND ORDER MEHROTRA-TYPE PREDICTOR-CORRECTOR ALGORITHM FOR SEMIDEFINITE OPTIMIZATION[J]. Mingwang ZHANG. Journal of Systems Science & Complexity. 2012(06)

[2] Polynomial Convergence of Second-Order Mehrotra-Type Predictor-Corrector Algorithms over Symmetric Cones [J].

Liu, Changhe ;

Liu, Hongwei ;

Liu, Xinze .

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2012, 154 (03) :949-965

[3]

A finite termination Mehrotra-type predictor–corrector algorithm[J] . Maziar Salahi. Applied Mathematics and Computation . 2007 (2)

[4]

Polynomial time second order Mehrotra-type predictor–corrector algorithms[J] . Maziar Salahi,Nezam Mahdavi-Amiri. Applied Mathematics and Computation . 2006 (1)

[5] A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming [J].

Monteiro, RDC ;

Zhang, Y .

MATHEMATICAL PROGRAMMING, 1998, 81 (03) :281-299

[6] A NEW POLYNOMIAL-TIME ALGORITHM FOR LINEAR-PROGRAMMING [J].

KARMARKAR, N .

COMBINATORICA, 1984, 4 (04) :373-395

← 1 →