Representing a convex optimization problem


(Salwa Mostafa) #1

I am new to this software. Can you help me write this convex optimization problem inside the convex solver. I mean how to represent it inside cvx_begin and cvx_end

min_{q_1,q_2,...,q_n} \sum^{S}_{d=1} \sum^N_{j=1} \gamma_d p_j (1- min(1,dq_j))
s.t
\sum^N_{j=1} q_j = M
0 \leq q_j \leq 1 \forall j \in [1,N]
q_j = m_j/n


(Mark L. Stone) #2

This can be entered into CVX almost exactly as written. Please read the CVX Users’ Guide http://cvxr.com/cvx/doc/ . Then fell free to ask for any specific help after you have done so.

The problem does seem a bit strange, though. Because m_j and n are not listed among the variables being optimized, q_j = m_j/n appears to completely constrain the q_j leaving no degress of freedom, i.e. rendering the optimization problem moot.


(Salwa Mostafa) #3

If I know q_j I can calculate m_j because n is constant. I have one question to check my implementation form the objective function I should write the sum as a two for loops ?


(Mark L. Stone) #4

You can use a double for loop. However, for speed of execution, it will be better to use a double sum, i.e., sum(sum( ... )) .

But as I wrote above, for this problem, there is nothing to optimize, and you will get the same argmin (optimal value of variables) no matter what the objective function is. There will either be a unique feasible solution, or the problem will be infeasible.


(Salwa Mostafa) #5

I calculated the value of \gamma_d for each d and p for each j and stored them as a vector

S = 10;
M = 50;
cvx_begin      
       variable q(N)
       for d = 1 : S
           for j = 1 : N 
              f = (gammad(d).*P(j)*(1- min(1,d*q))) 
           end
        end
       minimize (f)
       subject to
       sum(q) ==  M ;
       0 <= q <= 1;
    cvx_end

I suppose to get a vector of length N for q but it shows an error “Your objective function is not a scalar.” Can you help me ?
what I am tring to do is produce the work in this paper [https://arxiv.org/abs/1508.05753] if some thing is not clear. (https://arxiv.org/abs/1508.05753)


(Mark L. Stone) #6

f is being overwritten every time though the double for loops. And it is not a scalar.

Here is a way (not the only way) to re-write, correctly I hope, what you attempted to do. I leave it to you to determine whether this corresponds to the paper.

S = 10;   
gammad = (1:S)'; % S by 1 column vector, used for testing purposes
M = 50;
N = 100 % used for testing purposes (M must be >= M in order for the problem to be feasible)
p = ones(N,1); % for test purposes
cvx_begin
variable q(N)
minimize(sum(sum(gammad*p' - (gammad*p').*min(1, (1:S)'*q'))))
       subject to
   sum(q) ==  M ;
   0 <= q <= 1;
cvx_end

(Salwa Mostafa) #7

It still gives an error “Inner matrix dimensions must agree.” I think this is because this term min(1,d*q) d has dimention 1 by S and q has dimention 1 by N. I tried to fix it but still not working.


(Mark L. Stone) #9

I have fixed the code in the preceding post.


(Salwa Mostafa) #10

Thanks so much. I appreciate your help.


(Mark L. Stone) #11

The following line is equivalent to the corresponding line in the code I previously posted, but might be considered to be a little cleaner.

minimize(sum(sum(gammad*p'.*(ones(S,N) - min(1, (1:S)'*q')))))