I have a mixed integer programing problem as below
\underset{{\bf w}_k }{\max}\sum_{k=1}^K x_k\alpha_k \log_2(1+\gamma_k)
subject to
\sum_{k=1}^K x_k||{\bf w}_k||^2_2\le P
\sum_{k=1}^Kx_k=L
x_k\in\{0,1\}
where,
\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. We can store {\bf h}_k in \bf H as {\bf H}\in\mathbb{C}^{K\times N}=[{\bf h}_1; {\bf h}_2;\cdots; {\bf h}_K]
In this problem, {\bf w_k}\in\mathbb{C}^{N\times1},k=1,2,\cdots, K and x_k,k=1,2,\cdots,K are optimization variables. Similarly, {\bf W}\in\mathbb{C}^{N\times K}=[{\bf w}_1, {\bf w}_2,\cdots, {\bf w}_K]
@Mark_L_Stone, Thanks a lot. I have re-written my problem as a binary integer programming problem. Is there a way to reformulate the objective by exploiting binary variable? And, also how we can deal the first constraint?
For the objective, if there were no alpha’s, we could have transformed the summation into a multiplication.
Perhaps you can show what you now have, and what you still need to do to get a correct formulation, and what you would like to do to get a more efficient implementation.
@Mark_L_Stone, Do you think that the mixed integer problem that I have now is a correct formulation of the main scheduling problem?
Change
variables x(K) binary;
to
variable x(K) binary;
because CVX thinks you are trying to declare binary as a variable in addition to x(k). CVX produces an error message which should make this clear.
You haven’t shown us the formula for OBJ .
After x is declared, its only other appearance in what you show of the program is the constraint sum(x)==L. I presume x comes into play in some way in OBJ, but you don’t show us OBJ.
@Mark_L_Stone, Thanks a lot! You know that the objective a nonlinear. I am in search of some tricks to linearize it. Note that the first constraint is also non-linear. I am thinking of linearizing it using “if” constraint. I think the linearization of the objective is very critical.
Per my answer in your other thread Is this linearization process (of if constraint) correct?, Section 2,8 of “FICO Xpress Optimization Suite MIP formulations and linearizationsQuick reference” https://www.artelys.com/uploads/pdfs/Xpress/mipformref-1.pdf .shows how to lineraize the product of a binary variable and a continuous variable.
@Mark_L_Stone, thanks for the references. I used this technique for some of my other tasks.
You mean we cannot linearize it with “if” constraints I employed!! or the linearization equations I adopted are not correct?
CVX does not allow you to use
if {cvx_expression}
Some modeling systems allow this, but CVX does not.
So use the approach provided in the linked documents. Or any other approach which is in compliance with CVX’s rules.
@Mark_L_Stone. Thanks a lot! Okay, I will use what you are suggesting. Just from my curiosity, if you see the linearization, we do not have the expression
`if {cvx_expression}`
We just have some linear equations!
Anyway, I will use the method you proposed.
I now need your support on the objective function. Could you please suggest me some tricks to linearize it.
For binary * continuous_variable_cvx_expression, use the technique in Section 2.6 in which continuous_variable_cvx_expression takes the role of continuous variable x.
@Mark_L_Stone, no, its section 2.8!
Yes, I made a typo.
But now you know how to handle “logical or”
@Mark_L_Stone,
For the abovementioned linearization, I have the following equations:
for k=1:K
NV=power(norm(w(:,k)),2);
Z(k)<=x(k);
Z(k)>=0;
Z(k)<=NV;
Z(k)>=NV-(1-x(k));
end
sum(Z)<=P;
Z(k)<=NV is giving error.
That is because NV is convex. Therefore it is not allowed to be on the RHS of <= constraint.
http://cvxr.com/cvx/doc/basics.html#constraints
The following constraint types are supported in CVX:
Equality == constraints, where both the left- and right-hand sides are affine expressions.
Less-than <= inequality constraints, where the left-hand expression is convex, and the right-hand expression is concave.
Greater-than >= constraints, where the left-hand expression is concave, and the right-hand expression is convex.