Different solutions under different expressions of the same optimization problem

1

I have been trying to solve a problem whose MATLAB codes given below,

Dim = 4;
power = 1;

H = randn(Dim)+1jrandn(Dim);
H = (power / norm(H, ‘fro’)) * H;
H_s = randn(Dim)+1jrandn(Dim);
H_s_2 = H_s* H_s’;
Sgima_s = (power / norm(H_s_2, ‘fro’)) * H_s_2;
X = randn(Dim)+1j*randn(Dim);
X = (power / norm(X, ‘fro’)) * X;
I = eye(Dim);

P = 1;
rho = 0.2;
cvx_clear;
cvx_solver mosek
cvx_begin
variable WW_H(Dim, Dim) complex hermitian semidefinite;
maximize (log_det(I + Sgima_s * X * WW_H * X’)/log(2));
subject to
trace(WW_H) <= P;
log_det(I + H * WW_H * H’)/log(2) >= rho;
cvx_end

The codes above works well and give a reasonable answer.

However, if I change the objective function and one of the constraint into

maximize (log_det(I + X’ * Sgima_s * X * WW_H)/log(2));
subject to
trace(WW_H) <= P;
log_det(I + H’ * H * WW_H)/log(2) >= rho;

The CVX will give a totally different answer, i.e., WW_H = 1/Dim * I, a diagonal matrix.

I don’t know why does this happen, can anybody give an explanation?

2

Why are the objective function and 2nd constraint in the 2nd version equivalent to the 1st version? I don’t believe they are.

You performed a cyclic permutation of the 2nd (additive) term inside log_det. Perhaps you are confusing with trace, which is invariant to cyclic permutation of its argument.

And of course, even if you have equivalent formulations, you need to make sure you are not generating new random numbers for the input data, and therefore solving a different problem instance. And also, you would need to look at change in the optimal objective value, not in the argmax, due to the possibility of non-unique solutions.

3

Thank you for your kind reply, Mark.

Actually, the value of log_det(I + H * WW_H * H’) is the same as log_det(I + H’ * H * WW_H), as proved in the following link,

This means they are equivalent formulations. The random numbers for the input data are generated with fixed random seeds, for example, rng(1), and it makes sure the random numbers are the same.

It seems that the these two versions should be the same problems, but the CVX give totally different answers.

Is it a bug in CVX?

4

I + Sgima_s * X * WW_H * X' is Hermitian psd.

I + X' * Sgima_s * X * WW_H is not Hermitian. Therefore, CVX’s log_det evaluates the log_det of it to Inf.

So they are not equivalent in CVX. I presume the first version of the program is what you want. The 2nd version is essentially garbage, because it is evaluating log_det to Inf, for a somewhat subtle reason.

help log_det

log_det Logarithm of the determinant of an SDP matrix.
For a square matrix X, log_det(X) returns
LOG(DET(X))
if X is symmetric (real) or Hermitian (complex) and positive semidefinite,
and -Inf otherwise.

When used in a CVX model, log_det(X) causes CVX's successive 
approximation method to be invoked, producing results exact to within
the tolerance of the solver. Therefore, whenever possible, the use of
DET_ROOTN(X) is to be preferred, because the latter choice can be
represented exactly in an SDP. For example, the objective
    MAXIMIZE(log_det(X))
can be (and should be) replaced with
    MAXIMIZE(DET_ROOTN(X))
in fact, log_det(X) is implemented simply as N*LOG(DET_ROOTN(X)).

Disciplined convex programming information:
    log_det is concave and nonmonotonic; therefore, when used in
    CVX specifications, its argument must be affine.
5

Thank you so much, Mark! I appreciate you for your kindly help and patient reply.