# Converting a quadratically constrained optimization problem into a standard semidefinite program

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$$)?

• It looks like you already made a variable transformation. What is the original objective and problem definition (i.e. when you insert Y into the objective and simplify)? For scalars it simplifies to a linear expression, which would mean you probably have a linear objective with a convex quadratic inequality Mar 11, 2020 at 18:14
• @JohanLöfberg No this is the original form of the problem formulation itself, without any transformation of variables. But even when X and Y are scalars rather than matrices, this will give a quadratic objective with a quadratic constraint, unless I'm missing something Mar 11, 2020 at 18:24
• As far as I can tell the objective simplifies to $tr X^TQ\Lambda /2$, hence you effectively have a problem with a linear constraint and the convex constraint $-\frac{1}{2}R^{-1}Q \Lambda X^T - X \Lambda X^T \succeq 0$ (which you can write as a linear semidefinite constraint using a Schur complement) Mar 11, 2020 at 18:50
• ..."with a linear objective and the convex constraint" Mar 11, 2020 at 19:04
• Don't you get a linear objective with that form too? Mar 12, 2020 at 6:37

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.

• Thanks, I just edited the problem statement using your suggested reformulation. Does the Schur complement that I carried out above now turns the problem into an SDP? Mar 12, 2020 at 18:43
• It involves a semidefinite constraint, hence it is by definition amenable to semidefinite programming, Even better, it is linear, and thus solvable using a plethora of available SDP solvers. Mar 12, 2020 at 19:34