Why cvx solves wrong this problem?


(John) #1

Dear All,
I have been stuck in a problem as follows:
I am going to maximize the following objective function in general form: x^2/y which is convex, so I used its lower bound to maximize, I mean I used first order Taylor series to approximate the objective function in the form of: 2x_val/y(x-x_val) - x_val^2/y/y*(y-y_val). (here x_val or y_val means that the value of last iteration t-1 must be used in this optimization t.
So, with this in mind I wrote the matlab code as follows:

% clc;
clear;

numOfUEs = 5;
numOfSBSs = 4;
numOfRBs = 10;
K1 = numOfRBs/2;
K2 = K1;
alpha = 2;
P_ULmax = 1e2;
% addpath ‘C:\cvx\functions\vec_’
% savepath
%% Defining Variables
cvx_begin
cvx_solver mosek

variable y(numOfSBSs+1,numOfUEs,K1) nonnegative;
%% Defining Channel Matrices
SBS_location = [0.1 0.1;0.1 0.3; 0.3 0.1; 0.3 0.3];
UE_location = [0.0557597145674108,0.197592856063670;0.0829642546609909,0.185015446946940;0.0638408106727841,0.0851067236893036;0.216014006493015,0.136464498512740;0.153685530284463,0.1595177896501347];

MBS_location = [.2,.2];
% h(i,j,n) channel between Tx i and Rx j in RB n
h = ones(numOfSBSs+1,numOfUEs,K2);

%% Association Phase
% y(b,m,n)=1 it means that UE m connected to BS b in UL in RB n
p_ul = P_ULmax*ones(numOfSBSs+1,numOfUEs,K2);
% cvx_precision best
for iterations = 1:10
if iterations ==1
y_val = 1/K2/(numOfSBSs+1)*ones(size(y));
else
cvx_begin
cvx_solver mosek
variable y(numOfSBSs+1,numOfUEs,K1);
end
expression sinr_ul(numOfSBSs+1,numOfUEs,K2);
for n=1:K2 % number of Resource Blocks in UL
for b=1:numOfSBSs+1
for m=1:numOfUEs
expression Interference;expression linearTerm(numOfSBSs+1,numOfUEs);
Interference = cvx(1);
Interference_val = (1);
for b_p=1:numOfSBSs+1
for m_p=1:numOfUEs
if b~=b_p && m~=m_p
% Interference = Interference + y(b_p,m_p,n)*p_ul(b_p,m_p,n)*abs(h(b,m_p,n)).^2;
linearTerm(b_p,m_p) = p_ul(b_p,m_p,n)abs(h(b,m_p,n)).^2( y(b_p,m_p,n) - (y_val(b_p,m_p,n)));
Interference_val = Interference_val + y_val(b_p,m_p,n)*p_ul(b_p,m_p,n)abs(h(b,m_p,n)).^2;
else
linearTerm(b_p,m_p) = cvx(0);
end
end
end
sinr_ul(b,m,n) = (y_val(b,m,n)^2
p_ul(b,m,n)abs(h(b,m,n)).^2/(Interference_val)) + …
2
y_val(b,m,n)p_ul(b,m,n)abs(h(b,m,n)).^2/(Interference_val)(y(b,m,n)-(y_val(b,m,n))) -…
y_val(b,m,n)^2
p_ul(b,m,n)abs(h(b,m,n)).^2/Interference_val/Interference_valsum(linearTerm(:));

            end
        end
    end

    Objective = sum(sinr_ul(:));

    maximize(Objective)
    subject to

    0 <= y <= 1;
    cvx_end
    y_val = y;
end

The analysis on the formulas in optimization says that the y matrix should be in this form:
1 1 1 1 1;0 0 0 0 0;0 0 0 0 0; 0 0 0 0 0;0 0 0 0 0;
in each value of n in y(:,:,n).
BUT, after solving this optimization I get the following answer:
1 1 1 1 1;1 1 1 1 1;1 1 1 1 1;1 1 1 1 1;1 1 1 1 1;
Actually I have checked it in matlab also, which the objective function value is greater when we put mentioned analytically derived y’s.
which also doesn’t maximize the objective function!!!
PLEASE if you find anything wrong in my code, let me know. I am debugging for almost one week and haven’t find anything.


(Mark L. Stone) #2

I haven’t looked at the details of what you’ve done, but it appears you are attempting to use unsafeguarded Sequential Linear Programming to solve a (nonlinear) concave programming problem (i.e., minimizing a concave objective subject to convex constraints). I see no reason why to expect this algorithm to necessarily converge, let alone to converge to the solution of the problem you really want to solve. Behavior of the algorithm could depend on the starting values used.

Perhaps you have just made an implementation error, which if fixed, would make everything wonderful (I’m not saying it’'s the case, just not ruling it out). But I recommend you employ a non-convex solver to solve your non-convex problem. Your “algorithm” is in effect a lousy non-convex solver, likely vastly inferior to more sophisticated good quality non-convex solvers.


(John) #3

I have tried with different initial points, it converges to the point that I mentioned.
It is not about implementation error, because I tried the objective with the values I expect, and the objective vastly increased and became greater than what cvx reported to me.
I am determined that when we start from a feasible point in successive convex approximation technique, it will converge.
I don’t know where is the problem anyway, because I checked the code many times and I see no errors in implementation.