Quantitative Analysis
Parallel Processing
Numerical Analysis
C++ Multithreading
Python for Excel
Python Utilities
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.

Minimal common and maximal crossing points.

et $M$ be a subset of $\QTR{cal}{R}^{n+1}$ . The $M$ may have common points with the $\left( n+1\right) $ -th coordinate axis. We introduce the quantity MATH

A normal vector to a nonvertical hyperplane may be normalized to a form MATH . A nonvertical hyperplane that crosses the $\left( n+1\right) $ -th coordinate axis at the point MATH and has a normal vector MATH has the representation MATH Indeed, MATH

The set $M$ is contained in the upper half plane of MATH iff MATH Hence, the quantity MATH is the maximum $\left( n+1\right) $ -th axis crossing level for all hyperplanes that contain the set $M$ in the upper half space and have the normal vector MATH .

The MATH is a concave function.

We introduce the quantity MATH


(Weak duality theorem). Let $M$ be a subset of $\QTR{cal}{R}^{n+1}$ . Then MATH



We investigate the conditions for the equality MATH Observe that by definition of these quantities all that is needed is existence of a supporting hyperplane at a point MATH . The pictures ( Crossing points figure 1 )-( Crossing points figure 3 ) show basic examples when this may or may not happen.

Crossing points figure 1
Crossing points figure 1

Crossing points figure 2
Crossing points figure 2. The upper boundary is included in the set. The other boundaries are excluded.

Crossing points figure 3
Crossing points figure 3


(Crossing theorem 1). Let $M$ be a subset of $\QTR{cal}{R}^{n+1}$ . Assume the following:

1. $M$ and $\left( n+1\right) $ -th axis have nonempty intersection and $w^{\ast}\neq\infty$ .

2. The set MATH is convex.

Then MATH if and only if for any sequence MATH such that $u_{k}\rightarrow0$ we have MATH


By definition of $w^{\ast}$ , MATH .

$\bar{M}$ contains no vertical lines. Indeed, if it does then by the proposition ( Main properties of direction of recession ) one may infinitely go along the vector MATH inside $\bar{M}$ starting from any MATH . This contradicts the condition 1.

We have MATH for any small positive $\varepsilon$ . Indeed, on the contrary, if MATH then by definition of the closure one can construct the sequence MATH that violates MATH .

Therefore, by the proposition ( Nonvertical separation ), there is a nonvertical separation of $\bar{M}$ from MATH for any small positive $\varepsilon$ . The $\left( n+1\right) $ -th axis crossing point for such separating hyperplane must be between MATH and MATH . Hence, $q^{\ast}=w^{\ast}$ .


(Crossing theorem 2). Let $M$ be a subset of $\QTR{cal}{R}^{n+1}$ . Assume the following:

1. $M$ and $\left( n+1\right) $ -th axis have nonempty intersection and $w^{\ast}\neq\infty$ .

2. The set MATH is convex.

3. MATH , where the set $D$ is defined by MATH Then MATH and the solution set MATH has the form MATH where the set $\tilde{Q}$ is nonempty convex and compact and MATH is the orthogonal complement of MATH relative to the plane of the first n coordinates MATH .

Crossing theorem 2 figure
Crossing theorem 2 figure


By the proposition ( Proper separation 1 ) there is a separating hyperplane $H$ for the point MATH and set $\bar{M}$ . Such hyperplane cannot be vertical. Indeed, if it is vertical then the point MATH projects on the plane MATH along the $H$ onto the origin $0$ . Indeed, the segment MATH would belong to $H$ . But then the condition MATH is violated because it would belong to the boundary of $D$ . Therefore the $H$ is nonvertical, MATH and $Q^{\ast}$ is nonempty.

We next claim that MATH . Indeed, by construction of $D,$ if it has an orthogonal complement in MATH then we can rotate coordinate system to make MATH a coordinate subspace and then remove the coordinates that span the MATH from the consideration (see the picture ( Crossing theorem 2 figure )).

In addition, MATH . To see this, consider any hyperplane $H$ , corresponding normal $\mu$ that delivers MATH and the perturbation MATH . If MATH then $\mu+\lambda\eta$ can be made arbitrarily close to horizontal and $H$ would be close to vertical by taking large enough $\pm\lambda$ . Hence, such $\eta$ can be in $R_{Q^{\ast}}$ only if MATH . If MATH then the statement is trivially true. We exclude such case from consideration.

We conclude that MATH .

We next apply the proposition ( Decomposition of a convex set ) within the $\QTR{cal}{R}^{n}$ MATH with MATH . The $Q^{\ast}$ and MATH have no common direction of recession as we already established. Hence, MATH for some convex and nonempty $\tilde{Q}$ . The $\tilde{Q}$ is compact by ( Main properties of direction of recession )-2.

Notation. Index. Contents.

Copyright 2007