Quadratic functions with exponential number of local maxima (Q1079496)

The global maximization of a quadratic function \[ f(x)=\sum^{n}_{i=1}\sum^{n}_{j=i}q_{ij}x_ ix_ j \] over \(B^ n_ 2=\{x:\) \(x_ i\in \{0,1\}\) for \(i=1,...,n\}\) and over \(\bar B^ n_ 2=\{x:\) \(0\leq x_ i\leq 1\) for \(i=1,...,n\}\) is considered. The maximization over \(\bar B^ n_ 2\) is an NP-hard problem. For f convex, the maximization over \(\bar B^ n_ 2\) is equivalent to that over \(B^ n_ 2\). A measure of complexity of algorithms obtaining and analyzing local solutions that these problems possess is proposed. A quadratic function with an exponential \((2^ n)\) number of distinct local maxima is constructed. So, local algorithms for quadratic programming have an exponential worst case time complexity.