Saddlepoint

From Glossary

Jump to: navigation, search

Let LaTeX: \textstyle f : \mbox{ X } \times \mbox{ Y } \to \mathbb{R}. Then, LaTeX: \textstyle (x^*, y^*) is a saddle point of LaTeX: \textstyle f if LaTeX: \textstyle x^* minimizes LaTeX: \textstyle f(x, y^*) on LaTeX: \textstyle \mbox{ X }, and LaTeX: \textstyle y^* maximizes LaTeX: \textstyle f(x^*, y) on LaTeX: \textstyle \mbox{ Y }. Equivalently,

LaTeX: 
f(x^*, y) \le f(x^*, y^*) \le f(x, y^*) \mbox{ for all } x \mbox{ in X, } y \mbox{ in Y.}

Von Neumann (1928) proved this equivalent to:

LaTeX: 
\begin{array}{rcl}
f(x^*, y^*) & = &
\inf \{ \sup \{ f(x, y) : y \in \mbox{ Y } \} : x \in \mbox{ X } \} \\
& = & \sup \{ \inf \{ f(x, y) : x \in \mbox{ X } \} : y \in \mbox{ Y } \}.
\end{array}

A sufficient condition for a saddle point to exist is that LaTeX: \textstyle \mbox{ X } and LaTeX: \textstyle \mbox{ Y } are non-empty, compact, convex sets, LaTeX: f(.,y) is convex on LaTeX: \textstyle \mbox{ X } for each LaTeX: y in LaTeX: \textstyle \mbox{ Y }, and LaTeX: f(x,.) is concave on LaTeX: \textstyle \mbox{ Y } for each LaTeX: x in LaTeX: \textstyle \mbox{ X }.

Saddle point equivalence underlies duality. See also Lagrangian saddlepoint equivalence as well as the associated supplement.


Views
Personal tools