Optimization Models & Methods for Finance

If an LP in standard form has an optimal solution, then it has an optimal basic feasible solution (a vertex of the polyhedron). Justifies simplex's vertex-to-vertex search and the existence of sparse optimal allocations.

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 in the set. Examples: halfspaces, polyhedra, ellipsoids, the PSD cone.

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]. Twice-differentiable f is convex iff ∇²f ⪰ 0.

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(x) ≤ t, exposing constraints amenable to conic solvers.

minimize cᵀx subject to Ax = b, x ≥ 0. Objective and constraints are all linear; feasible set is a polyhedron and the optimum (if finite) is attained at a vertex.

minimize ½xᵀQx + cᵀx subject to Ax ≤ b (and possibly equality constraints). Convex iff Q is positive semidefinite.