A strengthened acceptance criterion for approximate projections in Karmarkar's algorithm
type: Item
instance of: scholarly article
title: A strengthened acceptance criterion for approximate projections in Karmarkar's algorithm
zbMATH Open document ID: 0618.90055
DOI: 10.1016/0167-6377(86)90080-5
author: Kurt M. Anstreicher
published in: Operations Research Letters
publication date: 1986-01-01T00:00:00Z
review text: As described by \textit{D. Goldfarb} and \textit{S. Mehrotra} [''A relaxed version of Karmarkar's method'', Tech. Rep., Dept. of Industrial Engineering and Oper. Res., Columbia Univ., New York (1985)] the convergence analysis of Karamarkar's method for linear programming leads naturally to an acceptance criterion when approximate projections are used in the course of the algorithm. Unfortunately, the preliminary results of Golbfarb and Mehrotra indicate that their criterion is generally not strong enough to insure that the algorithm makes reasonable progress. In this note we present a stronger criterion and show that the difference between the two criteria is potentially large.
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 4003900
zbMATH Keywords: projective algorithm
zbMATH Keywords: convergence analysis
zbMATH Keywords: Karamarkar's method
zbMATH Keywords: approximate projections
MaRDI profile type: Publication
full work available at URL: 0167-6377(86)90080-5
OpenAlex ID: W2049645719
cites work: A relaxed version of Karmarkar's method
cites work: Karmarkar's algorithm with improved steps
cites work: A new polynomial-time algorithm for linear programming
cites work: Q3686495
cites work: A reduced-gradient variant of Karmarkar's algorithm and null-space projections
cites work: An extension of Karmarkar's algorithm for linear programming using dual variables
description: scientific article; zbMATH DE number 4003900