The complexity of quadratic programming problems with two quadratic constraints is an open problem. In this paper we show that when one constraint is a ball constraint and the Hessian of the quadratic function defining the other constraint is positive definite, then, under quite general conditions, the problem can be solved in polynomial time in the real-number model of computation through an approach based on the analysis of the dual space of the Lagrange multipliers. However, the degree of the polynomial is rather large, thus making the result mostly of theoretical interest.

On the complexity of quadratic programming with two quadratic constraints / Consolini, Luca; Locatelli, Marco. - In: MATHEMATICAL PROGRAMMING. - ISSN 0025-5610. - (2017), pp. 91-128. [10.1007/s10107-016-1073-8]

On the complexity of quadratic programming with two quadratic constraints

CONSOLINI, Luca;LOCATELLI, Marco
2017

Abstract

The complexity of quadratic programming problems with two quadratic constraints is an open problem. In this paper we show that when one constraint is a ball constraint and the Hessian of the quadratic function defining the other constraint is positive definite, then, under quite general conditions, the problem can be solved in polynomial time in the real-number model of computation through an approach based on the analysis of the dual space of the Lagrange multipliers. However, the degree of the polynomial is rather large, thus making the result mostly of theoretical interest.
On the complexity of quadratic programming with two quadratic constraints / Consolini, Luca; Locatelli, Marco. - In: MATHEMATICAL PROGRAMMING. - ISSN 0025-5610. - (2017), pp. 91-128. [10.1007/s10107-016-1073-8]
File in questo prodotto:
File Dimensione Formato  
MP_2016_CDT.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: Creative commons
Dimensione 488.34 kB
Formato Adobe PDF
488.34 kB Adobe PDF Visualizza/Apri

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: http://hdl.handle.net/11381/2819435
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 6
social impact