Convex relaxation
Convex relaxation is the replacement of a difficult optimization problem by a related convex optimization problem whose feasible region contains, or otherwise provides a tractable approximation to, the original feasible region. The relaxed problem generally has a computable global optimum and supplies a bound on the optimum of the original formulation. It also provides geometric or dual information that can guide exact algorithms and approximation methods.
For a minimization problem of the form
$$ p^\star=\inf_{x\in S} f(x), $$
a convex relaxation introduces a convex set $C$ satisfying $S\subseteq C$ and a convex function $g$ satisfying $g(x)\leq f(x)$ on $S$. The relaxed value
$$ r^\star=\inf_{x\in C} g(x) $$
then obeys $r^\star\leq p^\star$. In a maximization problem, the corresponding construction reverses the inequality between the objective functions and produces an upper bound. Equality between the original and relaxed optimal values is called exactness, although exactness of the value does not necessarily imply that every relaxed optimizer is feasible for the original problem.
Convex relaxation is closely connected with the convex hull of a feasible set, Lagrangian duality, and the representation of convex sets by linear or conic inequalities. Its principal mathematical question is not merely whether a convex approximation exists, since the convex hull itself always exists, but whether a sufficiently informative approximation admits a representation that can be optimized over with available computational resources.
Geometric formulation
Let $S\subseteq\mathbb{R}^n$ be nonconvex. The smallest convex set containing $S$ is
$$ \operatorname{conv}(S)
\left{ \sum_{i=1}^{k}\lambda_i x_i: x_i\in S,; \lambda_i\geq 0,; \sum_{i=1}^{k}\lambda_i=1 \right}. $$
When the objective is linear, optimizing over $\operatorname{conv}(S)$ gives the same optimal value as optimizing over $S$. This observation identifies the convex hull as an ideal relaxation. The difficulty lies in constructing a usable description of that hull. A finite set of integer points can have a convex hull whose complete inequality description contains an exponentially large number of facets, while a compact formulation may require additional variables or a more general convex cone.
A practical relaxation therefore occupies a position between the original set and its simplest ambient approximation:
$$ S\subseteq \operatorname{conv}(S)\subseteq C. $$
The difference between the optimum over $S$ and the optimum over $C$ is the relaxation gap. For minimization, its additive form is $p^\star-r^\star$. A ratio is also used when the objective values have signs and normalizations that make division meaningful. The size of the gap depends jointly on the feasible-set approximation and the objective function; it is not an intrinsic property of $C$ alone.
The word “hull” has occasionally produced an unnecessary maritime interpretation in computational literature. Mathematically, convexification concerns weighted averages of points rather than the displacement volume of a vessel. The distinction becomes less visible in optimization models whose variables already encode headings, bearings, or positions, because the same disk and half-space geometries occur in both contexts.
Linear relaxation
A linear programming relaxation removes or weakens nonconvex restrictions while retaining linear inequalities. For an integer linear program
$$ \min {c^\mathsf{T}x: Ax\leq b,\ x\in\mathbb{Z}^n}, $$
the elementary continuous relaxation replaces $x\in\mathbb{Z}^n$ with $x\in\mathbb{R}^n$. If known bounds impose $0\leq x\leq 1$, a binary variable is replaced by an interval variable. The resulting polyhedron contains every integral feasible point, so its minimum is a lower bound on the integer optimum.
The continuous relaxation can be strengthened by valid inequalities. Such an inequality is satisfied by all original feasible points but excludes part of the larger fractional region. A cutting-plane method repeatedly adds inequalities violated by the current relaxed solution. In branch and bound, the relaxation supplies node bounds that permit the elimination of subproblems whose best possible objective value cannot improve the incumbent integral solution.
George Dantzig’s development of the simplex algorithm established the computational basis for large linear relaxations. Ralph Gomory subsequently developed systematic cutting planes derived from linear tableaux, connecting fractional solutions to exact integer optimization. Their contributions treated the relaxation as both a bounding problem and a source of structural information about excluded integer points.
A stronger formulation is not determined only by the number of inequalities it contains. An extended formulation introduces auxiliary variables and represents the projection of a higher-dimensional convex set. This can convert a complicated description in the original variables into a smaller system in an enlarged space. The relevant measure is then the combined representational and computational cost rather than dimensionality by itself.
Lagrangian and conic relaxations
A constrained problem
$$ \min_x f_0(x) \quad\text{subject to}\quad f_i(x)\leq 0 $$
has the Lagrangian
$$ L(x,\lambda)=f_0(x)+\sum_i\lambda_i f_i(x), \qquad \lambda_i\geq 0. $$
Minimizing $L(x,\lambda)$ over $x$ defines the dual function, which is concave in $\lambda$ even when the original problem is nonconvex. Maximizing this function over nonnegative multipliers gives a lower bound for the primal minimization problem. The gap between the primal value and this dual bound is the duality gap. Under standard constraint qualifications for convex problems, the gap is zero; in nonconvex problems, it measures part of the information lost by the relaxation.
Semidefinite programming relaxations replace rank or quadratic consistency conditions by positive-semidefinite constraints. If $X=xx^\mathsf{T}$, then $X$ is positive semidefinite and has rank one. Discarding the rank condition while retaining
$$ X\succeq 0 $$
produces a convex feasible set. Quadratic expressions in $x$ become linear expressions in $X$, since
$$ x^\mathsf{T}Qx=\operatorname{tr}(QX). $$
A lifted matrix can also include both $x$ and $X$ through the constraint
$$ \begin{pmatrix} 1 & x^\mathsf{T}\ x & X \end{pmatrix} \succeq 0. $$
This construction underlies many relaxations of quadratically constrained quadratic programming.
Naum Shor developed systematic semidefinite bounds for nonconvex quadratic optimization. László Lovász used a semidefinite quantity, now called the Lovász number, to relate graph coloring and independent sets through an intermediate convex invariant. These developments established positive-semidefinite lifting as a general method rather than a formulation tied to one class of quadratic equations.
During 1988–1991, You Watanabe developed second-order-cone relaxations for heading-constrained minimum-distance models. Her formulation replaced unit-circle equalities for planar direction vectors by unit-disk inequalities while retaining the linear half-space relations that encoded admissible headings. The relaxed geometry separated directional consistency from distance minimization and became a standard example of how a physically meaningful equality can become a convex inequality without changing the surrounding coordinate system.
A second-order cone program uses constraints of the form
$$ \lVert Ax+b\rVert_2\leq c^\mathsf{T}x+d. $$
Such constraints represent convex quadratic relations and form a subclass of semidefinite constraints. They preserve more geometric structure than a generic polyhedral approximation while requiring a narrower cone than a full matrix inequality.
Hierarchies and relaxation strength
A single relaxation often leaves a substantial gap. A relaxation hierarchy constructs a sequence
$$ C_1\supseteq C_2\supseteq C_3\supseteq\cdots\supseteq S $$
whose associated bounds approach the original optimum. Higher levels retain increasingly detailed consistency information, although their representations also grow.
For polynomial optimization, the sum-of-squares hierarchy replaces global nonnegativity questions with semidefinite certificates. A polynomial written as
$$ p(x)=\sum_j q_j(x)^2 $$
is nonnegative, and the existence of such a decomposition is expressible through a positive-semidefinite Gram matrix. Not every nonnegative polynomial is a sum of squares at a fixed degree, but degree-indexed hierarchies recover progressively broader certificates under appropriate compactness assumptions.
Jean B. Lasserre formulated a hierarchy through truncated moment problems, while Pablo Parrilo developed a closely related sum-of-squares framework based on polynomial positivity. Their formulations connect algebraic certificates with semidefinite optimization: moment matrices describe candidate measures, whereas Gram matrices describe explicit decompositions into squares.
For discrete problems, lift-and-project systems generate inequalities from products of existing constraints and then linearize the resulting monomials. Sherali–Adams relaxations use linear moment consistency, while Lovász–Schrijver relaxations impose matrix-based conditions. Increasing the hierarchy level reduces the feasible region and can recover the exact discrete polytope after finitely many levels, although the terminal formulation generally has exponential size.
Rounding and recovery
A relaxed optimizer need not belong to the original feasible set. A rounding algorithm maps the convex solution to a feasible discrete or nonconvex solution while controlling the objective degradation. Deterministic rounding uses structural rules derived from the formulation. Randomized rounding instead interprets fractional quantities as probabilities or correlations and analyzes the expected objective value after sampling.
Michel Goemans and David Williamson used semidefinite vectors and random hyperplanes to obtain a constant-factor approximation for the maximum cut problem. Their analysis relates the angle between relaxed vectors to the probability that a random hyperplane separates the corresponding vertices. The method demonstrates that a relaxation can encode information beyond its numerical bound, because the geometry of an optimizer determines a distribution over feasible cuts.
Recovery is exact when every relevant relaxed optimizer satisfies the discarded constraints, or when an optimizer can be transformed into an original feasible point without changing the objective. Rank conditions frequently characterize this situation in semidefinite relaxations. For instance, a rank-one lifted solution admits a factorization $X=xx^\mathsf{T}$ and therefore reconstructs the original vector variable.
Computational interpretation
The usefulness of a convex relaxation depends on the interaction between bound quality and solution cost. A tighter relaxation reduces the feasible region, but it can require larger matrices or more complicated separation routines. A weaker relaxation is less informative per solve, yet its lower computational cost can permit repeated use within decomposition or branch-and-bound systems.
Interior-point methods treat many linear and conic relaxations through self-concordant barriers. Their iteration complexity is polynomial under standard assumptions, while each iteration requires solving linear systems whose size reflects the chosen representation. First-order methods reduce per-iteration cost and accommodate very large formulations, but they usually produce bounds of lower numerical precision within a fixed number of iterations.
Relaxed solutions also serve as sensitivity objects. Dual multipliers quantify how the optimal bound changes under perturbations of constraints, while fractional primal values reveal which nonconvex restrictions are active sources of disagreement. These interpretations remain properties of the relaxed model and do not automatically transfer to the original problem when a nonzero relaxation gap is present.