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.

Extreme points.


efinition

For a nonempty convex set $C$ the point $x$ is an extreme point if there is no two points $u,w\in C$ such that MATH . We denote $ep\left( C\right) $ the set of all extreme points.

Proposition

(Krein-Milman theorem). Let $C$ be a nonempty convex set. Then

1. For a hyperplane $H$ that contains $C$ in one of its closed half-spaces MATH

2. If $C$ is closed then MATH

3. If $C$ is compact then MATH

Proof

(1). Assume the contrary: MATH . Then there must be MATH . There are three cases:

a. $u,w\not \in H$ . Since MATH and $x\in H$ this means that $H$ does not contain $C$ in one of its half-spaces.

b. $u,w\in H$ . Then MATH .

c. $u\in H,w\not \in H$ . Impossible because MATH and $x\in H$ .

Proof

(2). If MATH then any candidate $x$ to be in $ep\left( C\right) $ may be translated in both directions along any $y\in L_{C}$ while remaining in $C$ . Hence, MATH MATH . We have MATH for the same reason.

If $L_{C}=\varnothing$ then for any point $x\in C$ there is a direction $y$ such that the line MATH hits the relative boundary of $C$ at some point $x_{0}$ . By proposition ( Proper separation 1 ) there is a properly separating hyperplane $H$ at that point. By closedness of $C$ the set $H\cap C$ is not empty and MATH . We reduced the dimensionality of our proof. Because of the part (1) of the proposition we can complete this proof by induction in the number of dimensions.

Proof

(3). We prove the statement by induction in the number of dimensions of $\QTR{cal}{R}^{n}$ . For $n=1$ the statement is trivial. Assume that it is true in $\QTR{cal}{R}^{n-1}$ . Let MATH and $x\in C$ , MATH . There is a line that passes through $x~$ such that MATH and MATH . There are properly separating hyperplanes $H_{1}$ and $H_{2}$ at points $x_{1}$ and $x_{2}$ . By applying the statement in $\QTR{cal}{R}^{n-1}$ , MATH Then by (1), MATH , $i=1,2$ . Hence, MATH .

Proposition

(Extreme points of polyhedral set 1). Let $P$ be a polyhedral set. According to the proposition ( Minkowski-Weyl representation ) MATH We have MATH

Proof

According to the proposition ( Minkowski-Weyl representation ) any point $x\in P$ has the representation $x=y+z$ , MATH , MATH . An extreme point MATH may not have a non zero $z$ -part because it would contradict the definition of the extreme point. The $x^{\ast}$ also cannot be a convex combination of MATH . Therefore, the only possibility is MATH .

Proposition

(Extreme points of polyhedral set 2). Let $P$ be a polyhedral subset of $\QTR{cal}{R}^{n}$ . Then

1. Let $P$ has the form MATH and denote MATH then MATH

2. Let $P$ has the form MATH and denote MATH then MATH iff $B_{v}$ has the maximal rank (all columns are linearly independent) and $v\in P$ .

3. Let $P$ has the form MATH and denote MATH then MATH iff $C_{v}$ has the maximal rank (all columns are linearly independent) and $v\in P$ .

Proof

(1). We state that MATH iff for any direction vector MATH such that MATH for some $t\not =0$ and any small $\varepsilon>0$ one of the conditions MATH is violated. If $\dim A_{v}=n$ then no $y$ can be orthogonal to all $a_{j}\in A_{v}$ and then one of the conditions MATH is violated. Hence, MATH

Conversely, if there is a $y$ that is orthogonal to all $A_{v}$ then for such $y$ MATH if $v\in P$ . Hence, MATH .

Proof

(2). We apply the part (1) of the proposition. In context of the part (1) the $P$ is represented by MATH where the MATH is the coordinate basis. Therefore, the $A_{v}$ for such situation has the form MATH Note that $v\in P$ is given, hence, the condition MATH above is not restrictive. The set MATH contains linearly independent vectors. Let MATH . We cannot state that according to (1), for MATH we need to have at least $n-k$ independent vectors among MATH . Indeed, some of the $a_{j}$ might be in the linear span of the MATH . Hence, we need to exclude the projection on MATH . For MATH we need to have MATH where the MATH is the projection. The original matrix MATH has $n$ columns in total. To establish the last equality it is enough to form a matrix from the columns MATH , remove the $k$ columns that correspond to MATH and check that the remaining matrix has the maximal rank $n-k$ .

Proof

The proof of (3) is the same as the proof of (2).

Proposition

Let $C$ be a closed convex set with at least one extreme point. A convex function MATH that attains a maximum over $C$ attains the maximum at some extreme point of $C$ .

Proof

Let $S$ be a segment MATH . Note that $S$ is open. A convex function that attains its maximum at $S$ is constant on $S$ . Such statement follows directly from the definition of convexity.

The proof is based on the above statement and the theorem ( Proper separation 1 ). Let $x^{\ast}$ be a point where the maximum is attained. By the above statement either $f$ is constant on $C$ or MATH . In the former case we are done. In the latter case there is a properly separating hyperplane $H$ . Since $x^{\ast}\in C$ we have MATH . If MATH then we are done: the $x^{\ast}$ is an extreme point. Otherwise we observe that we reduce the dimension of the proof by switching the consideration from $C$ to $H\cap C$ .





Notation. Index. Contents.


















Copyright 2007