I have a linear optimization problem where the cost function is $ay - bx$. The variables are $(x, y)$. However, for one of the constraints, I have $\log_2 \frac{cx}{c^2 x + c(1 - y)(1 - c)} \geq \delta$. Note that the $x$ and $y$ are discrete here. The rest of the constraints are linear. I was wondering how can I find $x$ and $y$ that minimizes the cost function?

I have tried two approaches:

  1. I have tried to expand the $\log_2$ with the Taylor series and approximate with only a linear component. But the error, in this case, is really high

  2. In the second step, I tried to check if the cost function was convex or not. But as you can see the cost function is linear in $x$, and if I try to compute the second derivative (using central difference), it will result in 0.

So, what approach should I follow?


1 Answer 1


You can eliminate $\log_2$ by taking $2$ to the power of both sides. Then you can linearize the resulting constraint by clearing the denominator, assuming it is one-signed (positive?).

  • $\begingroup$ So, $cx \geq \delta '$, wehre $\delta ' = \delta (c^2x + c(1 - c)(1 - y))$. and then simplify $\endgroup$
    – Bikas
    Oct 19, 2020 at 21:33
  • $\begingroup$ No, you should have $\ge 2^\delta$ after the first step. $\endgroup$
    – RobPratt
    Oct 19, 2020 at 21:35
  • $\begingroup$ yeah, right thanks $\endgroup$
    – Bikas
    Oct 19, 2020 at 21:36
  • $\begingroup$ How about if I have $(ex + fy) \log_2 \frac{cx}{c^2x + c(1 - c)(1 - y)} \geq \delta$? Because in that case I will have $2^{\frac{\delta}{ex + fy}}$. So it's not linear in that case $\endgroup$
    – Bikas
    Oct 19, 2020 at 22:20
  • 2
    $\begingroup$ I don't see any way to linearize your second example. $\endgroup$
    – RobPratt
    Oct 19, 2020 at 23:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .