Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2019
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/1911.10877 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915535270182912 |
|---|---|
| author | Hladík, Milan Černý, Michal Rada, Miroslav |
| author_facet | Hladík, Milan Černý, Michal Rada, Miroslav |
| contents | We consider the quadratic optimization problem $\max_{x \in C}\ x^T Q x + q^T x$, where $C\subseteq\mathbb{R}^n$ is a box and $r := \mathrm{rank}(Q)$ is assumed to be $\mathcal{O}(1)$ (i.e., fixed). We show that this case can be solved in polynomial time for an arbitrary $Q$ and $q$. The idea is based on a reduction of the problem to enumeration of faces of a certain zonotope in dimension $O(r)$. This paper generalizes previous results where $Q$ had been assumed to be positive semidefinite and no linear term was allowed in the objective function. Positive definiteness was a strong restriction and it is now relaxed. Generally, the problem is NP-hard; this paper describes a new polynomially solvable class of instances, larger than those known previously. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1911_10877 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | A new polynomially solvable class of quadratic optimization problems with box constraints Hladík, Milan Černý, Michal Rada, Miroslav Optimization and Control We consider the quadratic optimization problem $\max_{x \in C}\ x^T Q x + q^T x$, where $C\subseteq\mathbb{R}^n$ is a box and $r := \mathrm{rank}(Q)$ is assumed to be $\mathcal{O}(1)$ (i.e., fixed). We show that this case can be solved in polynomial time for an arbitrary $Q$ and $q$. The idea is based on a reduction of the problem to enumeration of faces of a certain zonotope in dimension $O(r)$. This paper generalizes previous results where $Q$ had been assumed to be positive semidefinite and no linear term was allowed in the objective function. Positive definiteness was a strong restriction and it is now relaxed. Generally, the problem is NP-hard; this paper describes a new polynomially solvable class of instances, larger than those known previously. |
| title | A new polynomially solvable class of quadratic optimization problems with box constraints |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/1911.10877 |