Theoretical Question on extracting the solution out of the matrix in SDR

1

Hi,

I want to solve the following problem:
max x’Ax
s.t |x(i)| == 1; i = 1,…N.

Here, x is an Nx1 complex vector, and A is a PSD matrix.

This problem comes under non-convex problem.
So, the convex relaxation is:

max trace(XA)
s.t diag(X) == 1, X is SDP

This is what I’m doing:
clear;clc

N = 4;

A = randn(N,N)+1j*randn(N,N);

A = A*A’;

A = (A+A’)*0.5;

cvx_begin sdp

variable X(N,N) complex;

maximize real(trace(X*A));

subject to

X > hermitian_semidefinite(N);

diag(X) == ones(N,1);

cvx_end

However, I am getting the following error:
Unable to use a value of type struct as an index.

Error in cvxprob/solve (line 435)
[ x, status, tprec, iters ] = shim.solve( At, b, c, cones, quiet, prec, solv.settings, eargs{:} );

Error in cvx_end (line 88)
solve( prob );

Error in C2_Psi_CvXSolver (line 15)
cvx_end

Can you please help? I am new to CVX.

Thanks and regards
Kali

2

I could resolve this issue by restarting MATLAB. However, I do have a theoretical question about extracting the solution x from the matrix X. I want to mention again that we rewrite the objective as max x’Ax = max trace (xx’A) = max trace(XA) (Relaxing the rank one constraint).

Is it sufficient to take any of the column vectors as the solution?

3

Please read Semidefinite programming mode — CVX Users' Guide

Your statement
X > hermitian_semidefinite(N);
is not in accordance with any of the options in the CVX Usets’ Guide.

You can do

cvx_begin sdp
variable X(N,N) complex hermitian
X >= 0

or

cvx_begin
variable X(N,N) complex hermitian
X == hermitian_semidefinite(N)

or

cvx_begin
variable X(N,N) hermitian semidefinite

As for the solution, if the solution X is not a rank one matrix, the SDP relaxation only provides an upper bound (because you are maximizing) on the optimal objective value of the original solution. if the solution X is a rank one matrix, you can recover a vector x such that X = x*x' by choosing an eigenvector of X, scaled by the corresponding eigenvalue…

4

My understanding is that we omit the Rank 1 constraint of an SDP problem to relax it to be convex. So, in that case, the solution of X = x*x’ will not be a rank 1 matrix in any case. So, in such a case, how do we extract x out of X? Will the solution (upper bound of course) be accurate if we pick the eigenvector of X?

5

Unless you have some special problem, the solution to the SDP relaxation is not guaranteed to be rank one. That’s an example of no free lunch to evade non-convexity.

if the solution to the SDP relaxation is not rank-one, you can’t recover an optimal solution to the non-relaxed problem, and you have produced an upper bound for the optimal (max) objective value, but don’t know the actual optimal objective value. In American slang, we’d say “tough boogies”.

You can look at http://dsp.ee.cuhk.edu.hk/eleg5481/Lecture%20notes/10-SDR/SDR_QCQP_EUSIPCO2011.pdf , for instance slide 15, for some ideas on how to approximate a solution to the original problem if the SDP relaxation is not rank one. Slide 15’s approximation iis to approximately recover the optimal solution based on largest eigenvalue and corresponding eigenvector. Other slides have other approximations. I have no idea how well these approximations work - I suppose that is problem-dependent.

6

Thank you. I’ll go through it.

7

Under what conditions will the solution X be all ones (solver output)?

8

It’s your problem. You should be telling us, not asking us.