Optimization Models & Methods for Finance

Fundamental theorem of LP

If an LP in standard form has an optimal solution, then it has an optimal basic feasible solution (a vertex of the polyh

Convex set — definition

A set C ⊆ ℝⁿ is convex if for all x, y ∈ C and θ ∈ [0,1], θx + (1−θ)y ∈ C: the line segment between any two points lies

Convex function — definition

f: ℝⁿ → ℝ is convex if its domain is convex and f(θx + (1−θ)y) ≤ θ f(x) + (1−θ) f(y) for all x, y ∈ dom f and θ ∈ [0,1].

Epigraph and the epigraph trick

epi f = {(x, t) : f(x) ≤ t}. f is convex iff epi f is a convex set. The epigraph trick rewrites min f(x) as min t s.t. f

Linear program (LP) standard form

minimize cᵀx subject to Ax = b, x ≥ 0. Objective and constraints are all linear; feasible set is a polyhedron and the op