How can I solve this semidefinite relaxation problem in CVX?

Nonconvex
1

The original optimization problem is:

max trace(AX)/(trace(BX)+c)
s.t. diag(X)<=Y
and  rank(X)=1,X>=0

where X=ww’, w is a (10,1) complex vector, A,B are (10,10) matrix, c is a real scalar, Y is a real vector. Obviously, X is a symmetric semidefinite matrix.

In order to solve the problem in CVX, I use a semidefinite relaxation, and solve an equivalent problem:

max t
s.t. trace(X(A-tB))>=ct
and diag(X)<=Y
and X>=0

the code is here:

cvx_begin quiet
    variable X(10,10);
    X == semidefinite(10);
    variable t;
    maximize(t);
    Z = trace(X*(A-t*B))-c*t;
    subject to
        Z >= 0;
        diag(X) <= Y;
cvx_end

However, there’s always an error:

??? Error using ==> cvx.mtimes at 127
Disciplined convex programming error:
Invalid quadratic form: must be a scalar.

I’ve tried many other ways to modify the code. They didn’t work, though. I don’t know why. And please give me some suggestions to solve the problem. Thanks!

2

You probably want to solve the problem as a quasi-convex problem using bisection on t, which should then be fixed at each outer iteration. In the current formulation, you have
t as a variable, and the problem is correctly discarded as non-convex.

There are some filter-design examples in CVX that should give you the idea…

UPDATE:
You use your second formulation (which is not a relaxation, by the way, it’s an
equivalent problem). Suppose you know upper and lower bounds on t, respectively. Then you solve the problem for an intermediate value t; if the problem is feasible you increase
t, otherwise you decrease t. After repeating this for a number of steps, you know that the optimal t belongs to a sufficiently small interval.

3

I have used the bisection method. However, I don’t know how it works exactly. Is the maximum value of t solved the same with that of the objective function – trace(AX)/(trace(BX)+c) ??