1
$\begingroup$

I am trying to use CSDP and am struggling with it. Consider, for example, the following semidefinite program

$$\begin{array}{ll} \text{minimize} & 0\\ \text{subject to} & Q - A' Q A - \varepsilon I \succeq 0\\ & Q \succ 0\end{array}$$

where $A$ is a given matrix with spectral radius $\rho(A) < 1$. I need a Lyapunov function.

The condition $\rho(A) < 1$ the existence of a matrix norm $\| \cdot \|$ such that $\|A\| < 1$. Let $Q$ such that $Q \succ 0$ and $Q - A' Q A \succ 0$ (exists since $\rho(A) < 1$). I am wondering how one represents it in the standard CSDP format:

$$\begin{array}{ll} \text{maximize} & \mbox{tr} (C X)\\ \text{subject to} & \mbox{tr} (A_i X) = b_i, \qquad i \in \{1,2,\dots,n\}\\ & X \succeq 0\end{array}$$

Consider, for example, the semidefinite program proposed by Prof. Borchers.

Improve this question
$\endgroup$
19
  • 1
    $\begingroup$ If you use MATLAB, I recommend you use YALMIP, then you don't have to worry about standard form of the solver. YALMIP converts your inputs into whatever form is needed by the solver. YALMIP will let you specify CSDP, as solver, as well as many other SDP and non-SDP solvers. Or for (convex) SDPs, another somewhat simpler alternative is CVX, but that provides you fewer sober options (no CSDP, but does do MOSEK, SeDuMi, SDPT3). $\endgroup$
    – Mark L. Stone
    May 29, 2018 at 0:01
  • $\begingroup$ Of the various inequalities in your problem statement, which are $\succeq$ and which are element-wise constraints $\geq$? $\endgroup$
    – Brian Borchers
    May 29, 2018 at 4:12
  • $\begingroup$ As @MarkL.Stone mentioned Yalmip is designed specifically for this reason such that you don't worry about the internal syntax of the solver. $\endgroup$
    – percusse
    May 30, 2018 at 12:58
  • $\begingroup$ I work with C language so the solver that seems perfect is Csdp $\endgroup$
    – RàMi
    May 30, 2018 at 13:04
  • $\begingroup$ Oh my bad, I somehow assumed matlab immediately. Sorry about that. $\endgroup$
    – percusse
    May 30, 2018 at 18:09

1 Answer 1

Reset to default
1
$\begingroup$

The question is a bit unclear here, so I'll start by restating the problem. The OP has a matrix

$A=\left[ \begin{array}{cc} 0.5 & -0.4 \\ 1 & -0.5 \end{array} \right]$

and wants to find a symmetric matrix $Q$ such that

$Q-A^{T}QA \succeq 0$

$Q \succ 0$

The problem here is that $Q \succ 0$ isn't an SDP constraint. We could put in $Q \succeq 0$, but $Q=0$ is a solution to

$Q-A^{T}QA \succeq 0$

$Q \succeq 0$

and we want to constrain $Q$ to not be singular. In the comments, the OP suggested solving the SDP

$\min t$

$Q-A^{T}QA \succeq 0$

$tI-Q-A^{T}QA \succeq 0$

$Q \succeq 0$.

but $t=0$, $Q=0$ is an optimal solution to this problem too!

An alternative SDP formulation that does ensure that $Q \succ 0$ is

$\min 0$

$Q-A^{T}QA - \epsilon I \succeq 0$

$Q \succeq 0$

where $\epsilon$ is a small positive constant (I'll use $\epsilon=0.01$ in the following.) Because $A^{T}QA$ is positive semidefinite and $\epsilon I$ is positive definite, these constraints enforce $Q \succ 0$ (In fact, $Q \succeq \epsilon I$, so the smallest eigenvalue of $Q$ will be greater than or equal to $\epsilon$.)

Modeling packages like CVX and Yalmip can easily turn this formulation into an SDP that can be solved by a variety of solvers such as SDPT3, SeDuMi, CSDP, SDPA, etc. However, the OP wants to see how to turn this into a standard form SDP

$\max \mbox{tr}(CX) $

$\mbox{tr}(A_{i}X)=b_{i}\;\; i=1, 2, \ldots, m$

$X \succeq 0$

The first step is to introduce a slack variable $S$, and write the problem as

$\max 0$

$Q-A^{T}QA-S=\epsilon I$

$S \succeq 0$

$Q \succeq 0$.

The constraint $Q-A^{T}QA-S=\epsilon I$ is linear in the elements of $Q$, although this might not be immediately obvious. The key observation is that

$A^{T}QA=\sum_{i=1}^{2} \sum_{j=1}^{2} Q_{i,j} A_{i,:}^{T}A_{j,:}$

Since the matrices in $Q-A^{T}QA-S$ are all symmetric, we need 3 linear equality constraints for the (1,1), (1,2) and (2,2) elements of the matrix equality.

$0.75Q_{1,1}-0.5Q_{1,2}-0.5Q_{2,1}-1.0Q_{2,2}-S_{1,1}=\epsilon$

$0.2Q_{1,1}+1.25Q_{1,2}+0.4Q_{2,1}+0.5Q_{2,2}-S_{1,2}=0$

$-0.16Q_{1,1}-0.2Q_{1,2}-0.2Q_{2,1}+0.75Q_{2,2}-S_{2,2}=\epsilon$

The constraints must be in symmetric form, so we rewrite the second constraint as

$0.2Q_{1,1}+0.825Q_{1,2}+0.825Q_{2,1}+0.5Q_{2,2}-0.5S_{1,2}-0.5S_{2,1}=0$

Finally, we embed $Q$ and $S$ into a block diagonal matrix

$X=\left[ \begin{array}{cc} Q & 0 \\ 0 & S \\ \end{array} \right].$

The problem becomes

$\max \mbox{tr}(CX)$

$\mbox{tr}(A_{1}X)=\epsilon$

$\mbox{tr}(A_{2}X)=0$

$\mbox{tr}(A_{3}X)=\epsilon$

$X \succeq 0$

where

$C=0$

$A_{1}=\left[ \begin{array}{cccc} 0.75 & -0.5 & 0 & 0 \\ -0.5 & -1.0 & 0 & 0 \\ 0 & 0 & -1.0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{array} \right]$

$A_{2}=\left[ \begin{array}{cccc} 0.2 & 0.825 & 0 & 0 \\ 0.825 & 0.5 & 0 & 0 \\ 0 & 0 & 0 & -0.5 \\ 0 & 0 & -0.5 & 0 \\ \end{array} \right]$

$A_{3}=\left[ \begin{array}{cccc} -0.16 & -0.2 & 0 & 0 \\ -0.2 & +0.75 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & -1.0 \\ \end{array} \right]$

In SDPA format, the problem is

3
2
2 2
0.01 0 0.01
1 1 1 1 0.75
1 1 1 2 -0.5
1 1 2 2 -1.0
1 2 1 1 -1.0
2 1 1 1 0.2
2 1 1 2 0.825
2 1 2 2 0.5
2 2 1 2 -0.5
3 1 1 1 -0.16
3 1 1 2 -0.2
3 1 2 2 +0.75
3 2 2 2 -1.0

I solved this problem using CSDP and obtained

$Q=\left[ \begin{array}{cc} 38.5170 & -11.8166 \\ -11.8166 & 24.3371 \\ \end{array} \right]$

$S=\left[ \begin{array}{cc} 16.3572 & 0.3746 \\ 0.3746 & 16.8067 \\ \end{array} \right]$

It's easy to verify that $Q$ has all of the required properties.

There are infinitely many solutions to this problem- there is no reason to expect that all solvers will return the same solution.

You could also adjust the objective function or add additional constraints to push the solution in some desired direction. For example, you might want to minimize the maximum eigenvalue of $Q$ or minimize the sum of the eigenvalues of $Q$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I already had a problem like this, but I did it with yalmip what straddles me, the fact that you did that $ \min \;\; t $ $ Q - A^{T}QA \succeq 0$ $tI- Q-A^{T}QA- \succeq 0$ $ Q \succ 0$ instead of that $ \min \;\; t $ $ tId-Q \succeq 0$ $ Q-A^{T}QA-\varepsilon Id \succeq 0$ $ Q \succ 0$ besides that would be what the general formula applied for any $A$(like $A^{d \times d}$, $Q^{d}$, $S^{d}$), and for what reason $Q-A^{T}QA-S$ are all symmetric so that you rewrite the second constraint as $0.2Q_{1,1}+0.825Q_{1,2}+0.825Q_{2,1}+0.5Q_{2,2}-0.5S_{1,2}-0.5S_{2,1}=0$ $\endgroup$
    – M.Sonia
    Jul 23, 2018 at 14:02
  • $\begingroup$ @M.Sonia Its equivalent to &P_{1,1} \left[ E_{1,1} - \left( A_{1,1} A_{1,1} E_{1,1}+ A_{1,1} A_{1,2} E_{1,2}+A_{2,1} A_{1,1} E_{2,1} +A_{1,2} A_{1,2} E_{2,2} \right) \right] &=&\varepsilon then for example $P_{1,1} \left[ E_{1,1} - \left( A_{1,1} A_{1,1} E_{1,1}+ A_{1,1} A_{1,2} E_{1,2}+A_{2,1} A_{1,1} E_{2,1} +A_{1,2} A_{1,2} E_{2,2} \right) \right] =\varepsilon $ $\endgroup$
    – RàMi
    Jul 25, 2018 at 12:43
  • $\begingroup$ thereafter $E_{1,1} \left[ P_{1,1} \left(1- A_{1,1} A_{1,1}\right)- P_{1,2} \left( A_{1,1} A_{2,1}\right) -P_{2,1} \left( A_{2,1} A_{1,1}\right) -P_{2,2} \left(A_{2,1} A_{2,1}\right) \right]-S_{1,1} =\varepsilon$ $\endgroup$
    – RàMi
    Jul 25, 2018 at 12:44
  • $\begingroup$ Q is assumed to be symmetric in the original questions. Thus $A^{T}QA$ is symmetric. $Q$ and $S$ are symmetric matrix variables. $\endgroup$
    – Brian Borchers
    Jul 25, 2018 at 18:51

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.