Optimization Online


Boundedness Theorems for the Relaxation Method

Edoardo Amaldi (amaldi***at***elet.polimi.it)
Raphael Hauser (hauser***at***comlab.ox.ac.uk)

Abstract: A classical theorem by Block and Levin says that certain variants of the relaxation method for solving systems of linear inequalities produce bounded sequences of intermediate solutions even when running on inconsistent input data. Using a new approach, we prove a more general version of this result and answer an old open problem of quantifying the bounds as a function of the input data.

Keywords: Relaxation method, perceptron boundedness, condition number, linear inequalities.

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: NA 03/18 Oxford University Computing Laboratory; Wolfson Building; Parks Road; Oxford, OX1 3QD; United Kingdom

Download: [Postscript]

Entry Submitted: 12/11/2003
Entry Accepted: 12/11/2003
Entry Last Modified: 12/11/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society