# How to transform this problem with logarithmic objective function into an approximated convex optimization problem?

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)$$

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

## 1 Answer

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.

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