12
$\begingroup$

I am trying to understand the KKT conditions for LMI constraints in order to solve my original question in KKT conditions for $\max \log \det(X)$ with LMI constraints.

In the meantime, I found a much simpler problem that does not go through when extending the KKT conditions from scalar case to the vector case. The problem is \begin{align} & \max_{X\succeq0} \log \det(I + B XB^T)\\ \\ & s.t. \begin{pmatrix} AXA^T - X + Q & AXB^T \\ BXA^T& I + BXB^T \end{pmatrix}\succeq0, \end{align} and the goal is to show $(A - K(X^\ast)B)(A-K(X^\ast)B )^T\prec I$ where $K(X)\triangleq AXB^T(I + BXB^T)^{-1}$. This is an important consequence in control theory since it implies that the optimal solution $X^*$ is a stabilizing solution for the corresponding system. From here, I elaborate on my modest progress.

The constraints can be either written as a "big LMI": \begin{align} R(X)&=\begin{pmatrix} AXA^T - X + Q & AXB^T &0\\ BXA^T& I + BXB^T &0 \\ 0&0&X \end{pmatrix}\succeq 0 \end{align} or \begin{align} AXA^T-X+Q - AXB^T(I + BXB^T)^{-1}BXA^T\succeq0\\\ X\succeq0, \end{align} where we used the Schur complement along with $I+BXB^T\succ0$.

The scalar case:
By the KKT stationarity condition \begin{align}\label{eq:lagra_1} 0&= -B^2 -\lambda_1+ \lambda_2\{ 1 - A^2 + 2 A^2B^2X(I + BXB^T)^{-1} - A^2B^4X^2(I + BXB^T)^{-2}\} \end{align} for $\lambda_1,\lambda_2\ge0$ and correspond to the constraints. If $B\neq0$, it follows that $\lambda_2>0$ and \begin{align} 0&<1 - A^2 + 2 A^2B^2X^\ast(I + BX^\ast B^T)^{-1} - A^2B^4X^{2\ast}(I + BX^\ast B^T)^{-2}\\ &= 1 - (A - K(X^\ast)B)^2 \end{align} where $K(X)$ is defined above. If $B=0$, the stability condition holds only if $A<1$. The combination of this conditions lead to the following known result: there exists a stabilizing solution $X$ iff $(A,B)$ is detectable.

The vector case using the Schur complement constraint:
Following a great advice from @LinAlg in the comments, I could make the following progress. The Lagrangian is: \begin{align} L(X,\Lambda_1,\Lambda_2)= - \log \det(I + B XB^T) - \text{Tr}(X\Lambda_1) - \text{Tr}((AXA^T-X+Q - AXB^T(I + BXB^T)^{-1}BXA^T) \Lambda_2). \end{align}

From the stationarity condition, (is the derivative correct?) \begin{align} 0&=\frac{\partial L(X,\Lambda_1,\Lambda_1)}{\partial X}\\ &= - \text{det}(I+BX B^T)\text{Tr}((I+BX B^T)^{-1}BB^T) - \Lambda_1 \\ &\ \ + (I - A^TA + A^TKB + B^TK^TA - B^TK^TKB) \Lambda_2 \end{align} with $\Lambda_1,\Lambda_2\succeq0$. By the primal feasibility constraint $X\succeq0$, the first summand is positive so that \begin{align} (I - (A-KB)^T(A-KB))\Lambda_2 \succeq 0 \end{align} The complementary slackness conditions read as: \begin{align} 0&= \Lambda_1X\\ 0&= (AXA^T-X+Q - AXB^T(I + BXB^T)^{-1}BXA^T))\Lambda_2\\ &= [(A-KB)X(A-KB)^T - X + Q + KK^T ]\Lambda_2\\ \end{align} I do not know how to proceed from here, but I try to enlighten when I am aiming to arrive. A necessary condition for the existence of stabilizing solution is detectability, i.e., if $Ax = \lambda x$ for a vector $x$ and $|\lambda|\ge1$ then $Bx\neq0$.
Let's try to show this fact using contradiction: Assume there exists a vector $x\neq0$ such that $Ax = \lambda x$ and $Bx\neq0$ with $|\lambda|\ge1$. We can now pre- and post-multiplying the stationarity condition with $x^T$ and $x$ and have \begin{align} 0&= - y^Ty -x\Lambda_1 - x^T( )\Lambda_2x \end{align}

The vector case using the big LMI:
Without loss of generality, the dual variable is \begin{align} Z=\begin{pmatrix} S & U&0\\ U^T & T&0\\ 0&0&W \end{pmatrix}. \end{align} The Lagrangian in this case is: \begin{align} L(X,Z)&= - \log \det(I + B XB^T) - \text{Tr}(R(X)Z). \end{align} The KKT stationarity condition gives: \begin{align} 0&= - \text{det}(I+BX B^T)\text{Tr}((I+BX B^T)^{-1}BB^T) \\& \ \ -\text{Tr}( ASA^T - S + B^TU^TA + A^TUB + B^TTB + W ) \end{align} and the complementary slackness condition $R(X)Z=0$ simplifies to: \begin{align} 0&= (AXA^T - X + Q)S + AXB^T U^T\\ 0&= (AXA^T - X + Q)U + AXB^T T\\ 0&= BXA^T S + (I+BXB^T)U^T\\ 0&= BXA^T U + (I+BXB^T)T\\ 0&= XW \end{align}

If $B=I$, it follows that $S\succ0$ (Assume $Sx=0$ for some $x$ and conclude that $x=0$). For the general case, $Sx=0$ implies $Bx=0 \& \& Wx=0$.

$\endgroup$
3
  • 1
    $\begingroup$ you just add $-\text{Tr}(\Lambda(AXA^T-X+Q - AXB^T(I + BXB^T)^{-1}BXA^T))$ to the Lagrangian $\endgroup$ – LinAlg Feb 19 at 3:33
  • 1
    $\begingroup$ That is only true if it holds for all $B \succeq 0$, not just for one specific $B$. You can write $B=UU^T$ and use the cyclic property of the trace to simplify the left hand side to $\sum_{i=1}^p u_i^T (I - (A-BK)(A-BK)^T) u_i$. $\endgroup$ – LinAlg Feb 19 at 21:21
  • $\begingroup$ A simpler problem was solved by @LinAlg in <math.stackexchange.com/questions/4034735/…>. I am updating my progress, feel free to contribute. $\endgroup$ – Morad Feb 22 at 7:00

Your Answer

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

Browse other questions tagged or ask your own question.