Non-smooth objective function with generalized Stiefel manifold constriant

[Bai Bo]

Hi, All

I've encountered an interesting problem:

min    \sum_{j=1}^{M} 1/(x_j^T * W * x_j)
s.t.     X^T * D * X = I.
          X is non-negative matrix.

x_j is the j-th column of X, W=W^{T}, and D is symmetric positive definite matrix.

I tried to use generalized Stiefel factory to solve this problem. But the result is not even close to the optimal.
I noticed that the objective function is not smooth when X is a real matrix.

Is there any method to force X to be non-negative, or make the objective function smooth?


Thanks a lot for any kindly help!


Best Regards,
Bo
 

[Nicolas Boumal]

Hello Bo,

Enforcing nonnegativity in a matrix's entries is not idiomatic in optimization on manifolds. My best guess would be to penalize for negative entries in the cost function, but this is not always very successful.

Please let us know if it works for you, it would be interesting for many people!

To make the cost function smooth, one possibility is to replace the terms 1/(x_j^T * W * x_j) by 1/(epsilon + x_j^T * W * x_j) for a small, positive epsilon. I would start with a reasonable value of epsilon, optimize, then reduce epsilon by some factor, and optimize again, etc. This might help.

Best,

Nicolas

[Bai Bo]

Hello Nicolas,

Thank you very much for your suggestions. Recently, I found a paper entitled "MADMM: a generic algorithm for non-smooth optimization on manifolds". They proposed to use ADMM algorithm on manifold to deal with non-smooth objective functions. I am trying to apply this method to my problem. I will also try the relax method you suggested. I'll let you know if I have some progress.

Thanks again for your help.

Bo