How to approximate a rank-1 solution after exploiting semidefinite relaxation method

1

After exploiting SDR method, the considered convex problem can be effectively solved with a PSD solution (the variable is set to be PSD). Then, how can we get a rank-1 solution from the solution of PSD matrix (probably rank > 1)?

One way I heard from others is that to directly check the rank of the solution. If it happens to be rank 1, then we just choose the corresponding eigenvector to be the unique solution.

But if it’s not rank-1, what do we usually perform to approximate a rank-1 solution from the solved PSD, that satifies the object and the constraints as much as possible?

For example, my problem after SDR without rank-1 constraint will be shown below and it can be effectively solved by CVX, which is (as_ele_Tx is a known vector, Hm is a known matrix, J, epsilon are known scalars)

cvx_begin
variable F(J,J) hermitian semidefinite
variable u nonnegative
A = as_ele_Tx * as_ele_Tx’;
minimize( u )
subject to
trace(A* F) >= Z;
for i = 1:K
temp_H = Hm(i,: ) ’ * Hm(i,: ) + epsilon .* diag(ones(J,1)) ;
temp_H = 1/2 .* (temp_H + temp_H’);
trace(temp_H* F) <= u;
end
for ii=1:J
Q = zeros(J,J);
Q(ii,ii) = 1;
trace(Q* F) == P;
end
cvx_end

2

If CVX and the solver have solved the convex optimization provided to them, they have done their job. What to do if that problem is not the problem you really want to solve, and the solution to the problem provided to CVX does not happen to satisfy non-convex constraints omitted from your CVX formulation, is off-topic for this forum.

You might want to consider https://math.stackexchange.com/ or https://scicomp.stackexchange.com/ or https://or.stackexchange.com/ . or perhaps consult appropriate books and papers.

3

Thanks Mark! I will try them.