Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective value
type: Item
instance of: scholarly article
title: Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective value
zbMATH Open document ID: 0645.90048
DOI: 10.1007/BF01580729
author: Donald Goldfarb
author: Sanjay Mehrotra
published in: Mathematical Programming. Series A. Series B
publication date: 1988-01-01T00:00:00Z
review text: Considered is the linear programming problem minimize \(z(x)=c^ Tx\) subject to \(Ax=0,\) \(e^ T=n,\) \(x\geq 0,\) where A is an \(m\times n\) matrix of rank m, \(x\in R^ n\), \(c\in R^ n\), and \(e\in R^ n\) is the vector with all its elements equal to one. It is assumed that e is a feasible point, i.e. \(Ae=0\), and that a lower bound \(z^ 0\) on the optimal value is known. The authors give variants of Karmarkar's algorithm for this problem with unknown optimal objective value \(z^*\). These methods combine an earlier approach of the authors for relaxing the requirement that certain projections be computed exactly with the approach of Todd and Burrell for generating an improving sequence of lower bounds for \(z^*\) using dual feasible solutions. It is also discussed how to compute an initial lower bound for the optimal objective value and how to transform a ``standard form'' linear program into the form given in this paper.
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 4053340
zbMATH Keywords: variants of Karmarkar's algorithm
zbMATH Keywords: improving sequence of lower bounds
zbMATH Keywords: dual feasible solutions
reviewed by: Hans Benker
describes a project that uses: CRAIG
describes a project that uses: LSQR
MaRDI profile type: Publication
cites work: A monotonic projective algorithm for fractional linear programming
cites work: A variant of Karmarkar's linear programming algorithm for problems in standard form
cites work: A relaxed version of Karmarkar's method
cites work: A new polynomial-time algorithm for linear programming
cites work: LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
cites work: An extension of Karmarkar's algorithm for linear programming using dual variables
cites work: An experimental approach to karmarkar’s projective method for linear programming
description: scientific article; zbMATH DE number 4053340