I have the underdetermined outer optimization problem
$$\text{min}_{x\geq 0}\quad |Ax-b_1|_2^2+|AT(x)-b_2|_2^2$$
with A\in\mathbb{R}^{m\times n} and m<< n=64^2 or in corresponding CVX Matlab code

where p1,...,p5 are fixed parameters required by the function T. Inside T there is another linear minimization problem
$$\begin{aligned}\text{min}_{c,q} \quad &1^\top q&\\text{s.t.}\quad&Dc-x \leq q\-&Dc-x \leq -q\end{aligned}$$ with D\in\mathbb{R}^{n\times n} or in Matlab syntax

function value = T(x,p1,p2,p3,p4,p5)
... something happens ...
cvx_begin
variable c(n)
variable q(n)
minimize sum(q)
subject to
D*c-x <= q
-D*c-x >= -q
cvx_end
... something else happens and calculates return value ...

Unfortunately I get the error

Undefined function 'newcnstr' for input arguments of type 'cvx'.
Error in cvx/lt (line 22)
b = newcnstr( evalin( 'caller', 'cvx_problem', '[]' ), x, y, '<' );

after the cvx_end line in the function T. The other things which happen in function T are all CVX compatible. It looks like CVX doesn’t like itself and cannot handle its own data type, since the error occurs in a CVX function. Is that true?
Is it possible to nest CVX optimization problems like that somehow? If yes, how?

Whether you use norm or sum_square for the 2nd term in your objective function, T(x) needs to be affine in x, or it will not be CVX compliant.

Take a look at http://web.cvxr.com/cvx/doc/advanced.html#new-functions-via-partially-specified-problems Unfortunately, I don’t believe T(x) is going to be affine, but this capability might help you to use T(x) in another context. You haven’t told us what the “something happens” and the “something else happens” are, but I don’t think it matters, because I think you are out of luck anyway.

Most of CVX’s functions are implemented this way, so it’s not clear to me why your implementation is causing issues. However, it is also not clear to me that your model is convex. In fact it almost certainly isn’t, because the CVX model inside the T() function is convex, so T() is not affine. So the issue is somewhat moot. CVX cannot solve non-convex problems, per the FAQ.

I also think that “something happens” and “something else happens” doesn’t matter, because if I comment out just the inner CVX optimization from cvx_begin to cvx_end and just put a fixed result for the variable c (I don’t need q), then everything runs technically fine (although the result is nonsense, of course).
I read the FAQs before my post, but this is why I decided to post it anyway. mcg’s last post is a great take home message, but I think there are many nested problems like mine, which are incredibly hard to formulate without nesting.

You are right, most certainly T() is not convex (yet), but in any case I would not expect an error about the cvx data type.
So lets look at it from a technical point of view. Why is this happening?

If your code is not CVX compliant (DCP compliant), you will get a CVX error message, but it may not always seem to correspond to what your actual offending item is.

You are right, I found the reason for the error:
The first line below the inner optimization in function T is c(c < threshold) = 0;
This is where the error occurs and not the cvx optimization. So the < operator doesn’t work for cvx arguments… that’s a pitty. Still I don’t understand why this error occurs in cvx/lt, since it is not happening between cvx_begin and cvx_end and < is a Matlab operator, but I don’t know about the cvx implementation either.
And in addition this line makes the function T non-convex.
Sorry for bothering!
So, in general it is possible to nest CVX optimizations. Great!

Oh this is definitely an illegal use of a CVX variable. One of the challenges of designing software like this is anticipating all of the ways that people will try to use it incorrectly so that the error messages are constructive. I frankly don’t think I am going to bother with this one, because it is a rather egregious violation of the DCP rules.