How to formulate this expression in CVX?

  I am new in CVX, here is my optimization problem. How to express it in CVX?

K=64, N=4, {{P}_{\rm{total}}}=10, \{w_1=2,w_2=3,w_3=100\}

{{r}_{kn}}({{p}_{kn}})={\rm{log}}_2(1+{{p}_{kn}}x)

C:=\left\{ \left( k,n \right)|{{p}_{kn}}=0 \right\}

maximize \sum{{{w}_{k}}{{r}_{kn}}({{p}_{kn}})}

subject to. 1. $\hspace{3mm}$${{p}_{kn}}\ge 0,\hspace{3mm}\left( \forall k,n \right)$

\hspace{30mm}2. \sum{{{p}_{kn}}\le {{P}_{\rm{total}}}}

\hspace{30mm}R_1=\sum{{{c}_{1n}}{{p}_{1n}}\left( {{r}_{1n}} \right)}

\hspace{30mm}R_2=\sum{{{c}_{2n}}{{p}_{2n}}\left( {{r}_{2n}} \right)}

\hspace{30mm}3. \frac{R_1}{R_2}\le \frac{w_1}{w_2}

Please note that p_{kn} are the optimization variables.

I’d say the most challenging part is representing the C “filter”. This is probably what I’d do:

C = C~=0; % make C a logical array
Wkn = W(:,ones(1,N)) % make W a k x n array
cvx_begin
    variable p(K,N)
    maximize (W(C).*log(1+p(C)*x)/log(2))
    subject to
        p >= 0
        sum(P(C)) <= Ptotal
cvx_end

This is of the top of my head; I haven’t tried it. And please note the serious warning about the use of logarithms in CVX. Unfortunately, it is possible that this problem will fail to converge.

Having said that, the values of p_{kn} for which C_{kn}=0 are not really involved in the problem at all. It’s clear that their optimal value must be zero; otherwise, they would take away power that could be allocated to the C_{kn}=1 terms. I would consider changing p >= 0 to p(C) >= 0 in order to reduce the problem size a bit further. Those values of p left unconstrained will be set to zero by CVX by default.

EDIT: As an alternative to the use of logarithms, you might try this objective, a weighted geometric mean:

maximize(geo_mean(1+p(C)*x,[],W(C)))

This is actually mathematically equivalent to your model, although to get the original objective value you’ll have to recompute it from the value of p that comes out. This avoids the heuristic approach required for logarithms. To be clear, it also employs a different approximation approach, but one that is much more benign.

@mcg: Thanks a lot!

I have an other possible mathematical model for the problem I am considering, It is not actually the same problem as the above one.

{{r}_{kn}}({{p}_{kn}})={\rm{log}}_2(1+{{p}_{kn}}{{h}_{kn}})

 maximize v

w_{k}^{lower}v\le \sum\limits_{n=1}^{N}{{{c}_{kn}}{{r}_{kn}}\left( {{p}_{kn}} \right)\le }w_{k}^{upper}v

That’s right, except you forgot the exponents inside the product.

@mcg: I have an other possible mathematical model for the problem I am considering, It is not actually the same problem as the above one.

Unless all the hkn’s are zero, the right-side inequality constraint of your “other” possible mathematical model is not convex, and so it is not a convex optimization problem.

I understand, but that doesn’t mean you should be deleting the old question. This Q&A format is for the benefit of all readers—so if someone else has a similar type of problem, they benefit from this.

My comment above was made prior to your most recent edit. The version of your “other” problem I was commenting on explicitly stated rkn = log2(1+pkn * hkn); hkn are known. If rkn has some other form, that comment might not apply.

In your latest formulation, is v the only optimization variable, and everything else is input data? If so, it’s not a very interesting problem.If pkn’s are optimization variables (then you’re missing something), one side or the other of the inequality constraints is not convex unless all ckn*hkn=0.

@Mark L. Stone Thanks a lot. In this problem p_kn are also optimization variables.

@mcg: Thanks. However, what will be the computational complexities of the two methods you mentioned?

@mcg: However, what will be the computational complexities of the two methods you mentioned?

I don’t have a clue. I’ll be honest, I’m very pragmatic about convex optimization. I don’t care about theoretical complexity in the least, until it’s time for me to scale up a very specific problem.

@mcg: Thanks for your support. How can I incorporate constraint 3 in your proposed solution. I am always getting an error! Is there any equivalent mathematical model for this constraint?

You keep changing your model, with no indication to the reader that edits have been made—so many of our comments are now devoid of context. Please stop doing this, or I will be forced to close this question altogether, and you will not be permitted to post a new one.

As the question stands now, your model is nonconvex, and CVX cannot solve it. It is very likely that the nonconvexity is inherent in the model, and not something that can be reformulated away, which means that CVX will not be able to solve it under any reformulation.

Similar to my Nov 15 and 17 comments below, constraint 3 looks problematic. You can rewrite it as w2R1 - w1R2 <= 0, but that’s a concave minus a convex, so not DCP-compliant, and not convex except for trivial parameter values.

@Mark L. Stone: Thanks

I am interested on the original posted problem , but i can not find or follow the discussions !!