A well-known approach to the solution of large and sparse linearly constrained quadratic programming (QP) problems is given by the classical projection and splitting methods. These methods have a similar iterative scheme consisting in to solve a sequence of QP subproblems with the constraints of the original problem and an easily solvable Hessian matrix. A theorem of convergence, resuming the main results about the projection and splitting methods, is given for this general scheme. In order to achieve a higher numerical performance than that obtained by projection and splitting methods, we introduce two variants of an iterative scheme that use a variable projection parameter at each step. These two variable projection-type methods differ in the strategy used to assure a sufficient decrease in the objective function f(x). We prove, under very general hypotheses, the convergence of these scheme and we propose two practical, nonexpensive and efficient updating rules for updating the projection parameter.An extensive numerical experimentation shows that the variable projection-type methods have an efficient behaviour.These results are produced by a set of programs available at the URL: http://www.unife.it/AnNum97/index.html. About the solution of the inner subproblems of the projection-type methods, we observe that, when the structure of the constraints does not suggest a particular solver for the QP inner subproblems, we can formulate each inner subproblem as a mixed linear complementarity problem (LCP) that can be solved by the classical projected SOR method of Cryer. When the number of constraints (and, consequently, the size of the inner LCPs) is large, appropriate parallel splitting methods for LCPs can be used for the solution on multiprocessor systems. Finally we describe two applications, arising in the framework of data analysis, that involve QP problems suited to be solved by projection-type methods.

Galligani, Emanuele, Ruggiero, V. e Luca, Zanni. "Projection-type methods for large convex quadratic programs: theory and computational experience" Working paper, Monografie del Programma di Ricerca Scientifica 1998-2000 “Analisi Numerica: Metodi e Software Matematico”, 2000.

Projection-type methods for large convex quadratic programs: theory and computational experience

GALLIGANI, Emanuele;ZANNI, Luca
2000

Abstract

A well-known approach to the solution of large and sparse linearly constrained quadratic programming (QP) problems is given by the classical projection and splitting methods. These methods have a similar iterative scheme consisting in to solve a sequence of QP subproblems with the constraints of the original problem and an easily solvable Hessian matrix. A theorem of convergence, resuming the main results about the projection and splitting methods, is given for this general scheme. In order to achieve a higher numerical performance than that obtained by projection and splitting methods, we introduce two variants of an iterative scheme that use a variable projection parameter at each step. These two variable projection-type methods differ in the strategy used to assure a sufficient decrease in the objective function f(x). We prove, under very general hypotheses, the convergence of these scheme and we propose two practical, nonexpensive and efficient updating rules for updating the projection parameter.An extensive numerical experimentation shows that the variable projection-type methods have an efficient behaviour.These results are produced by a set of programs available at the URL: http://www.unife.it/AnNum97/index.html. About the solution of the inner subproblems of the projection-type methods, we observe that, when the structure of the constraints does not suggest a particular solver for the QP inner subproblems, we can formulate each inner subproblem as a mixed linear complementarity problem (LCP) that can be solved by the classical projected SOR method of Cryer. When the number of constraints (and, consequently, the size of the inner LCPs) is large, appropriate parallel splitting methods for LCPs can be used for the solution on multiprocessor systems. Finally we describe two applications, arising in the framework of data analysis, that involve QP problems suited to be solved by projection-type methods.
Dicembre
Monografie del Programma di Ricerca Scientifica 1998-2000 “Analisi Numerica: Metodi e Software Matematico”, n. 5
Galligani, Emanuele; V., Ruggiero; Zanni, Luca
Galligani, Emanuele, Ruggiero, V. e Luca, Zanni. "Projection-type methods for large convex quadratic programs: theory and computational experience" Working paper, Monografie del Programma di Ricerca Scientifica 1998-2000 “Analisi Numerica: Metodi e Software Matematico”, 2000.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/594002
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact