Quantitative Analysis
Parallel Processing
Numerical Analysis
C++ Multithreading
Python for Excel
Python Utilities
Services
Author
Printable PDF file
I. Basic math.
II. Pricing and Hedging.
III. Explicit techniques.
IV. Data Analysis.
V. Implementation tools.
1. Finite differences.
2. Gauss-Hermite Integration.
3. Asymptotic expansions.
4. Monte-Carlo.
5. Convex Analysis.
A. Basic concepts of convex analysis.
B. Caratheodory's theorem.
C. Relative interior.
D. Recession cone.
E. Intersection of nested convex sets.
F. Preservation of closeness under linear transformation.
G. Weierstrass Theorem.
H. Local minima of convex function.
I. Projection on convex set.
J. Existence of solution of convex optimization problem.
K. Partial minimization of convex functions.
L. Hyperplanes and separation.
M. Nonvertical separation.
N. Minimal common and maximal crossing points.
O. Minimax theory.
P. Saddle point theory.
Q. Polar cones.
R. Polyhedral cones.
S. Extreme points.
T. Directional derivative and subdifferential.
U. Feasible direction cone, tangent cone and normal cone.
V. Optimality conditions.
W. Lagrange multipliers for equality constraints.
X. Fritz John optimality conditions.
Y. Pseudonormality.
Z. Lagrangian duality.
[. Conjugate duality.
VI. Basic Math II.
VII. Implementation tools II.
VIII. Bibliography
Notation. Index. Contents.

Minimax theory.


et $\phi$ be a function MATH where the $X$ and $Z$ are subsets of $\QTR{cal}{R}^{n}$ and $\QTR{cal}{R}^{m}$ respectively. We always have MATH Therefore, MATH In this section we investigate the conditions for

MATH (Minimax equality)
and attainment of the sup and inf.

Definition

The pair MATH is called a saddle point of $\phi$ iff MATH for MATH .

Proposition

(Saddle point's defining property). The pair MATH is a saddle point iff the relationship ( Minimax equality ) holds and MATH

We introduce the function MATH given by

MATH (definition of minmax p)

Proposition

(Minimax lemma 1).Assume that MATH is convex for each $z\in Z$ . Then the function $p$ is convex.

Proof

The statement is a consequence of the propositions ( Preservation of convexity ) and ( Convexity of partial minimum ).

We will be using results of the section ( Min common and max crossing point section ). Following that section we define MATH

Proposition

(Minimax lemma 2). Let MATH and MATH is closed and convex for every $x\in X$ . Then

1. MATH

2. MATH iff the relationship ( Minimax equality ) holds.

Proof

By definitions we have

MATH (q mu 1)
Since $\mu\in Z$ we do not increase the last quantity by choosing $z=\mu$ among the $\sup_{z\in Z}$ values. We obtain MATH

Next, we prove that MATH when $\mu\in Z$ .

Take any small $\varepsilon>0$ and fix $z_{0}\in Z$ . Since the function MATH is convex then there is a separating hyperplane MATH between the point MATH and MATH . Hence, the point MATH lies below MATH : MATH and the MATH lies above MATH : MATH We combine both inequalities into the statement MATH where we claim existence of such $\eta_{x}$ for any $z\in Z$ . We transform the inequality as follows MATH We intend to combine this result with the expression ( q_mu_1 ) above. Hence, we set $z_{0}=\mu$ and perform the operation MATH . We obtain MATH Hence, MATH

Next, we prove that MATH when $\mu\not \in Z$ . Indeed, if MATH then for any $x\in X$ and any MATH the point MATH lies away from the epigraph of the convex function MATH of $z\in Z$ . Hence, there is always a nonvertical hyperplane MATH that separates any MATH from MATH and the MATH lies in the upper half plane. MATH Hence, MATH where we claim existence of such $\eta_{x}$ and the statement holds for fixed MATH and $\bar{w}$ and any $z\in Z$ . Again, we apply the operation MATH . Then the RHS becomes MATH and the LHS may be let to $-\infty$ . We conclude that MATH

With the representation MATH proven we remark that MATH and MATH Therefore the statement (2) of the proposition follows.

Proposition

(Minimax theorem). Let $X$ and $Z$ be nonempty convex subsets of $\QTR{cal}{R}^{n}$ and $\QTR{cal}{R}^{m}$ respectively and let $\phi$ be a function MATH such that

1. For every $x\in X$ the function MATH is convex and closed,

2. For every $z\in Z$ the function MATH is convex,

3. MATH

Then

1.The minimax equality MATH holds iff the function $p$ given by the formula ( definition of minmax p ) is lower semicontinuous at 0.

2. If MATH then the minimax equality holds and the supremum over Z in MATH is finite and is attained. Furthermore, MATH

Proof

The statement follows from propositions ( Minimax lemma 1 )-( Minimax lemma 2 ) and ( Crossing theorem 1 )-( Crossing theorem 2 ) applied to the epigraph of p.





Notation. Index. Contents.


















Copyright 2007