SemiDefinite What?

This page contains definitions for SemiDefinite things like matrices, programs, etc.

SemiDefinite Matrices

A positive SemiDefinite matrix is a HermitianMatrix all of whose eigenvalues are nonnegative. Thus any symmetric matrix that has a 0 on the diagonal is a SemiDefinite matrix.

SemiDefinite Programming

The following is taken from page 9 of Cousot05VMCAI reference - see my bibtex.

Suppose you have a loop in a program where the values of the variable values at the start of the loop are denoted $$x_0 \in \mathbb{R}^{n $a n d t h e v a l u e s a t t h e e n d o f t h e l o o p a r e d e n o t e d$ x $w h e r e$ n $i s t h e n u m b e r o f v a r i a b l e s . T h e n$ x_k $i s t h e v a r i a b l e v a l u e s a f t e r t h e$ k}{th}$$ loop.

Let

$M (x) = M_{0} + \sum_{k = 1}^{m} x_{k} . M_{k}$

with symmetric matrices $(M_{k} = M_{k}^{⊤}$ , and positive semidefiniteness (can you say that?) defined as:

$$$M(x) \succeq 0 \equiv \forall X \in \mathbb{R}^{N : XM(x)X}{\top} \ge 0$$$

Somehow I believe that $M$ is an encoding of the constraints in the loop. It doesn't say that in Cousot05VMCAI, but that is what I think it means. Then the SemiDefinite programming optimization problem is to find a solution to the constraints:

$$$\left\{\begin{array}{l} \exists x \in \mathbb{R}^{m : M(x) \succeq 0 \\ Minimizing~~c}{\top} x \end{array}\right.$$$

where $c \in R^{m}$ is a real given vector and $M$ is called the linear matrix inequality