How to include PSD constraint in TFOCS

[shirleyxq (Shirley Liu)]

Hi there!

I’m solving \min_{\mathbf{B}\succeq 0} \text{Trace}(\mathbf{B}) subject to \|\mathcal{A}(\mathbf{B}) - \mathbf{y}\|_2 \leq \epsilon where \mathcal{A}:\mathbb{R}^{L\times L} \to \mathbb{R}^m is a linear operator, \mathbf{B}\in \mathbb{R}^{L\times L} is a matrix, and \mathbf{y}\in \mathbb{R}^m is a vector.

I wrote a functioning programme using tfocs_scd for this problem without the PSD constraint, but didn’t know how to include the PSD constraint. Could you please advise me on this?

Many thanks,
Shirley

[Mark_L_Stone]

Do you really wish to use TFCOs as opposed to CVX?

Unfortunately, I don;t believe any of the TFOCS developers are still active on this forum, and doubt there are many or any advanced users of TFOCS still active here. So you may have to figure things out on your own.

Nevertheless, a quick search shows these 2 posts from @Stephen_Becker one of the TFOCS developers, which might help you.

Rank minimization with TFOCS

Here’s a solution for some of the formulations (e.g., A*vec(X) ~= b), with the CVX code and the TFOCS code: n = 10; m = round(n/2); A = randn(m,n^2); b = randn(m,1); epsilon = .1; %% Solve in CVX cvx_begin cvx_precision best variable X(n,n) minimize trace(X) subject to X == semidefinite(n) norm( A*vec(X) - b, Inf ) <= epsilon cvx_end X_CVX = X; %% Solve in TFOCS linear = linop_compose( linop_matrix(A), linop_vec([n,n]) ); affneF = { linear, -b }; objectiveF = prox_trace; dua…

Sparse PCA in TFOCS

Here’s one way to do it. I modified proj_psdUTrace.m to take in an extra trace term (since this is just a linear term). An extra linear term is quite common so we may take care of it nicely in a future release of TFOCS. For now, the modified proj_psdUTrace.m is in github, so head there to get the latest version. First, setup the problem rng(100); d = 20; X = randn(d); R = X'*X; % Sigma e = ones(d,1); lambda = 0.5; Now solve in CVX so we can verify we’re solving the right problem cvx_begin cv…

You can also see all posts on this forum categorized as TFOCS at http://ask.cvxr.com/c/tfocs/6 .

[shirleyxq (Shirley Liu)]

Thanks Mark. I’m going through these posts now. CVX works but it’s extremely slow, so my colleagues have advised that I try TFOCS. Is there any way that I can speed up CVX?

[Mark_L_Stone]

You haven’t shown us the PSD constraint (so I don;t know whether there is an opportunity to speed up things in the CVX formulation. But if your CVX code doesn’t have any for loops, there likely isn’t much or any opportunity to speed up the problem formulation by improved coding. But dualizing the problem might potentially speed up the solver (or could slow it down). If you need to solve a structurally same problem many times, but with different input data, then you can reduce problem formulation time by using YALMIP with its optimizer capability.

[shirleyxq (Shirley Liu)]

Here’s my code for the problem above:

cvx_begin quiet
variable B(L, L) semidefinite % a real symmetric PSD matrix
minimize(trace(B))
subject to
norm(bahmani_Woperator(B, W) - y, 2) <= epsilon
cvx_end
Did you mean that I should use YALMIP instead of CVX?

Thanks,
Shirley

[shirleyxq (Shirley Liu)]

bahmani_Woperator is a linear operator which I coded up in a separate script.

[Mark_L_Stone]

Don;t use quiet. That way you will see the solver and CVX output.
Is CVX formulation taking too long, or the solver once it starts taking too long? What are the problem dimensions?

I presume the mysterious bahmani_Woperator function is an affine function of its first argument?
If you re-run withoutquiet’, and post the CVX and solver output, maybe one of the forum readers can provide an assessment.

[shirleyxq (Shirley Liu)]

Hi Mark, I think I figured out how to use TFOCS for this problem! Instead of using prox_nuclear as my objective function, I should use prox_trace to impose the PSD constraint. This is because the proximity operator of trace is a combination of the proximity operator of trace and the indicator set of positive semi-definite matrices. So we do not need to explicitly include the positive semi-definite constraint.

Thanks for your help! - Shirley

[Mark_L_Stone]

Great. Please let us know the speed comparison on pertinent problem sizes.

I trust you will compare optimal objective values between TFOCS and CVX (perhaps TFOCS default solver tolerance is not as tight as CVX)), and verify that TFOCS solutions satisfy all intended constraints to within feasibility tolerance.