By perturbing properly a linear program to a separable quadratic program it is possible to solve the latter in its dual variable space by iterative techniques such as sparsity-preserving SOR (successive over relaxations). In this way large sparse linear programs can be handled. This paper gives a new computational criterion to check whether the solution of the perturbed quadratic programs provide the least 2-norm solution of the original linear program. This criterion improves on the criterion proposed in an earlier paper. The author also describes an algorithm for solving linear programs which is based on the SOR methods. The main property of this algorithm is that, under mild assumptions, it finds the least 2-norm solution of a linear program in a finite number of iterations.

A Finite Algorithm for the Least Two-Norm Solution of a Linear Program / Lucidi, Stefano. - In: OPTIMIZATION. - ISSN 0233-1934. - STAMPA. - 18:(1987), pp. 809-823.

A Finite Algorithm for the Least Two-Norm Solution of a Linear Program

LUCIDI, Stefano
1987

Abstract

By perturbing properly a linear program to a separable quadratic program it is possible to solve the latter in its dual variable space by iterative techniques such as sparsity-preserving SOR (successive over relaxations). In this way large sparse linear programs can be handled. This paper gives a new computational criterion to check whether the solution of the perturbed quadratic programs provide the least 2-norm solution of the original linear program. This criterion improves on the criterion proposed in an earlier paper. The author also describes an algorithm for solving linear programs which is based on the SOR methods. The main property of this algorithm is that, under mild assumptions, it finds the least 2-norm solution of a linear program in a finite number of iterations.
1987
LINEAR PROGRAMMING PROBLEM; QUADRATIC PROGRAMMING PROBLEMS; NONLINEAR PROGRAMMING ALGORITHMS
01 Pubblicazione su rivista::01a Articolo in rivista
A Finite Algorithm for the Least Two-Norm Solution of a Linear Program / Lucidi, Stefano. - In: OPTIMIZATION. - ISSN 0233-1934. - STAMPA. - 18:(1987), pp. 809-823.
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/17995
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? ND
social impact