Minimizing $\sum_{i=1}^n x_i/y_i$ over a polytope

Question

I want to solve a linear programming problem in the $2n$ variables $x_1, \ldots, x_n$ and $y_1, \ldots, y_n$ where the cost is of the form $x_1/y_1 + \cdots + x_n/y_n$. Specifically, I want to solve \begin{align*} & {\rm minimize}~ \sum_{i=1}^n x_i/y_i \\ &\mbox{ subject to } Ax + B y \leq c \\ & x>0, y>0, \end{align*} where $A$ and $B$ are given matrices and $c$ is a given vector.

This feels like it should be NP-hard due to the non-convexity of the objective, but I have no idea how to show this, or even whether I'm missing some kind of clever trick that makes it convex. If the matrices $A$ and $B$ were positive, you could plug in $x_i=e^{u_i}, y_i = e^{v_i}$ and the problem would become a convex problem that you could solve via geometric programming, but positivity is not an assumption. I'm not even sure what would be a natural combinatorial problem to try to write in this format, so any suggestions would be very welcome.

Answer 1

Your objective function is indeed not convex, but you can make it convex with the appropriate transformation, which means it is solvable in polynomial time. But applying this reformulation is complex: you should try a non-convex solver first and stop there if it works in practice.

The easy way: Non-convex quadratic model

As pointed in the comments, it is a quadratic program, so you can solve it with a non-convex quadratic solver. Although not a polynomial-time algorithm theoretically, these solvers are really efficient in practice.

\begin{align*} {\rm minimize}&~ \sum_{i=1}^n r_i \\ \mbox{ subject to } & \\ & Ax + B y \leq c \\ & r_iy_i \geq x_i \\ & x>0, y>0 \end{align*}

The hard way: Convex fractional programming reformulation

Stated as follows, it is clear that it is a fractional programming problem: \begin{align*} {\rm minimize}&~ \frac{\sum_{i=1}^n x_i \prod_{j\neq i} y_j}{\prod_{j=1}^n y_j} \\ \mbox{ subject to }& \\ & Ax + B y \leq c \\ & r_i \geq x_iy_i \\ & x>0, y>0 \end{align*}

Both the numerator and denominator are convex, so you can follow the transformation given in the above link to make it convex. This makes it solvable in polynomial time.

$$ \begin{align*} z_i &= \frac{x_i}{\prod_{j=1}^n y_j} \\ w_i &= \frac{y_i}{\prod_{j=1}^n y_j} \\ t &= \frac{1}{\prod_{j=1}^n y_j} \\ \end{align*} $$

And solve (yes, the convexity is far from obvious):

$$ \begin{align*} {\rm minimize}& ~ \frac{1}{t^{n-1}} \sum_{i=1}^n z_i \prod_{j\neq i} w_j \\ \mbox{ subject to } & \\ & \frac{\prod_{j\neq i} w_j}{t^{n-1}} \leq 1 \\ & Ax + By \leq ct \\ & z>0, w>0, t \geq 0 \end{align*} $$