1
$\begingroup$

I have an objective function as follows

$\underset{x_{m,n}}{\max}\hspace{1mm}\hspace{1mm}\sum_{m=1}^{M}\log_2\left(\frac{\sum_{n=1}^{N}(1-x_{m,n})\omega_{m,n}+z}{\sum_{n=1}^{N}x_{m,n}\omega_{m,n}}\right)$

Here, $x_{m,n}$ are optimization variables which are binary.

How can I transform this objective into a linear/convex function?

Thoughts:

Due to monotonicity of the logarithmic function, as well making use of logarithm rule for multiplicative terms, we can transform the problem as

$\underset{x_{m,n}, t_m,\beta_m }{\max}\hspace{1mm}\hspace{1mm}\prod_{m=1}^{M}t_m$

Consequently, the following constraints will be added to the system.

$\sum_{n=1}^{N}(1-x_{m,n})\omega_{m,n}+z\ge t_m\beta_m$

$\beta_m\ge \sum_{n=1}^{N}x_{m,n}\omega_{m,n}$

Am I doing it right?

$ \text{What are the steps forward?}$

$\bf \text{EDIT:}$ (According to Johan Löfberg's answer )

$\underset{x_{m,n}, y_{m,n},z_{m,n}}{\max}\hspace{1mm}\hspace{1mm}\sum_{m=1}^{M}\log_2\left(y_{m}\right)$

$\endgroup$
2
  • $\begingroup$ @MarkL.Stone, But we can do convex approximation, right? For example, sequential convex approximation, etc. $\endgroup$ Mar 11 at 0:28
  • $\begingroup$ in light of Johan Löfberg 's answer, I have deleted my answer and previous comments. $\endgroup$ Mar 12 at 12:46
3
$\begingroup$

Introduce a term $y_m$ to replace and lower bound the terms inside the logarithm.

Those lower bound constraints simplify to

$\sum_{n=1}^{N}(1-x_{m,n})\omega_{m,n}+z\ge y_m(\sum_{n=1}^{N}x_{m,n}\omega_{m,n})$

The only problem here are the bilinear terms $y_m x_{m,n}$. Since $x$ is binary this is linearly representable by introducing a new variable $z_{m,n}$ to replace the product and model the product via standard big-M $0 \leq z_{m,n} \leq M x_{m,n},0 \leq z_{m,n}-y_{m} \leq M (1-x_{m,n})$

At this point your constraints are linear and the objective is concave hence a mixed-integer convex program. Any mixed-integer nonlinear solver should work, but it is not only convex but exponential cone representable so the specialized solver Mosek will be applicable.

$\endgroup$
3
  • $\begingroup$ what would be the good choice for M, I mean how big this M would be? Also, where do you get $y_{m,n}$ from? Or you mean $y_{m,1}=y_{m,2}=\cdots=y_{m,N}$ $\endgroup$ Mar 12 at 11:53
  • $\begingroup$ Very good. I have deleted my answer. $\endgroup$ Mar 12 at 12:45
  • $\begingroup$ Typo on $y$. $M$ would have to be an upper bound on possible optimal $y$ which I guess would be something along the lines of $\frac{\sum \omega + z}{\min \omega}$ $\endgroup$ Mar 12 at 14:24

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.