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.

Hyperplanes and separation.


efinition

Hyperplane in $\QTR{cal}{R}^{n}$ is a set of the form MATH The $a$ is called the "normal vector". The sets MATH are called "closed half-spaces" associated with $H_{a,b}$ .

The two sets $C_{1}$ and $C_{2}$ are separated by $H_{a,b}$ if either MATH or MATH

The two sets $C_{1}$ and $C_{2}$ are strictly separated by $H_{a,b}$ if the above inequalities are strict.

A hyperplane $H_{a,b}$ may be represented as MATH for any fixed $\bar{x}\in H_{a,b}$ .

Proposition

(Supporting hyperplane theorem). Let $C$ be a nonempty convex subset of $\QTR{cal}{R}^{n}$ and MATH . If $\bar{x}$ does not belong to interior of $C$ then there is a hyperplane that passes through $\bar{x}$ and contains $C$ in one of its closed half-spaces: MATH

Proof

If MATH then we obtain the normal vector by projecting on $C:$ MATH The $b$ may be obtained from the requirement that the MATH pass trough $\bar{x}$ .

If MATH by does not belong to interior of $C$ then there is a sequence MATH such that MATH and MATH . We utilize the construction from the case MATH to obtain a sequence MATH . The MATH may be normalized to unity. The MATH then has a limit point. Such limit point delivers the sought out hyperplane because of the proposition ( Projection theorem )-2.

Proposition

(Separating hyperplane theorem). If the $C_{1},C_{2}$ are two nonempty disjoint convex sets then there is a hyperplane that separates them.

Proof

Apply the proposition ( Supporting hyperplane theorem ) to the set $C=C_{1}-C_{2}$ and $\bar{x}=0$ .

Two nonempty convex disjoint sets $C_{1},C_{2}$ are not necessarily strictly separated. For example, MATH , MATH do not have a strictly separating hyperplane.

Proposition

(Strict hyperplane separation 1). Let $C_{1}$ and $C_{2}$ are two nonempty convex disjoint sets. If $C_{1}-C_{2}$ is closed then there is a strictly separating hyperplane.

Proof

Let MATH , $x_{1}\in C_{1}$ , $x_{2}\in C_{2}$ . Set MATH By the closedness, $a\not =0$ . The $H_{a,b}$ strictly separates $C_{1},C_{2}$ .

Let $C_{1}$ and $C_{2}$ be two disjoint closed convex subsets of $\QTR{cal}{R}^{n}$ . To investigate the conditions for $C_{1}-C_{2}$ to be closed we introduce the subset MATH of $\QTR{cal}{R}^{2n}$ , note that the transformation MATH is linear and seek to apply the proposition ( Preservation of closeness result ). We note that $C$ is closed and convex, MATH and MATH The condition MATH of the proposition ( Preservation of closeness result ) becomes MATH

We arrive to the following additional sufficient conditions for strict separation.

Proposition

(Strict hyperplane separation 2). Let $C_{1}$ and $C_{2}$ are two nonempty convex disjoint sets. There is a strictly separating hyperplane if any of the following conditions holds.

1. $C_{1}$ is closed and $C_{2}$ is compact.

2. $C_{1},C_{2}$ are closed and MATH

3. $C_{1}$ is closed, $C_{2}$ is given by the linearity constraints MATH and MATH .

4. $C_{1}$ and $C_{2}$ are given by quadratic constraints MATH where the $Q_{ij}$ are positive semidefinite matrices.

Proposition

(Intersection of half-spaces). The closure of convex hull of a set $C$ is the intersection of all closed half-spaces that contain $C$ .

Proof

If there is a point in $C$ that is not contained in the intersection of half-planes then we arrive to contradiction by using the theorem ( Supporting hyperplane theorem ).

Definition

The subsets $C_{1},C_{2}$ of $\QTR{cal}{R}^{n}$ are properly separated by a hyperplane $H_{a,b}$ if the following conditions are true MATH

Let $l$ be a line MATH for some $x_{0}$ . The definition of the proper separation requires that MATH is a single point or nothing and MATH consists of more then one point.

The sets MATH and MATH may not be properly separated.

The sets MATH and MATH are properly separated by the x-axis MATH .

Proposition

(Proper separation 1) Let $C$ is a subset of $\QTR{cal}{R}^{n}$ and MATH . There is a properly separating hyperplane for $C$ and $\left\{ x\right\} $ if MATH

Proof

If MATH then $\left\{ x\right\} $ and MATH are strictly separated by the proposition ( Strict hyperplane separation 2 )-2.

If MATH then we translate MATH into a subspace $S$ and apply the ( Strict hyperplane separation 2 )-2 within MATH to obtain some separating plane $\bar{H}$ then extend it to a hyperplane by MATH .

Proposition

(Proper separation 2) The two subsets $C_{1},C_{2}$ of $\QTR{cal}{R}^{n}$ are properly separated if MATH

Proof

Apply the proposition ( Proper separation 1 ) to $C=C_{1}-C_{2}$ and $x=0$ .





Notation. Index. Contents.


















Copyright 2007