Branch-and-bound approaches to standard quadratic optimization problems |
| |
Authors: | Immanuel M Bomze |
| |
Institution: | (1) Department of Statistics and Decision Support Systems, University of Vienna, Vienna, Austria |
| |
Abstract: | This paper explores several possibilities for applying branch-and-bound techniques to a central problem class in quadratic programming, the so-called Standard Quadratic Problems (StQPs), which consist of finding a (global) minimizer of a quadratic form over the standard simplex. Since a crucial part of the procedures is based on efficient local optimization, different procedures to obtain local solutions are discussed, and a new class of ascent directions is proposed, for which a convergence result is established. Main emphasis is laid upon a d.c.-based branch-and-bound algorithm, and various strategies for obtaining an efficient d.c. decomposition are discussed. |
| |
Keywords: | D C decomposition Semidefinite relaxation Replicator dynamics |
本文献已被 SpringerLink 等数据库收录! |
|