convexrelaxation

Convex relaxation is a method in optimization used to transform a nonconvex problem into a convex one, typically by enlarging the feasible set or by replacing a nonconvex objective with a convex surrogate. The resulting problem is easier to solve with guaranteed convergence to a global optimum for convex problems. For a minimization problem, the relaxation usually yields a lower bound on the original optimum because the relaxed feasible set contains the original one.

A standard approach is to replace the nonconvex constraints with convex ones, or to take the convex hull of the feasible set. Another common tactic is to replace nonconvex objectives with convex surrogates. The relaxed problem is convex, and its optimal value provides a bound on the original problem. If the relaxation is tight, the optimal solutions to the relaxed and original problems coincide.

Common techniques include L1 relaxation for promoting sparsity by substituting the nonconvex L0 norm with the convex L1 norm; semidefinite relaxation, which lifts quadratic forms to higher-dimensional matrix variables and imposes positive semidefiniteness; and nuclear-norm relaxation, which uses the trace norm as a convex surrogate for rank. Convex hulls of nonconvex sets and linear programming relaxations of integer programs are also widely used.

Applications span machine learning, signal processing, control, computer vision, and combinatorial optimization. Convex relaxations underpin many practical algorithms due to their balance between tractability and providing useful bounds. Limitations include potential looseness of the bound and computational cost for large-scale or high-order relaxations; in some cases, the relaxation may be far from tight, necessitating stronger hierarchies or problem-specific refinements.