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 and the values at the end of the loop are denoted where is the number of variables. Then is the variable values after the loop.

Let

with symmetric matrices , and positive semidefiniteness (can you say that?) defined as:

Somehow I believe that 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:

where is a real given vector and is called the linear matrix inequality