I would like to minimize the following
\sum_{i,j} | v_i - v_j | + \left\| v - \mathop{\textrm{median}}(v) \right\|_1
which is convex. I am unsure if it possible to add a nested minimization problem inside a CVX problem ( as \left\| v - \mathop{\textrm{median}}(v) \right\|_1 is by itself a minimization problem).
The percentile function is neither convex nor concave, so it cannot be supported by CVX. The set of functions CVX supports is clearly documented in the reference guide.
That’s true. Let me explain better what I am looking for.
I just would like to minimize the following
\sum_{i,j} | v_i - v_j | + \left\| v - median(v) \right\|_1
which clearly is convex. I am unsure if it possible to add a nested minimization problem inside a CVX problem ( as \left\| v - median(v) \right\|_1 is by itself a minimization problem).
It is certainly not clear to me that this is convex. By all means, I would like to see a proof. If it is indeed convex, then your proof will likely serve as the beginning of an answer to your question, so it is a worthwhile exercise.
The function f(\nu)=\sum_i|\nu_i-median(\nu)| can be written as $$f(\nu)=\min_x g(x,\nu)$$ where g(x,\nu)=\sum_i|\nu_i-x|, which is jointly convex in x and \nu. I think this is what foucault means by nested minimization. If you look at Section 5.2 of the CVX user guide, it describes how you can define a function via incomplete specification. In your case, I think this should do the trick:
function cvx_optval = diff_med( x )
cvx_begin
variable m;
minimize(norm(x-m,1));
cvx_end
Now you can use diff_med within CVX, and it will recognize it as a convex function.
Excellent, Bien! Assuming you are correct on the equivalence, then the CVX code that you have supplied will serve as the function foucault needs.
I’m very glad you found an answer. In fact, I’m going to add this function to CVX, and call it AVG_ABS_DEV_MED (average absolute deviation about the median). I’m also adding AVG_ABS_DEV (average absolute deviation, about the mean) for completeness.
Great! Except the one for the mean would use the \ell_2 norm, so maybe “AVG_RMSE” would be a better name since ABS_DEV suggests \ell_1 norm?
Oh, actually probably just “RMSE” makes sense since the averaging is done within the square root.
“Absolute average deviation” is an \ell_1 measure, whether you use the mean or the median as the center. Standard deviation is certainly another good measure we could consider.
Oh, I see. So the AVG_ABS_DEV would just be defined directly using the composition convex(affine), without any incomplete specification…
That’s right. Although using an equality constraint would likely improve performance by preserving sparsity.
