Two properties of condition numbers for convex programs via implicitly defined barrier functions

被引：5

作者：

Peña, J ^{[1
]}

机构：

[1] Carnegie Mellon Univ, Grad Sch Ind Adm, Pittsburgh, PA 15213 USA

来源：

MATHEMATICAL PROGRAMMING | 2002年 / 93卷 / 01期

关键词：

D O I：

10.1007/s101070200294

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We study two issues on condition numbers for convex programs: one has to do with the growth of the condition numbers of the linear equations arising in interior-point algorithms; the other deals with solving conic systems and estimating their distance to infeasibility. These two issues share a common ground: the key tool for their development is a simple, novel perspective based on implicitly-defined barrier functions. This tool has potential use in optimization beyond the context of condition numbers.

引用

页码：55 / 75

页数：21

共 19 条

[1] Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results
Alizadeh, F
Haeberly, JPA
Overton, ML
[J]. SIAM JOURNAL ON OPTIMIZATION, 1998, 8 (03) : 746 - 768
[2] DONTCHEV AL, UNPUB T AMS
[3] Some characterizations and properties of the "distance to ill-posedness" and the condition measure of a conic linear system
Freund, RM
Vera, JR
[J]. MATHEMATICAL PROGRAMMING, 1999, 86 (02) : 225 - 260
[4] Condition-based complexity of convex optimization in conic linear form via the ellipsoid algorithm
Freund, RM
Vera, JR
[J]. SIAM JOURNAL ON OPTIMIZATION, 1999, 10 (01) : 155 - 176
[5] KOJIMA M, 1994, DECOMPOSITION INTERI, P152
[6] Ill-conditioned convex processes and conic linear systems
Lewis, AS
[J]. MATHEMATICS OF OPERATIONS RESEARCH, 1999, 24 (04) : 829 - 834
[7] Nesterov Y., 1994, INTERIOR POINT POLYN
[8] Self-scaled barriers and interior-point methods for convex programming
Nesterov, YE
Todd, MJ
[J]. MATHEMATICS OF OPERATIONS RESEARCH, 1997, 22 (01) : 1 - 42
[9] Primal-dual interior-point methods for self-scaled cones
Nesterov, YE
Todd, MJ
[J]. SIAM JOURNAL ON OPTIMIZATION, 1998, 8 (02) : 324 - 364
[10] Condition measures and properties of the central trajectory of a linear program
Nunez, MA
Freund, RM
[J]. MATHEMATICAL PROGRAMMING, 1998, 83 (01) : 1 - 28

← 1 2 →