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.

$\endgroup$

migrated from mathoverflow.net May 30 '18 at 10:41

This question came from our site for professional mathematicians.

  • 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 '18 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 '18 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 '18 at 12:58
  • $\begingroup$ I work with C language so the solver that seems perfect is Csdp $\endgroup$ – RàMi May 30 '18 at 13:04
  • $\begingroup$ Oh my bad, I somehow assumed matlab immediately. Sorry about that. $\endgroup$ – percusse May 30 '18 at 18:09
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$.

$\endgroup$
  • $\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 '18 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 '18 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 '18 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 '18 at 18:51

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.