Loewner partial order

The Löwner partial order or Loewner partial order is a special partial order on the vector space of the symmetric real matrices, which makes it an ordered vector space . It is used in particular in semidefinite programming , but also in optimal test planning . ${\displaystyle n\times n}$

definition

The real vector space of the symmetric real matrices is given ${\displaystyle n\times n}$

${\displaystyle S^{n}:=\{A\in \mathbb {R} ^{n\times n}\,|\,A^{T}=A\}.}$

Here the transposed matrix denotes the matrix . If one defines the Loewner-half order by ${\displaystyle A^{T}}$ ${\displaystyle A}$ ${\displaystyle \geq _{L}}$

${\displaystyle A\geq _{L}0\iff A{\text{ ist positiv semidefinit }}}$

and

${\displaystyle A\geq _{L}B\iff A-B\geq _{L}0\iff A-B{\text{ ist positiv semidefinit }}}$

such as

${\displaystyle B\leq _{L}A\iff A\geq _{L}B}$.

As an alternative to the formulation that a positive semi-definite matrix should be, there is also the requirement that all or all eigenvalues ​​of the matrix should be greater than or equal to zero. However, all three formulations are equivalent. ${\displaystyle A}$ ${\displaystyle x^{T}Ax\geq 0}$ ${\displaystyle x\in \mathbb {R} ^{n}}$ ${\displaystyle \lambda _{i}}$ ${\displaystyle A}$

Construction using an order cone

Alternatively, the semidefinite cone (the set of all positive semidefinite matrices in ) can also be interpreted as an order cone . The order induced by this cone is then the Loewner partial order. ${\displaystyle S_{+}^{n}}$ ${\displaystyle S^{n}}$

Construction as a generalized inequality

Since the semidefinite cone is actually a true cone , one can consider the generalized inequality it defines . It again corresponds to the Loewner partial order.

example

We consider the matrices

${\displaystyle A={\begin{pmatrix}12&2\\2&8\end{pmatrix}},\,B={\begin{pmatrix}5&1\\1&3\end{pmatrix}},\,C={\begin{pmatrix}1&2\\2&-1\end{pmatrix}}}$.

All three are symmetrical and real. A calculation of the eigenvalues ​​or the application of the Gerschgorin circles yields that both and are positive are definite, so it is ${\displaystyle A}$ ${\displaystyle B}$

${\displaystyle A\geq _{L}0{\text{ und }}B\geq _{L}0}$.

One calculates

${\displaystyle A-B={\begin{pmatrix}7&1\\1&5\end{pmatrix}}}$,

so this matrix is ​​also positive definite, since its eigenvalues ​​(according to the Gerschgorin circles) lie in the interval and must therefore always be positive. So is . ${\displaystyle [4,8]}$ ${\displaystyle A\geq _{L}B{\text{ bzw. }}B\leq _{L}A}$

In the case of the matrix , the Gerschgorin circles do not provide a definitive statement; a calculation gives the eigenvalues . So it is indefinite, neither is nor . This is because it is only a partial order: two elements (here and the zero matrix) do not necessarily have to be comparable with each other. ${\displaystyle C}$ ${\displaystyle \lambda _{1,2}=\pm {\sqrt {5}}}$ ${\displaystyle C}$ ${\displaystyle C\geq _{L}0}$ ${\displaystyle C\leq _{L}0}$ ${\displaystyle C}$

properties

Since the Loewner partial order turns the vector space of the real symmetric matrices into an ordered vector space, the following applies

• ${\displaystyle A\leq _{L}A}$for everyone , that is, is reflexive . ${\displaystyle A\in S^{n}}$ ${\displaystyle \leq _{L}}$
• From and follows for all , that is, is transitive . ${\displaystyle A\leq _{L}B}$ ${\displaystyle B\leq _{L}C}$ ${\displaystyle A\leq _{L}C}$ ${\displaystyle A,B,C\in S^{n}}$ ${\displaystyle \leq _{L}}$
• From follows for all , that is, is compatible with the addition. ${\displaystyle A\leq _{L}B}$ ${\displaystyle A+C\leq _{L}B+C}$ ${\displaystyle A,B,C\in S^{n}}$ ${\displaystyle \leq _{L}}$
• From follows for all and , that is, is compatible with respect to the multiplication by positive scalars. ${\displaystyle A\leq _{L}B}$ ${\displaystyle \lambda A\leq _{L}\lambda B}$ ${\displaystyle A,B\in S^{n}}$ ${\displaystyle \lambda \in \mathbb {R} _{+}}$ ${\displaystyle \leq _{L}}$

Since the semidefinite cone is a pointed cone , it is also antisymmetric , that is, if and , it must be. The Loewner partial order is therefore a strict order. ${\displaystyle \leq _{L}}$ ${\displaystyle A\leq _{L}B}$ ${\displaystyle B\leq _{L}A}$ ${\displaystyle A=B}$

use

The so-called matrix-monotonic functions are defined using the Loewner half-order . They are exactly the monotonous images from to . ${\displaystyle (S^{n},\leq _{L})}$ ${\displaystyle (\mathbb {R} ,\leq )}$

Strict variants

It can also get through

${\displaystyle A>0\iff A{\text{ ist positiv definit }}}$

Define strict variants of the Loewner partial order. But these usually do not have a proper name.

notation

There is a large number of notations for the Loewner partial order. In addition to the above notation, using is also common . This is often used in semidefinite programming or when using the construction as a generalized inequality, since it still specifies which cone defines the generalized inequality. The definition of an ordinal symbol is seldom omitted, for example instead of . ${\displaystyle \geq _{L}}$ ${\displaystyle \succcurlyeq _{S_{+}^{n}}}$ ${\displaystyle A\in -S_{+}^{n}}$ ${\displaystyle A\leq _{L}0}$

literature

• Johannes Jahn: Introduction to the Theory of Nonlinear Optimization. 3. Edition. Springer, Berlin 2007, ISBN 978-3-540-49378-5 .
• Florian Jarre, Josef Stoer: Optimization. Springer, Berlin 2004, ISBN 3-540-43575-1 .