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

Here is a wish list item, for which I will not be surprised if the answer is no, because perhaps it runs so counter to deeply ingrained ways of how CVX works under the hood, and therefore would require a complete re-do of most of CVX, nevertheless, I shall go ahead and suggest. As preface, I really like the CVX interface (leveraging on MATLAB) for the problem classes it allows, and find it much nicer than GAMS/AMPL/AIMMS and native interfaces to such solvers as BARON, and it is very nice to easily express conic and semidefinite constraints and objectives, with CVX doing the tedious, difficult, and error prone work/conversions under the hood so I don’t have to.

Let’s say I specify a model in CVX resulting in a nice convex constraint set, and perhaps I even get a convex objective. That would be fine if I wanted to minimize, but what if I wanted to maximize (or possibly both, on separate invocations so as to bound the possible range of the objective function subject to constraints)? I can do the minimize the convex function part in CVX, but then I am thrown completely into the wind to fend for myself on the non-convex variant (concave or indefinite programming), or perhaps due to some minor CVX ruleset non-compliance for what in reality is a convex problem formulation. What if CVX could interface into a non-convex solver, such as a global optimizer, for example BARON (which I believe used to support SDPs, but no longer does), or a local optimization solver (not guaranteed to find global optimum)? Ability to specify starting values would be nice for non-convex solvers and necessary for some, and adding that sounds simple enough to my innocent self, blissfully ignorant of all the under the hood doings in CVX. Of course, there might be compatibility issues with certain solvers, such as whether semidefinite constraints are supported. Perhaps a DCP or CVX ruleset relaxation flag could be be turned on at some point in a session - this would relax CVX’s normal rules to some more relaxed set, although I don’t know how relaxed, and then the model could not be sent to certain solvers.

I am prepared to accept a response that the suggestion is infeasible, violating fundamental tenets as to how CVX works, but perhaps certain limited relaxations could be allowed which would provide some benefit. Addition of integer constraints is already an example of limited allowed departure from convex program formulation, even though it was not originally supported. At a minimum, allowing semidefinite and conic constraints to be passed on to a solver in a nice enough way (not sure how well that can be done if solver doesn’t natively support, but should be better than Joe/Jane NotVeryDefinite-Pack trying to kluge it him/herself), and then allowing for limited types of non-convexities in the objective. The ability to throw in a non-convex constraint, such as nonlinear equalities, would also be nice. As a simple, but frequently occurring example, it would be nice if CVX could support in DCP relaxation mode a non-convex Quadratic Program, which several solvers can handle natively.

On a related front, it would be nice, at least for the case of DCP-compliant (CVX ruleset) problem formulations to be able to have CVX output the Lagrangian Dual problem formulation in as nice or intelligible a way as possible. Perhaps CVX works in such a way that the duals wind up being some horrid looking thing unintelligible to regular folks, so to speak. Going down the list to even less likely to be fulfilled requests, perhaps CVX could (optionally) output a Lagrangian Dual (in as nice a form as possible) for at least some subset of problems formulated in the aforementioned, hypothetical CVX ruleset relaxation mode - I can see how finding the dual (in a meaningful form allowing for dual problem to be input into a solver without much artistry being required by the user) might be harder than for convex problems, as perhaps automating “boundary case” formulation might not be straightforward. Also along similar lines, having CVX formulate the Lagrangian Dual of a non-convex problem (i.e., formulated in relaxation mode) and send it to a convex solver to at minimum get the dual optimum objective value, which serves as a lower bound (for primal minimization) on primal optimum (yeah, maybe there’s a duality gap, and maybe it’s big, but it’s still a lower bound, even if not tight, and maybe it’s useful to the user, even if big), even if the calculations can not be performed in all cases to relate the dual optimum solution back to the corresponding primal variables. Of course, this would be one type of convex relaxation, and perhaps CVX could automatically handle other possible convex relaxations (possibly better than Lagrangian Dual in some cases) and solve them for the user.

One can dream …

Thanks for your consideration. Now back to your regularly scheduled programming of problem formulations which violate CVX’s ruleset, usually because they are not convex.



Edit: This is in response to mcg’s post to my post above.

Thanks for the response. I am a good enough analyst to have, unfortunately in this case, correctly predicted the answer.

Thanks for the tip on YALMIP. I looked into it at the same time as CVX a little over a year ago, but “went” with CVX, because it seemed to require less effort to get up and running, and seemed well suited to a bunch of SDPs I had just conceived and wanted to quickly run (from a human effort, not computer run-time standpoint). Now I am increasingly formulating variations to those SDPs which are no longer convex, and perhaps it will be worth my effort to get up and running with YALMIP to complement CVX. As I advance in years, I find it harder to remember syntax for multiple similar things, and so that was why I probably just let YALMIP go into indefinite hold status, so to speak. I suppose there is some tradeoff at user level to get more flexibility at the expense of ease of use.

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…