Fast finite methods for a system of linear inequalities
type: Item
instance of: scholarly article
title: Fast finite methods for a system of linear inequalities
zbMATH Open document ID: 0614.65066
DOI: 10.1016/0898-1221(85)90060-4
publication date: 1985-01-01T00:00:00Z
review text: The paper deals with the solution of a system of m linear inequalities in n unknowns: \[ Ax\geq b. \] After a brief survey on the best known algorithms (simplex, Karmarkar) the author reformulates the problem to minimize the square of infeasibilities. To solve this problem a family of Newton-type algorithms is defined and two special cases of the family are discussed in detail. Some heuristics are also presented that can successfully be implemented in the algorithms. Proof of convergence for the simplest case is also given. The probabilistic estimate for the speed of convergence is \(O((m/n)\log^ 3n)\). The analysis is carefully described and some limited numerical experiences are also presented.
reviewed by: István Maros
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 90C20
zbMATH DE Number: 3994934
zbMATH Keywords: simplex
zbMATH Keywords: Karmarkar
zbMATH Keywords: Newton
zbMATH Keywords: convergence
author: Victor Y. Pan
MaRDI profile type: Publication
full work available at URL: 0898-1221(85)90060-4
OpenAlex ID: W2069879051
cites work: Feature Article—The Ellipsoid Method: A Survey
cites work: Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method
cites work: The Average number of pivot steps required by the Simplex-Method is polynomial
cites work: Q4079613
cites work: Q3844775
cites work: Q3325448
cites work: Q5624436
cites work: Q5584384
cites work: Khachiyan’s algorithm for linear programming
cites work: Worst case behavior of the steepest edge simplex method
cites work: The simplex algorithm with the pivot rule of maximizing criterion improvement
cites work: Q3050157
cites work: Q5585020
cites work: Q4051879
cites work: Q4039868
cites work: How to multiply matrices faster
cites work: Q5511852
cites work: Projection methods in constrained optimisation and applications to optimal policy decisions
cites work: Q3346084
cites work: On the average number of steps of the simplex method of linear programming
cites work: A bad network problem for the simplex method and other minimum cost flow algorithms
published in: Computers & Mathematics with Applications
description: scientific article; zbMATH DE number 3994934