Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
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.
My answer will be specific to your problem, but the more general transformation can be found on the linear-fractional programming Wikipedia page.
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.
