Convergence Analysis of the Inexact Infeasible Interior-Point Method for Linear Optimization

G. Al-Jeiroudi; J. Gondzio

doi:10.1007/s10957-008-9500-5

Convergence Analysis of the Inexact Infeasible Interior-Point Method for Linear Optimization

G. Al-Jeiroudi, J. Gondzio

School of Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

We present the convergence analysis of the inexact infeasible path-following (IIPF) interior-point algorithm. In this algorithm, the preconditioned conjugate gradient method is used to solve the reduced KKT system (the augmented system). The augmented system is preconditioned by using a block triangular matrix.

The KKT system is solved approximately. Therefore, it becomes necessary to study the convergence of the interior-point method for this specific inexact case. We present the convergence analysis of the inexact infeasible path-following (IIPF) algorithm, prove the global convergence of this method and provide complexity analysis.

Original language	English
Pages (from-to)	231-247
Number of pages	17
Journal	Journal of Optimization Theory and Applications
Volume	141
Issue number	2
DOIs	https://doi.org/10.1007/s10957-008-9500-5
Publication status	Published - May 2009

Keywords

Inexact interior-point methods
Linear programming
Preconditioned conjugate gradients
Indefinite system
SYSTEMS
ALGORITHM

Access to Document

10.1007/s10957-008-9500-5

Convergence Analysis of Inexact Infeasible Interior Point Method for Linear OptimizationSubmitted manuscript, 618 KB

http://www.maths.ed.ac.uk/~gondzio/REF/alJeiroudiGondzioJOTA.pdf

Cite this

@article{9b15966928394f5bb4ef0e9a4ed9ee2d,

title = "Convergence Analysis of the Inexact Infeasible Interior-Point Method for Linear Optimization",

abstract = "We present the convergence analysis of the inexact infeasible path-following (IIPF) interior-point algorithm. In this algorithm, the preconditioned conjugate gradient method is used to solve the reduced KKT system (the augmented system). The augmented system is preconditioned by using a block triangular matrix.The KKT system is solved approximately. Therefore, it becomes necessary to study the convergence of the interior-point method for this specific inexact case. We present the convergence analysis of the inexact infeasible path-following (IIPF) algorithm, prove the global convergence of this method and provide complexity analysis.",

keywords = "Inexact interior-point methods, Linear programming, Preconditioned conjugate gradients, Indefinite system, SYSTEMS, ALGORITHM",

author = "G. Al-Jeiroudi and J. Gondzio",

note = "This paper provides the convergence analysis of an inexact infeasible interior point method. ",

year = "2009",

month = may,

doi = "10.1007/s10957-008-9500-5",

language = "English",

volume = "141",

pages = "231--247",

journal = "Journal of Optimization Theory and Applications",

issn = "0022-3239",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - Convergence Analysis of the Inexact Infeasible Interior-Point Method for Linear Optimization

AU - Al-Jeiroudi, G.

AU - Gondzio, J.

N1 - This paper provides the convergence analysis of an inexact infeasible interior point method.

PY - 2009/5

Y1 - 2009/5

N2 - We present the convergence analysis of the inexact infeasible path-following (IIPF) interior-point algorithm. In this algorithm, the preconditioned conjugate gradient method is used to solve the reduced KKT system (the augmented system). The augmented system is preconditioned by using a block triangular matrix.The KKT system is solved approximately. Therefore, it becomes necessary to study the convergence of the interior-point method for this specific inexact case. We present the convergence analysis of the inexact infeasible path-following (IIPF) algorithm, prove the global convergence of this method and provide complexity analysis.

AB - We present the convergence analysis of the inexact infeasible path-following (IIPF) interior-point algorithm. In this algorithm, the preconditioned conjugate gradient method is used to solve the reduced KKT system (the augmented system). The augmented system is preconditioned by using a block triangular matrix.The KKT system is solved approximately. Therefore, it becomes necessary to study the convergence of the interior-point method for this specific inexact case. We present the convergence analysis of the inexact infeasible path-following (IIPF) algorithm, prove the global convergence of this method and provide complexity analysis.

KW - Inexact interior-point methods

KW - Linear programming

KW - Preconditioned conjugate gradients

KW - Indefinite system

KW - SYSTEMS

KW - ALGORITHM

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

U2 - 10.1007/s10957-008-9500-5

DO - 10.1007/s10957-008-9500-5

M3 - Article

VL - 141

SP - 231

EP - 247

JO - Journal of Optimization Theory and Applications

JF - Journal of Optimization Theory and Applications

SN - 0022-3239

IS - 2

ER -

Convergence Analysis of the Inexact Infeasible Interior-Point Method for Linear Optimization

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this