Semidefinite Programming and Combinatorial Optimization

AIAA 3225 · Learning and Optimization for Artificial Intelligence

Week 6: SDP and Combinatorial Optimization

Instructor: Prof. Xin Wang

Date: October 16, 2025

Matrix Norms via SDP

Nuclear & Spectral Norms

Maximum Cut Problem

Graph Laplacian & Binary Encoding

Goemans-Williamson

0.878-Approximation Algorithm

Shannon Capacity

Lovász Theta Function

Matrix Norms via Semidefinite Programming

Schatten $p$-Norms

For a matrix $A \in \mathbb{R}^{m \times n}$ with singular values $\sigma_1(A) \geq \sigma_2(A) \geq \cdots \geq 0$:

\|A\|_p := \begin{cases} \left(\sum_{k=1}^{\min(m,n)} \sigma_k^p(A)\right)^{1/p}, & 1 \leq p < \infty\\[8pt] \sigma_1(A), & p = \infty \end{cases}

Nuclear Norm ($p=1$): $\|A\|_1 = \sum_k \sigma_k(A)$

Sum of all singular values (also called trace norm)

Convex envelope of rank on the unit ball
Used in matrix completion and low-rank approximation
Sparsity-inducing norm for matrices

Frobenius Norm ($p=2$): $\|A\|_F = \sqrt{\sum_k \sigma_k^2(A)} = \sqrt{\sum_{ij} A_{ij}^2}$

Euclidean norm of the matrix entries

Also equals $\sqrt{\tr(A^TA)}$
Natural extension of vector $\ell_2$ norm
Easy to compute directly from entries

Spectral Norm ($p=\infty$): $\|A\|_\infty = \sigma_1(A)$

Largest singular value (also called operator norm or $\ell_2$ operator norm)

Equals $\max_{\|x\|_2=1,\|y\|_2=1} y^TAx$
For symmetric matrices: $\|A\|_\infty = \max\{|\lambda_{\max}(A)|, |\lambda_{\min}(A)|\}$
Measures maximum stretching factor

Norm Duality

The nuclear and spectral norms are dual to each other:

\|A\|_\infty = \max_{\|Y\|_1 \leq 1} \langle A, Y \rangle, \quad \|A\|_1 = \max_{\|Y\|_\infty \leq 1} \langle A, Y \rangle

where $\langle A, Y \rangle = \tr(A^TY)$ is the trace inner product

Spectral Norm via SDP

For a symmetric matrix $M \in \mathbb{S}^n$, the spectral norm is:

\|M\|_\infty = \max_{\|x\|_2 = 1} |x^T M x| = \max\{|\lambda_{\max}(M)|, |\lambda_{\min}(M)|\}

SDP Formulation via Schur Complement

Consider the block matrix:

X(t) = \begin{pmatrix} tI_n & M \\ M & tI_n \end{pmatrix} \in \mathbb{S}^{2n}

Key Insight (Schur Complement): $X(t) \succeq 0$ if and only if:

$tI_n \succeq 0$ (always true for $t \geq 0$)
$tI_n - M(tI_n)^{-1}M \succeq 0$, which gives $t^2I_n - M^2 \succeq 0$
This holds iff $t^2 I_n \succeq M^2$, i.e., $t \geq \|M\|_\infty$

Primal SDP: $$\begin{align} \minimize \quad & t \\ \st \quad & \begin{pmatrix} tI_n & M \\ M & tI_n \end{pmatrix} \succeq 0 \end{align}$$

Nuclear Norm via SDP

For a general matrix $M \in \mathbb{R}^{m \times n}$, the nuclear norm $\|M\|_1 = \sum_{k} \sigma_k(M)$:

SDP Formulation

Primal SDP: $$\begin{align} \minimize \quad & \frac{1}{2}(\tr(U) + \tr(V)) \\ \st \quad & \begin{pmatrix} U & M \\ M^T & V \end{pmatrix} \succeq 0 \\ & U \in \mathbb{S}^m, \; V \in \mathbb{S}^n \end{align}$$

Correctness: At optimum, by complementarity, $U$ and $V$ are tight, giving $U = (MM^T)^{1/2}$ and $V = (M^TM)^{1/2}$, hence $\tr(U) + \tr(V) = 2\sum_k \sigma_k(M)$

Schur Complement Interpretation

The PSD constraint ensures:

$U, V \succeq 0$
$U - MV^{-1}M^T \succeq 0$ (when $V \succ 0$)
All singular values satisfy $\sigma_k^2(M) \leq \lambda_i(U)\lambda_j(V)$

Dual Problem

With dual variable $Y \in \mathbb{R}^{m \times n}$:

\max \langle M, Y \rangle

subject to:

\begin{pmatrix} I_m & Y \\ Y^T & I_n \end{pmatrix} \succeq 0

which is equivalent to $\|Y\|_\infty \leq 1$

Duality Connection

The unit balls $\{\|M\|_\infty \leq 1\}$ and $\{\|M\|_1 \leq 1\}$ are polar to each other under the trace inner product, reflecting the fundamental duality between spectral and nuclear norms.

The Maximum-Cut Problem

Problem Setup

Weighted Undirected Graph: $G = (V,E,w)$ where:

$V=\{1,\dots,n\}$ is the vertex set
$E\subseteq\{\{i,j\} : i,j \in V, i\neq j \}$ is the edge set
$w:E\to\mathbb{R}_{>0}$ assigns positive weights $w_{ij} > 0$

\text{Cut Value: } \val(S,S^{c}) = \sum_{\substack{i\in S, j\in S^{c} \\ \{i,j\} \in E}} w_{ij}

Real-World Applications:

Social Networks: Community detection and clustering
VLSI Design: Circuit partitioning for chip layout
Statistical Physics: Ising spin glass ground states
Machine Learning: Feature selection and clustering
Image Segmentation: Computer vision applications

MAX-CUT Problem

\maximize_{S\subseteq V}\sum_{\substack{i\in S, j\in S^{c} \\ \{i,j\} \in E}} w_{ij}

This is NP-hard!

No polynomial-time exact algorithm unless P = NP (Karp, 1972)

Simple Example: Triangle Graph $K_3$

Complete graph on 3 vertices with unit weights:

Partition $(+,+,+)$ or $(-,-,-)$: Cut value = 0 (all on same side)
Partition $(+,+,-)$ and permutations: Cut value = 2 (two edges cut)

Optimal value: 2 (any balanced partition)

Binary Encoding and Graph Laplacian

Binary $\{-1,+1\}$ Encoding

Associate to every cut $(S,S^{c})$ the sign vector $x\in\{-1,+1\}^{n}$:

x_i = \begin{cases} +1 &\text{if } i\in S\\ -1 &\text{if } i\in S^{c} \end{cases}

Key Identity

For any edge $\{i,j\} \in E$:

\frac{1 - x_ix_j}{2} = \begin{cases} 1 &\text{if } x_i \neq x_j \text{ (edge is cut)}\\ 0 &\text{if } x_i = x_j \text{ (edge not cut)} \end{cases}

Since $(1-x_ix_j)/2 = (x_i - x_j)^2/4$ when $x_i, x_j \in \{-1,+1\}$

Graph Laplacian Matrix

Define $L_G\in\mathbb{S}^{n}$ such that:

x^{T} L_G x = \sum_{\{i,j\} \in E} w_{ij}(x_i - x_j)^2 \quad \forall x \in \mathbb{R}^n

Explicit form:

(L_G)_{ij} = \begin{cases} \sum_{k: \{i,k\} \in E} w_{ik} &\text{if } i=j \text{ (weighted degree)}\\ -w_{ij} &\text{if } \{i,j\} \in E\\ 0 &\text{otherwise} \end{cases}

Note: $L_G$ is positive semidefinite with smallest eigenvalue 0

Quadratic Reformulation

Step 1: Cut value in terms of indicator

\val(S,S^{c}) = \sum_{\{i,j\} \in E}w_{ij} \cdot \frac{1-x_ix_j}{2}

Step 2: Convert to quadratic form

= \frac{1}{4}\sum_{\{i,j\} \in E}w_{ij}(x_i-x_j)^2

Step 3: Express using Laplacian

= \frac{1}{4}x^{T}L_{G}x

Conclusion: MAX-CUT $\equiv$ $\maximize_{x\in\{-1,1\}^{n}} \frac{1}{4}x^{T}L_{G}x$

SDP Relaxation of MAX-CUT

Matrix Lifting Technique

Given feasible $x\in\{-1,1\}^{n}$, define $X := xx^{T}\in \mathbb{S}^{n}$

Property 1

$X\succeq 0$

(PSD as Gram matrix)

Property 2

$\text{rank}(X)=1$

(Rank-one structure)

Property 3

$X_{ii}=1$

(Since $x_i^2 = 1$)

Key observation: $x^{T}L_Gx = \sum_{ij}(L_G)_{ij}x_ix_j = \sum_{ij}(L_G)_{ij}X_{ij} = \tr(L_GX)$

Semidefinite Relaxation

Drop the non-convex rank-one constraint:

$$\begin{align} \maximize \quad & \frac{1}{4}\tr(L_G X) \\ \st \quad & X\succeq 0\\ & X_{ii}=1,\quad i=1,\dots,n \end{align}$$

Alternative formulation using $\tr(L_GX) = \frac{1}{2}\sum_{\{i,j\} \in E}w_{ij}(X_{ii} + X_{jj} - 2X_{ij})$:

$$\begin{align} \maximize \quad & \frac{1}{4}\sum_{\{i,j\} \in E}w_{ij}(1 - X_{ij}) \\ \st \quad & X\succeq 0,\; X_{ii}=1 \; \forall i \end{align}$$

                            Why It's a Relaxation
                            Feasibility: Every $x \in \{-1,1\}^n$ gives feasible $X=xx^T$
Objective: Same value $\tr(L_GX) = x^TL_Gx$
Relaxation: Larger feasible set (dropped rank constraint)
Result: SDP optimum $\geq$ true MAX-CUT value

                        

Geometric Interpretation

Cut Polytope: $\conv\{xx^T : x \in \{-1,1\}^n\}$

Elliptope: $\mathcal{E}_n = \{X \succeq 0 : X_{ii} = 1, i=1,\ldots,n\}$

We have: Cut Polytope $\subseteq$ Elliptope

SDP optimizes over the larger elliptope

Fundamental Question: How close is the SDP optimum to the true MAX-CUT value?

Quick Check: Understanding SDP Relaxations

Question: Why is the SDP relaxation always an upper bound on MAX-CUT?

A. Because SDP solvers use approximation algorithms

B. Because the Laplacian matrix is positive semidefinite

C. Because we dropped the rank-1 constraint, enlarging the feasible set

D. Because Goemans-Williamson proved it in 1995

✓ Correct!
The SDP feasible region (elliptope) contains all rank-1 matrices $xx^T$ from the original problem, but also includes higher-rank PSD matrices. Since we're maximizing, a larger feasible set can only give an objective value ≥ the original optimum. This is the fundamental principle of convex relaxation.

Key Takeaway

Every convex relaxation of a discrete optimization problem provides an upper bound (for maximization) or lower bound (for minimization) on the optimal value. The quality of this bound depends on how tight the relaxation is.

Goemans-Williamson Algorithm

Main Approximation Result (Goemans-Williamson, 1995)

\alpha_{GW} \cdot p^{\star}_{\text{SDP}} \leq v^{\star}_{\text{MAX-CUT}} \leq p^{\star}_{\text{SDP}}

where

\alpha_{GW} = \min_{0 \leq \theta \leq \pi}\frac{\theta/\pi}{(1 - \cos\theta)/2} \approx 0.87856

The minimum is achieved at $\theta \approx 2.331$ radians (equivalently $t = \cos\theta \approx -0.689$)

This is the best possible for polynomial-time algorithms assuming the Unique Games Conjecture (Khot et al., 2007)!

Randomized Hyperplane Rounding Algorithm

Input: Optimal SDP solution $X^{\star}$ with Cholesky factorization $X^{\star} = VV^T$

where $V \in \mathbb{R}^{n \times r}$ (with $r = \text{rank}(X^{\star})$) has rows $v_1, \ldots, v_n$ that are unit vectors: $\|v_i\|_2 = 1$

Algorithm Steps:

Draw random Gaussian vector $g \sim \mathcal{N}(0,I_r)$
For each $i = 1, \ldots, n$: Set $x_i := \sign(\langle v_i,g\rangle)$ where $\sign(0) = +1$
Define cut: $S = \{i : x_i = +1\}$, $S^c = \{i : x_i = -1\}$
Output cut $(S,S^c)$ with value $\frac{1}{4}x^TL_Gx$

Geometric Interpretation

The algorithm cuts the unit vectors $\{v_i\}_{i=1}^n \subset \mathbb{R}^r$ by a random hyperplane through the origin with normal direction $g$. Vertices on the same side of the hyperplane are placed in the same partition.

\text{Hyperplane: } \{u \in \mathbb{R}^r : \langle g, u \rangle = 0\}

Analysis of Goemans-Williamson

Key Lemma: Expected Correlation

For the rounding $x_i = \sign(\langle v_i,g\rangle)$ where $g \sim \mathcal{N}(0,I_r)$:

\mathbb{E}[x_ix_j] = 1-\frac{2}{\pi}\arccos(\langle v_i, v_j \rangle) = 1-\frac{2\theta_{ij}}{\pi}

where $\theta_{ij} = \arccos(\langle v_i,v_j\rangle) \in [0,\pi]$ is the angle between $v_i$ and $v_j$

Proof Sketch

Let $\theta = \arccos(\langle v_i,v_j\rangle)$ be the angle between $v_i$ and $v_j$.

Key insight: $x_ix_j = -1$ (different signs) occurs when $g$ falls in a cone of angular width $\theta$ on each side.

By rotational symmetry of the Gaussian:

\mathbb{P}[\sign(\langle v_i,g\rangle) \neq \sign(\langle v_j,g\rangle)] = \frac{\theta}{\pi}

Therefore:

\mathbb{E}[x_ix_j] = 1 \cdot (1-\theta/\pi) + (-1) \cdot \theta/\pi = 1 - 2\theta/\pi

Expected Cut Value

Using the identity $\val(S,S^c) = \frac{1}{4}x^TL_Gx$:

\mathbb{E}[\val(S,S^c)] = \frac{1}{4}\sum_{\{i,j\} \in E}w_{ij}(1-\mathbb{E}[x_ix_j])

= \frac{1}{4}\sum_{\{i,j\} \in E}w_{ij} \cdot \frac{2\theta_{ij}}{\pi}

Comparison to SDP Value

The SDP optimal value is:

p^*_{\text{SDP}} = \frac{1}{4}\sum_{\{i,j\} \in E}w_{ij}(1-X^*_{ij})

Since $X^*_{ij} = \langle v_i, v_j \rangle = \cos\theta_{ij}$:

p^*_{\text{SDP}} = \frac{1}{4}\sum_{\{i,j\} \in E}w_{ij}(1-\cos\theta_{ij})

Critical Approximation Bound

Define $\alpha(\theta) := \frac{\theta/\pi}{(1-\cos\theta)/2}$ for $\theta \in (0,\pi]$

Then: $\frac{2\theta}{\pi} \geq \alpha_{GW} \cdot (1-\cos\theta)$ where $\alpha_{GW} = \min_{\theta \in (0,\pi]} \alpha(\theta) \approx 0.87856$

Therefore:

\mathbb{E}[\val(S,S^c)] \geq \alpha_{GW} \cdot \frac{1}{4}\sum_{\{i,j\} \in E}w_{ij}(1-X^*_{ij}) = \alpha_{GW} \cdot p^*_{\text{SDP}}

Recap: Part I – Matrix Norms & MAX-CUT

What We've Covered So Far

📊 Matrix Norms via SDP

Nuclear norm $\|·\|_1$ and spectral norm $\|·\|_\infty$
Dual relationship via trace inner product
SDP formulations using Schur complements
Applications to matrix completion

✂️ Maximum Cut Problem

NP-hard combinatorial optimization
Quadratic formulation via graph Laplacian
SDP relaxation through matrix lifting
0.878-approximation via randomized rounding

                    🔑 Key Techniques
                    Convex Relaxation: Drop non-convex constraints (e.g., rank-1) to get tractable problems
Schur Complement: Essential tool for converting matrix inequalities to SDP form
Randomized Rounding: Extract discrete solutions from continuous SDP solutions
Probabilistic Analysis: Prove approximation guarantees in expectation

                

Coming Up Next: Shannon Capacity

We'll explore how SDP techniques apply to information theory and graph coloring problems through the Lovász theta function.

Shannon Capacity and Communication

Noisy Communication Model

Setting: Transmit symbols from alphabet $\{1,\dots,n\}$ over a noisy channel

Confusability Graph $G=(V,E)$:

Vertices $V = \{1,2,\ldots,n\}$ represent symbols
Edge $\{i,j\} \in E$ means symbols $i,j$ may be confused by receiver
Safe transmission requires independent set (no edges between used symbols)

\alpha(G) = \max\{|S| : S\subseteq V,\; \{i,j\} \notin E\text{ for all }i,j\in S, i \neq j\}

$\alpha(G)$ is the independence number (maximum size of independent set)

Block Coding Strategy

Transmit blocks of length $k$: $(i_1,\dots,i_k) \in V^k$

Strong Graph Product

$G^{\boxtimes k}$ has vertex set $V^k$ and edges:

\{(i_1,\ldots,i_k), (j_1,\ldots,j_k)\} \in E(G^{\boxtimes k})

if for every coordinate $\ell$, either $i_\ell=j_\ell$ or $\{i_\ell,j_\ell\} \in E(G)$

Shannon Capacity (Shannon, 1956)

\Theta(G) = \lim_{k\to\infty}\bigl(\alpha(G^{\boxtimes k})\bigr)^{1/k}

(The limit exists by Fekete's lemma since $\{\log\alpha(G^{\boxtimes k})\}$ is subadditive)

Information Rate: $\log_2\Theta(G)$ bits per symbol

Alternative form:

C_0(G) = \lim_{k\to\infty}\frac{1}{k}\log_2\alpha(G^{\boxtimes k})

Famous Example: Pentagon $C_5$

$\alpha(C_5) = 2$ (can use 2 non-adjacent symbols)
$\alpha(C_5^{\boxtimes 2}) = 5$ (block coding achieves more!)
Lovász proved: $\Theta(C_5) = \sqrt{5} \approx 2.236$
Open problem: What is $\Theta(C_7)$? (Known: $3 \leq \Theta(C_7) \leq 3.3177...$)

The Lovász Theta Function

Orthonormal Representation (Lovász, 1979)

A collection $(c,u_1,\dots,u_n)$ of unit vectors in $\mathbb{R}^m$ is an orthonormal representation of $G$ if:

\langle u_i, u_j \rangle = 0 \quad\text{whenever }\{i,j\}\notin E \text{ and } i \neq j

Non-adjacent vertices must have orthogonal unit vectors!

Note: All vectors are unit: $\|c\|_2 = \|u_i\|_2 = 1$

Lovász $\vartheta$ Function

\vartheta(G) := \min_{(c,u_1,\dots,u_n)} \max_{1\leq i\leq n}\frac{1}{(\langle c, u_i \rangle)^2}

where the minimum is over all orthonormal representations of $G$.

Alternative formulation: $\vartheta(G) = \max_{\text{orth. rep.}} \min_i (\langle c,u_i\rangle)^2$ is the dual form

Lower Bound

\alpha(G) \leq \vartheta(G)

Independent set gives orthogonal vectors

Upper Bound

\vartheta(G) \leq \chi(\overline{G})

$\chi(\overline{G})$ is chromatic number of complement

Computability

\text{Polynomial Time}

Via semidefinite programming!

Fundamental Inequalities (Lovász, 1979)

\alpha(G) \leq \Theta(G) \leq \vartheta(G) \leq \chi(\overline{G})

Furthermore, $\vartheta$ is multiplicative under strong product: $\vartheta(G \boxtimes H) = \vartheta(G) \cdot \vartheta(H)$

This implies $\vartheta(G^{\boxtimes k}) = \vartheta(G)^k$, so $\Theta(G) \leq \vartheta(G)$

Since computing $\alpha(G)$ is NP-hard, $\vartheta(G)$ provides a polynomial-time computable upper bound!

SDP Formulation of $\vartheta(G)$

Primal SDP via Gram Matrix

Let $u_0 = c$ and construct the $(n+1) \times (n+1)$ Gram matrix:

X = \begin{bmatrix} u_0 \\ u_1 \\ \vdots \\ u_n \end{bmatrix} \begin{bmatrix} u_0 \\ u_1 \\ \vdots \\ u_n \end{bmatrix}^T

So $X_{ij} = \langle u_i, u_j \rangle$ for $i,j = 0,1,\ldots,n$

Primal SDP: $$\begin{align} \vartheta(G) = \max \quad & \sum_{i=1}^n X_{0i}\\[6pt] \st \quad & X_{00} = 1\\ & X_{ij} = 0 \quad \forall\{i,j\}\notin E,\; 1 \leq i < j \leq n\\ & \tr(X) = 1 + \sum_{i=1}^n X_{ii} = n+1 \text{ (unit vectors)}\\ & X \succeq 0 \end{align}$$

Note: The objective $\sum_{i=1}^n X_{0i} = \sum_{i=1}^n \langle c,u_i\rangle$ is maximized when all $\langle c,u_i\rangle$ are equal

Constraint Interpretation

$X_{00} = 1$: Handle $c$ is unit vector
$X_{ij} = 0$: Orthogonality for non-edges in $G$
$\tr(X) = n+1$: All $n+1$ vectors are unit length
$X \succeq 0$: Valid Gram matrix structure

Dual SDP (Simplified)

$$\begin{align} \vartheta(G) = \min \quad & \lambda\\[4pt] \st \quad & \lambda I - J - A_{\overline{G}} \succeq 0 \end{align}$$

where $J$ is the all-ones matrix and $A_{\overline{G}}$ is the adjacency matrix of the complement graph $\overline{G}$

Polynomial-Time Solvability

Both primal and dual satisfy Slater's condition, ensuring:

Optimal values are equal (strong duality)
Optimal solutions exist
Solvable in polynomial time via interior-point methods
Complexity: $O(n^{4.5})$ or better with modern SDP solvers

Worked Example: Pentagon $C_5$

Computing $\vartheta(C_5) = \sqrt{5}$

The pentagon $C_5$ has 5 vertices arranged in a cycle. By symmetry, we can construct an optimal solution to the dual SDP:

\lambda I - J - A_{\overline{G}} \succeq 0

For $C_5$, the complement $\overline{C_5}$ consists of edges between vertices at distance 2 in the cycle.

Dual Certificate

The matrix $\lambda I - J - A_{\overline{C_5}}$ must be PSD. By symmetry and eigenvalue analysis:

All-ones vector has eigenvalue: $\lambda - 5 - 0 = \lambda - 5$
Other eigenvectors have eigenvalue: $\lambda - 0 - \varphi$ or $\lambda + \varphi - 1$

where $\varphi = \frac{1+\sqrt{5}}{2}$ is the golden ratio

Optimal Value

For PSD, we need all eigenvalues $\geq 0$:

\lambda \geq \max\{5, 1-\varphi\} = 5

But by careful analysis of the pentagon's structure:

\lambda^* = \sqrt{5}

Verification via Primal

The primal constructs unit vectors in $\mathbb{R}^3$ forming a symmetric "umbrella" configuration. The handle vector $c$ and rib vectors $u_1,\ldots,u_5$ satisfy:

All vectors have unit length
Non-adjacent vertices have orthogonal vectors
All inner products $\langle c, u_i\rangle$ are equal to $1/\sqrt{\varphi}$

This gives $\vartheta(C_5) = 5 \cdot (1/\sqrt{\varphi}) = \sqrt{5}$

Final Result

Since we also know $\alpha(C_5^{\boxtimes 2}) = 5$, we have $\Theta(C_5) \geq \sqrt{5}$

\boxed{\Theta(C_5) = \vartheta(C_5) = \sqrt{5}}

This is one of the few cases where Shannon capacity is exactly computable!

Summary: SDP in Combinatorial Optimization

Key Paradigms We've Learned

🔧 Matrix Lifting

Replace variables $x$ with matrices $X = xx^T$
Drop non-convex rank constraints
Preserve essential structure via linear constraints
Enables convex relaxation of discrete problems

🎯 Randomized Rounding

Extract discrete solutions from SDP solutions
Hyperplane cuts in geometric representations
Performance guarantees via probabilistic analysis
Often achieves best-known approximation ratios

                        Matrix Norms
                        Spectral norm: $\|M\|_\infty$ via Schur complement
Nuclear norm: $\|M\|_1$ minimization
Duality: $(·)_\infty$ and $(·)_1$ are dual norms
Applications: matrix completion, robust PCA

                    

                        Maximum Cut
                        Graph Laplacian formulation
SDP relaxation via matrix lifting
GW algorithm: 0.878-approximation
Best possible under UGC

                    

                        Shannon Capacity
                        Information-theoretic channel capacity
Lovász $\vartheta$ function bounds $\Theta(G)$
Polynomial-time via SDP
Exact for $C_5$: $\Theta(C_5) = \sqrt{5}$

                    

🚀 Broader Impact & Future Directions

Semidefinite programming has revolutionized approximation algorithms and beyond:

Machine Learning: Matrix completion, robust PCA, metric learning, kernel methods
Control Theory: Linear matrix inequalities (LMIs), robust control, $\mathcal{H}_\infty$ control
Quantum Information: Entanglement detection, quantum games, separability
Combinatorial Optimization: Graph coloring, MAX-SAT, constraint satisfaction
Sum-of-Squares: Polynomial optimization, moment problems, hierarchies

📚 Key References

Thank You!

Questions and Discussion