Conic Optimization: Linear, Second-Order Cone, and Semidefinite Programs

Intuition Beginner

Linear programming is the workhorse of optimization: minimize a linear cost while every variable stays nonnegative and a few linear equations hold. The nonnegativity rule says each coordinate lives on the good side of zero. Geometrically, the allowed region is a flat-faced shape — corners and straight edges — and the best point sits at a corner.

Conic optimization keeps the linear cost and the linear equations but swaps the "every coordinate is nonnegative" rule for a richer kind of rule: the variable must lie inside a chosen cone. A cone is a region that is closed under scaling up from the origin — if a point is in it, the whole ray from the origin through that point is in it too. The nonnegative quadrant is one cone, but there are curved ones as well.

Why bother with curved cones? Because two of them unlock problems that flat shapes cannot describe. The ice-cream cone (its formal name is the second-order or Lorentz cone) lets you say "the length of this vector is at most this number" — a smooth, round constraint that captures distances, norms, and uncertainty. The cone of positive-semidefinite matrices lets you constrain the eigenvalues of a matrix all at once, which controls vibration frequencies, stability, and energy.

The beautiful part is that all three live in one family. A linear program is a conic program over the quadrant; a second-order cone program is a conic program over the ice-cream cone; a semidefinite program is a conic program over the matrix cone. Each one contains the previous as a special case, so a single theory — one notion of duality, one kind of solver — handles all of them at once.

Visual Beginner

Figure: three cones side by side in increasing generality. On the left, the nonnegative quadrant of the plane — a flat wedge with straight edges, labelled LP. In the middle, the round ice-cream cone in three dimensions: all points whose horizontal radius is at most their height, labelled SOCP. On the right, a smooth curved cone of matrices labelled SDP, drawn as a rounded solid. Arrows of inclusion point left-to-right: the wedge sits inside the ice-cream cone, which sits inside the matrix cone.

      LP cone                 SOCP cone                  SDP cone
   (nonneg orthant)        (ice-cream / Lorentz)      (PSD matrices)

      t |  . . . .            t  |    /\               curved smooth
        | . region .             |   /  \              solid: matrices
        |. . . . . .             |  / .. \             with all
        +-----------  x          | /......\            eigenvalues >= 0
        |                        +---------- x
   straight edges,          round circular base,    a "bowl" of matrices;
   sharp corners            smooth side wall         its boundary is curved

          LP    is inside   SOCP    is inside    SDP
   (each is a special case of the next: one theory covers all three)

Worked example Beginner

We solve a small second-order cone problem by hand and watch the round constraint do its work. Minimize the cost $-x-y$ (so we want $x+y$ as large as possible) subject to the single round rule that the point $(x,y)$ stays inside the unit disk: $\sqrt{x^2+y^2}\le 1$.

Step 1. Read the rule as a cone constraint. The rule "length at most $1$" is the ice-cream-cone condition $\sqrt{x^2+y^2}\le t$ with the height fixed at $t=1$. It is a smooth, curved constraint, not a flat one.

Step 2. Guess the best direction. We want $x+y$ large. Pushing equally in $x$ and $y$ uses the budget best, so try the point on the circle in the direction $(1,1)$, normalized to length $1$: that is $(x,y)=\left(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}\right)$.

Step 3. Check feasibility. Its length is $\sqrt{\frac{1}{2}+\frac{1}{2}}=\sqrt{1}=1\le 1$, so the point sits exactly on the boundary of the disk and the rule holds.

Step 4. Compute the cost. Here $x+y=\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{2}}=\frac{2}{\sqrt{2}}=\sqrt{2}\approx 1.414$, so the cost $-x-y=-\sqrt{2}\approx -1.414$.

What this tells us. Unlike a linear program, the best point is not at a sharp corner — the disk has no corners. It is the point where the boundary circle is tangent to the cost direction. Curved cones move the optimum onto smooth boundary, and that single change is what lets conic programs capture distances and norms that linear programs cannot.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, ${\mathbb{R}}^n$ carries the standard inner product; in matrix space ${\mathbb{S}}^n$ (real symmetric $n\times n$ matrices) the inner product is $⟨A,B⟩=\mathrm{tr}(AB)$.

Definition (proper cone and generalized inequality). A convex cone $K\subseteq {\mathbb{R}}^N$ is proper if it is closed, has nonempty interior (solid), and contains no line (pointed: $K\cap (-K)=\{0\}$). A proper cone induces a partial order, the generalized inequality

$$x{⪯}_{K}y⟺y-x\in K,x{\prec }_{K}y⟺y-x\in \mathrm{int}K,$$

which is reflexive, antisymmetric, transitive, and compatible with addition and nonnegative scaling ^{[Boyd & Vandenberghe §2.4]}. Writing $x{⪰}_{K}0$ means $x\in K$.

Definition (conic program). Given $c\in {\mathbb{R}}^N$, an affine map specified by $A\in {\mathbb{R}}^{m\times N}$ and $b\in {\mathbb{R}}^m$, and a proper cone $K\subseteq {\mathbb{R}}^N$, the (primal) conic program in standard form is

$$p^{\star }=\underset{x}{\inf }{c}^{\top }x\text{subject to}Ax=b,x{⪰}_{K}0.$$

It is a convex program: the objective is linear and the feasible set $\{x:Ax=b\}\cap K$ is the intersection of an affine subspace with a convex cone, hence convex (the operation calculus of 44.01.01).

Definition (dual cone). The dual cone of $K$ is $K^{\ast }=\{y:⟨y,x⟩\ge 0\text{for all }x\in K\}$, itself a proper cone whenever $K$ is, with $K^{\ast \ast }=K$ for closed convex $K$. A cone is self-dual if $K^{\ast }=K$.

The three canonical cones. Each is proper and self-dual under its natural inner product:

• Nonnegative orthant $K={\mathbb{R}}_{+}^N=\{x:x_i\ge 0\}$. The conic program is a linear program (LP); ${⪯}_K$ is componentwise inequality.
• Second-order (Lorentz / ice-cream) cone $K={\mathcal{L}}^{n+1}=\{(u,t)\in {\mathbb{R}}^n\times \mathbb{R}:\Vert u{\Vert }_2\le t\}$. A conic program with this cone (or a product of such cones) is a second-order cone program (SOCP).
• Positive-semidefinite cone $K={\mathbb{S}}_{+}^n=\{X\in {\mathbb{S}}^n:X⪰0\}$, i.e. all eigenvalues nonnegative (01.01.13). The conic program over ${\mathbb{S}}_{+}^n$ is a semidefinite program (SDP); $X{⪯}_{K}Y$ means $Y-X$ is PSD. In standard SDP form $Ax=b$ is read as $⟨A_i,X⟩=b_i$ and the objective as $⟨C,X⟩$.

The inclusion LP $\subset$ SOCP $\subset$ SDP. A componentwise inequality $x\ge 0$ is a product of one-dimensional Lorentz constraints $\Vert 0{\Vert }_2\le x_i$, so every LP is an SOCP. A Lorentz constraint $\Vert u{\Vert }_2\le t$ is equivalent to a linear matrix inequality via the Schur complement (below): $\Vert u{\Vert }_2\le t⟺\left[\begin{array}{cc}tI& u\\ u^{\top }& t\end{array}\right]⪰0$, so every SOCP is an SDP. The expressive ladder is strict: SDP captures eigenvalue constraints no SOCP can.

Definition (conic dual problem). The Lagrange dual of the primal conic program, pairing the equality $Ax=b$ with a free multiplier $y$ and the cone membership $x{⪰}_{K}0$ with a multiplier in the dual cone, is the conic dual

$$d^{\star }=\underset{y}{\sup }{b}^{\top }y\text{subject to}{A}^{\top }y{⪯}_{K^{\ast }}c,\text{i.e.}c-A^{\top }y\in K^{\ast }.$$

Here $s=c-A^{\top }y\in K^{\ast }$ is the dual slack. The pairing is symmetric: dualizing the dual returns the primal, because $K^{\ast \ast }=K$.

Counterexamples to common slips

• Not every closed convex cone is proper. A halfspace $\{x:a^{\top }x\ge 0\}$ is a closed convex cone with nonempty interior but contains a line, so it is not pointed and induces no antisymmetric order. The orthant, Lorentz, and PSD cones are proper precisely because they are pointed.
• The dual cone is not the complement or the polar without a sign flip. $K^{\ast }$ uses $⟨y,x⟩\ge 0$; the polar cone $K^{\circ }=-K^{\ast }$ uses $\le 0$. Mixing the sign conventions flips the direction of the dual inequality and corrupts the dual program.
• Generalized inequality is only a partial order. For $X,Y\in {\mathbb{S}}_{+}^n$ it can happen that neither $X⪯Y$ nor $Y⪯X$ (their difference is indefinite). Statements that silently assume comparability of all PSD matrices are false.

Key theorem with proof Intermediate+

The organizing result is conic duality: weak duality is unconditional and identical in form across LP, SOCP, and SDP, while strong duality holds under a conic Slater condition, specializing the Lagrangian strong-duality theorem of 44.02.01 to a proper-cone constraint.

Theorem (conic weak and strong duality).

(i) (Weak duality.) For any primal-feasible $x$ and dual-feasible $(y,s)$ with $s=c-A^{\top }y\in K^{\ast }$, the primal cost dominates the dual cost: $b^{\top }y\le c^{\top }x$, and the conic duality gap equals $c^{\top }x-b^{\top }y=⟨s,x⟩\ge 0$. Hence $d^{\star }\le p^{\star }$.

(ii) (Strong duality under Slater.) Suppose the primal is strictly feasible: there exists $\bar{x}$ with $A\bar{x}=b$ and $\bar{x}\in \mathrm{int}K$ (the conic Slater condition), and $p^{\star }$ is finite. Then $d^{\star }=p^{\star }$ and the dual optimum is attained.

Proof of (i). Let $x$ be primal feasible ($Ax=b$, $x\in K$) and $(y,s)$ dual feasible ($s=c-A^{\top }y\in K^{\ast }$). The gap computation is direct:

$$c^{\top }x-b^{\top }y=c^{\top }x-(Ax{)}^{\top }y=c^{\top }x-x^{\top }{A}^{\top }y=x^{\top }(c-A^{\top }y)=⟨x,s⟩.$$

Since $x\in K$ and $s\in K^{\ast }$, the definition of the dual cone gives $⟨x,s⟩\ge 0$. Therefore $b^{\top }y\le c^{\top }x$. Taking the supremum over dual-feasible $(y,s)$ on the left and the infimum over primal-feasible $x$ on the right yields $d^{\star }\le p^{\star }$. $\square$

Proof of (ii). Write the conic constraint $x\in K$ as a generalized inequality $f(x)=-x{⪯}_{K}0$, a $K$-convex constraint (the map $x\mapsto -x$ is $K$-convex because $K$ is a convex cone). The problem $\inf \{c^{\top }x:Ax=b,-x{⪯}_{K}0\}$ is then a convex program with a generalized-inequality constraint, and its Lagrangian uses a multiplier $\lambda \in {\mathbb{R}}^N$ paired through the dual cone:

$$L(x,\lambda ,y)=c^{\top }x+⟨\lambda ,-x⟩+y^{\top }(b-Ax),\lambda {⪰}_{K^{\ast }}0.$$

The dual function is $g(\lambda ,y)={\inf }_{x}L={\inf }_x((c-\lambda -A^{\top }y{)}^{\top }x+b^{\top }y)$, finite only when $c-\lambda -A^{\top }y=0$, in which case it equals $b^{\top }y$. Eliminating $\lambda =c-A^{\top }y{⪰}_{K^{\ast }}0$ reproduces the conic dual $\sup \{b^{\top }y:c-A^{\top }y\in K^{\ast }\}$.

The conic Slater point $\bar{x}\in \mathrm{int}K$ with $A\bar{x}=b$ is exactly a strictly feasible point for the generalized-inequality constraint $-\bar{x}{\prec }_{K}0$. The strong-duality theorem of 44.02.01, in its generalized-inequality form, then applies: a strictly feasible point in the relative interior of the cone constraint, with finite optimal value and convex data, forces a zero duality gap and attainment of the dual optimum. Concretely, the value set

$$\mathcal{A}=\{(z,\tau ):\exists x,Ax=b,x{⪰}_K-z\text{(componentwise in the cone sense)},c^{\top }x\le \tau \}$$

is convex; $(0,p^{\star })$ is a boundary point with nothing in $\mathcal{A}$ strictly below it at $z=0$; the supporting-hyperplane theorem (finite-dimensional Hahn-Banach) produces a supporting functional whose cone component lands in $K^{\ast }$, and Slater rules out a vertical support exactly as in 44.02.01. Normalizing gives the multiplier $y^{\star }$ and slack $s^{\star }=c-A^{\top }{y}^{\star }\in K^{\ast }$ with $b^{\top }{y}^{\star }=p^{\star }$. $\square$

Bridge. This theorem builds toward the interior-point algorithms of 44.05.04 and appears again in every optimality certificate for LP, SOCP, and SDP. This is exactly the Lagrangian strong duality of 44.02.01 read through a proper cone: the dual multiplier $\lambda$ that was nonnegative for an inequality constraint is now required to lie in the dual cone $K^{\ast }$, so the per-coordinate sign condition $\lambda \ge 0$ generalises to the cone membership $s\in K^{\ast }$, and the complementary-slackness scalar ${\lambda }_i{f}_i=0$ generalises to the conic complementarity $⟨x^{\star },s^{\star }⟩=0$. The foundational reason strong duality can fail for SDPs while never failing for the polyhedral LP case is the same vertical-support phenomenon of 44.02.01: the orthant's polyhedral closedness makes LP duality automatic (the Farkas mechanism of 44.02.04), whereas the curved PSD cone needs the interior-point Slater hypothesis to exclude a vertical support. Putting these together, weak duality is dual to primal feasibility and is the single identity $⟨x,s⟩\ge 0$ across all three cones, while strong duality is the separation theorem applied to the value set over the cone, and the dual slack $s^{\star }$ is the price vector that closes the conic gap.

Exercises Intermediate+

Advanced results Master

Conic duality theory: the gap can be nonzero, finite, or unattained independently

Conic duality refines the Lagrangian picture of 44.02.01 by separating three phenomena the orthant conflates. For a closed convex cone the weak-duality identity $c^{\top }x-b^{\top }y=⟨x,s⟩$ holds verbatim, but strong duality splits into independent guarantees: finiteness of $d^{\star }$, attainment of the dual optimum, and a zero gap. The Ben-Tal-Nemirovski conic-duality theorem ^{[Ben-Tal & Nemirovski Lec. 2]} states that if the primal is strictly feasible and bounded below then the dual is solvable with equal optimal value; symmetrically, dual strict feasibility yields primal solvability. When neither problem is strictly feasible the gap may be positive even with both values finite — the curved-cone pathology absent from LP. The polyhedral case is special: when $K$ is the nonnegative orthant the cone is finitely generated, the value set is a polyhedron whose closedness is unconditional, and strong duality and the Farkas certificates of 44.02.04 hold with no interior hypothesis at all.

The Schur complement as the universal SDP-modeling primitive

The single most-used SDP-modeling tool is the Schur complement ^{[Vandenberghe & Boyd §6]}. For a symmetric block matrix with $A\succ 0$,

$$M=\left[\begin{array}{cc}A& B\\ B^{\top }& C\end{array}\right]⪰0⟺C-B^{\top }{A}^{-1}B⪰0,$$

and $M\succ 0$ iff additionally the complement is strictly positive. This converts a wide class of nonlinear convex constraints into linear matrix inequalities: a quadratic-over-linear bound $x^{\top }{P}^{-1}x\le t$ becomes $\left[\begin{array}{cc}P& x\\ x^{\top }& t\end{array}\right]⪰0$; a matrix-fractional or trace-quadratic objective, a Lorentz-cone constraint (the inclusion above), and the convexity of the perspective and matrix-fractional functions all reduce to one Schur-complement LMI. The proof factors $M$ through the congruence $\left[\begin{array}{cc}I& 0\\ -B^{\top }{A}^{-1}& I\end{array}\right]M\left[\begin{array}{cc}I& -A^{-1}B\\ 0& I\end{array}\right]=\mathrm{diag}(A,C-B^{\top }{A}^{-1}B)$, and congruence preserves inertia (01.01.13), so the PSD-ness of $M$ matches that of the block-diagonal form.

Eigenvalue optimization and the Lovász theta function

The PSD cone's distinctive power is spectral. Beyond minimizing ${\lambda }_{\max }$, the sum of the $k$ largest eigenvalues ${\sum }_{i=1}^k{\lambda }_i(X)$ is SDP-representable, as is minimizing the spectral norm, the nuclear norm, and the condition number, and bounding the spectrum into an interval. The Lovász theta function $\vartheta (G)$ ^{[Lovász 1979]} — the SDP $\max \{⟨J,X⟩:\mathrm{tr}X=1,X_{ij}=0\text{for }ij\in E,X⪰0\}$ — sandwiches between the clique and chromatic numbers, $\alpha (G)\le \vartheta (\bar{G})\le \chi (G)$, and is computable to arbitrary accuracy by interior-point methods even though the integer quantities it bounds are NP-hard. The same relaxation philosophy yields the Goemans-Williamson max-cut SDP ^{[Goemans & Williamson 1995]} with its $0.878$ randomized-rounding guarantee, the first demonstration that an SDP relaxation can beat every prior combinatorial bound and the template for sum-of-squares and Lasserre hierarchies.

Self-dual cones, symmetric cones, and the limits of the framework

The three workhorse cones are not merely self-dual but symmetric: self-dual and homogeneous (their automorphism group acts transitively on the interior). The Koecher-Vinberg theorem identifies symmetric cones with the cones of squares in Euclidean Jordan algebras, and the classification gives exactly five families, of which the orthant, the Lorentz cone, and the real/complex/quaternionic PSD cones are the cases used in practice. Self-concordant barriers exist for these cones with barrier parameter governing interior-point complexity — $\log$ for each orthant coordinate, $-\log (t^2-\Vert u{\Vert }_2^2)$ for the Lorentz cone, $-\log \det X$ for the PSD cone — which is why all three admit the same polynomial-time path-following solver of 44.05.04. Cones outside this class (the copositive cone, the cone of nonnegative polynomials in several variables) are convex and proper but lack tractable barriers; optimizing over them is NP-hard, marking the boundary between the conic problems that the LP/SOCP/SDP theory solves and the convex problems it can only approximate.

Synthesis. The conic program is exactly the linear program with its sign constraint replaced by membership in a proper cone, and the central insight is that weak duality is the single cone-pairing identity $⟨x,s⟩\ge 0$ valid across LP, SOCP, and SDP, so the entire duality theory of 44.02.01 transports to the cone with the dual multiplier living in $K^{\ast }$. The foundational reason the three canonical cones admit one unified solver is that each is self-dual and symmetric with a self-concordant barrier, which generalises the per-coordinate logarithm of the LP barrier to the Lorentz and log-determinant barriers and feeds the interior-point machinery of 44.05.04. Putting these together, the Schur complement is the engine that realizes the inclusion LP $\subset$ SOCP $\subset$ SDP, turning each Lorentz constraint into a linear matrix inequality, while eigenvalue optimization and the max-cut and Lovász relaxations show the strict gain in expressive power at the SDP level. This is exactly the same separation engine of 44.02.01 that is dual to primal feasibility, with the polyhedral orthant case is dual to the Farkas certificates of 44.02.04 needing no Slater hypothesis; the bridge is the dual cone $K^{\ast }$, the single object through which generalized inequalities, conic duality, complementary slackness, and the barrier-based interior-point algorithms of 44.05.04 become one theory, and it appears again in robust optimization, combinatorial relaxation, and control via linear matrix inequalities.

Full proof set Master

Proposition 1 (the three canonical cones are proper and self-dual). The nonnegative orthant ${\mathbb{R}}_{+}^n$, the Lorentz cone ${\mathcal{L}}^{n+1}$, and the PSD cone ${\mathbb{S}}_{+}^n$ are each closed, pointed, solid convex cones equal to their own dual under the standard (resp. trace) inner product.

Proof. Each is a convex cone closed under nonnegative scaling and addition; closedness follows from being a sublevel/intersection set of continuous functions, solidity from exhibiting an interior point ($1$, $(0,1)$, $I$ respectively), and pointedness because each contains no line. Self-duality of ${\mathbb{R}}_{+}^n$ is Exercise 1. For ${\mathbb{S}}_{+}^n$ the self-duality $({\mathbb{S}}_{+}^n{)}^{\ast }={\mathbb{S}}_{+}^n$ under $⟨A,B⟩=\mathrm{tr}(AB)$ is proved in 44.01.01 via the spectral decomposition and rank-one test matrices $v{v}^{\top }$. For the Lorentz cone, let $(u,t)\in {\mathcal{L}}^{n+1}$, so $\Vert u{\Vert }_2\le t$. For any $(v,s)$ with $\Vert v{\Vert }_2\le s$, Cauchy-Schwarz gives $⟨(u,t),(v,s)⟩=u^{\top }v+ts\ge -\Vert u{\Vert }_2\Vert v{\Vert }_2+ts\ge -ts+ts=0$, so ${\mathcal{L}}^{n+1}\subseteq ({\mathcal{L}}^{n+1}{)}^{\ast }$. Conversely, if $(v,s)$ satisfies $u^{\top }v+ts\ge 0$ for all $(u,t)\in {\mathcal{L}}^{n+1}$, take $t=\Vert u{\Vert }_2$ and $u=-sv/\Vert v{\Vert }_2$ (for $v\ne 0$): then $-s\Vert v{\Vert }_2+s\Vert v{\Vert }_2\cdot \frac{\Vert u{\Vert }_2}{\Vert u{\Vert }_2}$, optimizing over the choice forces $s\ge \Vert v{\Vert }_2$, so $(v,s)\in {\mathcal{L}}^{n+1}$. Hence ${\mathcal{L}}^{n+1}$ is self-dual. $\square$

Proposition 2 (conic weak duality and conic complementary slackness). For primal-feasible $x$ and dual-feasible $(y,s)$, $c^{\top }x-b^{\top }y=⟨x,s⟩\ge 0$; equality (zero gap) holds iff $⟨x,s⟩=0$, the conic complementarity condition.

Proof. The identity $c^{\top }x-b^{\top }y=⟨x,s⟩$ is the computation in part (i) of the Key theorem, using $b=Ax$ and $s=c-A^{\top }y$. Nonnegativity is the dual-cone definition applied to $x\in K$, $s\in K^{\ast }$. The gap of the pair is exactly $⟨x,s⟩$, so it vanishes iff $⟨x,s⟩=0$. For the PSD cone with $X,S⪰0$, $⟨X,S⟩=\mathrm{tr}(XS)=0$ together with $X,S⪰0$ forces $XS=0$: writing $X={\sum }_i{\lambda }_i{u}_i{u}_i^{\top }$ with ${\lambda }_i>0$, $0=\mathrm{tr}(XS)={\sum }_i{\lambda }_i{u}_i^{\top }S{u}_i$ with each term nonnegative forces $S{u}_i=0$ on the range of $X$, hence $XS=0$. $\square$

Proposition 3 (Schur-complement criterion). Let $M=\left[\begin{array}{cc}A& B\\ B^{\top }& C\end{array}\right]$ be symmetric with $A\succ 0$. Then $M⪰0⟺C-B^{\top }{A}^{-1}B⪰0$, and $M\succ 0⟺C-B^{\top }{A}^{-1}B\succ 0$.

Proof. Let $T=\left[\begin{array}{cc}I& -A^{-1}B\\ 0& I\end{array}\right]$, which is invertible. The congruence $T^{\top }MT=\left[\begin{array}{cc}A& 0\\ 0& C-B^{\top }{A}^{-1}B\end{array}\right]$ is verified by block multiplication. Congruence by an invertible matrix preserves inertia (Sylvester's law, 01.01.13), so $M$ and the block-diagonal matrix have the same numbers of positive, zero, and negative eigenvalues. Since $A\succ 0$, the block-diagonal matrix is PSD iff $C-B^{\top }{A}^{-1}B⪰0$ and PD iff $C-B^{\top }{A}^{-1}B\succ 0$. Transferring through the inertia-preserving congruence gives the claim for $M$. $\square$

Proposition 4 (eigenvalue-sum SDP representation). For symmetric $X\in {\mathbb{S}}^n$, the sum of the $k$ largest eigenvalues satisfies ${\sum }_{i=1}^k{\lambda }_i(X)={\min }_{t,Z}\{kt+\mathrm{tr}Z:Z⪰0,Z⪰X-tI\}$, an SDP in $(t,Z)$.

Proof. Fix $t$ and minimize over $Z$. The constraints $Z⪰0$ and $Z⪰X-tI$ mean $Z⪰\max (0,X-tI)$ in the PSD order; the minimizing $Z$ has eigenvalues $\max (0,{\lambda }_i(X)-t)$ in the eigenbasis of $X$, giving $\mathrm{tr}Z={\sum }_i({\lambda }_i(X)-t{)}_{+}$. The inner objective becomes $\varphi (t)=kt+{\sum }_i({\lambda }_i(X)-t{)}_{+}$. This is convex and piecewise linear in $t$; its minimum is attained at $t={\lambda }_k(X)$, where $\varphi ({\lambda }_k)=k{\lambda }_k+{\sum }_{i=1}^k({\lambda }_i-{\lambda }_k)={\sum }_{i=1}^k{\lambda }_i(X)$, because the terms with $i>k$ contribute zero and the first $k$ terms sum as shown. Hence the SDP value equals ${\sum }_{i=1}^k{\lambda }_i(X)$. The case $k=1$ recovers ${\lambda }_{\max }(X)=\min \{t:tI-X⪰0\}$ of Exercise 5. $\square$

Connections Master

• Lagrangian duality and Slater's condition 44.02.01 is the direct parent: conic duality is its specialization to a single generalized-inequality constraint $x{⪰}_{K}0$, with the nonnegative scalar multiplier replaced by a dual-cone multiplier $s\in K^{\ast }$, weak duality becoming the pairing $⟨x,s⟩\ge 0$, and the conic Slater condition $\bar{x}\in \mathrm{int}K$ replacing the strictly-feasible interior point. The strong-duality proof here invokes that unit's separating-hyperplane argument over the value set verbatim.

• The convex-cone and dual-cone calculus of 44.01.01 supplies every structural fact this unit relies on: that the orthant, Lorentz, and PSD cones are proper and self-dual, that $K^{\ast \ast }=K$ makes the primal-dual conic pairing symmetric, and that an affine preimage of a cone is convex, which is what makes the LP, SOCP, and SDP feasible sets convex and the inclusion chain meaningful.

• The spectral theorem and PSD characterization of 01.01.13 is the foundation of the SDP layer: the PSD cone is defined by nonnegativity of eigenvalues, eigenvalue optimization is SDP-representable through the order $tI-X⪰0$, and the Schur-complement proof rests on Sylvester's inertia law, which is the spectral structure of symmetric matrices applied under congruence.

• Farkas' lemma and the theorems of the alternative 44.02.04 are the polyhedral, nonnegative-orthant case of conic duality: when $K={\mathbb{R}}_{+}^n$ the value set is a polyhedron whose closedness is automatic, so strong duality and infeasibility certificates hold without any Slater hypothesis, and the conic theory of this unit generalizes those alternatives to an arbitrary closed convex cone via $K^{\ast }$. The interior-point algorithms of 44.05.04 then solve the conic programs assembled here in polynomial time using self-concordant barriers for each canonical cone.

Historical & philosophical context Master

Linear programming and its duality were established by George Dantzig's simplex method (1947) and the duality theorem formalized by John von Neumann and by David Gale, Harold Kuhn, and Albert Tucker around 1951, the same circle that produced the nonlinear-programming optimality conditions cited in 44.02.01. The decisive generalization to nonpolyhedral cones came with the interior-point revolution: Narendra Karmarkar's 1984 polynomial-time LP algorithm prompted Yurii Nesterov and Arkadi Nemirovski to identify the abstract property — self-concordance of a barrier — that makes polynomial-time interior-point methods possible, published in their 1994 monograph ^{[Nesterov & Nemirovski 1994]}, which framed LP, SOCP, and SDP as instances of one conic-programming theory solvable by one algorithmic principle.

Semidefinite programming as an explicit object was surveyed and popularized by Lieven Vandenberghe and Stephen Boyd in their 1996 SIAM Review article ^{[Vandenberghe & Boyd 1996]}, which assembled the eigenvalue, control, and Schur-complement applications; the conic-programming synthesis was codified pedagogically by Aharon Ben-Tal and Nemirovski ^{[Ben-Tal & Nemirovski Lec. 1-4]}. On the applications side, László Lovász's 1979 theta function ^{[Lovász 1979]} was the first influential combinatorial quantity computed by what is now recognized as an SDP, and Michel Goemans and David Williamson's 1995 max-cut relaxation ^{[Goemans & Williamson 1995]} established SDP relaxation with randomized rounding as an approximation-algorithm technique, seeding the sum-of-squares and Lasserre hierarchies that extend the PSD cone to polynomial optimization.

Bibliography Master

@book{boyd2004convex,
  author    = {Boyd, Stephen and Vandenberghe, Lieven},
  title     = {Convex Optimization},
  publisher = {Cambridge University Press},
  year      = {2004}
}

@book{bental2001lectures,
  author    = {Ben-Tal, Aharon and Nemirovski, Arkadi},
  title     = {Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications},
  series    = {MPS-SIAM Series on Optimization},
  publisher = {SIAM},
  year      = {2001}
}

@book{nesterov1994interior,
  author    = {Nesterov, Yurii and Nemirovski, Arkadi},
  title     = {Interior-Point Polynomial Algorithms in Convex Programming},
  series    = {SIAM Studies in Applied Mathematics},
  number    = {13},
  publisher = {SIAM},
  year      = {1994}
}

@article{vandenberghe1996semidefinite,
  author  = {Vandenberghe, Lieven and Boyd, Stephen},
  title   = {Semidefinite Programming},
  journal = {SIAM Review},
  volume  = {38},
  number  = {1},
  pages   = {49--95},
  year    = {1996}
}

@article{goemans1995improved,
  author  = {Goemans, Michel X. and Williamson, David P.},
  title   = {Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming},
  journal = {Journal of the ACM},
  volume  = {42},
  number  = {6},
  pages   = {1115--1145},
  year    = {1995}
}

@article{lovasz1979shannon,
  author  = {Lov\'asz, L\'aszl\'o},
  title   = {On the Shannon Capacity of a Graph},
  journal = {IEEE Transactions on Information Theory},
  volume  = {25},
  number  = {1},
  pages   = {1--7},
  year    = {1979}
}