# Minimizing $x_1/x_2$ over a simplex in the positive orthant

I need to solve the following problem \begin{align}\min&\quad x_1/x_2\\\text{s.t.}&\quad Ax \leq b\\&\quad x > 0\end{align} where $$A$$ is a positive matrix.

The best thing I can think of is to put $$x_1 = e^{z_1}, x_2 = e^{z_2}$$. Then the objective becomes a convex function $$e^{z_1 - z_2}$$ and the constraints are convex because of the positive nature of $$A$$.

Is there something better for this kind of problem?

As mentioned by @user3680510, your problem is a linear-fractional programming problem, and can be reformulated as a linear programming problem through the Charnes-Cooper transformation.

Start from your formulation and divide all constraints by $$x_2$$. This is allowed, as $$x_2 > 0$$. We get the equivalent problem: \begin{align}\min&\quad x_1/x_2\\\text{s.t.}&\quad A(x/x_2) \leq b(1/x_2)\\&\quad x > 0.\end{align}

It is straightforward to show that $$x > 0 \iff (x/x_2) > 0 \textrm{ and } (1/x_2) > 0,$$ which gives the equivalent problem: \begin{align}\min&\quad x_1/x_2\\\text{s.t.}&\quad A(x/x_2) \leq b(1/x_2)\\&\quad (x/x_2) > 0\\&\quad (1/x_2) > 0.\end{align}

Next, we will substitute $$y=x/x_2$$ and $$t = 1/x_2$$ to obtain a linear program. We do have to be careful that we only allow the variables $$y$$ and $$t$$ to take on values for which a corresponding $$x$$ exists.

For a feasible $$y$$ and $$t$$, we immediately have that $$x_2 = 1/t$$ is feasible. The value $$y_i$$ for $$i\neq 2$$ represents $$x_i/x_2$$. Because we already know the value for $$x_2$$, we have that $$x_i = y_i x_2 = y_i/t$$. The value $$y_2$$ represents $$x_2/x_2 = 1$$. Hence, we will have to enforce that $$y_2 = 1$$, or the solution cannot be translated back to the $$x$$ variables.

It follows that the original problem can be solved by solving: \begin{align}\min&\quad y_1\\\text{s.t.}&\quad Ay \leq bt\\&\quad y_2 = 1\\&\quad y > 0\\&\quad t > 0,\end{align} and taking $$x = y/t$$ (which includes $$x_2 = y_2/t = 1/t$$).

The linear program above is not standard, in the sense that you have strict inequality constraints. More about this can be found in this OR.SE question.

I think that you have choose a good way to solve this problem. In a problem with real variables and nonlinear optimization, the model that you can use are the Karush-Kuhn-Tucker conditions. This algorithm give you the necessary and sufficient conditions for an optimal solution. I would use the following strategy:

1) Perform the variable change from $$x=(x_1, x_2)$$ to $$z=(z_1, z_2)$$.

2) Use the Karush-Kuhn-Tucker conditions to find a solution.