Insights into the interior-point methods

Ruey-Lin Sheu, S. C. Fang

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

In this paper, we study the search directions of three important interior-point algorithms, namely, the primal-affine scaling method (with logarithmic barrier function), the dual-affine scaling method (with logarithmic barrier function), and the primal-dual interior point method. From an algebraic point of view, we show that the search directions of these three algorithms are merely Newton directions along three different "paths" that lead to a solution of the Karush-Kuhn-Tucker conditions of a given linear programming problem. From a geometric point of view, we show that these directions can be obtained by solving certain well-defined subproblems. Both views provide a general platform for studying the existing interior-point methods and deriving new interior-point algorithms. We illustrate the derivation of new interior-point algorithms by replacing the logarithmic barrier function with an entropic barrier function. The results have been generalized and discussed.

Original languageEnglish
Pages (from-to)227-257
Number of pages31
JournalZOR Zeitschrift für Operations Research Methods and Models of Operations Research
Volume36
Issue number3
DOIs
Publication statusPublished - 1992 May 1

Fingerprint

Interior Point Method
Logarithmic Barrier Function
Interior-point Algorithm
Affine Scaling
Primal-dual Interior Point Method
Karush-Kuhn-Tucker Conditions
Barrier Function
Linear programming
Well-defined
Path
Interior point method
Scaling

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Management Science and Operations Research

Cite this

@article{2971223ef952404b99f587b6ce4db10c,
title = "Insights into the interior-point methods",
abstract = "In this paper, we study the search directions of three important interior-point algorithms, namely, the primal-affine scaling method (with logarithmic barrier function), the dual-affine scaling method (with logarithmic barrier function), and the primal-dual interior point method. From an algebraic point of view, we show that the search directions of these three algorithms are merely Newton directions along three different {"}paths{"} that lead to a solution of the Karush-Kuhn-Tucker conditions of a given linear programming problem. From a geometric point of view, we show that these directions can be obtained by solving certain well-defined subproblems. Both views provide a general platform for studying the existing interior-point methods and deriving new interior-point algorithms. We illustrate the derivation of new interior-point algorithms by replacing the logarithmic barrier function with an entropic barrier function. The results have been generalized and discussed.",
author = "Ruey-Lin Sheu and Fang, {S. C.}",
year = "1992",
month = "5",
day = "1",
doi = "10.1007/BF01415890",
language = "English",
volume = "36",
pages = "227--257",
journal = "Mathematical Methods of Operations Research",
issn = "1432-2994",
publisher = "Physica-Verlag",
number = "3",

}

Insights into the interior-point methods. / Sheu, Ruey-Lin; Fang, S. C.

In: ZOR Zeitschrift für Operations Research Methods and Models of Operations Research, Vol. 36, No. 3, 01.05.1992, p. 227-257.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Insights into the interior-point methods

AU - Sheu, Ruey-Lin

AU - Fang, S. C.

PY - 1992/5/1

Y1 - 1992/5/1

N2 - In this paper, we study the search directions of three important interior-point algorithms, namely, the primal-affine scaling method (with logarithmic barrier function), the dual-affine scaling method (with logarithmic barrier function), and the primal-dual interior point method. From an algebraic point of view, we show that the search directions of these three algorithms are merely Newton directions along three different "paths" that lead to a solution of the Karush-Kuhn-Tucker conditions of a given linear programming problem. From a geometric point of view, we show that these directions can be obtained by solving certain well-defined subproblems. Both views provide a general platform for studying the existing interior-point methods and deriving new interior-point algorithms. We illustrate the derivation of new interior-point algorithms by replacing the logarithmic barrier function with an entropic barrier function. The results have been generalized and discussed.

AB - In this paper, we study the search directions of three important interior-point algorithms, namely, the primal-affine scaling method (with logarithmic barrier function), the dual-affine scaling method (with logarithmic barrier function), and the primal-dual interior point method. From an algebraic point of view, we show that the search directions of these three algorithms are merely Newton directions along three different "paths" that lead to a solution of the Karush-Kuhn-Tucker conditions of a given linear programming problem. From a geometric point of view, we show that these directions can be obtained by solving certain well-defined subproblems. Both views provide a general platform for studying the existing interior-point methods and deriving new interior-point algorithms. We illustrate the derivation of new interior-point algorithms by replacing the logarithmic barrier function with an entropic barrier function. The results have been generalized and discussed.

UR - http://www.scopus.com/inward/record.url?scp=34249842952&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34249842952&partnerID=8YFLogxK

U2 - 10.1007/BF01415890

DO - 10.1007/BF01415890

M3 - Article

VL - 36

SP - 227

EP - 257

JO - Mathematical Methods of Operations Research

JF - Mathematical Methods of Operations Research

SN - 1432-2994

IS - 3

ER -