How can this objective can be linearized?


(Dipak Narayanan) #1

The objective function I am dealing is
\underset{{\bf w}_k,x_k }{\max}\sum_{k=1}^K x_k \log_2(1+\gamma_k)

Here,
x_k, k=1,2,\cdots,K are binary variables

\gamma_k, k=1,2,\cdots,K are also functions of other optimization variables.

\gamma_k=\frac{|{\bf h}_k{\bf w}_k|^2}{\sigma^2+\sum_{i=1,i\neq k}^K |{\bf h}_i{\bf w}_i|^2}.

The vectors {\bf h_k}\in\mathbb{C}^{1\times N}, k=1,2,\cdots, K are known.

How can I linearize them?

\textbf{Some Tricks}

\underset{{\bf w}_k }{\max}\sum_{k=1}^K x_k \log_2(1+\gamma_k)

=\underset{{\bf w}_k }{\max}\sum_{k=1}^K \log_2(1+\gamma_k)^{x_k}

=\underset{{\bf w}_k }{\max}\prod_{k=1}^K(1+\gamma_k)^{x_k}

=\underset{{\bf w}_k }{\max}\prod_{k=1}^K(1+\gamma_k{x_k})


(Mark L. Stone) #2

You haven’t told what particular function of other optimization variables \gamma_k is. Leaving aside x_k, the remainder of the objective function may not necessarily even be concave (needed so that maximizing it is “convex”).


(Dipak Narayanan) #3

@Mark_L_Stone Edited. So, there is no means/tricks to linearize it?


(Mark L. Stone) #4

First show that the objective function, not including the binary variable (i.e., pretend it equals 1), is concave. otherwise there is no hope of doing anything with CVX.


(Dipak Narayanan) #5

@Mark_L_Stone, Or is there any hope if \alpha's are not there!! Edited my question.


(Mark L. Stone) #6

No, presuming I am correctly interpreting what your objective function is supposed to be. Please tell me if i didn’t get this correct.

Take a simple case, K = 2, and each w is a real scalar. Set \sigma^2 = 1.
Then the objective function = log2(1+w_1^2/(1+w_2^2))+log2(1+w_2^2/(1+w_1^2))
The Hessian of the objective function at w_1 = w_2 = 1 has one negative eigenvalue and one positive eigenvalue, and therefore is indefinite. So the objective function is neither concave nor convex,.

Throwing in \alpha's and binary variables as additional multiplicative factors cannot improve matters with regard to the objective function being neither concave nor convex. So CVX can not be used for this problem. if you figure out how to do so and are under 40, I will recommend you for the Fields medal.


(Dipak Narayanan) #7

So, the only way to solve it optimally is by exhaustive search! For small system, this might be okay. In fact, I am no way looking for the optimal solution. Some suboptimal solutions are very okay and that is what I am looking for!


(Mark L. Stone) #8

If you just want suboptimal solutions, try using a mixed-integer nonlinear optimizer such as KNITRO. If you want to find a globally optimal solution, you can ntry a global optimizer such as BARON. Global optimizers don;t have to do a brute force exhaustive search, they can be clover about chopping off large portions of the feasible region while guaranteeing they have not chopped off the global optimum.

Further discussion of how to proceed along these lines is out of scope of this forum.For now, https://scicomp.stackexchange.com/ may be your best bet for further guidance. Perhaps https://area51.stackexchange.com/proposals/121892/operations-research-and-analytics if and when that board gets up and running.