🔎Convex Geometry Unit 8 – Convex Cones and Their Geometry

Key Concepts and Definitions

• Convex cones generalize the notion of convexity to include rays and half-lines emanating from a common origin
• Defined as a subset of a vector space closed under linear combinations with non-negative coefficients
• Play a fundamental role in various fields such as optimization, linear algebra, and geometry
• Characterized by the property that any convex combination of points within the cone remains inside the cone
• Serve as a natural extension of convex sets and encompass important structures like subspaces and polyhedral cones
  • Subspaces are convex cones that are also closed under negation
  • Polyhedral cones are formed by the intersection of finitely many half-spaces
• Provide a framework for studying directional properties and constraints in mathematical optimization
• Enable the analysis of feasible regions, optimality conditions, and duality in convex optimization problems

Properties of Convex Cones

• Closure under non-negative scalar multiplication ensures that scaling a vector within the cone by a non-negative factor results in another vector inside the cone
• Closure under addition guarantees that the sum of any two vectors in the cone also belongs to the cone
• Convexity implies that the convex combination of any two points in the cone lies within the cone
• Pointed cones have the origin as their unique extreme point, meaning the only way to express the origin as a convex combination of points in the cone is by using the origin itself
• Salient cones are pointed cones that do not contain any entire lines, ensuring a well-defined direction for optimization
• Solid cones have a non-empty interior, allowing for the existence of a ball of positive radius within the cone
• Polyhedral cones are finitely generated and can be represented as the conical hull of a finite set of generating vectors
  • The conical hull is the smallest convex cone containing a given set of vectors

Geometric Representation

• Convex cones can be visualized as unbounded regions in a vector space that emanate from the origin
• In two dimensions, convex cones appear as angular regions bounded by two half-lines starting from the origin
  • Example: The non-negative quadrant in the Cartesian plane ($x \geq 0$ and $y \geq 0$) forms a convex cone
• In three dimensions, convex cones take the shape of infinite pyramids or unbounded polyhedra with the origin as the apex
• The boundary of a convex cone consists of the rays and faces that define its shape and separate it from the rest of the vector space
• The interior of a solid convex cone contains an open ball around each point, allowing for small perturbations within the cone
• The extreme rays of a convex cone are the one-dimensional faces that cannot be expressed as convex combinations of other points in the cone
  • Extreme rays play a crucial role in the representation and analysis of convex cones
• Polyhedral cones have a finite number of extreme rays and can be represented as the intersection of finitely many half-spaces

Types of Convex Cones

• Nonnegative orthant: The set of vectors with all components non-negative, forming a convex cone in the positive quadrant/octant
• Ice-cream cone: A circular cone defined by a quadratic inequality, resembling the shape of an ice-cream cone
• Lorentz cone (second-order cone): Defined by a quadratic inequality involving the Euclidean norm, used in second-order cone programming
• Semidefinite cone: Consists of positive semidefinite matrices, used in semidefinite programming and convex optimization
• Exponential cone: Defined by exponential inequalities, arises in geometric programming and entropy optimization
• Power cone: Generalizes the nonnegative orthant and captures power-like constraints in optimization problems
• Polyhedral cone: Formed by the intersection of finitely many half-spaces, has a finite number of extreme rays
  • Examples include the nonnegative orthant and the cone of non-negative combinations of a finite set of vectors

Algebraic Characterization

• Convex cones can be characterized algebraically using their generating sets and dual cones
• The generating set of a convex cone is a subset of the cone such that every point in the cone can be expressed as a non-negative linear combination of the generating vectors
  • The generating set is not necessarily unique, and different generating sets can yield the same convex cone
• The dual cone of a convex cone $K$ is defined as the set of vectors that form non-negative inner products with every vector in $K$
  • Formally, the dual cone $K^*$ is given by $K^* = \{y : \langle x, y \rangle \geq 0, \forall x \in K\}$
• The bipolar theorem states that the double dual of a closed convex cone is equal to the original cone, i.e., $(K^*)^* = K$
• Farkas' lemma provides a fundamental result connecting the feasibility of a linear system with the existence of a solution to its dual system
  • It states that either $Ax = b$ has a solution $x \geq 0$, or $A^Ty \geq 0$, $b^Ty < 0$ has a solution $y$, but not both
• The Minkowski-Weyl theorem characterizes polyhedral cones as the sum of a finitely generated cone and a linear subspace
  • It establishes a duality between the vertex and facet representations of polyhedral cones

Applications in Optimization

• Convex cones play a central role in convex optimization, where the feasible region and the epigraph of the objective function are often modeled as convex cones
• Linear programming (LP) problems can be formulated using polyhedral cones, where the feasible region is defined by linear inequality constraints
  • The non-negative orthant is used to represent the non-negativity constraints on the decision variables
• Second-order cone programming (SOCP) problems involve constraints defined by the Lorentz cone, allowing for the modeling of quadratic and norm-based constraints
• Semidefinite programming (SDP) problems utilize the semidefinite cone to optimize over positive semidefinite matrices, with applications in combinatorial optimization and control theory
• Conic optimization generalizes LP, SOCP, and SDP by considering optimization problems over arbitrary convex cones
  • It provides a unified framework for solving a wide range of convex optimization problems
• Duality theory in convex optimization relies on the concept of dual cones to derive optimality conditions and establish strong duality results
• Barrier functions and interior-point methods for convex optimization exploit the properties of convex cones to develop efficient algorithms for solving large-scale problems

Dual Cones and Polarity

• The dual cone of a convex cone $K$ is defined as the set of vectors that form non-negative inner products with every vector in $K$
  • Formally, the dual cone $K^*$ is given by $K^* = \{y : \langle x, y \rangle \geq 0, \forall x \in K\}$
• The dual cone $K^*$ is always a closed convex cone, regardless of whether $K$ is closed or not
• The bipolar theorem states that the double dual of a closed convex cone is equal to the original cone, i.e., $(K^*)^* = K$
  • This result establishes a duality relationship between a convex cone and its dual cone
• Polarity is a correspondence between convex cones and their dual cones, generalizing the concept of orthogonality in Euclidean spaces
• The polar cone of a convex cone $K$ is defined as the negative of its dual cone, i.e., $K^\circ = -K^*$
  • The polar cone consists of vectors that form non-positive inner products with every vector in $K$
• The polarity relationship between a convex cone and its polar cone satisfies properties such as reflexivity, anti-monotonicity, and invertibility
• Farkas' lemma and the Minkowski-Weyl theorem have dual formulations in terms of polar cones, connecting the primal and dual representations of convex cones

Advanced Topics and Extensions

• Cone programming generalizes convex optimization by considering optimization problems over arbitrary convex cones
  • It subsumes linear programming, second-order cone programming, and semidefinite programming as special cases
• Cone duality theory extends the concepts of Lagrangian duality and KKT conditions to the setting of cone programming
  • It provides optimality conditions and duality results for a wide range of convex optimization problems
• Symmetric cones are self-dual cones that exhibit favorable algebraic and geometric properties
  • Examples include the nonnegative orthant, the Lorentz cone, and the positive semidefinite cone
• Homogeneous cones are convex cones that are homogeneous under the action of a linear automorphism group
  • They have connections to Jordan algebras and have applications in interior-point methods and conic optimization
• Hyperbolicity cones are convex cones associated with hyperbolic polynomials and have connections to real algebraic geometry and convex optimization
• Spectral cones are convex cones arising from the eigenvalue functions of symmetric matrices and have applications in matrix optimization and control theory
• Copositive and completely positive cones are non-polyhedral cones that have gained attention in combinatorial optimization and quadratic programming
  • Copositive programming generalizes semidefinite programming by considering cones of copositive matrices