Writing a nonconvex program as a linear program

74 Views Asked by At

I want to write the following non-convex program $\texttt{P}_1$ as a linear program (LP)

$$ \begin{align} \min_x \sum_i \frac{a_i^Tx+b_i}{c^Tx+d} \\\\ s.t. \ Ax \geq b \end{align} \tag{$\texttt{P}_1$}$$

I think that this minimization problem is equivalent to the following linear program $\texttt{P}_2$

$$ \begin{align} \min_x &\sum_i a_i^Tx+b_i -(c^Tx+d) \\\\ &s.t. \ Ax \geq b \end{align} \tag{$\texttt{P}_2$}$$

This is because in order for the fraction to be minimized the numerator should be minimized and the denominator should be maximized. However, I am unable to rigorously prove that the two programs $\texttt{P}_1$ & $\texttt{P}_2$ are equivalent. Any help will be appreciated.

1

There are 1 best solutions below

0
On BEST ANSWER

It is not Equivalent.

(1) Consider the Original Case to minimize $Y=A/C$ , where it might occur that the minimum value is $Y=1/2$
We will get the $x$ which will make the minimum $Y=1/2$ where $A=2C$

In the New Case , we want to minimize $Z=A-C$ , where it might occur that $A=C$
We will then get the $x$ which will make the minimum $Z=0$ where $A=C$ & $Y=A/C=1$ which is very far from ( & unrelated to ) the Original Case minimum

We will , naturally , not get Equivalent Solutions.

Beyond that , we can see more Differences too :

(2) In Original Case , $C$ can not be $0$. In New Case , there is no such restriction.

(3) In Original Case , the Minimum might have some restriction to be Positive. In New Case , there is no such restriction & the Minimum might go Negative too.

ADDENDUM :

User RobPratt has given a comment referring to the wiki , where "Charnes-Cooper transformation" is shown.

The Over-view is to transform $A$ to $A_t$ & transform $C$ to $C_t$ where $C_t \equiv 1$

Minimizing $A/C$ is then minimizing $A_t/C_t$ which is in turn minimizing $A_t$ with Constant $C_t$

More here :

https://onlinelibrary.wiley.com/doi/abs/10.1002/nav.3800090303

https://statisticaloddsandends.wordpress.com/2020/05/05/what-is-the-charnes-cooper-transformation/