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$)?
$\begingroup$
$\endgroup$
13
-
$\begingroup$ 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 $\endgroup$– Johan LöfbergMar 11, 2020 at 18:14
-
$\begingroup$ @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 $\endgroup$– user2348674Mar 11, 2020 at 18:24
-
1$\begingroup$ 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) $\endgroup$– Johan LöfbergMar 11, 2020 at 18:50
-
1$\begingroup$ ..."with a linear objective and the convex constraint" $\endgroup$– Johan LöfbergMar 11, 2020 at 19:04
-
1$\begingroup$ Don't you get a linear objective with that form too? $\endgroup$– Johan LöfbergMar 12, 2020 at 6:37
|
Show 8 more comments
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered Mar 12, 2020 at 18:08
-
$\begingroup$ 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? $\endgroup$ Mar 12, 2020 at 18:43
-
1$\begingroup$ 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. $\endgroup$ Mar 12, 2020 at 19:34