A new kernel function yielding the best known iteration bounds for primal-dual interior-point algorithms

被引：17

作者：

Bai, Yan Qin ^{[1
]}

Guo, Jin Li ^{[2
]}

Roos, Cornelis ^{[3
]}

机构：

[1] Shanghai Univ, Dept Math, Shanghai 200436, Peoples R China

[2] Shanghai Univ Sci & Technol, Sch Business, Shanghai 200093, Peoples R China

[3] Delft Univ Technol, Fac Elect Engn Math & Comp Sci, NL-2600 GA Delft, Netherlands

来源：

ACTA MATHEMATICA SINICA-ENGLISH SERIES | 2009年 / 25卷 / 12期

基金：

中国国家自然科学基金;

关键词：

linear optimization; interior-point method; primal-dual method; large-update method; polynomial complexity;

D O I：

10.1007/s10114-009-6457-8

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm for solving linear optimization problems. In this paper we present a new kernel function which yields an algorithm with the best known complexity bound for both large- and small-update methods.

引用

页码：2169 / 2178

页数：10

共 8 条

[1] A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization
Bai, YQ
El Ghami, M
Roos, C
[J]. SIAM JOURNAL ON OPTIMIZATION, 2004, 15 (01) : 101 - 128
[2] A new efficient large-update primal-dual interior-point method based on a finite barrier
Bai, YQ
El Ghami, M
Roos, C
[J]. SIAM JOURNAL ON OPTIMIZATION, 2003, 13 (03) : 766 - 782
[3] Megiddo N., 1989, PROGR MATH PROGRAMMI, P131, DOI 10.1007/978-1-4613-9617-8_8
[4] Peng J., 2001, J. Comput. Technol., V6, P61
[5] Peng Jiming., 2002, PRIN SER APPL MATH
[6] ROSS C, 2005, THEORY ALGORITHMS LI
[7] SONNEVEND G, 1986, LECT NOTES CONTR INF, V84, P866
[8] Primal-dual interior-point algorithms for second-order cone optimization based on a new parametric kernel function
Yan Qin Bai
Guo Qiang Wang
[J]. ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2007, 23 (11) : 2027 - 2042

← 1 →