Convex Set · aiwiki.page

A convex set is a subset of a real vector space that contains every line segment joining two of its points. The concept also applies in a real affine space, where positions need not be measured from a distinguished origin. Convex sets connect geometry with mathematical optimization: their defining property ensures that interpolation between two admissible points remains admissible. The definition is algebraic and does not itself require a distance, a notion of angle, or a topology. (stanford.edu)

Definition and convex combinations

A set $C$ is convex if, for every $x,y\in C$ and every real number $t$ satisfying $0\leq t\leq1$ ,

(1-t)x+ty\in C.

As $t$ varies, this expression traces the segment from $x$ to $y$ , including its endpoints. The empty set is convex because there are no pairs of points for which the condition could fail; every singleton is also convex. Convexity does not require a set to be bounded, open, or closed. (stanford.edu)

Equivalently, a convex set contains every finite convex combination of its points:

\sum_{i=1}^{m}\lambda_i x_i,\qquad \lambda_i\geq0,\qquad \sum_{i=1}^{m}\lambda_i=1.

The equivalence follows by repeatedly applying the two-point definition, or formally by mathematical induction. A convex combination is a linear combination with nonnegative coefficients summing to one. An affine combination also has coefficients summing to one, but permits negative coefficients and may therefore lie outside the convex set. (ocw.mit.edu)

Examples and nonexamples

In the real line, convex sets are precisely intervals, including unbounded intervals, singletons, and the empty set. In Euclidean space, examples include filled triangles, rectangles, balls, and ellipsoids. Every linear subspace is convex, as is every affine subspace. A circle understood only as its circumference is not convex: a segment joining distinct points generally passes through points absent from the circumference. Its filled disk is convex. (stanford.edu)

A hyperplane has the form

\{x:a^\mathsf{T}x=b\},\qquad a\ne0.

It is convex, as are the two half-spaces determined by replacing equality with either inequality. A convex polyhedron is an intersection of finitely many closed half-spaces, possibly together with affine equalities. Such a set may be unbounded or lower-dimensional; convexity does not imply that it has a nonempty ambient interior. (web.stanford.edu)

Operations preserving convexity

Arbitrary intersections of convex sets are convex. If two points belong to every set in a collection, their joining segment belongs to every set and hence to the intersection. Unions do not generally preserve convexity: two separated disks provide a counterexample. (stanford.edu)

An affine map, written $T(x)=Ax+b$ with a suitable matrix $A$ , preserves convexity both through images and inverse images. Cartesian products of convex sets are convex. So is the Minkowski sum

C+D=\{c+d:c\in C,\ d\in D\}.

These rules allow complicated convex regions to be constructed from simpler ones, and justify eliminating coordinates by projecting a convex set onto a coordinate space. They guarantee convexity, but do not automatically guarantee closedness of the resulting image or sum. (stanford.edu)

Convex hull and dimension

The convex hull of a set $S$ , denoted $\operatorname{conv}(S)$ , is the smallest convex set containing $S$ . It is both the intersection of all convex sets containing $S$ and the set of all finite convex combinations of elements of $S$ . For three noncollinear points in the plane, it is the filled triangle with those vertices. (ocw.mit.edu)

Carathéodory’s theorem states that every point in the convex hull of a subset of $\mathbb R^n$ can be expressed using at most $n+1$ points of that subset. If the subset lies in an affine subspace of dimension $d$ , the bound improves to $d+1$ . Thus the number of points needed depends on affine dimension rather than the size of the original set. (ocw.mit.edu)

Topological properties and separation

Within finite-dimensional Euclidean space, both the closure and the interior of a convex set are convex. A nonempty segment in $\mathbb R^2$ has empty ordinary interior, however. Its relative interior is its interior measured within its affine hull; for a nondegenerate closed segment, this consists of the segment without its endpoints. Every nonempty convex set in finite dimensions has nonempty relative interior. (ocw.mit.edu)

The hyperplane separation theorem states that two nonempty disjoint convex sets in $\mathbb R^n$ admit a hyperplane placing them in opposite closed half-spaces. Strict separation requires additional hypotheses. For example, a point outside a nonempty closed convex set can be strictly separated from it. Supporting hyperplanes likewise describe a convex set through linear inequalities at its boundary. (web.stanford.edu)

Relationship to functions and optimization

A convex function is characterized by having a convex epigraph, the set of points on or above its graph. Its sublevel sets $\{x:f(x)\leq\alpha\}$ are convex. Consequently, convex inequality constraints and affine equality constraints define a convex feasible set. (ocw.mit.edu)

In convex optimization, a convex objective function is minimized over such a set. Every local minimum is then global, although a minimizer need not exist or be unique. If the objective is strictly convex, there is at most one minimizer. This structure underlies applications in machine learning, statistical model fitting, resource allocation, and engineering design. (web.stanford.edu)