Convex Analysis

Click any term below to expand its definition. Definitions link to related concepts which can be expanded nested up to 2 levels deep.

Definitions

• A nonnegative real below every epsilon is zero — If ℓ≥0 and ℓ<ε for all ε>0, then ℓ=0
• Affine Hull and Affine Combination — The smallest affine set containing Ω, and linear combinations with coefficients summing to 1.
• Affine images and preimages of convex sets are convex — Affine maps preserve convexity under both images and inverse images
• Affine mapping — A map of the form x↦Ax+b, i.e., linear plus a translation
• Affine Set — A set containing the entire line through any two of its points.
• Affine Sets are Translates of Subspaces — Ω is affine iff Ω−ω is a linear subspace (equivalently, Ω=ω+L).
• Algebra of limits in normed spaces — Limits commute with addition and scalar multiplication
• Algebraic Interior (Core) — The algebraic analogue of interior for subsets of vector spaces
• Auxiliary Separation Lemma — Disjoint convex sets are separable if one has nonempty core and the sets are disjoint.
• Balanced and absorbing sets — Two scaling properties of subsets in a vector space
• Bases are maximal linearly independent sets — A nonempty set is a basis iff it is linearly independent and maximal for inclusion
• Basic properties of closed sets — Intersections of closed sets are closed; finite unions of closed sets are closed
• Basic properties of closure — Monotonicity, idempotence, and compatibility with finite unions
• Basic properties of interior — Monotonicity, idempotence, and compatibility with finite intersections
• Basic properties of open sets — Unions of open sets are open; finite intersections of open sets are open
• Basis and dimension — A Hamel basis is a linearly independent set that spans the whole vector space
• Bounded Linear Functional and Its Norm — A linear functional is bounded iff it is continuous; its operator norm is sup_{||x||≤1}|f(x)|.
• Bounded sets and sequences — A set is bounded if it lies in some ball; a sequence is bounded if its range is bounded
• Cartesian product of convex sets is convex — The product Ω1×Ω2 is convex when each factor is convex
• Cauchy sequence — A sequence whose terms eventually become arbitrarily close to each other
• Cauchy sequence with a convergent subsequence converges — A Cauchy sequence converges if one of its subsequences converges
• Cauchy sequences are bounded — A Cauchy sequence must lie in some ball
• Characterization of affine mappings — Affine maps are exactly those that preserve two-point convex combinations
• Characterization of direct sums — A sum is direct iff every element has a unique decomposition into components
• Closed balls are closed — In any metric space, every closed ball is a closed set
• Closed set — A set whose complement is open
• Closed sets via sequences (proof I) — A set is closed iff it contains limits of all convergent sequences from it
• Closed sets via sequences (proof II) — A set is closed iff it contains limits of all convergent sequences from it
• Closure — The smallest closed set containing a given set
• Closure of intersections under an interior-point condition — If convex sets have intersecting interiors, closure distributes over their intersection
• Closure via balls — A point is in the closure iff every ball around it meets the set
• Closure via sequences — In metric spaces, a point is in the closure iff it is a limit of a sequence from the set
• Codimension — The dimension of the quotient space X/L for a subspace L⊂X.
• Codimension-One Subspaces Give Direct Sum Decompositions — If codim(L)=1 and x0∉L, then X=L⊕span{x0}.
• Complete metric space and complete subset — A metric space is complete if every Cauchy sequence converges (in the space)
• Completeness and closedness — Complete subsets are closed; closed subsets of complete spaces are complete
• Completeness of R^k — Every Cauchy sequence in Euclidean space converges
• Complex Separation Theorem (Real Parts) — In complex vector spaces, separation holds via the real part of a complex linear functional.
• Continuity and Level Sets of the Minkowski Gauge — If 0 lies in the interior of a convex set, its gauge is continuous and recovers int(Ω) and cl(Ω).
• Continuity of Linear Functionals via Closed Level Sets — A linear functional on a normed space is continuous iff one of its level sets is closed.
• Convergence implies convergence of norms — If x_n→x, then ||x_n||→||x||
• Convergence in normed spaces — A sequence converges if the norm of its difference to the limit goes to zero
• Convergence of a sequence in a metric space — A sequence converges if points eventually lie arbitrarily close to the limit
• Convergent sequences are bounded — A convergent sequence in a metric space must lie in some ball
• Convergent sequences are Cauchy — Convergence implies the Cauchy property in any metric space
• Convex combination — A weighted average of finitely many points with nonnegative weights summing to one
• Convex function via epigraph — A function is convex if and only if its epigraph is a convex set
• Convex hull — The smallest convex set containing a given set
• Convex hull is the smallest convex set containing Ω — co(Ω) is convex, contains Ω, and lies in every convex superset of Ω
• Convex hull via convex combinations — The convex hull equals the set of all finite convex combinations of points in Ω
• Convex set — A set is convex if it contains the line segment between any two of its points
• Convex sets via convex combinations — A set is convex iff it contains convex combinations of its points
• Convexity characterized by monotonicity of the derivative — A differentiable function on an interval is convex iff its derivative is nondecreasing
• Convexity characterized by positive semidefinite Hessian — A C^2 function on an open convex set is convex iff its Hessian is positive semidefinite everywhere
• Convexity of the Marginal (Optimal Value) Function — Under convexity of the objective and the set-valued map, the value function is convex
• Convexity on a convex subset via extension — Define convexity on Ω by extending f to X with value ∞ outside Ω
• Convexity Preserved Under Affine Composition — Precomposition of a convex function with an affine map preserves convexity
• Convexity Preserved Under Monotone Convex Composition — If f is convex and φ is convex and nondecreasing, then φ∘f is convex
• Convexity via nonnegative second derivative — A twice differentiable function is convex iff f''≥0 on the interval
• Core Characterized by Absorbing Translations — A point lies in core(Ω) iff translating Ω by that point makes it absorbing
• Core Equals Interior for Convex Sets in Normed Spaces — For convex sets with nonempty interior, algebraic and topological interiors coincide.
• Core of a Convex Set is Convex — Taking algebraic interior preserves convexity
• Direct sum of subspaces — A sum of subspaces with trivial intersection
• Distance function to a set — d_Ω(x)=inf{||x−w||: w∈Ω} in a normed space
• Domain of a convex function is convex — The effective domain dom(f) of a convex function is a convex set
• Domain, epigraph, and proper function — dom(f) is where f is finite; epi(f) is the set above the graph; proper means dom(f)≠∅
• Dual Space and Duality Pairing — The continuous dual X* and the pairing ⟨x*,x⟩=x*(x).
• Equivalent characterizations of convex functions — Convexity via epigraph is equivalent to Jensen and extended Jensen inequalities
• Existence of a basis — Every nonzero vector space admits a Hamel basis
• Existence of a Norming Functional — For any nonzero z0, there is a bounded functional f with ||f||=1 and f(z0)=||z0||.
• Extended real number system and conventions — Conventions for inf/sup and extended-real-valued functions used in convex analysis
• Extension of a linearly independent set to a basis — Any nonempty linearly independent set sits inside some Hamel basis
• Hahn–Banach Extension Dominated by a Seminorm (Real Case) — A real linear functional bounded by a seminorm extends with the same bound.
• Hahn–Banach Theorem (Complex Vector Spaces) — Complex linear functionals dominated by a seminorm extend to the whole space.
• Hahn–Banach Theorem (Real Vector Spaces) — A linear functional dominated by a sublinear function extends to the whole space.
• Hahn–Banach Theorem in Normed Spaces — A bounded linear functional on a subspace extends to the whole space without increasing its norm.
• Hölder inequality (finite sums) — ∑|x_i y_i| is bounded by the product of ℓ^p and ℓ^q norms for conjugate exponents
• Hölder inequality (integrals) — ∫|fg| ≤ (∫|f|^p)^(1/p)(∫|g|^q)^(1/q) for conjugate exponents
• Hyperplane — An affine set whose direction subspace has codimension one.
• Hyperplanes as Level Sets of Linear Functionals — In real vector spaces, Ω is a hyperplane iff Ω={x : f(x)=α} for some f≠0.
• Idempotence of the Core Operator — Taking the core twice gives the same set: core(core(Ω))=core(Ω).
• Image, kernel, and linear isomorphism — The image and kernel of a linear operator; bijective linear maps are isomorphisms
• Images and preimages of subspaces under linear maps — Linear maps send subspaces to subspaces and pull back subspaces to subspaces
• Index bound for subsequences — If n1<n2<… are positive integers, then nk≥k
• Indicator function of a set — The extended-real function that is 0 on Ω and ∞ outside Ω
• Interior — The largest open set contained in a given set
• Interior and closure of a convex set are convex — In a normed space, convexity is preserved under interior and closure
• Interior and closure relations for convex sets with nonempty interior — For convex sets with nonempty interior: cl(int Ω)=cl Ω and int(cl Ω)=int Ω
• Interior via balls — A point lies in the interior iff a ball around it is contained in the set
• Intersections of convex sets are convex — Any intersection of convex sets is convex
• Intersections of subspaces — The intersection of any family of linear subspaces is a linear subspace
• Isomorphism theorem for linear operators — The image of a linear map is isomorphic to the quotient by its kernel
• Kernel of a Nonzero Functional Has Codimension One — If f≠0 is linear, then codim(ker f)=1.
• Line Connecting Two Points — The affine line through a and b: {λa+(1−λ)b : λ∈R}.
• Line segments in a vector space — Segments are sets of convex combinations of two points
• Linear Closure — The algebraic analogue of closure for subsets of vector spaces
• Linear Closure Equals Topological Closure for Solid Convex Sets — For convex sets with nonempty interior in a normed space, lin(Ω)=cl(Ω).
• Linear Closure of a Convex Set is Convex — The set lin(Ω) is convex whenever Ω is convex.
• Linear combination — A finite sum of scalar multiples of vectors
• Linear independence and dependence — A set is linearly independent if only the trivial finite linear combination equals zero
• Linear operator — A map between vector spaces preserving addition and scalar multiplication
• Linear subspace — A subset closed under addition and scalar multiplication, forming a vector space in its own right
• Marginal (Optimal Value) Function — The infimum of an objective over a set-valued constraint mapping
• Metric and metric space — A distance function satisfying positivity, symmetry, and the triangle inequality
• Minkowski Function (Gauge) — A set-generated sublinear functional pΩ(x)=inf{t≥0 : x∈tΩ}.
• Nonnegative (positive-semidefinite) operator — A self-adjoint operator A is nonnegative if ⟨Ax,x⟩≥0 for all x
• Norm and normed vector space — A norm assigns lengths to vectors and induces a metric
• Norm induces a metric (and conversely) — A norm defines a metric by d(x,y)=||x−y||; conversely, certain metrics come from norms
• Open and closed balls — Basic neighborhoods defined by a metric
• Open balls are open — In any metric space, every open ball is an open set
• Open set — A set that contains a small open ball around each of its points
• Operations on subsets of a vector space — Set addition, scalar multiplication, and difference inside a vector space
• Operations Preserving Convexity — Nonnegative scaling, finite sums, and finite maxima preserve convexity
• Parallel Affine Set — An affine set Ω is parallel to a subspace L if Ω=ω+L for some ω∈Ω.
• Parallel Subspace to an Affine Set is Ω−Ω — Every nonempty affine set is parallel to a unique subspace L=Ω−Ω.
• Product space — A Cartesian product of vector spaces with componentwise operations
• Properties of Affine Sets and Affine Hulls — Characterizations and closure properties of affine sets; representation of aff(Ω).
• Properties of the Minkowski Gauge of a Convex Set — For absorbing convex Ω, pΩ is sublinear and its level sets describe core(Ω) and lin(Ω).
• Quasiconvex function — A function with f(λx+(1−λ)y)≤max{f(x),f(y)}
• Quasiconvexity via convex sublevel sets — f is quasiconvex iff all sublevel sets {x: f(x)≤α} are convex
• Quotient vector space and codimension — A vector space of cosets modulo a subspace; its dimension defines codimension
• Reverse triangle inequality — The norm difference is bounded by the norm of the difference
• Segments from Core Points Stay in the Core — If a is in core(Ω) and b in Ω, then points on [a,b) remain in core(Ω).
• Segments from interior points stay in the interior — From an interior point, the segment to any other point stays interior except possibly at the endpoint
• Self-adjoint linear operator — An operator A with ⟨Ax,y⟩=⟨x,Ay⟩ on an inner product space
• Seminorm — A subadditive, absolutely homogeneous function p(λx)=|λ|p(x).
• Separating a Point from a Convex Set via the Core — If x0 is outside core(Ω) and core(Ω)≠∅, then Ω and {x0} are separable by a hyperplane.
• Separation by a Closed Hyperplane — Separation using a nonzero continuous functional in the dual space.
• Separation by a Hyperplane — Two sets are separable if a nonzero linear functional orders them.
• Separation by Closed Hyperplane Under an Interior Condition — If int(Ω1)≠∅ and int(Ω1)∩Ω2=∅, then Ω1 and Ω2 are separable by a continuous functional.
• Separation of a Point and a Subspace — If a point has positive distance to a subspace, a bounded functional separates them.
• Separation of Two Convex Sets via the Core Condition — If core(Ω1)≠∅ and core(Ω1) is disjoint from Ω2, then Ω1 and Ω2 are separable by a hyperplane.
• Separation via Sup/Inf Inequality — Hyperplane separation is equivalent to sup_{Ω1}f ≤ inf_{Ω2}f for some f≠0.
• Set-valued mapping (multifunction), domain, graph, and convexity — A set-valued map assigns sets to points; convexity is defined via its graph
• Slope inequalities for convex functions — Secant slopes of a convex function are ordered
• Span — The smallest linear subspace containing a given set
• Span equals finite linear combinations — The span of a set consists exactly of its finite linear combinations
• Strict Separation by a Closed Hyperplane — Strict separation means there is a positive gap between the two sets under a continuous functional.
• Strict Separation of Compact and Closed Convex Sets — Disjoint compact convex and closed convex sets in a normed space admit strict separation by a continuous functional.
• Strict Separation When One Set is Open — An open convex set can be separated from a convex set with a strict inequality gap.
• Strictly convex function — A convex function with strict inequality for distinct points
• Subadditive, Positively Homogeneous, and Sublinear Functions — Key algebraic properties for gauges and Hahn–Banach domination.
• Subsequence — A sequence obtained by restricting to an increasing index sequence
• Subsequences of convergent sequences converge to the same limit — Any subsequence of a convergent sequence converges to the same limit
• Subspace test — A nonempty subset is a subspace iff it is closed under addition and scalar multiplication
• Sum of subspaces and span of the union — The sum of two subspaces is a subspace and equals the span of their union
• Sums and scalar multiples of convex sets are convex — Minkowski sums and dilations preserve convexity
• Supremum of Convex Functions — The pointwise supremum of any family of convex functions is convex
• Uniqueness of limits — A sequence in a metric space has at most one limit
• Uniqueness of limits and boundedness in normed spaces — Limits are unique, and every convergent sequence is bounded
• Vector space — A set with addition and scalar multiplication satisfying the vector space axioms
• Weighted arithmetic–geometric mean inequality — For a,b≥0 and θ∈(0,1): a^θ b^(1−θ) ≤ θa+(1−θ)b
• Young's Inequality — A conjugate-exponent bound: |xy| is controlled by |x|^p/p + |y|^q/q