Global Solution to a Rank-constrained optimization Problem

[geng...@gmail.com]

Dear all,
I'm working on the following optimization problem:

\min_W Tr(C*W)
s.t. Tr(A*W) <= b and rank(W) = 1
W \ge 0

The decision variable is a n-by-n matrix $W$ (indeed it is positive semidefinite), and $A$, $C$ and $b$ are all known constants. Tr(A*W) calculates the trace of the matrix product A*W

We tried to relax the rank constraint (e.g. using nuclear norm), but sometimes we failed to get rank-1 solution we want.

I checked the tutorial of manopt, it seems able to handle rank constraint (with guarantee on convergence?). However, I did not find much about the optimal solution returned by manopt. Is it guaranteed to be a global minizer?

I'm very new to manopt, and apologize if this is a naive question.

Thanks,
Steven

[Nicolas Boumal]

Hello Steven,

Interesting question which comes quite close to a lot of things I've been interested in.

I'm going to assume that the constraint matrix A is positive definite and that b is positive. Otherwise, the feasible set of the optimization problem is unbounded or empty, and this can cause the problem to fail to have a solution.

Furthermore, the inequality constraint can really be treated as an equality constraint. Indeed, if the inequality is not active at the optimum, then the optimum actually solves

\min_W Tr(C*W)
s.t. rank(W) = 1
W \ge 0

The infimum value of this problem is 0 if C is positive semidefinite, and -inf otherwise. Not too interesting.

In the more interesting case, the inequality constraint is active at the optimum, and we can equivalently study the equality-constrained version of the problem:

\min_W Tr(C*W)
s.t. Tr(A*W) = b and rank(W) = 1
W \ge 0

This case is also special, because it actually corresponds to the generalized eigenvalue problem. Since W is psd and rank(W) = 1, we have W = xx' for some x; So, the problem really is:

minimize_x  f(x) = x'*C*x subject to x'*A*x = b.

The global optimum of this can be obtained via a proper call to eigs, probably [x, f] = eigs(C, A, 1, 'SA'). Then, x only needs to be scaled to satisfy x'*A*x = b (by default, x'*A*x = 1, I believe.)

(If we remove the rank constraint, this:

\min_W Tr(C*W)
s.t. Tr(A*W) = b

W \ge 0

is a semidefinite program (SDP) with one equality constraint. It so happens that this SDP always admits a rank 1 global optimum. Hence, the SDP relaxation is equivalent to the rank-constrained problem. The set defined by the quadratic constraint x'*A*x = b is an ellipsoid (if A is positive definite), which is a nice smooth manifolds and the defining equation is regular, so you get that optimizing over that ellipsoid is easy because, despite non-convexity, first- and second-order necessary optimality conditions are sufficient for global optimality. So, you might want to use that, except it's not necessarily easy to stay on that manifold. Manopt's generalized Stiefel manifold with p = 1 allows you to do it, but it's not necessarily efficient.)  This is all explained in detail in this paper: https://arxiv.org/abs/1606.04970.

Best,

Nicolas

[geng...@gmail.com]

Hi Nicolas,
Thanks for your reply! I talked to my friend about this question last week, and surprisingly he sent me your paper (!), the same one you mentioned in your reply.

I spent some time going through your paper, unfortunately the conditions there do not work for my problem....

Your reply is very helpful for a small test case I'm having. However, for larger test cases, it is a little more complicated than I described in the first post.

Here I'm describing my problem in complete details, and there are two possible problem formulations:

(P1)

minimize_x f(x) = x'*C*x
subject to

x' * A_i * x = a_i, where i = 1,2,....,m
x' * B_j * x <= b_j, where j = 1,2,.....n

we know every B_j is positive semi definite and b_j >=0, thus the inequalities are considered "easy". The real trouble is from the equality constraint x' * A_i * x = a_i, and A_i is not symmetric)

(P2)
minimize_W Tr(P*W)
subject to
Tr(Q_i*W) <= q_i, where i = 1,2,..., s
Tr(R_i*W) <= r_i, where i = 1,2,..., t
rank(W) = 1
W >= 0 and W = W'

in this formulation (P2), the trouble is from the rank-1 constraint, all the other constraints are considered easy since they could be handled by semidefinite programming, therefore I did not mention them in the first post.


I went through several examples at https://github.com/NicolasBoumal/manopt/tree/master/examples
but it seems after choosing the manifold, I cannot add any other constraints. Am I supposed to put everything (constraints) by defining the manifold? All my other constraints are "easy" ones in the sense of convex optimization, hopefully this won't cause too many troubles for manopt.


Thanks!
Steven

[Nicolas Boumal]

Hello Steven

Thanks for the feedback.

You are right: manopt does not support (as is) adding extra constraints on top of the manifold. One possibility is to follow the Augmented Lagrangian Method paradigm from "standard" constrained optimization, where one adds a penalty term in the cost function, to penalize violation of the extra constraints (which are then removed, since they are accounted for in the cost.) This, however, requires some engineering to get right. One of my students worked on this last summer, and we are working toward making a report of our findings publicly available (this will take a bit of time.) I expect that one can indeed make this work; it just won't be a "direct" application of Manopt.

Another ressource (quite different) that might be relevant for you is this recent paper about quadratically constrained quadratic programming:

https://arxiv.org/abs/1802.02688

Best wishes for your project,

Best,

Nicolas

 

On Wednesday, January 17, 2018 at 2:08:51 AM UTC-5, xbg...@tamu.edu wrote:

[geng...@gmail.com]

Thank you Nicolas! I will try it.

Steven

[Rui Li]

Hi Steven,

This is Ricky. Have you solved your problem with the manopt?

My problem is similar to yours. Perhaps we can have a chat on this.

Regards, 

Ricky

[Rui Li]

Hi Nicolas,

This is Rui. 

I am wondering whether can I access to your investigation of the Augmented Lagrangian Method paradigm as indicated in your reply to Steven. If it is, could you share the link with me?

Thank you so much.

Regards,

Rui

[Nicolas Boumal]

Hello Rui,

Changshuo Liu, a student at Princeton University did the work on ALM; the code is on his github (paper still in preparation); you may want to start looking here: https://github.com/losangle/bfgsManopt/blob/master/constrained/alm.m.

Best,

Nicolas

[Rui Li]

Dear Nicolas,  

Thank you so much. I shall try it.

Regards,

Rui