COMPUTATIONAL EXPERIENCE WITH A GLOBALLY CONVERGENT PRIMAL DUAL PREDICTOR CORRECTOR ALGORITHM FOR LINEAR-PROGRAMMING

被引：20

作者：

LUSTIG, IJ

MARSTEN, RE

SHANNO, DF

机构：

[1] RUTGERS STATE UNIV,RUTGERS CTR OPERAT RES,NEW BRUNSWICK,NJ 08903

[2] PRINCETON UNIV,DEPT CIVIL ENGN & OPERAT RES,PROGRAM STAT & OPERAT RES,PRINCETON,NJ 08544

[3] GEORGIA INST TECHNOL,SCH IND ENGN & OPERAT RES,ATLANTA,GA 30332

来源：

MATHEMATICAL PROGRAMMING | 1994年 / 66卷 / 01期

关键词：

PRIMAL-DUAL INTERIOR POINTS; GLOBAL CONVERGENCE; WARM STARTS;

D O I：

10.1007/BF01581140

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Kojima, Megiddo, and Mizuno proved global convergence of a primal-dual algorithm that corresponds to methods used in practice. Here, the numerical efficiency of a predictor-corrector extension of that algorithm is tested. Numerical results are extremely positive, indicating that the safety of a globally convergent algorithm can be obtained at little computational cost. The algorithm is tested on infeasible problems with less success. Finally, the algorithm is applied to a warm started problem, with very encouraging preliminary results.

引用

页码：123 / 135

页数：13

共 12 条

[1] HIGHER-ORDER PREDICTOR-CORRECTOR INTERIOR POINT METHODS WITH APPLICATION TO QUADRATIC OBJECTIVES
Carpenter, Tamra J.
Lustig, Irvin J.
Mulvey, John M.
Shanno, David F.
[J]. SIAM JOURNAL ON OPTIMIZATION, 1993, 3 (04) : 696 - 725
[2] Chvatal V, 1983, LINEAR PROGRAMMING
[3] Fiacco AV, 1990, NONLINEAR PROGRAMMIN
[4] A POTENTIAL-FUNCTION REDUCTION ALGORITHM FOR SOLVING A LINEAR PROGRAM DIRECTLY FROM AN INFEASIBLE WARM START
FREUND, RM
[J]. MATHEMATICAL PROGRAMMING, 1991, 52 (03) : 441 - 466
[5] Gay D. M., 1985, MATH PROGRAMMING SOC
[6] A PRIMAL DUAL INFEASIBLE-INTERIOR-POINT ALGORITHM FOR LINEAR-PROGRAMMING
KOJIMA, M
MEGIDDO, N
MIZUNO, S
[J]. MATHEMATICAL PROGRAMMING, 1993, 61 (03) : 263 - 280
[7] COMPUTATIONAL EXPERIENCE WITH A PRIMAL-DUAL INTERIOR POINT METHOD FOR LINEAR-PROGRAMMING
LUSTIG, IJ
MARSTEN, RE
SHANNO, DF
[J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 1991, 152 : 191 - 222
[8] ON IMPLEMENTING MEHROTRA'S PREDICTOR-CORRECTOR INTERIOR-POINT METHOD FOR LINEAR PROGRAMMING
Lustig, Irvin J.
Marsten, Roy E.
Shanno, David F.
[J]. SIAM JOURNAL ON OPTIMIZATION, 1992, 2 (03) : 435 - 449
[9] MANNE AS, 1973, MULTILEVEL PLANNING, P107
[10] Megiddo N., 1989, PROGR MATH PROGRAMMI, P131, DOI DOI 10.1007/978-1-4613-9617-8_8

← 1 2 →