Computing Manifold in Lagrange Equation Format

[Allan Ding]

Hi,

Thanks for your efforts on Manopt. 

I have used Manopt now, but I found one problem. Since I usually deal with such optimization problem: 

min_{P,Z,E} ||Z||_* +\lambda||E||_1, s.t., P^T X = P^T XZ + E, P^TP=I.

That is, I need to format it into Lagrange Equation, so I wonder if I can still apply Manopt to solve the problem. Can I still calculate the gradient w.r.t. P as the input when fixing other variables?

Thanks.

Allan

[BM]

Hello Allan, 

Thanks for the interest in Manopt. 

If I understand the issue correctly, the question is whether we could use Manopt for solving the Lagrangian formulation. Is that so? I have two additional enquiries.

1) What precisely is the Lagrangian formulation that you are looking at? It would help us to understand the problem.  

2) It seems that you want to optimize only with respect to P. Is my understanding correct? 

Regards,

Bamdev

[BM]

Hello Allan, 

In this case, it is possible to optimize for P with Manopt to a critical point of the red part. Below is the sample code. We assume that you have already defined L, X, Z, E, Y, alpha, and mu. Assume also that P is of size n-by-r.

problem.M = stiefelfactory(n, r);

problem.cost = @cost; % Cost function handle. 

function f = cost(P)

         Errormat = P'*X - P'*(X*Z) - E;

         f = alpha*trace(P'*(L*P)) + trace(Y'*Errormat)  + 0.5*mu*norm(Errormat, 'fro')^2;

end

problem.egrad = @egrad; % Gradient function handle of the objective function.

function grad = egrad(P)

         Errormat = P'*X - P'*(X*Z) - E;

         L = 0.5*(L + L'); % The gradient depends only on the symmetric part of L.

         grad = 2*alpha*(L*P) + X*Y'  - (X*Z)*Y' + mu*((X - X*Z)*Errormat');

end

checkgradient(problem); % Check whether the gradient computation is correct. 

Popt = trustregions(problem); % Call the trust-regions solver. other choices include steepestdescent and conjugategradient.

Let us know if you require further inputs. I hope, I did not make a mistake in the gradient computation, but do verify it.

Regards,

Bamdev

 

On Sat, Jul 2, 2016 at 1:35 AM, Allan Ding wrote:

Hi Bamdev,

Thanks for your kind reply.

Actually, I want to solve this problem

 

where X is the data matrix, L is a known matrix and I is the identity matrix. Since it its hard to jointly optimize P, Z, E, so I optimize one by one. When Z, E are fixed, I aim to update the following Lagrange function:

where Y and \mu are parameters. For this case, can I first calculate the gradient of red box part w.r.t P, then apply Manopt to optimize P with the orthogonal constraint? Thanks

Best,

Allan

PhD Student

Department of Electrical and Computer Engineering

Northeastern University

Phone: (1)617-3906211

E-mail: allan...@gmail.com

Homepage: https://sites.google.com/site/allanding630/

[Nicolas Boumal]

Hello Allan and Bamdev,

On my computer, the equations in the post from July 2, 2016 do not appear (the images appear to be missing.)

If you get a chance to write these equations here, that could be useful for future readers.

Thanks,

Nicolas

[BM]

Hello Nicolas, 

The original problem is 

min_{P, Z, E} || Z||_* + \lambda || E||_1 + \alpha trace(P'LP) 

subject to P'X = P'XZ + E and P'P = I. 

The (augmented) Lagrange version for updating only P is 

P = argmin_{P'P = I} \alpha trace(P'LP)  + <Y,  P'X - P'XZ - E> + 0.5 \mu ||  P'X - P'XZ - E||_F^2,

where Y and \mu are parameters.

Regards,

Bamdev

[Nicolas Boumal]

Thank you, Bamdev!

Nicolas