Convex Optimization 2026, 03 - Examples and Definitions

Define a hyperplane as {x | a^Tx = b}, a ∈ ℝⁿ, a ≠ 0, b ∈ ℝ. A normal vector can be used to shift the hyperplane from the origin. It divides ℝⁿ into two halfspaces. These can be either closed, or open (2.2.1).

A (euclidean) ball in ℝⁿ is defined as B(x_c, r) = {x | ||x - x_c||₂ ≤ r}. It's a convex set, and related to the ellipsoids {x | (x - x_c)^TP^-1(x - x_c) ≤ 1} (2.2.2).

The norm cone is C = {(x, t) | ||x|| ≤ t} ⊂ ℝⁿ⁺¹. It's also convex.

Polyhedra are the solution sets of a finite number of linear equations P = {x | a_j^Tx ≤ b_j, j = 1, ..., m, c_j^Tx = d_j , j = 1, ..., p}. They describe the intersection of finite number of halfspaces and hyperplanes. Affine sets, rays, line segments are halfspaces are describable as polyhedra. If a polyhedron is bounded, it's a polytope. Simplexes are polyhedra with affinely independent points with conv{v₀, ..., v_k}. Polyhedra can be described as a convex hull (2.2.4).

A positive semidefinite cone is Sⁿ = {X ∈ ℝ^n×n | X = X^T}, which as dimension n(n+1)/2. If narrowed down to symmetric positive semidefinite matrices, Sⁿ₊, and if narrowed down further to symmetric positive definite matrices Sⁿ₊₊ (2.2.5).