In some part of my CVX program, I need to do: velocity = norm(x-x_0)/T;
and add the following constraint: y >= K*norm(velocity - v_measured);
where x is the optimization variable.
I know that this restriction is not convex, then CVX refuse it with the following message: Cannot perform the operation norm( {convex}, 2 ). (Am I right?)
Weirdly, sometimes it works and I don’t know exactly why.
Do you know another form to formulate this constraint in order to make it convex?
Yes, you are right: the second norm is just abs and the inequality is also non-convex.
With sometimes I mean that when I run the complete Matlab code the CVX doesn’t complain with the message Cannot perform the operation norm( {convex}, 2 ). It works. I have checked the velocity variable and it is still cvx: positive convex so the the inequality is non-convex, but it works!.
For example, this is an output when it works: velocity =
cvx: positive convex
Calling SDPT3 4.0: 33 variables, 11 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------
num. of constraints = 11
dim. of socp var = 24, num. of socp blk = 8
dim. of linear var = 9
*******************************************************************
SDPT3: Infeasible path-following algorithms
*******************************************************************
version predcorr gam expon scale_data
NT 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap prim-obj dual-obj cputime
-------------------------------------------------------------------
0|0.000|0.000|1.0e+01|3.5e+00|1.2e+03| 6.752147e+01 0.000000e+00| 0:0:00| chol 1 1
1|1.000|0.781|2.5e-06|8.0e-01|2.8e+02| 8.397246e+01 -6.736138e+00| 0:0:00| chol 1 1
2|0.934|0.911|2.0e-06|7.5e-02|4.7e+01| 2.978877e+01 -2.278644e+00| 0:0:00| chol 1 1
3|0.911|0.995|3.0e-07|7.0e-04|5.9e+00| 5.769693e+00 -4.811441e-02| 0:0:00| chol 1 1
4|0.987|0.988|8.9e-09|4.5e-05|7.5e-02| 7.424529e-02 -5.142616e-04| 0:0:00| chol 1 1
5|0.989|0.989|1.7e-10|4.1e-06|8.3e-04| 8.219637e-04 4.195300e-06| 0:0:00| chol 1 1
6|0.989|0.989|2.3e-10|4.1e-07|9.1e-06| 9.039179e-06 1.035068e-06| 0:0:00| chol 1 1
7|0.993|1.000|2.3e-09|4.5e-11|1.2e-07| 1.201483e-07 -3.038138e-09| 0:0:00| chol 1 1
8|0.692|1.000|3.9e-09|6.8e-11|5.6e-08| 6.841797e-08 -1.727995e-09| 0:0:00| chol 1 1
9|0.669|1.000|2.7e-09|1.0e-10|2.8e-08| 3.719571e-08 -8.496394e-10| 0:0:00| chol 1 1
10|0.596|1.000|1.1e-09|1.5e-10|1.6e-08| 1.888541e-08 -4.257070e-10| 0:0:00| chol 1 1
11|0.604|1.000|4.3e-10|2.1e-10|9.0e-09| 9.700256e-09 -2.371168e-10| 0:0:00|
stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
number of iterations = 11
primal objective value = 9.70025586e-09
dual objective value = -2.37116759e-10
gap := trace(XZ) = 8.98e-09
relative gap = 8.98e-09
actual relative gap = 9.94e-09
rel. primal infeas (scaled problem) = 4.25e-10
rel. dual " " " = 2.15e-10
rel. primal infeas (unscaled problem) = 0.00e+00
rel. dual " " " = 0.00e+00
norm(X), norm(y), norm(Z) = 1.0e+00, 2.6e+00, 7.8e+00
norm(A), norm(b), norm(C) = 6.7e+00, 2.0e+00, 1.1e+01
Total CPU time (secs) = 0.06
CPU time per iteration = 0.01
termination code = 0
DIMACS: 4.3e-10 0.0e+00 5.0e-10 0.0e+00 9.9e-09 9.0e-09
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +6.0653
I wonder if there are another function in CVX like abs but convex when its argument is convex as norm.
% SOCP
function socploc(A)
% These variables are constant
global red sigma_l sigma_e N
% Vectors dist_vel and v_med are defined here.
for nodo = 1:N,
vecinos = find(A(:,nodo)); % Neighbors of node nodo
% The following vectors are defined according to vector 'vecinos'
% and have the following sizes.
%
% b = vector size(vecinos) x 1
% c = vector size(vecinos) x 1
% x = real value
% d = vector size(vecinos) x 1
cvx_begin
% Variable declaration
variable s(1,2);
variable y;
% Objective function
minimize (y);
% Constraints
subject to
% Error constraints
y >= (norm([c; x])).^2;
% Velocity error constraint (THE PROBLEMATIC LINES)
dist_vel = norm(s-red(nodo,3:4))/T;
x >= (1/sigma_e)*abs(dist_vel - v_med(nodo));
for veci = 1:size(vecinos,1), % For each neighbor node
% Distance error constraint
c(veci) >= (1/sigma_l)*abs(b(veci) - d(veci));
% Distance constraint
b(veci) >= norm(s - red(vecinos(veci),1:2));
end
cvx_end
end
Unfortunately, I can not supply specific inputs because they are random.
I have tried to overcome the problem by putting:
% Velocity error constraint (THE PROBLEMATIC LINES)
dist_vel = norm(s-red(nodo,3:4))/T;
x >= (1/sigma_e)*abs(power(dist_vel - v_med(nodo), 1));
that is, using function power as I know that I need an affine function as an argument of function abs in order to be convex; but the problem persists.
If the statement y >= (norm([c; x])).^2;
didn’t produce an error message, that suggests you were using CVX 3.0beta, because that is allowed in CVX 3.0beta but not in CVX 2.1 (square_pos is needed in CVX 2.1)
Unfortunately, CVX 3.0beta has many bugs, so if you were using that, perhaps your subsequent non-convex inequality was being allowed due to a bug in CVX 3.0beta.
What is the output of cvx_version ? If you are using CVX 3.0beta, please uninstall it and install CVX 2.1.
---------------------------------------------------------------------------
CVX: Software for Disciplined Convex Programming (c)2014 CVX Research
Version 3.0beta, Build 1183 (dda2109) Sun Dec 17 18:58:10 2017
---------------------------------------------------------------------------
>> cvx_version
---------------------------------------------------------------------------
CVX: Software for Disciplined Convex Programming (c)2014 CVX Research
Version 2.1, Build 1127 (95903bf) Sat Dec 15 18:52:07 2018
---------------------------------------------------------------------------
Now, the program doesn’t work as expected because of the nonconvexity. However there is another output that I don’t understand:
Warning: A non-empty cvx problem already exists in this scope.
It is being overwritten.
> In cvxprob (line 28)
In cvx_begin (line 41)
In socploc (line 35)
What does it mean?
And, of course, the original problem (how to express that non-convex statement into a convex one?) persists…
The warning is because you had a previous cvx_begin without corresponding cvx_end and then another cvx_begin. Everything from the previous cvx_begin is ignored, and CVX will process starting from the 2nd cvx_begin. So it is harmless. You can avoid the warning by issuing the command cvx_clear prior to the 2nd cvx_begin.
Try a different solver. I don;t know whether that will help. Perhaps the error is due to a bug in the CVX/solver interface or in the solver. Or perhaps not.