Maximization of a Convex Quadratic Form on a Polytope: Factorization and the Chebyshev Norm Bounds

0507646 - ÚI 2021 RIV CH eng C - Konferenční příspěvek (zahraniční konf.)
Hladík, M. - Hartman, David
Maximization of a Convex Quadratic Form on a Polytope: Factorization and the Chebyshev Norm Bounds.
Optimization of Complex Systems: Theory, Models, Algorithms and Applications. Cham: Springer, 2020 - (Le Thi, H.; Minh Le, H.; Pham Dinh, T.), s. 119-127. Advances in Intelligent Systems and Computing, 991. ISBN 978-3-030-21802-7.
[WCGO 2019: World Congress on Global Optimization /6./. Metz (FR), 08.07.2019-10.07.2019]
Institucionální podpora: RVO:67985807
Klíčová slova: Convex quadratic form * Relaxation * NP-hardness * Interval computation
Obor OECD: Pure mathematics

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.
Trvalý link: http://hdl.handle.net/11104/0298623