Converting a quadratically constrained optimization problem into a standard semidefinite program

convex optimizationoptimizationqcqpschur-complementsemidefinite-programming

I have a constrained matrix optimization problem as follows
\begin{align}
\max\limits_{X,Y} \;\; &tr\Big( X^T B X \Lambda \Big) + tr\Big( BY\Big) + tr\Big( X^T C \Lambda \Big) \\
\text{subject to} \;\; &-\frac{1}{2}R^{-1}Q \Lambda X^T = X \Lambda X^T + Y \\
& Y \;\; \text{is symmetric positive-semi-definite}
\end{align}

where $R$ is symmetric and $\Lambda$ is symmetric and positive-semi-definite. I can plug in the expression for $Y$ into the objective to get a linear objective function. Moreover, the equality constraint can be posed as the following PSD constraint: $-\frac{1}{2}R^{-1}Q\Lambda X^T – X \Lambda X^T \succeq 0$. Using a Schur complement I can reformulate the constraint $-\frac{1}{2}R^{-1}Q\Lambda X^T – X \Lambda X^T \succeq 0$ as the following PSD constraint:
\begin{align}
\left[
\begin{array}{ll}
I & \Lambda^{1/2} X^T \\
X \Lambda^{1/2} & -\frac{1}{2}R^{-1}Q\Lambda X^T
\end{array}
\right] \succeq 0
\end{align}

Does this constraint convert the initial program into an SDP (in addition to imposition of the symmetry of $R^{-1}Q\Lambda X^T$ to ensure symmetry of $Y$)?

Best Answer

After inserting the definition of $Y$in the objective and simplifying, the objective simplifies to $tr\Big( X^T C \Lambda - \frac{1}{2}BR^{-1}Q\Lambda ^T X^T \Big)$. The constraint $\frac{1}{2}BR^{-1}Q\Lambda ^T X^T - X\Lambda X^T \succeq 0$ is reformulated using a Schur complement.

Using a tool such as YALMIP (disclaimer, developed by me) and an SDP solver, a model could then be

X = sdpvar(n,m,'full');
Z = sdpvar(n);
Model = [Z == .5*B*inv(R)*Q*Lambda'*X', [Z X;X' inv(Lambda)] >= 0]
Objective = trace(X'*C*Lambda - .5*B*inv(R)*Lambda*X');
optimize(Model,Objective);

If $\Lambda$ is singular, you factorize it as $\Lambda = SS^T$ and change the Schur complement accordingly.

Related Question