Undominated d.c. Decompositions of Quadratic Functions and Applications to Branch-and-Bound Approaches |
| |
Authors: | Immanuel M Bomze Marco Locatelli |
| |
Institution: | (1) ISDS, Universität Wien, Austria, Universitätsstraße 5, A-1010 Wien;(2) Dipartimento di Informatica, Università di Torino, Italy, Corso Svizzera 185, 10149 Torino |
| |
Abstract: | In this paper we analyze difference-of-convex (d.c.) decompositions for indefinite quadratic functions. Given a quadratic function, there are many possible ways to decompose it as a difference of two convex quadratic functions. Some decompositions are dominated, in the sense that other decompositions exist with a lower curvature. Obviously, undominated decompositions are of particular interest. We provide three different characterizations of such decompositions, and show that there is an infinity of undominated decompositions for indefinite quadratic functions. Moreover, two different procedures will be suggested to find an undominated decomposition starting from a generic one. Finally, we address applications where undominated d.c.d.s may be helpful: in particular, we show how to improve bounds in branch-and-bound procedures for quadratic optimization problems. |
| |
Keywords: | branch-and-bound global optimization matrix pencil quadratic optimization semidefinite programming |
本文献已被 SpringerLink 等数据库收录! |
|