On well definedness of the central path

被引:13
作者
Drummond, LMG [1 ]
Svaiter, BF
机构
[1] UFRJ, COPPE, Programa Engn Sistemas Computacao, Rio De Janeiro, Brazil
[2] Inst Matemat Pura & Aplicada, Rio De Janeiro, Brazil
关键词
convex programming; linear constraints; central path; logarithmic barrier function; analytic center;
D O I
10.1023/A:1021768121263
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
We study the well definedness of the central path for a linearly constrained convex programming problem with smooth objective function. We prove that, under standard assumptions, existence of the central path is equivalent to the nonemptiness and boundedness of the optimal set. Other equivalent conditions are given. We show that, under an additional assumption on the objective function, the central path converges to the analytic center of the optimal set.
引用
收藏
页码:223 / 237
页数:15
相关论文
共 18 条
[1]  
[Anonymous], 1979, Soviet Math. Dokl
[2]  
BAYER DA, 1986, NONLINEAR GEOMETRY L
[3]   A Polynomial Newton Method for Linear Programming [J].
de Ghellinck, Guy ;
Vial, Jean-Philippe .
ALGORITHMICA, 1986, 1 (1-4) :425-453
[4]  
DENHORTOG D, 1994, INTERIOR POINT APPRO
[5]  
Fiacco AV, 1990, NONLINEAR PROGRAMMIN
[6]  
FRISH KR, 1955, LOGARITHMIC POTENTIA
[7]  
GONZAGA CC, 1988, PROGR MATH PROGRAMMI, P1
[8]   Central paths, generalized proximal point methods, and Cauchy trajectories in Riemannian manifolds [J].
Iusem, AN ;
Svaiter, BF ;
Neto, JXD .
SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 1999, 37 (02) :566-588
[9]   A NEW POLYNOMIAL-TIME ALGORITHM FOR LINEAR-PROGRAMMING [J].
KARMARKAR, N .
COMBINATORICA, 1984, 4 (04) :373-395
[10]   A POLYNOMIAL-TIME ALGORITHM FOR A CLASS OF LINEAR COMPLEMENTARITY-PROBLEMS [J].
KOJIMA, M ;
MIZUNO, S ;
YOSHISE, A .
MATHEMATICAL PROGRAMMING, 1989, 44 (01) :1-26