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$
    – KGM
    Commented Mar 11, 2021 at 0:28
  • $\begingroup$ in light of Johan Löfberg 's answer, I have deleted my answer and previous comments. $\endgroup$ Commented Mar 12, 2021 at 12:46

1 Answer 1

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$
    – KGM
    Commented Mar 12, 2021 at 11:53
  • $\begingroup$ Very good. I have deleted my answer. $\endgroup$ Commented Mar 12, 2021 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$ Commented Mar 12, 2021 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.