Name
Title | ||
|---|---|---|
A New Polynomially Solvable Class Of Quadratic Optimization Problems With Box Constraints |
Abstract | ||
|---|---|---|
We consider the quadratic optimization problem max(x is an element of C) x(T)Qx + q(T)x, where C subset of 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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1007/s11590-021-01711-6 | OPTIMIZATION LETTERS |
Keywords | DocType | Volume |
Quadratic optimization, Box-constrained optimization, Low-rank matrix, Zonotope, Computational complexity | Journal | 15 |
Issue | ISSN | Citations |
6 | 1862-4472 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Milan Hladík | 1 | 268 | 36.33 |
| Černý Michal | 2 | 0 | 0.34 |
| Rada Miroslav | 3 | 0 | 0.34 |