Milan Hladík, Michal Černý, and Miroslav Rada. A new polynomially solvable class of quadratic optimization problems with box constraints. Optim. Lett., 15(6):2331–2341, September 2021.
[PDF] [gzipped postscript] [postscript] [HTML]
We consider the quadratic optimization problem $\max_x \in C\ x^T Q x + q^Tx$, where $C\subseteq R^n$ is a box and $r:=rank(Q)$ is assumed to be $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.
@article{HlaCer2021c,
author = "Milan Hlad\'{\i}k and Michal {\v{C}}ern\'{y} and Miroslav Rada",
title = "A new polynomially solvable class of quadratic optimization problems with box constraints",
journal = "Optim. Lett.",
fjournal = "Optimization Letters",
volume = "15",
number = "6",
month = "September",
pages = "2331-2341",
year = "2021",
doi = "10.1007/s11590-021-01711-6",
issn = "1862-4480",
url = "http://link.springer.com/article/10.1007/s11590-021-01711-6",
bib2html_dl_html = "https://doi.org/10.1007/s11590-021-01711-6",
bib2html_dl_pdf = "https://rdcu.be/cvZEJ",
abstract = "We consider the quadratic optimization problem $\max_{x \in C}\ x^T Q x + q^Tx$, where $C\subseteq R^n$ is a box and $r:=rank(Q)$ is assumed to be $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.",
keywords = "Quadratic optimization; Box-constrained optimization; Low-rank matrix; Zonotope; Computational complexity",
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Dec 11, 2024 08:26:23