5

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?

RobPratt
  • 32,006
  • 1
  • 44
  • 84
P.T.
  • 53
  • 2
  • 5
    see https://en.wikipedia.org/wiki/Linear-fractional_programming, there is a possible reformulation, you can check if the assumptions are satisfied in your problem. – user3680510 Apr 14 '20 at 12:14

2 Answers2

4

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.

Kevin Dalmeijer
  • 6,167
  • 1
  • 17
  • 48
0

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.