convexify

Convexify is a term used in mathematics and related fields to describe the process of turning a nonconvex object or problem into a convex one. It is employed in geometry, convex analysis, and optimization to obtain a simpler or more tractable surrogate of the original object.

In geometry, convexification typically refers to forming the convex hull. Given a set S in Euclidean space, its convexification is the smallest convex set containing S, denoted conv(S). The convex hull of two points is the line segment joining them; the convex hull of a polygon is the smallest convex polygon that contains it.

In analysis and optimization, convexification can also mean turning a function into a convex function. The convex envelope (also called the lower convex envelope) of a function f on a convex domain is the greatest convex function g such that g(x) ≤ f(x) for all x. If f is proper and lower semicontinuous, this envelope coincides with the biconjugate f**.

As a relaxation technique, convexification is used to transform nonconvex problems into convex ones that can be solved efficiently, providing bounds or global optima for the original problem. Common methods include linear underestimators, McCormick envelopes for bilinear terms, and semidefinite relaxations. In computational geometry, convex hull algorithms such as Graham scan and Quickhull explicitly compute the convexification of a finite point set.

Across disciplines, convexification serves to simplify analysis and computation by replacing nonconvex structure with convex approximations, acknowledging that relaxation may introduce approximation error that must be managed.