5
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.