How to write it in CVX acceptable/equivalent form?


#1

How can I rewrite the objective function in CVX so that it accepts it

Maximize $$\sum_{t=1}^{T}w_tc_t{\mathrm{log}_2}(1+p_th_t)$$

Here c_t\in{0,1} are binary variables, p_t\ge0 are nonnegative variables.

w_t>0 and h_t>0 are constants.

Please suggest me some efficient linearization or convexification solutions…


(Mark L. Stone) #2

Are you trying to maximize this? Note that if c_t were constants, then this would be a concave function of the p_t. One option if T is small enough is brute force enumeration of all possible values of the c_t and solving 2^T separate optimization problems, treating c_t as constants. Pick the best.


(Mark L. Stone) #3

If you’re trying to minimize this, then I think you’ll need to accept that this is (highly) non-convex and proceed accordingly. if you’re trying to maximize, someone may have a better suggestion for using CVX than my brute force, but even then, another tool might be the way to go.


(Mark L. Stone) #4

Maybe fewer than 2^T brute force optimization problems depending on any constraints you might have on the c_t.


(Michael C. Grant) #5

I have an idea here, but I do have to know if you intend to minimize or maximize this. If you intend to minimize, there is nothing to be done. Note that c_t\log_2(1+p_th_t)=\log_2(1+p_tc_th_t) (try it for c_t=0 and c_t=1!)


(Mark L. Stone) #6

@mcg, while the equality is true, doesn’t that leave an indefinite product of optimization variables inside the log on the right hand side, and still therefore not Mixed Integer DCP compliant?


(Michael C. Grant) #7

It does, but it’s one step closer to a compliant MIDCP solution.


(Michael C. Grant) #8

See this: How to express this objective function in CVX


(Mark L. Stone) #9

Stupid me. I forgot about geo_mean, which is just the ticket here. Thanks.


(Mark L. Stone) #10

Is this a maximum likelihood problem? If so, this illustrates that for conic optimization, it may be better not taking the log and converting the product in the objective to a sum, since the way to get it into CVX is to undo this log transformation, which should not have been done in the first place


#11

@Mark L. Stone, Thanks for your comments. I want to maximise it…


(Mark L. Stone) #12

Look at the link in mcg’s comment above. Apply that approach to your problem.


(Mark L. Stone) #13

As described over in https://www.or-exchange.org/questions/11431/how-to-linearize-this-optimization-problem , you’ll need to change the geo_mean argument to w.*q , where w is a vector of w_t. I am assuming you have other constraint(s), such as upper bound, on the p_t.


(Michael C. Grant) #14

OK, it’s good news that you want to maximize it. So here’s what you do. You need to define some sort of maximum for p_t, let’s call it P. Make it large enough so that it doesn’t really change your problem, but do make it as small as possible for numerical reasons.

Because c_t is binary, we have
$$c_t\log(1+h_tp_t) = \log(1+c_th_tp_t) = \log(1+h_t\min{Pc_t,p_t})$$
So your problem becomes
$$\text{maximize} ~ \sum_{t=1}^T w_t \log(1+h_t\min{Pc_t,p_t})$$
or, in CVX,

maximize( sum( w .* log(1 + h .* min(P*c, p) ) ) )

But you don’t want to stop there, because frankly CVX doesn’t work very well with logarithms. However, thos problem is equivalent to a weighted geometric mean:

maximize( geo_mean( 1 + h .* min(P*c, p), 1, w ) )

#15

@mcg, Thanks for your answer. However, I am getting the following error: Error using maximize (line 16)
Too many input arguments.

Error in TEST_Program (line 39)
maximize( geo_mean( 1 + h_new .* min(P_up.*c, p) ), 1, W )


(Mark L. Stone) #16

There is a typo in mcg’s answer, which is also on your line 39. The double right parenthesis should be single, and the last right parenthesis should be double.


(Michael C. Grant) #17

Yes, that’s right. Sorry. I fixed it.


#18

@Mark L. Stone, @mcg:I forgot to tell you that I had tried this version before @mcg fixed it. The error I was getting was: Error using cvx/geo_mean (line 26)
Third argument must be a vector of length 1

Error in TEST_Program (line 39)
maximize( geo_mean( 1 + h_new .* min(P_up*c, p), 1, W ) )


#19

@mcg, the logarithm approach solves the problem but gives : Status: Unbounded
Optimal value (cvx_optval): +Inf


(Michael C. Grant) #20

I probably won’t be able to help further. There is a reason we tell people to avoid logarithms in CVX.