A polynomially solvable case of unconstrained (-1,1)-quadratic fractional optimization

Abstract

In this paper, we consider an unconstrained (-1,1)-quadratic fractional optimization in the following form: ${\min }_{x\in \{-1,1{\}}^n}(x^{T}Ax+\alpha )/(x^{T}Bx+\beta )$, where $A$ and $B$, given by their nonzero eigenvalues and associated eigenvectors, have ranks not exceeding fixed integers $r_a$ and $r_b$, respectively. We show that this problem can be solved in $O(n^{r_a+r_b+1}{\log }^{2}n)$ by the accelerated Newton-Dinkelbach method when the matrices $A$ has nonpositive diagonal entries only, $B$ has nonnegative diagonal entries only. Furthermore, this problem can be solved in $O(n^{r_a+r_b+2}{\log }^{2}n)$ when $A$ has $O(\log (n))$ positive diagonal entries, $B$ has $O(\log (n))$ negative diagonal entries.

13 pages, 1 figure