Saddle point problem

In mathematics , a saddle point problem denotes a special class of problems which leads to a linear system of equations in block form, namely a matrix of form ${\displaystyle (n+m)\times (n+m)}$ ${\displaystyle M}$

${\displaystyle M={\begin{pmatrix}A&B\\B^{T}&0\end{pmatrix}},}$

where is a matrix and a matrix. The block is the size . ${\displaystyle A}$ ${\displaystyle n\times n}$ ${\displaystyle B}$ ${\displaystyle n\times m}$ ${\displaystyle 0}$ ${\displaystyle m\times m}$

Origin of saddle point problems

Systems of equations in saddle point form arise in many applications, for example in the case of optimization problems under secondary conditions .

An example of this is solving quadratic programs with equation restrictions by applying the Karush-Kuhn-Tucker conditions . These are equivalent to determining a saddle point in the Lagrange duality , which explains the name.

Another important class of saddle point problems comes from the discretization of partial differential equations . The most important example are the incompressible Navier-Stokes equations in linearized form , for example discretized with finite elements , which naturally results in a linear system of equations in the block form above. The block matrix arises there from the discretization of the velocity term in the momentum equation , the matrix from the discretization of the pressure term , and the matrix results from the discretization of the velocity in the continuity equation . ${\displaystyle A}$ ${\displaystyle {\vec {u}}}$ ${\displaystyle B}$ ${\displaystyle p}$ ${\displaystyle B^{T}}$

Solution of saddle point equations

Applications like the discretized Navier-Stokes equations require the solution of a linear system of equations

${\displaystyle Mx=b.}$

In order for the system of equations to be uniquely solvable, the matrix must have full rank . A necessary prerequisite for this is that the number of rows in the matrix is not greater than the number of columns. A sufficient condition is the so-called LBB condition (after Ladyschenskaja , Babuška and Brezzi ), often also called the inf-sup condition . ${\displaystyle B^{T}}$

Efficient numerical algorithms for solving systems of equations with a saddle point structure use a special form of the Schur complement , which uses the block structure of the matrix. This variant is particularly popular for the numerical solution of the Navier-Stokes equations.

Ordinary iterative solution methods such as the Krylov subspace method GMRES without considering the structure of are, on the other hand, relatively poorly suited because the common methods for preconditioning such as the Jacobi , Gauß-Seidel method or the ILU decomposition because of the zeros on the main diagonal in lower diagonal block do not work. Without preconditioning , even the often excellent Krylov subspace methods converge very slowly and are unusable. ${\displaystyle M}$

Disambiguation

The term saddle point problem for an equation of form

${\displaystyle Mx={\begin{pmatrix}A&B\\B^{T}&0\end{pmatrix}}{\begin{pmatrix}u\\p\end{pmatrix}}={\begin{pmatrix}0\\0\end{pmatrix}}=b}$

derives from the properties of the associated square shape

${\displaystyle F(u,p)=u^{T}Au+u^{T}Bp+p^{T}B^{T}u}$

with a symmetrically positive definite matrix , the derivation here being for a homogeneous right-hand side. The general case with has analogous properties. ${\displaystyle A}$ ${\displaystyle b\neq 0}$

Let be a solution of the linear system of equations . Then there is a saddle point of , because for everyone : ${\displaystyle x^{*}=(u^{*},p^{*})}$ ${\displaystyle Mx=0}$ ${\displaystyle (u^{*},p^{*})}$ ${\displaystyle F}$ ${\displaystyle u\in \mathbb {R} ^{n}}$

${\displaystyle F(u,p^{*})=u^{T}Au+2u^{T}Bp^{*}=u^{T}Au-2u^{T}Au^{*}+(u^{*})^{T}Au^{*},}$

where the second equality is achieved by replacing and inserting the term . Now ${\displaystyle Bp^{*}=-Au^{*}}$ ${\displaystyle (u^{*})^{T}Au^{*}=0}$

${\displaystyle F(u,p^{*})=(u-u^{*})^{T}A(u-u^{*})\geq 0=F(u^{*},p^{*}),}$

The term is nonnegative for all because the matrix is symmetrically positive definite. ${\displaystyle (u-u^{*})^{T}A(u-u^{*})}$ ${\displaystyle u}$ ${\displaystyle A}$

It also shows the inequality

${\displaystyle F(u^{*},p)\leq 0}$

for all , which shows the existence of the saddle point. ${\displaystyle p\in \mathbb {R} ^{m}}$

See also

• Schur complement
• Oseen's equations
• Darcy Law

literature

• Dieter Braess: Finite Elements. Theory, quick solvers, and applications in elasticity theory. Section III.4, Springer-Verlag, Berlin 2003, ISBN 3-540-00122-0 .