I am trying to implement a convex optimization and I have the constraint $\mathbf{Tr}(A + BC^{-1}B^T)< K$ where $A\succeq0,B,C\succ0$ are the decision variables. Can it be transformed into a linear constraint or a linear matrix inequality?

  • 1
    $\begingroup$ Are there any other constraints on the variables, e.g. positive-semidefinite? $\endgroup$ – Rammus Nov 21 '20 at 12:31
  • $\begingroup$ As $A + B C^{-1} B^T$ is the Schur complement of the block matrix $\begin{pmatrix} A & B \\ B^T & - C \end{pmatrix}$. Although I don't see immediately how to relate the block matrix to the trace inequality without strengthening it to an operator inequality. $\endgroup$ – Rammus Nov 21 '20 at 12:36
  • $\begingroup$ Hello @Rammus. Yes, I can assume $A \succeq0$ and $C\succ0$. $\endgroup$ – Morad Nov 21 '20 at 18:10

The trace can also be written as

$$ \mathbf{Tr}(A + B\,C^{-1}B^\top) = \sum_{i=1}^n e_i^\top (A + B\,C^{-1}B^\top)\,e_i, \tag{1} $$

with $n$ such that $A \in \mathbb{R}^{n\times n}$ and $e_i$ the $i$th column of an $n \times n$ identity matrix. By introducing intermediate scalar variables $\alpha_i$ one can write the initial inequality in an indirect way by using

\begin{align} e_i^\top (A + B\,C^{-1}B^\top)\,e_i &< \alpha_i, \forall\,i = 1 \dots n, \tag{2} \\ \sum_{i=1}^n \alpha_i &< K. \tag{3} \end{align}

The inequality from $(3)$ is already a linear inequality. The inequality from $(2)$ can be formulated as linear (matrix) inequality by using the Schur complement. It can be noted that applying the Schur complement to each inequality from $(2)$ does require the additional assumptions that $C$ is positive definite.

  • $\begingroup$ Thanks Kwin. I can assume $A\succeq0$ and $C\succ0$ so your answer is perfect. I wanted to ask whether your reply is the easiest way to implement in CVX or that there is another form. Thanks again. $\endgroup$ – Morad Nov 21 '20 at 18:12
  • $\begingroup$ @Morad What is CVX? $\endgroup$ – Kwin van der Veen Nov 21 '20 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.