Can a multi-block non smooth function be solved by Manopt?

[grandowife]

Hi there,

I have an objective function which like:

L(U, E) = ||X-UU'X||_F^2 + sum(sum(E)) + sum(sum(max(0, U'X-E))) + ||U||_2,1

where U is on stiefel manifold S(d, p); E is on euclidean (p, n); X is a given sample data which on euclidean (d, n);

【||M||_F^2  is the power of matrix M's frobenius norm ;   ||U||_2.1 is the matrxi U's L2,1 norm】

As in L(U, E) there exists L2,1 norm which leads to its non-smooth. 

So I wonder if the Manopt can solve it. Or is there exist some better solvers?

PS.  I have tried MADMM method, but I found it can not solve it because: 1) MADMM is a two-block optimization method; 2) no convergence is ensured in MADMM.

Best 

[Nicolas Boumal]

Hello,

I'm not sure what you mean by "multi-block" and "two-block"? Perhaps that there are two matrix variables? This shouldn't cause any particular difficulty.

Notice that max(0, ...) is also nonsmooth.

About optimizing nonsmooth cost functions: unfortunately at this time I do not have a better answer than the one I gave you in this post a couple weeks ago. Essentially, I recommend iterative smoothing. What exactly doesn't work with MADMM?

Best,

Nicolas

[grandowife]

Hi Nicolas,

Actually, I am not very good at optimization slovers, because I mainly concentrate on formulating an objective function based on some physical meanings in my area then I hope to use a existing optimization solver to handle it.

Therefore, firstly I tried to solve my function (below) with MADMM.

L(U, E) =  obj1                   +  obj2                + obj3                                     + obj4

             = ||X-UU'X||_F^2  +  sum(sum(E))  + sum(sum(max(0, U'X-E)))  + ||U||_2,1

[obj1: is a concave but smooth function ;

obj2: is a convex and smooth function;

obj3: is a convex but nonsmooth function;

obj4: is a convex but nonsmooth function.]

However, I found some problems when handling it with MADMM:  It cannot convergence after many iterations (I set it to 75, but the time consuming is unacceptable when setting to a large value).

So then I tried to find the reasons, and I suppose:

1) Since MADMM is an extension to classical ADMM, it may be only suitable for 2-block functions.? Should I try another solver, any suggestions?

And the meaning of blocks, as I am also new here, I think one block (eg. obj1) is a part of the objective function(L(U,E))  which the variable need to satisfy.

2) Maybe it because my obj1 is concave? However, I have no idea about how to find a way out of it.

Best  wishes,

Qiuying Shi

在 2019年5月22日星期三 UTC+8下午9:09:49，Nicolas Boumal写道：

[Nicolas Boumal]

Hello Qiuying,

This question is unfortunately too technical for me to answer here, as issues may arise from many fronts (issues with the model, the math, the code, the methods). It would take significant effort to get to the bottom of this.

Best of luck with it!

Nicolas

[grandowife]

Hi Nocolas，

Thank you, all the same, I will continue work on it!. 

Best wishes 

Qiuying Shi

在 2019年5月23日星期四 UTC+8下午7:53:57，Nicolas Boumal写道：