Maximization of a PSD quadratic form and factorization

Milan Hladík, David Hartman, Moslem Zamani

Research output: Contribution to journalArticleScientificpeer-review

Abstract

We consider the problem of maximization of a convex quadratic form on a convex polyhedral set, which is known to be NP-hard. In particular, we focus on upper bounds on the maximum value. We investigate utilization of different vector norms (estimating the Euclidean one) and different objective matrix factorizations. We arrive at some kind of duality with positive duality gap in general, but with possibly tight bounds. We discuss theoretical properties of these bounds and also extensions to generally preconditioned factors. We employ mainly the maximum vector norm since it yields efficiently computable bounds, however, we study other norms, too. Eventually, we leave many challenging open problems that arose during the research.
Original languageEnglish
Pages (from-to)2515-2528
JournalOptimization Letters
Volume15
Issue number7
DOIs
Publication statusPublished - Oct 2021

Keywords

  • Concave programming
  • Convex quadratic form
  • Maximum norm
  • NP-hardness
  • Preconditioning
  • Upper bound

Fingerprint

Dive into the research topics of 'Maximization of a PSD quadratic form and factorization'. Together they form a unique fingerprint.

Cite this