How to Formulate in CVX - 1D Total Variation Extension

Given the problem

\min_{ x \in {\mathbb{R}}^{n} } \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + \sum_{i = 1}^{n - 2} \sqrt{{\left( {x}_{i} - {x}_{i + 1} \right)}^{2} + {\left( {x}_{i + 1} - {x}_{i + 2} \right)}^{2}}

How could one formulate it in CVX?
I could handle it without the sqrt yet couldn’t do it in this form.

Thank You.

What if I have a dual form which separable, how could I use it with CVX?

How did you prove the objective function is convex?

Hi @Mark_L_Stone, well, I could rewrite the problem as:

\min_{ x \in {\mathbb{R}}^{n} } \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + \sum_{i = 1}^{n - 2} \sqrt{{\left( {x}_{i} - {x}_{i + 1} \right)}^{2} + {\left( {x}_{i + 1} - {x}_{i + 2} \right)}^{2}} = \min_{ x \in {\mathbb{R}}^{n} } \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + \sum_{i = 1}^{n - 2} { \left\| {B}_{i} x \right\| }_{2}

Where the matrix {B}_{i} extracts a vector such that

{z}_{i} = {B}_{i} x = \begin{bmatrix} {x}_{i} - {x}_{i + 1} \\ {x}_{i + 1} - {x}_{i + 2} \end{bmatrix}

This must be Convex.

Thank You.

Well, there you go. Code that up in a straightforward manner, and CVX should accept it.

Hi @Mark_L_Stone,

That’s the issue, I don’t know how to insert the Loop into CVX.
It can’t be written in one minimize argument.

Thank You.

cvx_begin
variable x(n)
Objective = 0.5*sum_square(x-y)
for i=1:n-2
  Objective = Objective + norm([x(i)-x(i+1);x(i+1)-x(i+2)])
end
minimize(Objective)
% insert any other constraints
cvx_end
1 Like

Hi @Mark_L_Stone,

It really solved it.
I wasn’t aware it can be done that way (Looping inside CVX Block).

Is there a way to mark question as solved?

Thank You.

Nice pedagogical technique there, Mark!

There is no marking questions as solved in this forum. Your post stating that it is solved will accomplish that purpose for readers.

Well,

This question is solved.

CVX is really awesome.
Just need better support for large size arrays.

Now that you have some experience with CVX, perhaps you should re-read the CVX Users’ Guide, so that you can pick up on things which you didn’t fully absorb the first time.

Has the MathJaX Plug In of the site stopped working?

Is is not displaying for me either, in 2 different browsers.

Yeah, it seems busted and I as yet do not know how to fix it.

Any update on that?

It is crucial to the forum.

Thank You.

No, I’d love it if someone would figure it out! I have not succeeded.

The guys over Julia are using the same forum and have it working.

Maybe they could assist?