When I use CVX to solve this function f(x,y,z)=x*z*log2(1+y/z))，the algorithm does not converge

[Yallenliang]

Hi there!

I am dealing with an optimization problem that I intend to solve it using the Block Coordinate Descent (BCD) method. Since I set the random initial value for variables when I run the code, the code doesn’t converge.

Primitive function like this f(x,y,z)=xzlog2(1+y/z)), I wonder if there is a CVX grammar writing problem or whether this function can not be solved by an iterative algorithm. I appreciate any help. Thank you in advance. Here is my code:

Iteration = 80;
P_op = randi([170,190],K,N);
B_op = randi([810^5,910^5],K,N);
c_op = 1;

lambda_op = zeros(K,N); % 0-1

for i = 2:Iteration

% ------Optimize x，that is，it is represent by lambda(K,N)----------------------------------
cvx_begin %quiet
%cvx_solver sedumi
variable lambda(K,N) nonnegative; %
expression B_width(1,K);
expression P_ower(1,K);
expression B_sum(1,N);
expression P_sum(1,N);
expression Capacity_op(K,1,N,Cir);
expression Capacity_op_th(1,K); %
expression Capacity_lambda(1,Iteration);
expression Capacity_op_total1(1,length(time_slot));
expression obj_1_1;

    time_slot = 0:1:N;

        for n = 1:(length(time_slot)-1)
           for k = 1:K
               Capacity_op(k,1,n,c_op) = Simutime/N*lambda(k,n)*B_op(k,n)/log(2)*log(1+(Beta0*P_op(k,n)/(N0 * B_op(k,n)*dis_uau_act(k,:,n,c_op)^2)));  % the Capicity
               
               B_width(k) = lambda(k,n)*B_op(k,n);
               P_ower(k) = lambda(k,n)*P_op(k,n);
           end 
           B_sum(n) = sum(B_width);
           P_sum(n) = sum(P_ower);
        end

    for n = 1:(length(time_slot)-1)  
           Capacity_op_total1(n) = sum(Capacity_op(:,1,n,c_op)); % the capicity of every slots 
    end
    
    for k = 1:K
        Capacity_op_th(k) = sum(Capacity_op(k,1,:,c_op));
    end
    obj_1_1 = 1/Simutime*sum(Capacity_op_total1);

    maximize(obj_1_1)
    subject to
    for n = 1:N
        for k = 1:K
           0 <= lambda(k,n) <= 1;
           Capacity_op_th(k) >= 10^7;
        end
        B_sum(n) <= B_max;
        P_sum(n) <= P_max;
    end
    cvx_end
    lambda_op = roundn(lambda,-4);

% ------Optimize y, that is, it is represent by P_op1(K,N)----------------------------------
cvx_begin %quiet %
variable P_op1(K,N) nonnegative; %
expression P_ower1(1,K);
expression P_sum1(1,N);
expression Capacity_op2(K,1,N,Cir);
expression Capacity_op_th2(1,K);
expression Capacity_P(1,Iteration);
expression Capacity_op_total2(1,length(time_slot));
expression obj_1_2;
time_slot = 0:1:N;

     for n = 1:(length(time_slot)-1)
        for k = 1:K
            Capacity_op2(k,1,n,c_op) = Simutime/N*lambda_op(k,n)*B_op(k,n)/log(2)*log(1+(Beta0*P_op1(k,n)/(N0*B_op(k,n)*dis_uau_act(k,:,n,c_op)^2)));
            P_ower1(k) = lambda_op(k,n)*P_op1(k,n);
       end 
        P_sum1(n) = sum(P_ower1);
     end

     for n = 1:(length(time_slot)-1)  
            Capacity_op_total2(n) = sum(Capacity_op2(:,1,n,c_op));
     end

     obj_1_2 = 1/Simutime*sum(Capacity_op_total2);
     
     for k = 1:K
         Capacity_op_th2(k) = sum(Capacity_op2(k,1,:,c_op));
     end 
     
     maximize (obj_1_2)
     subject to
     for n = 1:N
         for k = 1:K
           0 <= P_op1(k,n) <= P_max;
            Capacity_op_th2(k) >= 10^7; 
         end
         P_sum1(n) <= P_max;
     end
     cvx_end  
     
     P_op = roundn(P_op1,-4);

% ------Optimize z, that is, it is represent by B_op1(K,N)----------------------------------
cvx_begin %quiet
variable B_op1(K,N) nonnegative; %
expression B_width1(1,K);
expression B_sum1(1,N);
expression Capacity_op3(K,1,N,Cir);
expression Capacity_op_th3(1,K);
expression Capacity_B(1,Iteration);
expression Capacity_op_total3(1,length(time_slot));
expression obj_1_3;

    time_slot = 0:1:N;

    for n = 1:(length(time_slot)-1)
       for k = 1:K
           % rel_entr
           Capacity_op3(k,1,n,c_op) = Simutime/N*lambda_op(k,n)/log(2)...
               *(-rel_entr(B_op1(k,n),B_op1(k,n)+(Beta0*P_op(k,n)/(N0*dis_uau_act(k,:,n,c_op)^2))));
           B_width1(k) = lambda_op(k,n)*B_op1(k,n);
       end 
       B_sum1(n) = sum(B_width1);
    end

    for n = 1:(length(time_slot)-1)  
           Capacity_op_total3(n) = sum(Capacity_op3(:,1,n,c_op));
    end
    Capacity_B(i) = 1/Simutime*sum(Capacity_op_total3);
    obj_1_3 = 1/Simutime*sum(Capacity_op_total3);
    
    for k = 1:K
        Capacity_op_th3(k) = sum(Capacity_op3(k,1,:,c_op));
    end 
    
    maximize (obj_1_3)
    subject to   
    for n = 1:N
        for k = 1:K
           0 < B_op1(k,n) <= B_max;
           Capacity_op_th3(k) >= 10^7;
        end
        B_sum1(n)<= B_max;
    end
    cvx_end
    B_op = roundn(B_op1,-4);

end

[Yallenliang]

This is the iterative result of f(x,z)=xzlog2(1+1/z)) when y is regarded as a constant, and it obviously does not converge after 100 iterations.

[Yallenliang]

This is the iterative result of f(x,y)=x*log2(1+y) when z is regarded as a constant. It is obvious that it converges after 3 iterations.

[Yallenliang]

This is the iterative result of f(x,y,z)=xzlog2(1+y/z), and it obviously does not converge after 100 iterations. I would appreciate it if the question could be answered.

[Mark_L_Stone]

Diagnosis of lack of convergence of an iterative algorithm calling CVX to solve subproblems to solve a non-convex optimization problem is out of scope of this forum. Do you have a proof that your algorithm will converge to something from any starting point? If not, you take your chances and maybe get lucky.

[jackfsuia (Jack)]

Even you proved it converge theoretically, small fluctuations can happened with so many iterations, due to the numerical issues of solvers. It may not be monotone increasing/decreasing despite the use of BCD method.

[Yallenliang]

Thank you, Jack. Do you mean the numerical results of the solver are unstable because of too many iterations? So how to solve this problem or should I use a low-complexity algorithm to solve it?

[jackfsuia (Jack)]

Sorry I dont know. Your first picture looks like a convergence although it is not 100% theoretically right. As a outsider of optimization, I just accept whatever result the solver gives me, it might not be perfect.

[Mark_L_Stone]

If the algorithm converges to something, it might not necessarily converge to a local optimum of the original non-convex problem, let alone a global optimum.

[Yallenliang]

Hi, Mark. Thank you for the previous answer. I use the log function and the-rel_entr function to solve the problem, but I wonder why there is a precision deviation like figure 2 after the calculated value on the right side of the equation is assigned to the left. How can I eliminate this deviation?

[Mark_L_Stone]

I’m not sure what exactly you are showing.
-rel_entr(1,number) should be the same as log(number) to within roundoff error. What is the difference when the exact same argument is provided to both?

[Yallenliang]

After using the -rel_entr(1, number), the two sides of the equal sign are not equal after the assignment. Does rel_entr () have any requirements for numeric order of magnitude?

[jackfsuia (Jack)]

Capacity_op is your expression holder,according to the following

@Yallenliang

expression Capacity_op(K,1,N,Cir);

so I think some of the following words might help:

After the cvx finished the optimization, the expression values are not equal to the original constraint values

In order to reliably have the optimal values of expressions after CVX completes, they must be reconstructed starting from CVX variable values. That is due to a design decision in CVX. CVX could have been designed to automatically do this, but it does not. However, the correct values of the expressions are used internally in performing the optimization.