169. Novel and Tractable Convex Relaxations of Standard Quadratic Optimization Problems under Cardinality Constraints
Invited abstract in session MB-13: True sparsity in Standard Quadratic Problems, stream Sparsity guarantee and cardinality-constrained (MI)NLPs.
Monday, 10:30-12:30Room: B100/6009
Authors (first author is the speaker)
| 1. | E. Alper Yildirim
|
| School of Mathematics, The University of Edinburgh | |
| 2. | Immanuel Bomze
|
| Dept. of Statistics and OR, University of Vienna | |
| 3. | Bo Peng
|
| University of Vienna | |
| 4. | Yuzhou Qiu
|
| School of Mathematics, The University of Edinburgh |
Abstract
Standard quadratic optimization problems (StQPs) provide a
versatile modelling tool in a multitude of applications such as
mathematical finance, machine learning (clustering) and modelling in
biosciences (e.g. selection and ecology). In this talk, we consider
StQPs under an additional sparsity or cardinality constraint, which,
even for convex objectives, renders NP-hard problems. One motivation to
study StQPs under such sparsity restrictions is the high-dimensional
portfolio selection problem with too many assets to handle, in
particular in the presence of transaction costs. We present novel
computational approaches to this relevant but difficult problem,
involving modern conic optimization techniques and significant
dimensional reduction, which is essential for the tractability of these
methods when the problem size grows. In addition, we propose a
particular generation procedure that systematically avoids instances
that are too easy. We present extensive computational results
demonstrating the versatility and strength of the proposed relaxations.
Keywords
- Nonlinear mixed integer optimization
- Conic and semidefinite optimization
Status: accepted
Back to the list of papers