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.

Polyhedral cones.


efinition

A cone $C$ is polyhedral if it has the form MATH

A cone $C$ is finitely generated if it has the form MATH where MATH .

Proposition

(Polar polyhedral cone). Let MATH . Then MATH is closed and MATH

Proof

First we prove that MATH . Indeed, by the definition of polar cone MATH

Next, we prove that $C$ is close by induction in $r$ .

For $r=1$ it is closed.

We assume that MATH is closed and prove that MATH is closed. Without loss of generality we assume MATH .

Take any sequence MATH . We aim to prove that $x_{0}\in C_{r+1}$ . We have MATH The $\lambda_{k}\,\ $ must be a bounded sequence. Hence, we take a subsequence converging to some limit point and restrict consideration to such subsequence: MATH We have MATH Therefore, $y_{k}$ must be convergent: MATH and $y_{0}\in C_{r}$ by the induction hypothesis. Hence, MATH

Proposition

(Farkas lemma). Let MATH MATH where MATH .

Then MATH

Proof

Note that MATH MATH Therefore, by the proposition ( Polar polyhedral cone ), MATH and $C$ is closed. Hence, MATH

Proposition

(Minkowski-Weyl theorem). A cone is polyhedral if and only if it is finitely generated.

Proof

Suppose MATH is a finitely generated cone MATH We prove that there exist vectors MATH such that MATH

Let $H$ be a linear span of MATH , and $k\equiv\dim H$ . We introduce MATH to be the orthogonal basis of $H$ . Hence we have defined the linear transformations $\Lambda$ and $A$ as follows MATH The transformation $\vartheta$ is known as "orthogonalization". Some of its columns have all zero elements because MATH might be linearly dependent.

We have MATH Let MATH MATH We introduce the vectors MATH : MATH then MATH MATH Therefore, MATH

Definition

A set $P$ is a polyhedral set if it is nonempty and has the form MATH

Proposition

(Minkowski-Weyl representation). A set $P$ is polyhedral iff MATH for some MATH .

Proof

Note that the inequality MATH may be represented as MATH Based on this observation we aim to apply the proposition ( Minkowski-Weyl theorem ). Set of the form MATH is not cone. We consider MATH Observe that MATH . By the proposition ( Minkowski-Weyl theorem ), we have MATH We introduce the notation MATH We have MATH

Definition

A function MATH is polyhedral if MATH is polyhedral.

The following proposition is a direct consequence of the definition.

Proposition

(Polyhedral function). Let MATH be a convex function. Then $f$ is polyhedral if and only if MATH is polyhedral and MATH





Notation. Index. Contents.


















Copyright 2007