1
$\begingroup$

$\DeclareMathOperator{\Tr}{Tr}\DeclareMathOperator*{\argmax}{\arg\!\max}$Consider the following semidefinite program (SDP) $$ \begin{aligned} \min_V \quad & \Tr(V) \\ \textrm{s.t.} \quad & AVB + CVD + Q \succeq 0 \\ \quad & V \succeq 0 \end{aligned} \tag{1} $$ where $V \in \mathbb R^{n \times n}, A \in \mathbb R^{m \times n}, B \in \mathbb R^{n \times m}, C \in \mathbb R^{m \times n},D \in \mathbb R^{n \times m}$, and $Q \in \mathbb R^{m \times m} \succeq 0$. The solution to this problem is trivial, but this is a minimal example of a larger and more complex problem that I have a question about. More specifically, how can I convert the problem in $(1)$ into the following equivalent standard form of an SDP? $$ \begin{aligned} \min_x \quad & c^Tx \\ \textrm{s.t.} \quad & F_0 + x_1F_1 + \cdots + x_mF_m \succeq 0 \end{aligned} \tag{2} $$ where $F_0,\dots,F_m$ are symmetric matrices, $c \in \mathbb R^m$, and $x \in \mathbb R^m$. That is, how can I relate $x, c,$ and the matrices $F_0,\dots,F_m$ in $(2)$ to the matrices $V, A, B, C, D,$ and $Q$ given in $(1)$? The reason I'm interested in this conversion is that the standard form in $(2)$ is more amenable to further analysis than the form given in $(1)$.

$\endgroup$

1 Answer 1

0
$\begingroup$

$\DeclareMathOperator{\Tr}{Tr}\DeclareMathOperator*{\argmax}{\arg\!\max}$We transform the problem in $(1)$ into the problem in $(2)$ as follows. First, for $(i,j) \in \{(k,\ell) \mid (k,\ell) \in \{1,\dots,n\}^2, k \leq \ell\}$, let $E_{ij} \in \mathbb R^{n \times n}$ be the matrix with a $1$ in the $(i,j)$ and $(j,i)$ positions and $0$'s everywhere else. When $i = j$, $E_{ii}$ is the matrix with a $1$ in the $(i,i)$ position and $0$'s everywhere else. For example, when $n = 2$, we have the following 3 matrices $$ \begin{align} E_{11} &= \begin{bmatrix}1 & 0 \\ 0 & 0\end{bmatrix} \\ E_{12} &= \begin{bmatrix}0 & 1 \\ 1 & 0\end{bmatrix} \\ E_{22} &= \begin{bmatrix}0 & 0 \\ 0 & 1\end{bmatrix} \end{align} $$ Note that these 3 matrices form a basis for the vector space of $2 \times 2$ symmetric positive semi-definite matrices. More generally, for arbitrary $n$, the $n + \frac{n(n-1)}{2} = \frac{n(n+1)}{2}$ matrices $E_{11},E_{12},\dots,E_{1n},E_{22},E_{23},\dots,E_{2n},\dots,E_{(n-1)(n-1)},E_{(n-1)n},E_{nn}$ form a basis for the vector space of $n \times n$ symmetric positive semi-definite matrices. Therefore, every $V \succeq 0 \in \mathbb R^{n \times n}$ can be decomposed as $$ \begin{align} V &= \sum_{i=1}^n \sum_{j=i}^n v_{ij}E_{ij} \tag{3} \\ &= \sum_{j=1}^n v_{1j}E_{1j} + \sum_{j=2}^n v_{2j}E_{2j} + \cdots + \sum_{j=n-1}^n v_{(n-1)j}E_{(n-1)j} + \sum_{j=n}^n v_{nj}E_{nj} \end{align} $$ where $v_{ij}$ is the element of $V$ in the $(i,j)$ position. We first substitute this expression for $V$ into the objective function in $(1)$ to get $$ \begin{align} \Tr(V) &= \Tr\left(\sum_{i=1}^n \sum_{j=i}^n v_{ij}E_{ij}\right) \\ &= \sum_{i=1}^n \sum_{j=i}^n v_{ij}\Tr\left(E_{ij}\right) \tag{4} \end{align} $$ Note that, when $i \neq j$, $\Tr(E_{ij}) = 0$, and when $i = j$, $\Tr(E_{ij}) = 1$. So, the expression in $(4)$ above simplifies to $$ \begin{align} \Tr(V) &= \sum_{i=1}^n v_{ii}\Tr\left(E_{ii}\right) \\ &= \sum_{i=1}^n v_{ii} \end{align} $$ Therefore, to relate the objective function in the problem in $(1)$ to the objective function in the problem in $(2)$, we let $$ \begin{align} x = \begin{bmatrix}v_{11} \\ v_{12} \\ \vdots \\ v_{1n} \\ v_{22} \\ v_{23} \\ \vdots \\ v_{2n} \\ \vdots \\ v_{(n-1)(n-1)} \\ v_{(n-1)n} \\ v_{nn}\end{bmatrix}, \quad c = \begin{bmatrix}1 \\ 0 \\ \vdots \\ 0 \\ 1 \\ 0 \\ \vdots \\ 0 \\ \vdots \\ 1 \\ 0 \\ 1\end{bmatrix} \end{align} $$ Note that $x \in \mathbb R^{\frac{n(n+1)}{2}}$ and $c \in \mathbb R^{\frac{n(n+1)}{2}}$. Next, we relate the constraints in the problem in $(1)$ to the constraint in the problem in $(2)$ as follows. We substitute the expression for $V$ given in $(3)$ into the first constraint in $(1)$ to get $$ \begin{align} AVB + CVD + Q &\succeq 0 \\ A\left(\sum_{i=1}^n \sum_{j=i}^n v_{ij}E_{ij}\right)B + C\left(\sum_{i=1}^n \sum_{j=i}^n v_{ij}E_{ij}\right)D + Q &\succeq 0 \\ \left(\sum_{i=1}^n \sum_{j=i}^n v_{ij}AE_{ij}B\right) + \left(\sum_{i=1}^n \sum_{j=i}^n v_{ij}CE_{ij}D\right) + Q &\succeq 0 \\ \sum_{i=1}^n \sum_{j=i}^n v_{ij}\left(AE_{ij}B + CE_{ij}D\right) + Q &\succeq 0 \tag{5} \end{align} $$ Similarly, we apply this process to the second constraint in $(1)$ to get $$ \begin{align} V &\succeq 0 \\ \sum_{i=1}^n \sum_{j=i}^n v_{ij}E_{ij} &\succeq 0 \tag{6} \end{align} $$ We can combine the constraints in $(5)$ and $(6)$ together into one constraint as follows. $$ \begin{align} \sum_{i=1}^n \sum_{j=i}^n v_{ij}\left(AE_{ij}B + CE_{ij}D\right) + Q \succeq 0 \ \wedge \ \sum_{i=1}^n \sum_{j=i}^n v_{ij}E_{ij} \succeq 0 &\iff \begin{bmatrix}\sum_{i=1}^n \sum_{j=i}^n v_{ij}\left(AE_{ij}B + CE_{ij}D\right) + Q & 0 \\ 0 & \sum_{i=1}^n \sum_{j=i}^n v_{ij}E_{ij} \end{bmatrix} \succeq 0 \\ &\iff \sum_{i=1}^n \sum_{j=i}^n v_{ij} \begin{bmatrix}AE_{ij}B + CE_{ij}D & 0 \\ 0 & E_{ij} \end{bmatrix} + \begin{bmatrix}Q & 0 \\ 0 & 0\end{bmatrix} \succeq 0 \tag{7} \end{align} $$ We then let $$ F_0 = \begin{bmatrix}Q & 0 \\ 0 & 0\end{bmatrix} $$ and for $(i,j) \in \{(k,\ell) \mid (k,\ell) \in \{1,\dots,n\}^2, k \leq \ell\}$, we let $$ F_{ij} = \begin{bmatrix}AE_{ij}B + CE_{ij}D & 0 \\ 0 & E_{ij} \end{bmatrix} $$ such that the constraint in $(7)$ becomes $$ \sum_{i=1}^n \sum_{j=i}^n v_{ij} F_{ij} + F_0 \succeq 0 $$ as desired.


The decomposition of $V$ into its constituent basis matrices was adapted from section 2.1.2, titled "Linear equality constraints", in the book

S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan, Linear matrix inequalities in system and control theory. Society for Industrial and Applied Mathematics, 1994. doi: 10.1137/1.9781611970777.

A similar decomposition can be found in remark 1.24 in section 1.4.1 in the lecture notes titled "Linear Matrix Inequalities in Control" by Carsten Scherer and Siep Weiland (2015) (available here).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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