Milan Hladík and David Hartman. Maximization of a convex quadratic form on a polytope: Factorization and the Chebyshev norm bounds. In Optimization of Complex Systems: Theory, Models, Algorithms and Applications, pp. 119–127, AISC 991, Springer, Cham, 2020.
[PDF] [gzipped postscript] [postscript] [HTML]
Maximization of a convex quadratic form on a convex polyhedral set is an NP-hard problem. We focus on computing an upper bound based on a factorization of the quadratic form matrix and employment of the maximum vector norm. Effectivity of this approach depends on the factorization used. We discuss several choices as well as iterative methods to improve performance of a particular factorization. We carried out numerical experiments to compare various alternatives and to compare our approach with other standard approaches, including McCormick envelopes.
@inProceedings{HlaHar2020a,
author = "Milan Hlad\'{\i}k and David Hartman",
editor = "Hoai An {Le Thi} and others",
feditor = "{Le Thi}, Hoai An and Le, Hoai Minh and {Pham Dinh}, Tao",
title = "Maximization of a convex quadratic form on a polytope: {Factorization} and the {Chebyshev} norm bounds",
booktitle = "Optimization of Complex Systems: {Theory}, Models, Algorithms and Applications",
series = "AISC",
fseries = "Advances in Intelligent Systems and Computing",
volume = "991",
publisher = "Springer",
address = "Cham",
pages = "119-127",
year = "2020",
doi = "10.1007/978-3-030-21803-4_12",
isbn = "978-3-030-21803-4",
issn = "2194-5357",
url = "https://link.springer.com/chapter/10.1007/978-3-030-21803-4_12",
bib2html_dl_html = "https://doi.org/10.1007/978-3-030-21803-4_12",
bib2html_dl_pdf = "https://doi.org/10.1007/978-3-030-21803-4_12",
abstract = "Maximization of a convex quadratic form on a convex polyhedral set is an NP-hard problem. We focus on computing an upper bound based on a factorization of the quadratic form matrix and employment of the maximum vector norm. Effectivity of this approach depends on the factorization used. We discuss several choices as well as iterative methods to improve performance of a particular factorization. We carried out numerical experiments to compare various alternatives and to compare our approach with other standard approaches, including McCormick envelopes.",
keywords = "Convex quadratic form; Relaxation; NP-hardness; Interval computation",
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Oct 23, 2024 08:16:44