Charles Explorer logo
🇨🇿

Maximization of a PSD quadratic form and factorization

Publikace na Matematicko-fyzikální fakulta |
2021

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

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. © 2020, Springer-Verlag GmbH Germany, part of Springer Nature.