Milan Hladík, David Hartman, and Moslem Zamani. Maximization of a PSD quadratic form and factorization. Optim. Lett., 15(7):2515–2528, October 2021.
[PDF] [gzipped postscript] [postscript] [HTML]
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.
@article{HlaHar2021a,
author = "Milan Hlad\'{\i}k and David Hartman and Moslem Zamani",
title = "Maximization of a {PSD} quadratic form and factorization",
journal = "Optim. Lett.",
fjournal = "Optimization Letters",
volume = "15",
number = "7",
month = "October",
pages = "2515-2528",
year = "2021",
doi = "10.1007/s11590-020-01624-w",
issn = "1862-4480",
url = "https://link.springer.com/article/10.1007/s11590-020-01624-w",
bib2html_dl_html = "https://doi.org/10.1007/s11590-020-01624-w",
bib2html_dl_pdf = "https://rdcu.be/cxepq",
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.",
keywords = "Convex quadratic form; Concave programming; NP-hardness; Upper bound; Maximum norm; Preconditioning",
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Oct 23, 2024 08:16:44