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 [J].

Bai, YQ ;

El Ghami, M ;

Roos, C .

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 [J].

Bai, YQ ;

El Ghami, M ;

Roos, C .

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 [J].

Yan Qin Bai ;

Guo Qiang Wang .

ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2007, 23 (11) :2027-2042

← 1 →