A new polynomially solvable class of quadratic optimization problems with box constraints

We consider the quadratic optimization problem max x ∈ C x T Q x + q T x , where C ⊆ 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 enumera...

Full description

Saved in:
Bibliographic Details
Published in:Optimization letters 2021-09, Vol.15 (6), p.2331-2341
Main Authors: Hladík, Milan, Černý, Michal, Rada, Miroslav
Format: Article
Language:English
Subjects:
Computational Intelligence
Mathematics
Mathematics and Statistics
Numerical and Computational Physics
Operations Research/Decision Theory
Optimization
Short Communication
Simulation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the quadratic optimization problem max x ∈ C x T Q x + q T x , where C ⊆ 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.
ISSN:1862-4472
1862-4480
DOI:10.1007/s11590-021-01711-6