0

A problem of the form was hinted at on an upcoming assignment:

$minimize$ $tr(P)$
$s.t.$
$A^TP+PA = -Q$,
$P=P^T>0$

It was hinted that the desired solution require the problem be transformed into a form similar to the one shown below and solved via KKT optimality conditions. Where the transformed constraints will be four equalities or inequalities.

$minimize$ $(C^TX)$
$s.t.$
$AX = b$


My question is how are these four transformed constraints found or derived?


---update---

Perhaps I am over complicating this. If $A$, $Q$ and $P$ are $2x2$, that would be four linear equalities of the form $Ax=b$. For $P=\begin{bmatrix}p_1&p_3\\p_3&p_2\end{bmatrix}$, would it be valid specify the problem as $minimize(p_1+p_2)$, since we want to minimize $trace(P)$? Then taking the 1st equality piecewise:

$(1)$ $2A_{11}p_1+2A_{21}p_3=-Q_{11}$
$(2)$ $A_{12}p_1+A_{21}p_2+(A_{11}p_1+A_{22})p_3=0$
$(3)$ $2A_{22}p_2+2A_{12}p_3=-Q_{22}$

And to define P as PSD:
$(4)$ $p_1 \geq 0$
$(5)$ $p_1p_2-p_3^2 \geq 0$

Then apply the KKT conditions to $min(p_1+p_2)$ and constraints 1-5, treating $p_1, p_2$ & $p_3$ as the variables for which to be solved?

If that is the case, why did the instructor hint that the problem should be transformed to $minimize(C^TX)$?

JDD
  • 1
  • why do you call the constraints of the original problem quadratic? – LinAlg Nov 28 '18 at 02:48
  • Are they not? Isn't the Lyapunov equality usually associated with the form $x^TPx$? – JDD Nov 28 '18 at 02:50
  • That's irrelevant to the immediate task at hand. The point is your problem in $P$ already has a linear objective, a set of linear equations in $P$, and a semidefinite constraint. – Michael Grant Nov 28 '18 at 02:56
  • $C^{T}X$ is a matrix rather than a scalar- are you actually meant to be minimizing $\mbox{tr}(C^{T}X)$? – Brian Borchers Nov 28 '18 at 05:01
  • Michael Grant, I think I understand. Are you saying that everything is already correct for applying KKT, similar to what I added to the original question? – JDD Nov 28 '18 at 05:03
  • $C^TX$ is a scalar. If $X$ is vector of length $n$, then $C$ is a vector of length $n$ such that $C^TX=\sum_{k=1}^{n} (C_kX_k)$ – JDD Nov 28 '18 at 05:12

0 Answers0