HIGHER-ORDER PREDICTOR-CORRECTOR INTERIOR POINT METHODS WITH APPLICATION TO QUADRATIC OBJECTIVES

被引：45

作者：

Carpenter, Tamra J. ^{[1
]}

Lustig, Irvin J. ^{[1
]}

Mulvey, John M. ^{[1
]}

Shanno, David F. ^{[2
]}

机构：

[1] Princeton Univ, Dept Civil Engn & Operat Res, Program Stat & Operat Res, Princeton, NJ 08544 USA

[2] Rutgers State Univ, Rutgers Ctr Operat Res, New Brunswick, NJ 08903 USA

来源：

SIAM JOURNAL ON OPTIMIZATION | 1993年 / 3卷 / 04期

基金：

美国国家科学基金会;

关键词：

interior point methods; linear programming; quadratic programming; higher-order methods; predictor-corrector method; composite Newton method;

D O I：

10.1137/0803036

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper, the authors explore the full utility of Mehrotra's predictor-corrector method in the context of linear and convex quadratic programs. They describe a procedure for doing multiple corrections at each iteration and implement it within the framework of OB1. Computational results are provided for the multiple correcting procedure using several strategies for determining the number of corrections in a given iteration. The results indicate that iteration counts can be significantly reduced by allowing higher-order corrections but at the the cost of extra work per iteration. The procedure is shown to be a level-m composite Newton interior point method, where m is the number of corrections performed in an iteration.

引用

页码：696 / 725

页数：30

共 13 条

[1]

CARPENTER T. J., 1990, SOR902 PRINC U DEP C

[2]

GAY D. M., 1988, ELECT MAIL DISTRIBUT

[3]

Kojima M., 1989, PROGR MATH PROGRAMMI, P29, DOI [10.1007/978-1-4613-9617-8_2, DOI 10.1007/978-1-4613-9617-8_2]

[4] FORMULATING 2-STAGE STOCHASTIC PROGRAMS FOR INTERIOR POINT METHODS [J].

LUSTIG, IJ ;

MULVEY, JM ;

CARPENTER, TJ .

OPERATIONS RESEARCH, 1991, 39 (05) :757-770

[5] COMPUTATIONAL EXPERIENCE WITH A PRIMAL-DUAL INTERIOR POINT METHOD FOR LINEAR-PROGRAMMING [J].

LUSTIG, IJ ;

MARSTEN, RE ;

SHANNO, DF .

LINEAR ALGEBRA AND ITS APPLICATIONS, 1991, 152 :191-222

[6] ON IMPLEMENTING MEHROTRA'S PREDICTOR-CORRECTOR INTERIOR-POINT METHOD FOR LINEAR PROGRAMMING [J].

Lustig, Irvin J. ;

Marsten, Roy E. ;

Shanno, David F. .

SIAM JOURNAL ON OPTIMIZATION, 1992, 2 (03) :435-449

[7] ON FINDING A VERTEX SOLUTION USING INTERIOR POINT METHODS [J].

MEHROTRA, S .

LINEAR ALGEBRA AND ITS APPLICATIONS, 1991, 152 :233-253

[8] ON THE IMPLEMENTATION OF A PRIMAL-DUAL INTERIOR POINT METHOD [J].

Mehrotra, Sanjay .

SIAM JOURNAL ON OPTIMIZATION, 1992, 2 (04) :575-601

[9]

MIZUNO S., 1989, 878 CORN U SCH OP RE

[10] A POLYNOMIAL-TIME PRIMAL-DUAL AFFINE SCALING ALGORITHM FOR LINEAR AND CONVEX QUADRATIC-PROGRAMMING AND ITS POWER-SERIES EXTENSION [J].

MONTEIRO, RDC ;

ADLER, I ;

RESENDE, MGC .

MATHEMATICS OF OPERATIONS RESEARCH, 1990, 15 (02) :191-214

← 1 2 →