Another form to formulate this restriction

(J) #1

Hi everybody:

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?

Thanks in advance.

(Mark L. Stone) #2

The second (i.e., outer) norm is just abs, due to its argument being a scalar. Nevertheless, I believe the inequality constraint is non-convex.

Please clarify what the “sometimes” when it works is.

(J) #3

Thank you for your response.

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.

(Mark L. Stone) #4

Please show a complete (small size if possible) reproducible code, complete with all input data, in which the program executes without error.

There is no other function in CVX like abs but convex when its argument is convex as norm .

(J) #5

Here is my small size code:


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
			% 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));

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.

Thank you very much.

(Mark L. Stone) #6

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.

(J) #8

Yes, it’s version 3.0beta
>> cvx_version

CVX: Software for Disciplined Convex Programming       (c)2014 CVX Research
Version 3.0beta, Build 1183 (dda2109)              Sun Dec 17 18:58:10 2017
(J) #9

I have installed CVX 2.1:

>> 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…


(Mark L. Stone) #10

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.

As for your original question, please read Why isn't CVX accepting my model? READ THIS FIRST! .

(J) #11

Thank you for your responses.

Only to prove, I have removed the non convex line. CVX 3.0 didn’t mark any error. However CVX 2.1 reports this cryptic message:

Non-overloaded subscripting can produce only one result.

Error in cvxprob/solve (line 423)
            [ x, status, tprec, iters, y ] = shim.solve( At, b, c, cones, quiet, prec, solv.settings, eargs{:} );

Error in cvx_end (line 88)
        solve( prob );

Error in socploc (line 68)

What does it mean?

Thanks in advance.

PS. I have checked this thread, but no clarification are done there.

(Mark L. Stone) #12

I don’t know. …

(J) #13

Thank you. I am going to look for a solution to this new message.

I appreciate your time in replying this thread.

Best regards,

(Mark L. Stone) #14

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.