You need to provide the entire specification of your problem, then it can be determined whether your problem is convex, which of course you should be doing.

Edit: Now that you have posted your problem, your problem formulation (leaving aside the integer aspect) is not convex, and so can not be modeled in CVX. r/norm(A*x-b) is not convex. So your function definition would more properly be called your non-convex function definition.

Edit^2: For mcg:
There appears to be a bug in CVX Build 1023.
The following code is accepted, despite the non-convexity. Sedumi and SDPT3 both declare the problem to be infeasible. On the 3nd to last iteration, SDPT3 reported

linsysolve: Schur complement matrix not positive definite
switch to LU factor. lu 30 30

That’s convex. inv_pos is convex and decreasing so it takes a concave argument, and -norm(x) is concave. As for why it fails to converge, it’s minimum value is -\infty, achieved when x=0, so it’s got some degeneracies there. The solvers are certainly struggling.

Maybe this is a senior moment, but Eigenvalues(subs(x=1,y=1,Hessian(-1/sqrt(x^2+y^2),[x,y]))); in MAPLE produces one positive eigenvalue and one negative eigenvalue. The expression is the eigenvalues of the Hessian of -1/sqrt(x^2+y^2) w.r.t. x and y evaluated at x=y=1.

I don’t know what to tell you Mark. The composition of a convex decreasing function (inv_pos) with a concave function (negative of the norm) is convex. Can’t speak for Maple.

Actually, it’s my turn for a senior moment. Two things. First, Maple is using 1/x, not inv_pos. Those are two different functions. Maple is not computing the derivatives of the function CVX is accepting.

But here’s the second and more important point: norm() is non-negative, so -norm() is non-positive. The domain of inv_pos is the positive interval. Thus, inv_pos(-norm()) has an empty domain. It’s an ill-posed construction! CVX can’t detect this kind of situation, hence the failure.

Ah yes, inv_pos(-f(x)) ~= -inv_pos(f(x)), a senior moment indeed. So I was sort of right that CVX shouldn’t accept this, but for the wrong reason. Did CVX pass a problem to the solvers which in exact arithmetic would be infeasible or is it actually feasible due to strict vs. non-strict inequality?

Well, depends would you mean by “shouldn’t”. It is compliant with the DCP ruleset, and that’s all CVX cares about. It has no intelligence about the domains and ranges of the functions it uses.

It basically converts the objective to minimize(z2); [z1,1;1,z2]==semidefinite(2); {x,-z1}==lorentz(2); This is infeasible but asymptotically feasible (z1=0,z2=infinity). It’s one of the harder scenarios for a solver to handle.