Chapter 4: Convex Optimization Problems

4.1 Optimization Problem in Standard Form

An optimization problem in standard form is written as

$$\begin{array}{rl}\underset{x}{min}& f_0(x)\\ \text{s.t.}& f_i(x)\le 0,i=1,\dots ,m\\ & h_j(x)=0,j=1,\dots ,p\end{array}$$

where:

• $x\in {\mathbb{R}}^n$ is the optimization variable.
• $f_0:{\mathbb{R}}^n\to \mathbb{R}$ is the objective (cost) function.
• $f_i$ are inequality constraint functions.
• $h_j$ are equality constraint functions.

Optimal Value

The optimal value $p^{\star }$ of the problem is defined as

$$p^{\star }=inf\{f_0(x)\mid f_i(x)\le 0,h_j(x)=0\}$$

• $p^{\star }=\mathrm{\infty }$: the problem is infeasible.
• $p^{\star }=-\mathrm{\infty }$: the problem is unbounded below.

Feasible, Optimal, and Locally Optimal Points

• $x$ is feasible if it satisfies all constraints.

• $x$ is optimal if $x$ is feasible and $f_0(x)=p^{\star }$.

• $x$ is locally optimal if $x$ is optimal for (for any $R>0$)

  $$\begin{array}{rl}\underset{z}{min}& f_0(z)\\ \text{s.t.}& f_i(z)\le 0,i=1,\dots ,m\\ & h_i(z)=0,i=1,\dots ,p\\ & \parallel z-x{\parallel }_2\le R\end{array}$$

• If $x$ is feasible and $f_0(x)-p^{\star }\le \epsilon$, then $x$ is called $\epsilon$-suboptimal.

Examples (with $n=1$, $m=p=0$):

• $f_0(x)=-\log x$, $\mathrm{dom}{f}_0={\mathbb{R}}_{++}$: $p^{\star }=-\mathrm{\infty }$
• $f_0(x)=x\log x$, $\mathrm{dom}{f}_0={\mathbb{R}}_{++}$: $p^{\star }=-1/e$, $x^{\star }=1/e$
• $f_0(x)=x^3-3x$, $\mathrm{dom}{f}_0=\mathbb{R}$: $p^{\star }=-\mathrm{\infty }$, local optimum at $x=1$

Implicit Constraints and Domain

The implicit domain constraint is

$$x\in \mathcal{D}=\bigcap _{i=0}^m\mathrm{dom}{f}_i\cap \bigcap _{j=1}^p\mathrm{dom}{h}_j$$

• $\mathcal{D}$ is the domain of the problem.
• Explicit constraints: $f_i(x)\le 0$, $h_j(x)=0$.
• The problem is unconstrained if $m=p=0$.

Example:

$$\underset{x}{min}{f}_0(x)=-\sum _{i=1}^k\log (b_i-a_i^{\mathrm{\top }}x)$$

is an unconstrained problem with implicit constraints $a_i^{\mathrm{\top }}x<b_i$.

Feasibility Problem

A feasibility problem asks whether any feasible point exists:

$$\begin{array}{rl}\text{find}& x\\ \text{s.t.}& f_i(x)\le 0,i=1,\dots ,m\\ & h_j(x)=0,j=1,\dots ,p\end{array}$$

This can be considered a special case of the general problem with $f_0(x)\equiv 0$:

• $p^{\star }=0$ if constraints are feasible (any feasible $x$ is optimal).
• $p^{\star }=\mathrm{\infty }$ if infeasible.

---

4.2 Convex Optimization Problem

A problem is a convex optimization problem if it is of the form

$$\begin{array}{rl}\underset{x}{min}& f_0(x)\\ \text{s.t.}& f_i(x)\le 0,i=1,\dots ,m\\ & a_i^{\mathrm{\top }}x=b_i,i=1,\dots ,p\end{array}$$

Definition. An optimization problem is convex if:

1. $f_0$ is convex.
2. $f_1,\dots ,f_m$ are convex.
3. $h_1,\dots ,h_p$ are affine: $h_i(x)=a_i^{\mathrm{\top }}x-b_i$.

Key Property. The feasible set of a convex optimization problem is convex: it is the intersection of $m$ sublevel sets (of convex functions) and $p$ hyperplanes, which is convex.

---

4.3 Local and Global Optima

Theorem (Local = Global). For a convex optimization problem, every locally optimal point is also globally optimal.

Proof. Suppose $x$ is locally optimal and there exists a feasible $y$ with $f_0(y)<f_0(x)$. For $z=\theta y+(1-\theta )x$ with small $\theta >0$, convexity gives

$$f_0(z)\le \theta f_0(y)+(1-\theta )f_0(x)<f_0(x)$$

But local optimality requires $f_0(x)\le f_0(z)$ for all feasible $z$ sufficiently near $x$ — a contradiction.

Uniqueness. If $f_0$ is strictly convex, then a convex optimization problem has at most one global minimizer (uniqueness).

---

4.4 First-Order Optimality Condition

For a convex problem

$$\underset{x}{min}f(x)\text{s.t.}x\in C$$

Theorem (First-Order Optimality). A feasible point $x^{\star }$ is optimal if and only if

$$⟨\mathrm{\nabla }f(x^{\star }),y-x^{\star }⟩\ge 0\mathrm{\forall }y\in C$$

Geometric interpretation:

• $\mathrm{\nabla }f(x^{\star })$ makes an acute ($\le {90}^{\circ }$) angle with all feasible directions at an optimal $x^{\star }$.
• $\mathrm{\nabla }f(x^{\star })$ defines a supporting hyperplane to the feasible set $C$ at $x^{\star }$.
• $-\mathrm{\nabla }f(x^{\star })$ is normal to the tangent plane of the feasible set.

Special Cases

Unconstrained optimization:

$$\mathrm{\nabla }{f}_0(x^{\star })=0$$

Equality-constrained minimization:

$$\begin{array}{rl}\underset{x}{min}& f_0(x)\\ \text{s.t.}& Ax=b\end{array}⟹\mathrm{\exists }z:\mathrm{\nabla }{f}_0(x^{\star })+A^{\mathrm{\top }}z=0$$

Minimization over the nonnegative orthant:

$$\begin{array}{rl}\underset{x}{min}& f_0(x)\\ \text{s.t.}& x⪰0\end{array}⟹\mathrm{\nabla }{f}_0(x^{\star })⪰0,x_i^{\star }(\mathrm{\nabla }{f}_0(x^{\star }){)}_i=0,i=1,\dots ,n$$

Example: Unconstrained Quadratic Minimization

Consider minimizing the quadratic function:

$$f(x)=\frac{1}{2}{x}^{\mathrm{\top }}Qx+b^{\mathrm{\top }}x+c$$

where $Q⪰0$. The first-order condition yields

$$\mathrm{\nabla }f(x)=Qx+b=0$$

• If $Q\succ 0$, there is a unique solution: $x=-Q^{-1}b$.
• If $Q$ is singular and $b\notin \mathcal{R}(Q)$, there is no solution ($\underset{x}{min}f(x)=-\mathrm{\infty }$).
• If $Q$ is singular and $b\in \mathcal{R}(Q)$, there are infinitely many solutions: $x=-Q^{+}b+z$, $z\in \mathcal{N}(Q)$, where $Q^{+}$ is the pseudoinverse of $Q$.

---

4.5 Equivalent Transformations

Two problems are (informally) equivalent if their solutions can be readily converted into each other. Common transformations that preserve equivalence:

Transformations and Change of Variables

If $h:\mathbb{R}\to \mathbb{R}$ is a monotone increasing transformation, then

$$\underset{x\in C}{min}f(x)⟺\underset{x\in C}{min}h(f(x))$$

This can be used to reveal "hidden convexity" of a problem.

If $\phi :{\mathbb{R}}^n\to {\mathbb{R}}^m$ is one-to-one and its image covers the feasible set $C$, then we can change variables:

$$\underset{x}{min}f(x)\text{s.t.}x\in C⟺\underset{y}{min}f(\phi (y))\text{s.t.}\phi (y)\in C$$

Example: Log-likelihood transformation. In maximum likelihood estimation (MLE), given independent samples $x_1,\dots ,x_n$ with likelihood

$$L(\theta )=\prod _{i=1}^{n}p(x_i\mid \theta )$$

applying the strictly increasing $\log (\cdot )$ transformation yields

$$\ell (\theta )=\log L(\theta )=\sum _{i=1}^n\log p(x_i\mid \theta )$$

with the key property: ${\mathrm{argmax}}_{\theta }L(\theta )={\mathrm{argmax}}_{\theta }\ell (\theta )$.

Eliminating Equality Constraints

Given:

$$\begin{array}{rl}\underset{x}{min}& f_0(x)\\ \text{s.t.}& f_i(x)\le 0,i=1,\dots ,m\\ & Ax=b\end{array}$$

Any feasible point can be expressed as $x=My+x_0$, where $A{x}_0=b$ and $\mathcal{R}(M)=\mathcal{N}(A)$. The problem is equivalent to

$$\begin{array}{rl}\underset{y}{min}& f_0(My+x_0)\\ \text{s.t.}& f_i(My+x_0)\le 0,i=1,\dots ,m\end{array}$$

Introducing Slack Variables

Given:

$$\begin{array}{rl}\underset{x}{min}& f_0(x)\\ \text{s.t.}& f_i(x)\le 0,i=1,\dots ,m\\ & Ax=b\end{array}$$

inequality constraints can be transformed via slack variables $s_i\ge 0$:

$$\begin{array}{rl}\underset{x,s}{min}& f_0(x)\\ \text{s.t.}& s_i\ge 0,i=1,\dots ,m\\ & f_i(x)+s_i=0,i=1,\dots ,m\\ & Ax=b\end{array}$$

Note. This transformation is no longer convex unless $f_i$ are affine.

Epigraph Formulation

The standard form problem

$$\begin{array}{rl}\underset{x}{min}& f_0(x)\\ \text{s.t.}& f_i(x)\le 0,i=1,\dots ,m\\ & Ax=b\end{array}$$

is equivalent to its epigraph form:

$$\begin{array}{rl}\underset{x,t}{min}& t\\ \text{s.t.}& f_0(x)-t\le 0,\\ & f_i(x)\le 0,i=1,\dots ,m\\ & Ax=b\end{array}$$

Relaxation

Given an optimization problem

$$\underset{x}{min}f(x)\text{s.t.}x\in C$$

we can always take an enlarged constraint set $\tilde{C}\supseteq C$ and consider

$$\underset{x}{min}f(x)\text{s.t.}x\in \tilde{C}$$

This is called a relaxation and its optimal value is always smaller or equal to that of the original problem (for minimization).

Example: Continuous relaxation of integer constraints.

$$\begin{array}{rl}\underset{x}{min}& c^{\mathrm{\top }}x\\ \text{s.t.}& Ax⪯b,\\ & x\in \{0,1{\}}^n\end{array}⟹x\in [0,1{]}^n$$

• Feasible set becomes convex (a polytope).
• The problem reduces to a linear program (LP).
• Provides a lower bound on the integer optimum.

Example: Relaxing nonconvex sets. $x^2+y^2=1$ (unit circle) $⟹$ $x^2+y^2\le 1$ (unit disk). For non-affine equality constraints $h_j(x)=0$ where $h_j$ are convex, replace with $h_j(x)\le 0$.

Converting a Nonconvex Problem to a Convex One

Via observation:

Nonconvex problem:

$$\begin{array}{rl}\underset{x_1,x_2}{min}& f_0(x)=x_1^2+x_2^2\\ \text{s.t.}& f_1(x)=\frac{x_1}{1+x_2^2}\le 0,\\ & h_1(x)=(x_1+x_2{)}^2=0\end{array}$$

$f_0$ is convex, but $f_1$ is not convex and $h_1$ is not affine. The equivalent convex formulation is:

$$\begin{array}{rl}\underset{x_1,x_2}{min}& x_1^2+x_2^2\\ \text{s.t.}& x_1\le 0,\\ & x_1+x_2=0\end{array}$$

Via substitution:

Nonconvex problem: $\underset{x}{min}(|x|-1{)}^2$. Let $t=|x|$ where $t\ge 0$. The equivalent convex problem is $\underset{t}{min}(t-1{)}^2$ subject to $t\ge 0$.

Example: Geometric program (monomial case). The original nonconvex problem

$$\begin{array}{rl}\underset{x\succ 0}{min}& f_0(x)=c_0{x}_1^{a_{01}}{x}_2^{a_{02}}\cdots x_n^{a_{0n}}\\ \text{s.t.}& f_i(x)=c_i{x}_1^{a_{i1}}{x}_2^{a_{i2}}\cdots x_n^{a_{in}}\le 1,i=1,\dots ,m\end{array}$$

where $c_i>0$, becomes convex via the monotone transformation $y_i=\log x_i$ ($x_i=e^{y_i}$):

$$\begin{array}{rl}\underset{y\in {\mathbb{R}}^n}{min}& \log c_0+a_{01}{y}_1+\cdots +a_{0n}{y}_n\\ \text{s.t.}& \log c_i+a_{i1}{y}_1+\cdots +a_{in}{y}_n\le 0,i=1,\dots ,m\end{array}$$

---

4.6 Linear Programming (LP)

Definition (Linear Program). An LP minimizes a linear objective subject to linear inequality and equality constraints:

$$\begin{array}{rl}\underset{x}{min}& c^{\mathrm{\top }}x\\ \text{s.t.}& Dx⪯d,\\ & Ax=b\end{array}$$

An LP is a convex problem with affine objective and constraint functions. It is the most fundamental problem class in convex optimization.

Inequality and Standard Forms

Inequality form:

$$\underset{x}{min}{c}^{\mathrm{\top }}x\text{s.t.}Ax⪯b$$

Standard form:

$$\underset{x}{min}{c}^{\mathrm{\top }}x\text{s.t.}Ax=b,x⪰0$$

Conversion between forms:

• Replace $a_i^{\mathrm{\top }}x\le b_i$ with $a_i^{\mathrm{\top }}x+s_i=b_i$, $s_i\ge 0$ (slack variables).
• Replace a free variable $x_j$ with $x_j=x_j^{+}-x_j^{-}$, where $x_j^{+},x_j^{-}\ge 0$.

Example: Diet Problem

Find the cheapest combination of foods that satisfies certain nutritional requirements:

$$\begin{array}{rl}\underset{x}{min}& c^{\mathrm{\top }}x\\ \text{s.t.}& Dx⪰d\\ & x⪰0\end{array}$$

where $c_j$ is the per-unit cost of food $j$, $d_i$ is the minimum required intake of nutrient $i$, $D_{ij}$ is the content of nutrient $i$ per unit of food $j$, and $x_j$ is the units of food $j$ in the diet.

Example: Piecewise-linear Minimization

Consider minimizing the piecewise-linear function:

$$f(x)=\underset{i=1,\dots ,m}{max}(a_i^{\mathrm{\top }}x+b_i)$$

This can be transformed to an equivalent LP via its epigraph form:

$$\begin{array}{rl}\underset{t,x}{min}& t\\ \text{s.t.}& a_i^{\mathrm{\top }}x+b_i\le t,i=1,\dots ,m\end{array}$$

This is an LP (in inequality form) with variables $x$ and $t$.

Example: Chebyshev Center of a Polyhedron

Given a polyhedron $P=\{x\in {\mathbb{R}}^n:Ax⪯b\}$, find the largest Euclidean ball that fits inside it:

$$B(x_c,r)=\{x\in {\mathbb{R}}^n:\parallel x-x_c{\parallel }_2\le r\}=\{x_c+u:\parallel u{\parallel }_2\le r\}$$

The problem is formulated as

$$\begin{array}{rl}\underset{x_c,r}{max}& r\\ \text{s.t.}& a_i^{\mathrm{\top }}{x}_c+\parallel a_i{\parallel }_{2}r\le b_i,i=1,\dots ,m\end{array}$$

• $\parallel a_i{\parallel }_2$ is the Euclidean norm of the normal vector of the $i$-th face.
• Each constraint ensures the ball does not cross the corresponding face.
• This is a linear program (LP) in $x_c$ and $r$.
• Applications: emergency facility placement, sensor/Wi-Fi placement, urban planning.

Example: Basis Pursuit

Consider an underdetermined linear system $Ax=b$, $A\in {\mathbb{R}}^{m\times n}$, $m<n$. The goal is to find the sparsest solution (minimize the number of nonzero entries).

• Exact sparsity minimization (${\ell }_0$-norm) is NP-hard.
• Relaxation: minimize the ${\ell }_1$-norm instead: $\underset{x}{min}\parallel x{\parallel }_1$ s.t. $Ax=b$.
• The ${\ell }_1$-norm encourages sparsity while remaining convex.

By introducing nonnegative variables $u_i\ge 0$ to represent $|x_i|$ ($-u_i\le x_i\le u_i$), the LP formulation is

$$\begin{array}{rl}\underset{x,u}{min}& \sum _{i=1}^n{u}_i\\ \text{s.t.}& Ax=b,\\ & -u_i\le x_i\le u_i,i=1,\dots ,n,\\ & u_i\ge 0,i=1,\dots ,n\end{array}$$

---

4.7 Quadratic Programming (QP)

Definition (Quadratic Program). A QP minimizes a quadratic objective subject to linear constraints:

$$\begin{array}{rl}\underset{x}{min}& \frac{1}{2}{x}^{\mathrm{\top }}Qx+c^{\mathrm{\top }}x\\ \text{s.t.}& Dx⪯d,\\ & Ax=b\end{array}$$

If $Q⪰0$ (positive semidefinite), the problem is convex. Convex QPs have globally optimal solutions and can be solved efficiently.

Example: Least Squares

Least squares problem:

$$\underset{x}{min}\parallel Ax-b{\parallel }_2^2$$

Least squares with bounds:

$$\underset{x}{min}\parallel Ax-b{\parallel }_2^2\text{s.t.}\ell ⪯x⪯u$$

QP formulation:

$$\underset{x}{min}\frac{1}{2}{x}^{\mathrm{\top }}(2A^{\mathrm{\top }}A)x-(2A^{\mathrm{\top }}b{)}^{\mathrm{\top }}x=\frac{1}{2}{x}^{\mathrm{\top }}Qx+c^{\mathrm{\top }}x$$

where $Q=2A^{\mathrm{\top }}A⪰0$, $c=-2A^{\mathrm{\top }}b$.

Example: Distance Between Two Polyhedra

Given polyhedra $P_1=\{x\in {\mathbb{R}}^n:A_{1}x⪯b_1\}$ and $P_2=\{y\in {\mathbb{R}}^n:A_{2}y⪯b_2\}$, the distance between them is

$$\begin{array}{rl}\underset{x,y}{min}& \parallel x-y{\parallel }_2^2\\ \text{s.t.}& A_{1}x⪯b_1,\\ & A_{2}y⪯b_2\end{array}$$

This is a convex QP.

Example: Linear Program with Random Cost

Let cost be $c^{\mathrm{\top }}x$ where $c$ is random with mean $\overline{c}=\mathbb{E}[c]$. A risk-averse objective is

$$\underset{x}{min}{\overline{c}}^{\mathrm{\top }}x+\lambda \mathrm{Var}(c^{\mathrm{\top }}x)$$

Expanding the variance:

$$\mathrm{Var}(c^{\mathrm{\top }}x)=\mathbb{E}[(c^{\mathrm{\top }}x-{\overline{c}}^{\mathrm{\top }}x{)}^2]=x^{\mathrm{\top }}\mathbb{E}[(c-\overline{c})(c-\overline{c}{)}^{\mathrm{\top }}]x=x^{\mathrm{\top }}\mathrm{\Sigma }x$$

The QP formulation is

$$\begin{array}{rl}\underset{x}{min}& {\overline{c}}^{\mathrm{\top }}x+\lambda x^{\mathrm{\top }}\mathrm{\Sigma }x\\ \text{s.t.}& Dx⪰d,x⪰0\end{array}$$

where $\mathrm{\Sigma }$ is the covariance matrix of $c$.

Example: LASSO (Basis Pursuit with Noise)

LASSO trades off data fidelity and sparsity.

Penalty formulation:

$$\underset{x}{min}\frac{1}{2}\parallel Ax-b{\parallel }_2^2+\lambda \parallel x{\parallel }_1$$

Constrained formulation:

$$\underset{x}{min}\parallel Ax-b{\parallel }_2^2\text{s.t.}\parallel x{\parallel }_1\le k$$

Key characteristics:

• Handles noisy data (LASSO $\iff$ BP when noise-free).
• Sparsity controlled by $\lambda$ (or $k$).
• Can be written as a QP.

---

4.8 Quadratically Constrained Quadratic Programming (QCQP)

Definition (QCQP). A QCQP minimizes a quadratic objective subject to quadratic inequality and linear equality constraints:

$$\begin{array}{rl}\underset{x}{min}& \frac{1}{2}{x}^{\mathrm{\top }}{P}_{0}x+q_0^{\mathrm{\top }}x+r_0\\ \text{s.t.}& \frac{1}{2}{x}^{\mathrm{\top }}{P}_{i}x+q_i^{\mathrm{\top }}x+r_i\le 0,i=1,\dots ,m\\ & Ax=b\end{array}$$

If $P_0,P_1,\dots ,P_m⪰0$, the problem is convex.

QCQP generalizes QP by allowing quadratic inequality constraints, and in turn is a special case of SOCP.

---

4.9 Second-Order Cone Programming (SOCP)

Definition (SOCP). An SOCP is of the form:

$$\begin{array}{rl}\underset{x}{min}& c^{\mathrm{\top }}x\\ \text{s.t.}& \parallel D_{i}x+d_i{\parallel }_2\le e_i^{\mathrm{\top }}x+f_i,i=1,\dots ,m\\ & Ax=b\end{array}$$

Second-Order (Lorentz) Cone

The second-order cone (also called the Lorentz cone or ice-cream cone) is

$$\mathcal{Q}=\{(x,t)\in {\mathbb{R}}^{n+1}:\parallel x{\parallel }_2\le t\}$$

The constraint $\parallel D_{i}x+d_i{\parallel }_2\le e_i^{\mathrm{\top }}x+f_i$ is equivalent to $(D_{i}x+d_i,e_i^{\mathrm{\top }}x+f_i)\in \mathcal{Q}$.

Why is $\mathcal{Q}$ convex? It is the epigraph of the Euclidean norm $\parallel x{\parallel }_2$, which is a convex function.

QP $\subset$ SOCP

A QP can be reformulated as an SOCP:

$$\begin{array}{rl}\underset{x}{min}& \frac{1}{2}{x}^{\mathrm{\top }}Qx+c^{\mathrm{\top }}x\\ \text{s.t.}& Dx⪯d,\\ & Ax=b\end{array}⟹\begin{array}{rl}\underset{x,t}{min}& c^{\mathrm{\top }}x+\frac{1}{2}t\\ \text{s.t.}& Dx⪯d,x^{\mathrm{\top }}Qx\le t,Ax=b\end{array}$$

with $x^{\mathrm{\top }}Qx\le t⟺\parallel Q^{1/2}x{\parallel }_2^2\le \frac{1}{4}(1+t{)}^2-\frac{1}{4}(1-t{)}^2$, which is an SOC constraint.

Example: Robust Linear Program (Deterministic)

In LP, there may be uncertainty in the data $c$, $a_i$, or $b_i$. With uncertainty in $a_i$, two approaches:

Deterministic (worst-case guarantee): constraints must hold for all $a_i$ in an ellipsoidal uncertainty set

$${\mathcal{E}}_i=\{{\overline{a}}_i+P_{i}u:\parallel u{\parallel }_2\le 1\},{\overline{a}}_i\in {\mathbb{R}}^n,P_i\in {\mathbb{R}}^{n\times n}$$

Robust LP:

$$\underset{x}{min}{c}^{\mathrm{\top }}x\text{s.t.}{a}_i^{\mathrm{\top }}x\le b_i\mathrm{\forall }{a}_i\in {\mathcal{E}}_i,i=1,\dots ,m$$

Equivalent SOCP:

$$\underset{x}{min}{c}^{\mathrm{\top }}x\text{s.t.}{\overline{a}}_i^{\mathrm{\top }}x+\parallel P_i^{\mathrm{\top }}x{\parallel }_2\le b_i,i=1,\dots ,m$$

since $\underset{\parallel u{\parallel }_2\le 1}{sup}({\overline{a}}_i+P_{i}u{)}^{\mathrm{\top }}x={\overline{a}}_i^{\mathrm{\top }}x+\parallel P_i^{\mathrm{\top }}x{\parallel }_2$.

Example: Robust Linear Program (Stochastic)

Assume $a_i\sim \mathcal{N}({\overline{a}}_i,{\mathrm{\Sigma }}_i)$ is Gaussian. Then $a_i^{\mathrm{\top }}x\sim \mathcal{N}({\overline{a}}_i^{\mathrm{\top }}x,x^{\mathrm{\top }}{\mathrm{\Sigma }}_{i}x)$, and

$$Pr(a_i^{\mathrm{\top }}x\le b_i)=\mathrm{\Phi }\left(\frac{b_i-{\overline{a}}_i^{\mathrm{\top }}x}{\parallel {\mathrm{\Sigma }}_i^{1/2}x{\parallel }_2}\right)$$

where $\mathrm{\Phi }$ is the CDF of $\mathcal{N}(0,1)$. The robust LP with probability constraint

$$\underset{x}{min}{c}^{\mathrm{\top }}x\text{s.t.}Pr(a_i^{\mathrm{\top }}x\le b_i)\ge \eta ,i=1,\dots ,m$$

is equivalent to the SOCP (for $\eta \ge \frac{1}{2}$):

$$\underset{x}{min}{c}^{\mathrm{\top }}x\text{s.t.}{\overline{a}}_i^{\mathrm{\top }}x+{\mathrm{\Phi }}^{-1}(\eta )\parallel {\mathrm{\Sigma }}_i^{1/2}x{\parallel }_2\le b_i,i=1,\dots ,m$$

The terms $\parallel P_i^{\mathrm{\top }}x{\parallel }_2$ and ${\mathrm{\Phi }}^{-1}(\eta )\parallel {\mathrm{\Sigma }}_i^{1/2}x{\parallel }_2$ are interpreted as the budget margin for robustness.

---

4.10 Semidefinite Programming (SDP)

Definition (SDP). A semidefinite program is of the form:

$$\begin{array}{rl}\underset{x}{min}& c^{\mathrm{\top }}x\\ \text{s.t.}& x_1{F}_1+x_2{F}_2+\cdots +x_n{F}_n+F_0⪯0\\ & Ax=b\end{array}$$

where $F_i\in {\mathbb{S}}^k$ (symmetric $k\times k$ matrices). The inequality constraint $x_1{F}_1+\cdots +x_n{F}_n+F_0⪯0$ is called a linear matrix inequality (LMI).

LP $\subset$ SDP

An LP can be expressed as an SDP by using a diagonal matrix:

$$\underset{x}{min}{c}^{\mathrm{\top }}x\text{s.t.}Ax⪯b⟹\underset{x}{min}{c}^{\mathrm{\top }}x\text{s.t.}\mathrm{diag}(Ax-b)⪯0$$

SOCP $\subset$ SDP

The SOC constraint $\parallel x{\parallel }_2\le t$ is equivalent to the LMI

$$\parallel x{\parallel }_2\le t⟺\left[\begin{array}{cc}tI& x\\ x^{\mathrm{\top }}& t\end{array}\right]⪰0$$

This follows from the Schur Complement Theorem: for symmetric $A$, $C$ with $C\succ 0$,

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

Thus an SOCP can be rewritten as an SDP:

$$\begin{array}{rl}\underset{x}{min}& c^{\mathrm{\top }}x\\ \text{s.t.}& \parallel D_{i}x+d_i{\parallel }_2\le e_i^{\mathrm{\top }}x+f_i\end{array}⟹\underset{x}{min}{c}^{\mathrm{\top }}x\text{s.t.}\left[\begin{array}{cc}(e_i^{\mathrm{\top }}x+f_i)I& D_{i}x+d_i\\ (D_{i}x+d_i{)}^{\mathrm{\top }}& e_i^{\mathrm{\top }}x+f_i\end{array}\right]⪰0$$

Example: Eigenvalue Minimization

$$\underset{x}{min}{\lambda }_{max}(A(x))$$

where $A(x)=A_0+x_1{A}_1+\cdots +x_n{A}_n$ (with given $A_i\in {\mathbb{S}}^k$). Equivalent SDP:

$$\begin{array}{rl}\underset{x,t}{min}& t\\ \text{s.t.}& A(x)⪯tI\end{array}$$

since ${\lambda }_{max}(A)\le t⟺A⪯tI$.

---

4.11 Hierarchy of Problem Classes

The canonical convex optimization problem classes form a nested hierarchy:

$$\boxed{{\displaystyle \text{LP}\subset \text{QP}\subset \text{QCQP}\subset \text{SOCP}\subset \text{SDP}\subset \text{Conic Program}}}$$

Each class is a special case of the next, with increasing modeling expressiveness and computational cost.

Class	Objective	Constraints	Key Structure
LP	Linear $c^{\mathrm{\top }}x$	Linear inequalities $Ax⪯b$	Polyhedral feasible set
QP	Quadratic $\frac{1}{2}{x}^{\mathrm{\top }}Qx+c^{\mathrm{\top }}x$, $Q⪰0$	Linear inequalities	LP with quadratic objective
QCQP	Quadratic, $P_0⪰0$	Quadratic inequalities $P_i⪰0$	Quadratic in both objective and constraints
SOCP	Linear	$|D_{i}x+d_i{|}_2\le e_i^{\mathrm{\top }}x+f_i$	Second-order cone constraints
SDP	Linear	Linear matrix inequality $\sum x_i{F}_i+F_0⪯0$	Semidefinite constraints

Conic Program

At the top of the hierarchy is the conic program:

Definition (Conic Program).

$$\begin{array}{rl}\underset{x}{min}& c^{\mathrm{\top }}x\\ \text{s.t.}& \mathcal{A}(x)\in \mathcal{K}\\ & Ax=b\end{array}$$

where $\mathcal{A}:{\mathbb{R}}^n\to \mathcal{X}$ is an affine map and $\mathcal{K}$ is a convex cone.

All the previous classes are special cases of conic programs, depending on the choice of cone $\mathcal{K}$:

Problem	Cone $\mathcal{K}$
LP	$\mathcal{K}={\mathbb{R}}_{+}^n=\{x\in {\mathbb{R}}^n:x_1,\dots ,x_n\ge 0\}$ (nonnegative orthant)
SOCP	$\mathcal{K}=\mathcal{Q}=\{(x,t)\in {\mathbb{R}}^{n+1}:|x{|}_2\le t\}$ (second-order cone)
SDP	$\mathcal{K}={\mathbb{S}}_{+}^n=\{X\in {\mathbb{S}}^n:X⪰0\}$ (positive semidefinite cone)

---

4.12 Comparison: LP vs. QP in Practice

Aspect	LP	QP
Objective	$min{c}^{\mathrm{\top }}x$	$min\frac{1}{2}{x}^{\mathrm{\top }}Qx+c^{\mathrm{\top }}x$
Constraints	$Dx⪯d$, $Ax=b$	$Dx⪯d$, $Ax=b$

• LP $\subset$ QP (QP recovers LP when $Q=0$).
• Often, solving an LP in theory amounts to solving a QP in practice.

Diet problem:

• In theory: cost $c$ is deterministic $\to$ LP.
• In practice: $c$ is a random vector $\to$ QP.

Basis pursuit:

• In theory: samples are noise-free ($Ax=b$) $\to$ LP.
• In practice: samples are noisy ($Ax\ne b$) $\to$ QP (LASSO).

Deterministic vs. stochastic robustness:

• In theory: deterministic LP $\to$ LP.
• In practice: robust LP under uncertainty $\to$ SOCP.

---

4.13 Practical Methods for Establishing Convexity

Establishing Convexity of a Set $C$

1. Apply the definition: $x_1,x_2\in C$, $0\le \theta \le 1⟹\theta x_1+(1-\theta )x_2\in C$.
2. Show $C$ is obtained from simple convex sets by operations that preserve convexity:
   • Intersection
   • Affine function
   • Perspective function
   • Linear-fractional function
3. Show $C$ is a sublevel set of a convex function.
4. Show $C$ is the epigraph of a convex function.

Establishing Convexity of a Function $f$

1. Apply the definition: $f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y)$.
2. Use equivalent conditions (e.g., ${\mathrm{\nabla }}^{2}f(x)⪰0$).
3. Show $f$ is obtained from simple convex functions by operations that preserve convexity:
   • Nonnegative weighted sum: $g(x)=\sum _{i=1}^m{\alpha }_i{f}_i(x)$, ${\alpha }_i\ge 0$.
   • Composition with affine function: $g(x)=f(Ax+b)$.
   • Pointwise maximum: $g(x)=max\{f_1(x),\dots ,f_m(x)\}$.
   • Pointwise supremum.
   • Composition with scalar functions.
   • Minimization.
   • Perspective.

---

4.14 Summary of Key Theorems

1. The feasible set of a convex optimization problem is convex.
2. Every local optimum of a convex problem is a global optimum.
3. For strictly convex $f_0$, the optimal solution (if it exists) is unique.
4. First-order optimality condition: $x^{\star }$ is optimal for $\underset{x\in C}{min}f(x)$ iff $⟨\mathrm{\nabla }f(x^{\star }),y-x^{\star }⟩\ge 0$ for all $y\in C$.
5. Problems can be made equivalent through monotone transformations, change of variables, slack variables, epigraph formulation, and relaxation.
6. The hierarchy LP $\subset$ QP $\subset$ QCQP $\subset$ SOCP $\subset$ SDP $\subset$ Conic Program provides progressively richer modeling frameworks, each with convex structure guaranteeing global optimality.