Polynomial time second order mehrotra-type predictor--corrector algorithms
type: Item
instance of: scholarly article
title: Polynomial time second order mehrotra-type predictor--corrector algorithms
zbMATH Open document ID: 1112.65057
author: Maziar Salahi
author: Nezam Mahdavi-Amiri
published in: Applied Mathematics and Computation
publication date: 2007-02-13T00:00:00Z
review text: An improvement of the second-order Mehrotra-type predictor-corrector interior point algorithm is proposed. The original algorithm was published by [\textit{Y. Zhang} and \textit{D. Zhang} [Math. Program 68, No. 3(A), 303--318 (1995; Zbl 0837.90087)]. The algorithm solves the standard linear programming problem under the assumption that the relative interiors of the feasible solution set of this problem and its dual are nonempty. The authors explain on an example the possible bad behavior of the algorithm and propose so called safeguarded versions of the algorithm, which does not suffer from this bad behavior. A polynomial complexity of the safeguarded algorithms is proved. Some computational experience with, the proposed algorithms is summarized in the concluding part of the paper.
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C51
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 5125259
zbMATH Keywords: linear optimization
zbMATH Keywords: predictor--corrector methods
zbMATH Keywords: interior point methods
zbMATH Keywords: second order methods
zbMATH Keywords: polynomial complexity
reviewed by: Karel Zimmermann
describes a project that uses: LIPSOL
describes a project that uses: PCx
describes a project that uses: McIPM
describes a project that uses: NETLIB LP Test Set
MaRDI profile type: Publication
full work available at URL: j.amc.2006.05.092
OpenAlex ID: W2025574637
cites work: PCx: an interior-point code for linear programming
cites work: Q4206561
cites work: On the Implementation of a Primal-Dual Interior Point Method
cites work: Q4339096
cites work: On Mehrotra-Type Predictor-Corrector Algorithms
cites work: Q3738934
cites work: Q5691079
cites work: On polynomiality of the Mehrotra-type predictor-corrector interior-point algorithms
cites work: Solving large-scale linear programs by interior-point methods under the Matlab∗Environment†
DOI: 10.1016/J.AMC.2006.05.092
description: scientific article; zbMATH DE number 5125259