Theoretical efficiency of a shifted-barrier-function algorithm for linear programming
type: Item
instance of: scholarly article
title: Theoretical efficiency of a shifted-barrier-function algorithm for linear programming
zbMATH Open document ID: 0729.65040
DOI: 10.1016/0024-3795(91)90265-X
author: Robert M. Freund
published in: Linear Algebra and its Applications
publication date: 1991-01-01T00:00:00Z
review text: The author gives an algorithm for solving a linear program \(\min \{C^ Tx| \quad Ax=b,\quad x\geq 0\},\) using a sequence of shifted-barrier problems \(\min \{C^ Tx-\epsilon \cdot \sum^{n}_{j=1}\ln (x_ j+\epsilon h_ j)| \quad Ax=b,\quad x+\epsilon h>0\}\) for a fixed shift vector \(h>0\), and a sequence of \(\epsilon >0\), that converges to zero. The advantages of the shifted-barrier algorithm are presented.
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 4205884
zbMATH Keywords: algorithm
zbMATH Keywords: linear program
zbMATH Keywords: shifted-barrier problems
zbMATH Keywords: shifted-barrier algorithm
MaRDI profile type: Publication
Wikidata QID: Q114852088
cites work: A monotonic projective algorithm for fractional linear programming
cites work: Optimization of “$\log x$” Entropy over Linear Equality Constraints
cites work: A Method for the Parametric Center Problem, with a Strictly Monotone Polynomial-Time Algorithm for Linear Programming
cites work: Projective transformations for interior-point algorithms, and a superlinearly convergent algorithm for the w-center problem
cites work: A variant of Karmarkar's linear programming algorithm for problems in standard form
cites work: Conical projection algorithms for linear programming
cites work: Q4739657
cites work: A polynomial-time algorithm, based on Newton's method, for linear programming
cites work: An extension of Karmarkar's algorithm for linear programming using dual variables
cites work: Q4735032
cites work: Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming
full work available at URL: 0024-3795(91)90265-x
OpenAlex ID: W1970687372
description: scientific article; zbMATH DE number 4205884