Wish List: Allow Limited DCP Non-Compliance as Front End for Non-Convex Solvers

I appreciate your willingness to express your wish thoroughly and eloquently.

But as you have correctly predicted, I am going to tell you that it is simply not feasible, at least for CVX. I would encourage you to check out YALMIP. Johan Löfberg, the developer of YALMIP, has said that I’m the “disciplined” guy, and he’s the “undisciplined” guy. He has indeed taken efforts to support a wider variety of models. A lot of people swear by YALMIP; indeed, CVX was inspired in part by YALMIP, so I’m a fan too. But the complexities required to support the wider variety of models are simply not something that I can afford the time to take on.

Looking at the bigger picture, it is certainly possible for someone to build a system that “handles”, in some sense, a wider variety of models than CVX or even YALMIP. But I cannot think of a single piece of the essential CVX code that could be re-used in such an effort. CVX was built for the ground up for DCPs, and it informs the design throughout. So even if I personally made the decision to move forward with an effort to extend support for nonconvex problems, what I would be moving forward with is an entirely new system.

Sorry, because of the limitation of number of replies to one topic, i can only give my reply under this topic.

The specific error message is as follows:

The function’vec’ corresponding to the input parameter of type’double’ is not defined.
error cvxprob/solve (line 250)
Anew2 = Anew * diag(sparse(vec(amult(orow,:))));

error cvx_end (line 88)
solve( prob );

error TDMA_solvedby_cvx (line 110)
cvx_end

After i type “which -all vec”,there is:

D:\Program Files\MATLAB\R2016b\cvx-w64 (1)\cvx\functions@cvx\vec.m % cvx method
D:\Program Files\MATLAB\R2016b\toolbox\yalmip-master@sdpvar\vec.m % sdpvar method
D:\Program Files\MATLAB\R2016b\toolbox\yalmip-master\extras@ndsdpvar\vec.m % ndsdpvar method

Try re-downloading CVX 2.2, and installing it. i

If that doesn’t resolve matters,

There should be a vec.m under sedumi in the CVX installation. Do you have a sedumi directory under D:\Program Files\MATLAB\R2016b\cvx-w64 ?
Try copying that file to a directory somewhere before CVX in yout MATLAB path.

================

Perhaps the forum software won’t let you post another reply at Cannot perform the operation: {concave} ./ {real affine} because you’re a new poster? It let me (I then deleted the test post).

Okay, I will try it later, although I reinstalled CVX two days ago.
Yes, because I am a new user, i can’t reply more than three items under the same topic.
Thank you very much, I may have to disturb you if I encounter any problems later, really thanks!

Hello, sorry to disturb you again. Yesterday’s problems have all been resolved, and new problems have emerged.
Could you please help me to see if there is any possibility that this optimization problem can be modified? Obviously an error will be reported when calculating l.
Part of the program code is as follows ,

J=0;
cvx_begin

variable p(K,N+1,M) ;
variable rou(K,N+1,M) binary;
expression l(K,N+1,M);
l=BnT(1/2)*rou.*log(1+p.*alpha_eq)/log(2);
J=sum(sum(sum(rou.*p.T)));%energy consumption in offloading
J=J+gamma_c
(D-sum(sum(l,3),2)).c.(f.^2);%energy consumption in local computing
minimize(J)
subject to
sum(sum(rou,1),2)<=1;
sum(sum(sum§))<=P_sum;
p>=0;
0<=sum(sum(l,3),2)<=D;

cvx_end

Many thanks !

That doesn’t look convex to me.

Well ,thank you very much~

Dear Mark, could you give me any advice about the Lagrangian duality method? Actually, I tried to use the Lagrangian dual method to solve this problem, but the Lagrangian multiplier did not converge. I want to know what might be wrong…

Now that I’m looking at your code again, i noticed that tou is binary. Therefore, I and J can be linearized as the product of binary variable and continuous variable per section 2.8 of https://www.fico.com/en/resource-access/download/3217 . The linearized version can be entered in CVX.

Sorry, I don’t know why I can’t click on the link you provide. Maybe because I don’t have enough knowledge about the conversion of non-convex to convex problems, could you say more in detail?Thanks

Try this if the other link doesn’t work for you.

If you need further help on how to do the linearization, i refer you to or.stackexchange.com , because that is rather peripheral to the CVX forum.

Hello, I have adopted your suggestion. I have linearized the relevant constraints, but there is a new error as follows. Do you think this constraint can be adjusted to make it a convex form that can be accepted by cvx?

cvx_begin
variables p(K,N+1,M) z(K,N+1,M) ;
variable rou(K,N+1,M) binary;
expressions l(K,N+1,M) l_k(K,1);
l=BnT(1/2)log(1+z.alpha_eq)/log(2);
l_k=sum(sum(l,3),2);%每个用户的卸载总量
J_off=sum(sum(sum(z
T)));%卸载过程的能耗
J_local=sum(gamma_c.
(D-l_k).c.(f.^2));%本地计算的能耗
J=J_local+J_off;
minimize(J)
subject to
sum(sum(rou,1),2)<=1;%对每一个子载波来说,最多只能被一个用户和中继使用
% sum(sum(sum(rou.*p)))<=P_max;
p>=0;
l_min<=l_k<=D;
z>=0;
z<=p;
z<=p-(1-x)*P_max;

the error message as follows,

error in cvxprob/newcnstr (line 192)
Disciplined convex programming error:
Invalid constraint: {concave} <= {real constant}

error <= (line 21)
b = newcnstr( evalin( ‘caller’, ‘cvx_problem’, ‘[]’ ), x, y, ‘<=’ );

error OFDMA_solvedby_cvx (line 52)
l_min<=l_k<=D;

Sorry about that, I guess I was too tired when I posted that it could be linearized. Indeed, the linearization will not work due to requiring a non-convex inequality.

You may be able to use YALMIP, which allows non-convex problems.

Hello, I feel I am a little confused about the concepts of convex optimization and linear programming and nonlinear programming. Could you tell me briefly about the relationship between them? I can’t understand why a optimization problems with discrete variables can also be solved by cvx? I think if an optimization problem has discrete variables, then it must be a non-convex problem, right?
Thanks very much.

CVX can handle problems whose integer relaxation satisfy its DCP rules. If integer-constrained, these are indeed non-convex. Indeed, Mixed-Integer Linear Programming problems (MILP) are non-convex, but often referred to as linear.

Hi,Mark
I’m facing another problem now.I turned my original problem into a convex form and wanted to solve it with cvx, but the process of solving it really took a long time, I don’t know why, I don’t know how long it will take to get the result, and I’m not sure I’ll get the right result when it’s finished. Here I have M=32, N=1
the part of cold as follows,
cvx_begin
cvx_solver mosek
cvx_expert true %不让warning信息输出在屏幕上
variables E(K,N+1,M) l(K,N+1,M);
variable rou(K,N+1,M) binary;
% expression midifier_1(K,1);
expression l_k(K,1);
% l_k=zeros(K,N+1,M);
for k=1:K
for n=1:N+1
for m=1:M
J=J+E(k,n,m)*T;
l_k(k)=l_k(k)+l(k,n,m);
end
end
J=J+pow_abs((R(k)-l_k(k))*c(k),3)*pow_p(T,-2);
end

minimize(J)

subject to

sum(sum(rou,1),2)<=1;%对每一个子载波来说,最多只能被一个用户和中继使用
sum(sum(sum(E)))<=P_max;
E>=0;
l>=0;
(llog(2)/(BnT))<=-rel_entr(rou,(rou+E.alpha_eq));
(R-l_k)<=(T
f_max(k)/c(k));
l_k<=R;
l_k>=0;

cvx_end

could you give me any advice?many thanks!

Please start a new thread. Unless you provide all the input data, or at least as much as the solver and CVX output as you can manage to get, there may not be much help that can be provided.

I don’t quite understand. You mean it’s impossible to judge the complexity of the solution just by looking at my optimization problem, right? How long does the cvx solve have a lot to do with the value of the input parameters I give? Would it be serious to see the speed of solving if there were binary variables?
really thanks

The forum readers don’t even know the size of the problem because you haven’t provided the values of the array dimensions

Binary variables can make worst case execution time much worse than just continuous variables…

Hello, I have encountered a new problem again. Now I have simplified my original optimization problem, but I don’t understand why the value of K changes slightly, sometimes it is solvable, sometimes it prompts “”, and sometimes it prompts. I am really anxious, how can I get a stable solution? could you give me some suggestions, thank you very much!

%NEWMODEL
T=0.01;

K=6;
N=2;
M=16;
Bn=180000;
R=21e4+1e4rand(K,1);%随机产生每个用户的数据量
L=zeros(K,N,M);
L(:,1:N,:)=TBn;
L(:,N+1,:)=T
Bn/2;
[SNR_USV_BS,SNR_DF]=Multirelay_OFDMA_channelmodel_byhh(K,N,M,Bn);

alpha_eq=zeros(K,N+1,M);
for k=1:K
for n=1:N
for m=1:M
alpha_eq(k,n,m)=SNR_DF(k,n,m);
end
end
end
for k=1:K
for m=1:M
alpha_eq(k,N+1,m)=SNR_USV_BS(k,m);%表示选择直接通信所对应的信噪比
end
end

J=0;
cvx_begin
cvx_solver mosek
cvx_expert true %
variables E(K,N+1,M);
variable rou(K,N+1,M) binary;

J=sum(sum(sum(E)));
% for k=1:K

minimize(J)
subject to
sum(sum(rou,1),2)<=1;
R(k)<=sum(sum(L.*(-rel_entr(rou,(rou+E.*alpha_eq))),2),3);
E>=0;

cvx_end

p=zeros(K,N,M);
for k=1:K
for n=1:N+1
for m=1:M
if rou(k,n,m)==0
p(k,n,m)=0;
else
p(k,n,m)=E(k,n,m);
end
end
end
end