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.

Intersection of nested convex sets.


ntersection of nested closed compact sets is not empty.

Intersection of nested unbounded closed convex sets may be empty. Consider MATH MATH . The sets $C_{k}$ escape to infinity along the common direction of recession $\left( 0,1\right) $ . However, if all directions of recession are included in a common linearity space then this cannot happen as stated in the proposition below.

Proposition

(Principal intersection result). Let MATH be a sequence of nonempty closed convex sets, MATH . Let $R_{k}$ and $L_{k}$ be the recession cone and linearity space of $C_{k}$ and let MATH If $C_{k+1}\subset$ $C_{k}$ and $R=L$ then the intersection $\cap_{k}C_{k}$ is nonempty and MATH for some nonempty compact set $\tilde{C}$ .

Proof

Starting from some $k$ the $L_{k}$ has to stop decreasing because it is a space of finite dimension. After such $k$ we have $L_{k}=L$ . Let us restrict attention to such $k$ .

Starting from some $k$ we must have MATH Indeed, if this is not so then for every $k$ there is MATH . We consider MATH . The sets $R_{k}$ are closed and nested. Hence, a limit point of such sequence MATH has to be in $R$ . This contradicts the condition $R=L$ .

We now apply the result ( Decomposition of a convex set ). MATH Hence, MATH Starting from some $k$ the set MATH has no direction of recession. Hence, the sets MATH are nested and compact. We conclude MATH .

Proposition

(Linear intersection result). Let MATH be a sequence of closed convex subsets of $\QTR{cal}{R}^{n}$ .

Let $X$ be the set given by the relationships MATH where MATH and MATH .

Assume that

1. MATH for all $k$ .

2. MATH for all $k.$

3. MATH where MATH , MATH , MATH .

Then MATH .

To see that the $X$ has to be linear consider MATH and MATH . Such $X$ and $C_{k}$ fail only the linearity requirement and the conclusion of the theorem.

Proof

If MATH then the statement is a consequence of the ( Principal intersection result ). We exclude such case from further consideration.

We consider the case when MATH . Since always MATH and MATH then there has to be a $y\in R_{X}\cap R$ that does not belong to $L_{X}$ .

Let us take a sequence MATH such that MATH . Since the sets $C_{k}$ are nested it is enough to prove the statement for some subsequence.

For any $k$ we form the sum MATH . Since $y\in R_{X}\cap R$ and $-y\notin R_{X}$ then for some $\bar{\lambda}_{k}$ the MATH lies on the boundary of $X$ . Hence, MATH . The $X$ is given by a finite number of linear conditions. Hence, there is some $j_{0}$ such that MATH for infinite number of $k$ . We restrict our attention to such subsequence.

The set MATH satisfies the conditions of the proposition within the subspace MATH and MATH is one dimension smaller then MATH . Therefore, we proceed by induction in the number of dimensions of MATH . The proposition is true for dimension 0 ( $X$ is a point). Then we assume that it is true for MATH and prove it for MATH using the construction above. Indeed, since the proposition holds for $\bar{X}$ then the intersection MATH is not empty for the chosen subindexing of $k$ . But $\bar{X}\subset X$ hence MATH .

Proposition

(Quadratic intersection result). Let MATH be a sequence of subsets of $\QTR{cal}{R}^{n}$ given by MATH where $Q$ is a symmetric positive semidefinite matrix, $a$ is a vector, $b$ is a scalar and $w_{k}$ is a non-increasing sequence of real numbers converging to 0.

Let $X$ be a subset of $\QTR{cal}{R}^{n}$ of the form MATH where the $Q_{j}$ are positive semidefinite matrixes.

Let $X\cap C_{k}$ be nonempty for all $k$ .

Then the intersection MATH is nonempty.

Proof

The elements of recession cones and linear spaces of $C_{k}$ are given by MATH and are $k$ -independent.

If MATH then the statement follows from the ( Principal intersection result ). Hence, we consider the situation MATH and MATH . If there is a $y\in R_{X}\cap R$ then $a^{T}y\leq0$ and for any $x\in X,~\lambda>0$ we have $x+\lambda y\in X$ . Note, MATH

If MATH then for a sufficiently large $\lambda$ the $x+\lambda y$ lies in all $C_{k}$ and in $X$ and we are done.

Therefore, it remains to consider a situation when for any $y\in R_{X}\cap R$ we have MATH but MATH .

The recession cone of $X$ is given by MATH Hence, we are considering the case when for any $y\in R_{X}\cap R$ we have MATH and MATH for some $j$ .

We now proceed by induction in the number of conditions $r$ . For $r=0\,$ the case that we are considering is excluded. Hence, we assume that the proposition holds for $\bar{r}$ and proceed to prove that it hold for $\bar {r}+1$ . We are interested only in adding an equation with MATH because the all the equations with MATH may be arranged to be in the beginning of the induction and, hence, fall into the $R_{X}=L_{X}$ category.

A step of the induction in $\bar{r}$ proceeds in the following stages.

1. Assume that the statement holds for $\bar{r}$ .

2. Let $X$ be the $\bar{r}+1$ -equations set.

3. Let $\bar{X}$ be the set holding $\bar{r}$ equations of $X$ . The exclusion of a condition from $X$ makes the $\bar{X}$ a bigger set. Hence, the conditions of the statement holds for the set $\bar{X}$ and MATH is not empty.

4. We take a point MATH and a direction MATH . In our case $a_{j}^{T}\bar{y}<0$ for the one additional equation. Hence, we can construct MATH by taking a sufficiently large $\lambda$ .





Notation. Index. Contents.


















Copyright 2007