🔎Convex Geometry Unit 10 – Semidefinite Programming in Convex Geometry

Key Concepts and Definitions

• Convex set a set of points where any two points can be connected by a line segment that lies entirely within the set
• Convex function a function defined on an interval where the line segment between any two points on the graph lies above or on the graph
• Semidefinite programming (SDP) a subfield of convex optimization concerned with optimizing a linear objective function over the intersection of the cone of positive semidefinite matrices with an affine space
• Positive semidefinite matrix a symmetric matrix with non-negative eigenvalues
  • Eigenvalues are the scalar values that, when multiplied by an eigenvector, result in a vector in the same direction as the original eigenvector
• Cone a special type of convex set that is closed under linear combinations with non-negative coefficients
  • Examples include the non-negative orthant (set of vectors with non-negative components) and the second-order cone (set of vectors satisfying a quadratic inequality)
• Dual problem a related optimization problem that provides bounds on the optimal value of the original (primal) problem
• Interior point methods a class of algorithms for solving convex optimization problems by traversing the interior of the feasible region

Historical Context and Applications

• Convex geometry has roots in ancient mathematics, with early work on convex polygons and polyhedra by Euclid and Archimedes
• Modern convex geometry emerged in the 19th and 20th centuries with contributions from mathematicians such as Minkowski, Carathéodory, and Helly
• Semidefinite programming was introduced in the 1990s as a generalization of linear programming, allowing for the optimization of matrix variables
• SDP has found applications in various fields, including:
  • Control theory designing optimal controllers for dynamical systems
  • Combinatorial optimization approximating solutions to NP-hard problems (max-cut, graph coloring)
  • Machine learning kernel methods, dimensionality reduction, and clustering
  • Quantum information theory characterizing entanglement and quantum channel capacities
• SDP has become a powerful tool in theoretical computer science, providing approximation algorithms and lower bounds for hard optimization problems
• Recent developments include faster algorithms for solving large-scale SDP problems and extensions to more general conic optimization problems

Fundamentals of Convex Geometry

• Convex hull the smallest convex set containing a given set of points
  • Can be visualized as the shape formed by stretching a rubber band around the points
• Separation theorems state that disjoint convex sets can be separated by a hyperplane
  • Supports the duality theory of convex optimization
• Extreme points and faces characterize the boundary structure of convex sets
  • Extreme points cannot be expressed as convex combinations of other points in the set
  • Faces are intersections of the set with supporting hyperplanes
• Polyhedral convex sets are defined by a finite number of linear inequalities
  • Includes polytopes (bounded polyhedra) and simplices (minimal polytopes)
• Ellipsoids and balls are important examples of smooth convex sets
  • Ellipsoids are affine transformations of the unit ball
  • Used in the ellipsoid method for convex optimization
• Convex functions play a central role in optimization theory
  • Subgradients generalize the notion of gradients to non-differentiable convex functions
  • Convexity allows for efficient minimization algorithms

Introduction to Semidefinite Programming

• SDP is a generalization of linear programming (LP) where the non-negative constraints on vector variables are replaced by positive semidefinite constraints on matrix variables
• The standard form of an SDP problem is: $\min_X \langle C, X \rangle \text{ s.t. } \langle A_i, X \rangle = b_i, i = 1, \ldots, m, X \succeq 0$ where $C, A_i$ are symmetric matrices, $b_i$ are scalars, and $X \succeq 0$ denotes that $X$ is positive semidefinite
• SDP includes LP and convex quadratic programming (QP) as special cases
  • LP corresponds to diagonal matrices $X$ and $C$
  • QP corresponds to block-diagonal matrices with 2x2 blocks
• SDP can be seen as an optimization problem over the cone of positive semidefinite matrices intersected with an affine subspace
• The dual problem of an SDP has a similar form, with the roles of primal and dual variables exchanged
  • Strong duality holds under mild assumptions (Slater's condition)
• SDP relaxations provide tractable approximations to hard optimization problems
  • Replace non-convex constraints with convex ones
  • Leads to bounds and approximation algorithms

Mathematical Formulation and Notation

• The space of $n \times n$ symmetric matrices is denoted by $\mathbb{S}^n$
  • Equipped with the inner product $\langle A, B \rangle = \text{tr}(AB)$
• The cone of positive semidefinite matrices is denoted by $\mathbb{S}^n_+$
  • Defined by the constraint $X \succeq 0$, meaning $v^TXv \geq 0$ for all vectors $v$
• The primal SDP problem in standard form is: $\min_X \langle C, X \rangle \text{ s.t. } \langle A_i, X \rangle = b_i, i = 1, \ldots, m, X \succeq 0$
• The dual SDP problem is: $\max_y b^Ty \text{ s.t. } \sum_{i=1}^m y_iA_i + S = C, S \succeq 0$ where $y \in \mathbb{R}^m$ and $S \in \mathbb{S}^n_+$
• The feasible set of an SDP is a spectrahedron, a convex set defined by linear matrix inequalities (LMIs)
• SDP can be formulated in various equivalent forms, such as:
  • Inequality form: $\langle A_i, X \rangle \leq b_i$
  • Maximization form: $\max \langle C, X \rangle$
  • Conic form: $\min c^Tx \text{ s.t. } Ax = b, x \in \mathcal{K}$, where $\mathcal{K}$ is a convex cone

Algorithms and Solution Methods

• Interior point methods are the most widely used algorithms for solving SDP problems
  • Based on the idea of traversing the interior of the feasible region while approaching the optimal solution
  • Includes primal-dual path-following methods and potential reduction methods
• The ellipsoid method is a general-purpose algorithm for convex optimization
  • Iteratively refines an ellipsoid containing the optimal solution
  • Polynomial-time complexity but slower in practice compared to interior point methods
• First-order methods, such as the projected gradient method and the mirror descent method, are used for large-scale SDP problems
  • Exploit the structure of the problem and use only gradient information
  • Faster per-iteration complexity but may require more iterations to converge
• Cutting plane methods iteratively refine a polyhedral approximation of the feasible set
  • Includes the analytic center cutting plane method (ACCPM)
• Augmented Lagrangian methods solve a sequence of unconstrained problems with a quadratic penalty term
  • Includes the alternating direction method of multipliers (ADMM)
• Exploiting sparsity and structure can significantly speed up SDP solvers
  • Chordal sparsity in the constraint matrices allows for decomposition into smaller subproblems
  • Symmetry in the problem data can be used to reduce the size of the SDP

Practical Examples and Case Studies

• Max-cut problem: Given a graph, find a partition of the vertices that maximizes the number of edges between the two parts
  • SDP relaxation provides a 0.878-approximation (Goemans-Williamson algorithm)
• Graph coloring: Assign colors to the vertices of a graph such that adjacent vertices have different colors
  • SDP relaxation gives bounds on the chromatic number and approximation algorithms
• Lovász theta function: An SDP-based graph parameter that upper bounds the Shannon capacity
  • Used in the proof of the Lovász sandwich theorem, relating graph parameters
• Quantum entanglement: SDP is used to characterize the entanglement of quantum states
  • Entanglement witnesses and measures can be formulated as SDP problems
• Sensor network localization: Determine the positions of sensors in a network based on noisy distance measurements
  • SDP relaxation provides accurate and efficient localization algorithms
• Portfolio optimization: Find an investment strategy that maximizes expected return while minimizing risk
  • SDP can be used to model and optimize various risk measures (variance, Value-at-Risk)
• Structural optimization: Design structures (trusses, frames) that minimize weight or compliance
  • SDP formulations can incorporate stability and buckling constraints

Advanced Topics and Current Research

• Conic optimization generalizes SDP to optimization over more general convex cones
  • Includes the second-order cone (SOC) and the exponential cone
  • Allows for modeling a wider range of problems, such as geometric programming and entropy maximization
• Robust optimization deals with optimization under uncertainty in the problem data
  • SDP-based formulations provide tractable ways to handle uncertainty sets
• Sum-of-squares (SOS) optimization is a generalization of SDP where the variables are polynomials
  • Used for global optimization of polynomial functions and polynomial matrix inequalities
• Matrix completion aims to recover a low-rank matrix from a subset of its entries
  • SDP relaxations based on nuclear norm minimization have strong theoretical guarantees and practical performance
• Tensor optimization extends SDP to higher-order tensors
  • Includes tensor completion, tensor decomposition, and polynomial optimization
• Quantum algorithms for SDP, such as the quantum interior point method, exploit the properties of quantum computers to solve SDP problems faster
  • Potential for exponential speedup over classical methods
• Deep learning and neural networks have been used to speed up SDP solvers and to learn approximate solutions from data
  • Includes deep neural networks for predicting solution ranks and initializing interior point methods