I know that f(x)=\sup_{y\in S} g(x,y) is convex as long as g(\cdot,y) is convex for each y\in S. I can implement the \ell_2 norm of a vector x using CVX:
function cvx_optval = mynorm( x )
n=length(x);
cvx_begin
variable y(n)
maximize(sum(y.*x))
subject to
norm(y) <= 1;
cvx_end
end
This works fine on fixed inputs (i.e., outside of CVX); however, when I try using mynorm within CVX, it is not recognized as a convex function. I see that the section of the manual on partially specified problems says that g(x,y) has to be jointly convex. Is there a partial specification approach based on the “pointwise maximum” rule to define functions in CVX? Obviously, there’d be no reason to define mynorm in this way, but I actually have a more complicated problem in mind. Thanks!
This is a very good question, but I am afraid the answer is no. The reason is that these functions are basically inserted in your model “inline”, and so if you pass a variable into mynorm, you will be confronted with the DCP-violation in sum(y.*x).
Having said, that, you usually can represent all of these functions in CVX—you just need to do a little more work. What you need to do is find the convex dual of this optimization problem. Specifically, assume that x is constant, and compute the dual, which is a minimization. As long as the resulting expressions satisfy the DCP ruleset for both x and the new variables, it will be a valid CVX version of the function.
For instance, in this case, we need to compute the dual of
$$\begin{array}{ll}\text{maximize}&x^T y\\text{subject to}&|y|\leq 1\end{array}$$
The Lagrangian is
$$L(y,z,s) = x^Ty+\langle z,y\rangle +s\cdot 1$$
where \|z\|_*\leq 1, \|\cdot\|_* being the dual norm for \|\cdot\|. Maximizing this over y yields the dual problem:
$$\begin{array}{ll}\text{minimize}&s\\text{subject to}&x+z=0\&|z|_*\leq s\end{array}$$
Of course, this just reduces down to \|x\|_*. I suspect you knew that. But for more complex partial specifications, this technique may be useful.
In fact, I derived the implementation of sum_largest in just this manner.
You don’t see it because I had to do the conversion to dual form by hand. That’s my point: you can’t enter these kinds of models into CVX; you have to convert to dual yourself.