2
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ On possible simplification might be to introduce a new set of variables $y_{(i,j)}=z_iz_j$. $\endgroup$
    – Joseph Zambrano
    Commented Aug 29, 2016 at 13:59
  • $\begingroup$ Would you be interested in (computable) relaxations of this problem? $\endgroup$
    – Surb
    Commented Sep 2, 2016 at 13:50
  • $\begingroup$ 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? $\endgroup$
    – Joseph Zambrano
    Commented Sep 2, 2016 at 14:33
  • $\begingroup$ 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? $\endgroup$
    – Noah Stein
    Commented Sep 2, 2016 at 18:44

1 Answer 1

Reset to default
1
$\begingroup$

This not a solution but a though. At least it gives you an easily computable upper bound.

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$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .