Real-time solution of quadratic optimization problems with banded matrices and indicator variables
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_ | 1866910436144709632 |
|---|---|
| author | Gomez, Andres Han, Shaoning Lozano, Leonardo |
| author_facet | Gomez, Andres Han, Shaoning Lozano, Leonardo |
| contents | We consider mixed-integer quadratic optimization problems with banded matrices and indicator variables. These problems arise pervasively in statistical inference problems with time-series data, where the banded matrix captures the temporal relationship of the underlying process. In particular, the problem studied arises in monitoring problems, where the decision-maker wants to detect changes or anomalies. We propose to solve these problems using decision diagrams. In particular we show how to exploit the temporal dependencies to construct diagrams with size polynomial in the number of decision variables. We also describe how to construct the convex hull of the set under study from the decision diagrams, and how to deploy the method online to solve the problems in milliseconds via a shortest path algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_03051 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Real-time solution of quadratic optimization problems with banded matrices and indicator variables Gomez, Andres Han, Shaoning Lozano, Leonardo Optimization and Control 90C26, 90C27 We consider mixed-integer quadratic optimization problems with banded matrices and indicator variables. These problems arise pervasively in statistical inference problems with time-series data, where the banded matrix captures the temporal relationship of the underlying process. In particular, the problem studied arises in monitoring problems, where the decision-maker wants to detect changes or anomalies. We propose to solve these problems using decision diagrams. In particular we show how to exploit the temporal dependencies to construct diagrams with size polynomial in the number of decision variables. We also describe how to construct the convex hull of the set under study from the decision diagrams, and how to deploy the method online to solve the problems in milliseconds via a shortest path algorithm. |
| title | Real-time solution of quadratic optimization problems with banded matrices and indicator variables |
| topic | Optimization and Control 90C26, 90C27 |
| url | https://arxiv.org/abs/2405.03051 |