Maximization of Binary Multilinear Fractional Function

Problem: Let $a_{i,j}$, $b_{i,j}\in\mathbb{R}$ for all $(i,j)\in\left[m\right]^2$ such that $a_{i,j}=a_{j,i}$ and $b_{i,j}=b_{j,i}$. Let $z_k\in\{0,1\}$ for $k\in\left[m\right]$. We wish to maximize,

$f(z)=\displaystyle\frac{\displaystyle\sum_{(i,j)}a_{i,j}z_iz_j}{\displaystyle\sum_{(i,j)}b_{i,j}z_iz_j}$

Note that the numerator and denominator are assumed to be strictly positive.

Thoughts: I am aware of general notions of linear fractional programming. However, I am unsure whether the $z_iz_j$ terms/optimization over the hypercube will drastically change the availability of methods.

• On possible simplification might be to introduce a new set of variables $y_{(i,j)}=z_iz_j$. Commented Aug 29, 2016 at 13:59
• Would you be interested in (computable) relaxations of this problem?
– Surb
Commented Sep 2, 2016 at 13:50
• Yes, relaxations are certainly of interest. Of course the main hope is to get an answer on the hypercube. Perhaps a relaxation might yield insight to the more restrictive solution? Commented Sep 2, 2016 at 14:33
• When you say the numerator and denominator are strictly positive, do you mean that you optimize only over the set of z such that the denominator is nonzero? It would seem that z=0 always makes the denominator zero. Are you also interested in a version where (say) the $z_i$ are constrained to $\{-1,1\}$ and $B$ is positive definite so you don't have this issue? Commented Sep 2, 2016 at 18:44

First, look at it as a generalized Rayleigh quotient. As $B$ is positive definite, the Cholesky decomposition guarantees the existence of a matrix $U$ lower triangular with positive diagonal entries (and thus invertible) such that $B=U^*U$. We have $$\frac{\langle z,Az\rangle}{\langle z,Bz\rangle}=\frac{\langle y,V^*AVy\rangle}{\langle y,y\rangle} \qquad \text{with}\qquad y=Uz \quad\text{ and }\quad V=U^{-1}.$$ Let $$C = V^*AV\qquad \text{and}\qquad\mathcal D =\Big\{\frac{U^{-1}z}{\|U^{-1}z\|_2}\ \Big|\ z\in\{0,1\}^n\Big\}$$ We have then $$\max_{z\in\{0,1\}^n}f(z) = \max_{y\in \mathcal{D}}\langle y,Cy\rangle\leq \max_{\|y\|_2=1}\langle y,Cy\rangle=\rho(C).$$ where $\rho(C)$ denotes the spectral radius of $C$.