3.3. Convex Relaxation

Convex Relaxation

Convex relaxation is a technique used to approximate a difficult, non-convex optimization problem by a related convex problem that is easier to solve. Consider a general optimization problem
$\min f(x)\text{s.t. }x\in S,$
where $f$ is convex but the feasible set $\mathcal{S}$ is non-convex. A convex relaxation replaces $\mathcal{S}$ with a convex superset $\tilde{\mathcal{S}}$ such that $\mathcal{S}\subseteq \tilde{\mathcal{S}}$, yielding
$\min f(x)\text{s.t. }x\in \tilde{\mathcal{S}}.$

The relaxed problem is convex and therefore tractable using convex optimization tools. Because the feasible set has been enlarged, the optimal value of the relaxed problem provides a lower bound on the optimal value of the original problem. Formally, if $x^{\ast }$ is a global minimizer of the original problem and $\tilde{x}$ is a global minimizer of the relaxed problem, then
$f(\tilde{x})\le f(x^{\ast }).$

If the solution $\tilde{x}$ of the convex relaxation happens to lie in the original feasible set $\mathcal{S}$, then $\tilde{x}$ is also a global minimizer of the original problem. In this case, the relaxation is said to be exact, meaning that solving the convex relaxation solves the original non-convex problem.

A particularly important case occurs when all vertices of the relaxed feasible set are integral (i.e., have integer coordinates), in which case every optimal solution of the relaxation corresponds to a valid solution of the original problem.