Convexification of Multi-period Quadratic Programs with Indicators
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913622997860352 |
|---|---|
| author | Lee, Jisun Gómez, Andrés Atamtürk, Alper |
| author_facet | Lee, Jisun Gómez, Andrés Atamtürk, Alper |
| contents | We study a multi-period convex quadratic optimization problem, where the state evolves dynamically as an affine function of the state, control, and indicator variables in each period. We begin by projecting out the state variables using linear dynamics, resulting in a mixed-integer quadratic optimization problem with a (block-) factorizable cost matrix. We discuss the properties of these matrices and derive a closed-form expression for their inverses. Employing this expression, we construct a closed convex hull representation of the epigraph of the quadratic cost over the feasible region in an extended space. Subsequently, we establish a tight second-order cone programming formulation with $\mathcal{O}(n^2)$ conic constraints. We further propose a polynomial-time algorithm based on a reformulation of the problem as a shortest path problem on a directed acyclic graph. To illustrate the applicability of our results across diverse domains, we present case studies in statistical learning and hybrid system control. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_17178 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Convexification of Multi-period Quadratic Programs with Indicators Lee, Jisun Gómez, Andrés Atamtürk, Alper Optimization and Control We study a multi-period convex quadratic optimization problem, where the state evolves dynamically as an affine function of the state, control, and indicator variables in each period. We begin by projecting out the state variables using linear dynamics, resulting in a mixed-integer quadratic optimization problem with a (block-) factorizable cost matrix. We discuss the properties of these matrices and derive a closed-form expression for their inverses. Employing this expression, we construct a closed convex hull representation of the epigraph of the quadratic cost over the feasible region in an extended space. Subsequently, we establish a tight second-order cone programming formulation with $\mathcal{O}(n^2)$ conic constraints. We further propose a polynomial-time algorithm based on a reformulation of the problem as a shortest path problem on a directed acyclic graph. To illustrate the applicability of our results across diverse domains, we present case studies in statistical learning and hybrid system control. |
| title | Convexification of Multi-period Quadratic Programs with Indicators |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2412.17178 |