Convex set ($(1-t)x+ty\in C(0\le t\le 1)$)

A convex set permits every intermediate mixture of two of its points. If two choices meet its constraints, continuously averaging them also meets those constraints. This geometric property makes many feasible regions easier to explore: there is no forbidden gap along a straight move between feasible choices.

Formally, a subset $C$ of a real vector space is convex whenThe parameter $t$ traverses the entire line segment, including both endpoints. The definition does not require a closed subset, a bounded set, or a nonempty interior. The empty set, the whole vector space, and every affine subspace are convex; an open unit disk and a closed unit disk are both convex.^[ref]

The triangle inequality verifies the disk example directly: if $\Vert x\Vert ,\Vert y\Vert \le 1$, then $\Vert (1-t)x+ty\Vert \le (1-t)\Vert x\Vert +t\Vert y\Vert \le 1$. For the open disk, the last inequality is strict. The unit circle fails the same test: $(1,0)$ and $(-1,0)$ belong to it, but their midpoint $(0,0)$ does not. A curved route along the unit circle connects the endpoints, so being path-connected is weaker than being a convex set.

The distinction between a convex set and a convex function matters. The former concerns where one may choose a point; the latter concerns how a value changes along line segments. Convex optimization combines both: averaging preserves feasibility, and a convex function obeys an upper bound by the corresponding average of endpoint values. A convex set alone does not make an arbitrary objective a convex function or eliminate its inferior local minima.

Consider a stipulated continuous-allocation problem. Amounts $x,y$ of two activities use $x+2y$ units of a common resource, with budget six. The feasible regionis a triangle with extreme points $(0,0)$, $(6,0)$ and $(0,3)$. It is the intersection of three closed half-spaces, hence a closed convex set. The general intersection argument is short: a line segment between two points in every constraint set belongs to every constraint set, so it belongs to their intersection.^[ref]

For an original numerical check, take $A=(1,2)$ and $B=(5,1/4)$. Their resource totals are $5$ and $11/2$. Every convex combination $Z(t)=(1-t)A+tB$ is nonnegative and has resource totalIn particular the midpoint is $(3,9/8)$, using $21/4$ units. This verifies the full line segment, rather than just a plotted sample of it.

This is useful whenever divisible quantities share linear limits: the feasible choices remain compatible under averaging. A new linear equation also preserves this property, because averaging two identical constraint values gives the same value. The affine subspace and closed half-space viewpoints explain this without requiring a separate argument for every budget.

If the amounts in the budget example must be integers, the actual feasible region is $C\cap {\mathbb{Z}}^2$. Both $(0,0)$ and $(1,0)$ are feasible, but their midpoint $(1/2,0)$ is not. Thus the continuous feasible region is a convex set while the integer-restricted choices are not. Averaging two manufacturing plans may specify half an indivisible item. Integer programming must respect that restriction; using the surrounding convex set is a relaxation, not a proof that its averages are admissible integer plans.

Checking only midpoints is not enough for an arbitrary subset of a real vector space. The rational numbers contain the midpoint of every pair of rational numbers, but the line segment from $0$ to $1$ also contains irrational numbers. For instance $\sqrt{2}/2$ lies on that line segment and is not rational. This shows why the definition quantifies over every real $t\in [0,1]$.

There is a useful additional hypothesis: a closed subset $C\subseteq {\mathbb{R}}^d$ containing the midpoint of every pair of its points is a convex set. Repeated bisection includes all points $(1-t)x+ty$ with dyadic rational $t\in [0,1]$. These coefficients approach every real $t\in [0,1]$; being a closed subset then includes each limit. This is a short proof outline, and the rational numbers example identifies precisely why a closed subset was required.

A convex set that is also a closed subset in the specified topology. In a Hilbert space with its norm topology, every nonempty closed convex set has a unique nearest point to every ambient vector, by the Hilbert projection theorem.

Two nonempty disjoint convex sets in a finite-dimensional real vector space admit a separating nonzero linear functional: for an appropriate $h\ne 0$ and $a$, $h\cdot x\le a\le h\cdot y$ on the respective sets. Strict separation requires additional assumptions, such as one set being compact and the other closed. For an open convex cone $C$ excluding zero, separation from $\{0\}$ gives $h\cdot c\ge 0$ for all $c\in C$; scaling cone elements forces the separating level to be zero. This finite-dimensional result is related to the supporting hyperplane theorem.

A convex set in a finite-dimensional space has a nonzero supporting linear functional at each boundary point. If zero lies outside a nonempty convex set $C$, weak separation gives $p\ne 0$ with $p\cdot c\ge 0$ for all $c\in C$, even when zero belongs to its closure. Strict separation needs stronger hypotheses.

The relative interior of a convex set is its interior in its affine span. A polyhedral cone has nonempty relative interior in its linear span, even when its ordinary interior in the ambient vector space is empty.

// Target: geometry-and-topology.bigb

A subset $C$ of a real vector space is radially open when, for each $x\in C$ and each vector $v$, the points $x+tv$ remain in $C$ for all sufficiently small real $t$. No ambient topology is required. If $C$ is also convex and contains zero, it is absorbing and its Minkowski functional $p_C(x)=\inf \{s>0:x\in sC\}$ is finite and sublinear, with $C=\{p_C<1\}$. Convexity gives subadditivity; radial openness permits a slight dilation of any point of $C$, giving the strict inequality.

A closed convex set in a finite-dimensional Euclidean space is the intersection of all containing closed half-spaces. For a point outside a nonempty set, its Euclidean projection onto a convex set gives a separating normal. Applied to an epigraph, this turns geometric separation into affine lower bounds and is a key step in the Fenchel-Moreau theorem.

The recession cone of a nonempty convex set $C$ consists of directions $d$ for which $x+td\in C$ for every $x\in C$ and $t\ge 0$. For a linear polyhedron $P=\{x:Ax\le b\}$ it is exactly $\{d:Ad\le 0\}$. A nonzero recession direction gives an unbounded ray, so a bounded nonempty polyhedron has recession cone $\{0\}$. This excludes spurious zero-scale feasible points in the Charnes-Cooper transformation.

A convex set $F\subseteq C$ is a face of $C$ if $ty+(1-t)z\in F$, with $y,z\in C$ and $0<t<1$, implies $y,z\in F$. A singleton face is an extreme point. A face of a face is a face of the original convex set.

Let $F$ be a nonempty norm-closed face of a convex set $[0,1_A]$ in a unital C-star algebra, with $0\notin F$. Every $a\in F$ has norm one: otherwise $a=\Vert a\Vert (a/\Vert a\Vert )+(1-\Vert a\Vert )0$ is a nontrivial convex decomposition forcing zero into the face. If $g:[0,1]\to [0,1]$ is continuous and nondecreasing with $g(0)=0,g(1)=1$, then $g(a)\in F$.

To prove this, for $n\ge 2$ replace $g$ near the endpoints by a function $g_n$ which is zero on $[0,1/(2n)]$, one on $[1-1/(2n),1]$, agrees with $g$ on $[1/n,1-1/n]$, and interpolates linearly in between. Monotonicity and endpoint continuity give $g_n\to g$ uniformly. With $\delta =1/(2n)$, the function $h_n(t)=(t-\delta g_n(t))/(1-\delta )$ takes values in $[0,1]$: check the two constant regions and use $\delta \le t\le 1-\delta$ elsewhere. The continuous functional calculus gives $a=\delta g_n(a)+(1-\delta )h_n(a)$ with both summands positive contractions. The face property gives $g_n(a)\in F$, and closedness gives $g(a)\in F$.

An exposed face of a convex set $K$ is the nonempty set on which a supporting real linear functional attains its maximum. It is a face of a convex set: if $x=ty+(1-t)z$ with $0<t<1$ attains the maximum and $y,z\in K$, each of $f(y),f(z)$ is at most that maximum, so both equal it. On a complex vector space, take the real part of a complex linear functional. An exposed point is an exposed face consisting of one point.

A compact convex set $K\subseteq {\mathbb{R}}^n$ is a compact set that is also a convex set. If $K$ is nonempty, its support function $H_K(\eta )={\max }_{x\in K}x\cdot \eta$ is finite in every direction. For such a nonempty $K$, every exterior point $x_0$ admits a strictly separating hyperplane: minimize $|x_0-y|$ over $y\in K$, and put $\omega =x_0-y$. Convexity and differentiation along the segment from $y$ to any $z\in K$ give $\omega \cdot (z-y)\le 0$, while $\omega \cdot (x_0-y)=|\omega {|}^2>0$. This is the separation used to recover spatial support from Fourier growth.

The nonnegative orthant consists of vectors whose coordinates are all nonnegative. Its interior is the positive orthant, where every coordinate is positive.

It is the closed orthant obtained by choosing the nonnegative sign for every coordinate.

A convex combination is a finite weighted average of points in a real vector space. For $n\ge 1$, it has the formThe nonnegative coefficients forbid subtracting a component, and their unit sum keeps the result on the same affine scale as the inputs. With two points it parametrizes their line segment; equal coefficients give their centroid. A convex set contains every finite convex combination of its points. Conversely, the two-point case already gives the defining property of a convex set.^[ref]

The distinction from a linear combination is concrete. Combining $(0,0)$ and $(2,0)$ with coefficients $-1$ and $2$ gives $(4,0)$, outside their line segment, despite the unit coefficient sum. Using two coefficients both equal to one gives $(2,0)$ here, but their sum is two, so it is not a convex combination with those coefficients. A numerical output may happen to coincide with a point admitting a different convex representation; the definition applies to the specified coefficients.

Every allocation $(x,y)$ in the convex feasible region for a resource budget is a convex combination of its three extreme points:The condition $x+2y\le 6$ is exactly ${\lambda }_1\ge 0$; nonnegative $x,y$ give the other two nonnegative coefficients. Thus the half-space description and the convex hull description encode the same triangle. At $(2,1)$ all three coefficients are $1/3$, and at $(3,9/8)$ they are $1/8$, $1/2$, $3/8$. The green and orange points in the budget diagram therefore have two complementary interpretations: direct resource constraints and mixtures of extreme choices.

The three extreme points alone are not a convex set, because their midpoints are absent. Their convex hull fills the whole triangle. More generally, Caratheodory theorem bounds how many generating points are needed for one convex combination in a finite-dimensional real vector space; its geometric content is that a complicated collection can describe each attainable average with a short representation.

If a convex subset of ${\mathbb{R}}^n$ is invariant under cyclic coordinate permutation, averaging the $n$ cyclic images of $x$ shows thatalso belongs to the set.

A closed half-space is a set of the form $\{x:a^{T}x\le b\}$ for a nonzero vector $a$; it is a convex set and is closed.

This is the non-strict version of a half-space; replacing the inequality by a strict one gives the open version.

The line segment joining vectors $x$ and $y$ is

The midpoint of the line segment joining two points with position vectors $a,b$ is the point $m=(a+b)/2$. Its displacements from the endpoints are $(b-a)/2$ and $(a-b)/2$, so it lies on the segment and is equidistant from its endpoints. It is also the centroid of the two endpoints.

For line segments $P+sd$ and $Q+te$, $0\le s,t\le 1$, the squared Euclidean distance is a convex quadratic function on a square. Its minimum is either an admissible stationary point or a minimum on one of the four edges. Each edge minimum is a point-to-segment orthogonal projection, restricted to the interval. Testing these five candidates gives a complete algorithm; when the directions are parallel, the edge candidates suffice. Independently restricting both coordinates of the unconstrained stationary point is generally incorrect because the variables are coupled by $d\cdot e$.

For segments with initial direction vectors $U,T$, initial endpoint displacement $D$, and translation velocities $V,W$, contact is feasibility of the displayed linear equation with $s,r\in [0,1]$ and $t\ge 0$. Minimizing $t$ is a small linear programming problem. A nonsingular three-column coefficient matrix gives at most one candidate; singular, parallel and degenerate cases require the constrained feasibility problem rather than division by a vanishing determinant.

The earliest approach within distance $d$ is a convex optimization problem with a norm constraint and the same segment and time bounds as contact. An elementary alternative enumerates whether each segment parameter is free or at an endpoint. In each nonsingular active case the free closest-point parameters are affine functions of time, leaving a quadratic distance inequality on a valid time interval. Rank-deficient cases need their null-space constraints retained. Unlike contact, the two segment parameters and time are no longer determined by a vector equality.

A convex polytope is a bounded intersection of finitely many closed half-spaces, equivalently the convex hull of finitely many points.

A zonotope is a Minkowski sum of finitely many line segments, equivalently an affine map image of a cube. For vectors ${\xi }_j$, the set ${\sum }_j[0,1]{\xi }_j$ is the support of the associated box spline. A centred version uses $[-1/2,1/2]{\xi }_j$ instead. In two dimensions, sums of differently directed segments give centrally symmetric polygons; repeated directions lengthen their corresponding edges without adding new edge directions.

A lattice polytope is the convex hull of finitely many points of a Euclidean lattice. It need not contain the origin. Integral translation changes its associated homogeneous semigroup ring by a grading-preserving isomorphism.

// Target: geometry-and-topology.bigb

A convex polygon is a two-dimensional convex polytope, equivalently the convex hull of a finite planar set with nonempty interior. Its vertices are the extreme points of that hull. Saying that given points form a convex polygon means every specified point is a vertex; points inside the hull or in the interior of a straight boundary segment do not count as vertices.

A strictly convex polygon is a convex polygon whose interior angles are all strictly less than $180$ degrees.

For a finite point set in the plane, a convex polygon whose vertices of a polygon belong to the set and whose interior contains no point of the set. The convention must specify whether additional points on the boundary are allowed. A fan triangulation reduces emptiness to tests on constituent triangles, together with checks that internal diagonals contain no forbidden points.

A triangulation of a convex polygon divides a convex polygon into triangles using diagonals between its existing vertices of a polytope, with no diagonal crossings in the interior. For $m\ge 3$ vertices it uses $m-3$ diagonals and produces $m-2$ triangles. Fixing one boundary edge, its adjacent triangle separates two smaller polygon regions; summing over the possible third vertices of a polytope gives the Catalan recurrence. Thus the number of triangulations of a convex polygon is $C_{m-2}$, with $C_n$ the Catalan number. A quadrilateral has two choices and a pentagon has five.

A convex chain between two fixed points inside a triangle is a finite point set whose union with the endpoints forms the vertices of a convex polygon, with the endpoint segment as one boundary edge. In the triangle $0\le y\le x\le 1$, with endpoints $(0,0)$ and $(1,1)$, its ordered lower boundary has strictly increasing segment slopes. Every subset of its intermediate vertices remains a convex chain. This hereditary property lets selected point coordinates certify the existence of a long chain.

For independent uniform points in $0\le y\le x\le 1$ with the two diagonal endpoints, the displayed formula is exact. Order the $k$ intermediate points so that both coordinates increase, and write the $k+1$ positive coordinate spacings as $(u_i)$ and $(v_i)$, with each sum equal to one. The two spacing vectors have uniform simplex measure, independently, and the full ordered-coordinate region has volume $1/(k!{)}^2$. Simultaneous permutation of the spacing pairs preserves that measure, so all $(k+1)!$ orders of the ratios $v_i/u_i$ have equal volume. Strictly increasing ratios characterize a convex chain and automatically place the intermediate points below the diagonal. Thus its ordered volume is $1/((k!{)}^2(k+1)!)$. There are $k!$ ways to assign labels, and uniform triangle density is $2^k$, giving the formula. Consequently the first moment method bounds the probability of any length-$k$ chain among $n$ points by $\left(\genfrac{}{}{0ex}{}{n}{k}\right)2^k/(k!(k+1)!)$.

For $n$ points in a triangle and two fixed endpoint vertices, the longest convex chain length is the largest number of sampled points in a convex chain joining those endpoints. It is a certifiable function: a chain of length $a$ supplies a certificate of exactly $a$ point coordinates. Changing one point changes the maximum by at most one, since deleting that point from any optimal chain loses at most one vertex. For independent uniform points, its median is $O(n^{1/3})$ and its fluctuation scale about the median is at most $n^{1/6}$, as proved by convex-chain probability in a triangle and convex-chain median concentration.

Let $m$ be an integer median for the longest convex chain length of independent uniform points in a triangle. If $L_n(x)\ge a$, fix a certificate of $a$ coordinates. Every configuration with $L_n\le b$ must disagree with at least $a-b$ of those coordinates; equal weights $1/\sqrt{a}$ prove Talagrand convex distance separation at least $(a-b)/\sqrt{a}$. Talagrand's convex distance inequality then gives $\mathbb{P}(L_n\ge a)\mathbb{P}(L_n\le b)\le e^{-(a-b{)}^2/(4a)}$. Set $b=m$, then $a=m$, in the two respective applications to obtain the displayed tails for positive integer $t$. The exact chain-counting bound gives $m\le C{n}^{1/3}$. Hence any interval centred at $m$ with length $\omega (n)n^{1/6}$, where $\omega (n)\to \infty$, contains $L_n$ with high probability. No upper restriction on the growth of $\omega$ is required.

A vertex of a convex polytope is an extreme point: it cannot be expressed as a nontrivial convex combination of two distinct points in that polytope. In a full-dimensional simple polytope of dimension $n$, a vertex lies on exactly $n$ incident facets.

A facet of a full-dimensional convex polytope in ${\mathbb{R}}^n$ is a face of dimension $n-1$. Each irredundant supporting closed half-space defines one facet.

If $r\ge \sqrt{2}$ and a convex polytope satisfies $r^{-1}{B}^n\subseteq P\subseteq B^n$, then it has at least $(1-r^{-2}{)}^{-n/2}\ge e^{n/(2r^2)}$ facets. Its outward facet normals define spherical caps covering the unit sphere; the spherical cap area upper bound supplies the estimate.

The convex hull of the positive and negative coordinate unit vectors. Its boundary triangulates a sphere, and each face contains at most one member of each antipodal pair of coordinate unit vectors. This makes its barycentric subdivision useful for triangulating Real projective space.

An extreme point of a convex set is a point that cannot be made by genuinely mixing two different points of the set. For a convex set $C$ in a real vector space, the condition on $p\in C$ isThus $p$ lies on no open line segment between two distinct points of $C$. It is enough to exclude midpoint representations: if $p$ lies inside a line segment, two nearby points on opposite sides have midpoint $p$.^[ref]

The square $[-1,1{]}^2$ has just four extreme points, at $(\pm 1,\pm 1)$. In a convex combination giving a corner, each coordinate is already at its largest or smallest allowed value, forcing both input points to agree with that corner. In contrast, the boundary point $(1,0)$ is not extreme:It is the midpoint of two other points on the same edge. An interior point also admits a small line segment through it.

The unit disk $D=\{z\in {\mathbb{R}}^2:\Vert z{\Vert }_2\le 1\}$ has a different shape: every point on its unit circle is extreme. For a unit vector $p$, the Cauchy-Schwarz inequality givesand equality is possible only at $z=p$. If a convex combination equals $p$, applying this linear functional forces both ingredients to attain that equality. Both must therefore be $p$. Extremality need not look like a sharp corner.

These points help describe all allowable mixtures. Every $(x,y)\in [-1,1{]}^2$ is a convex combination of its four corners, with the weight on $(a,b)\in \{-1,1{\}}^2$ equal to $(1+ax)(1+by)/4$. For the unit disk, write $z=rp$, with $0\le r\le 1$ and $p$ a unit vector; at zero choose any $p$. ThenTwo extreme points suffice for that mixture. The Krein-Milman theorem gives a much broader reconstruction: a nonempty compact convex set in a locally convex space whose topology is Hausdorff is the closed convex hull of its extreme points.

Mark Krein and David Milman published their reconstruction theorem in 1940. Milman's colleagues describe that result and its subsequent use as a method of representing convex sets through their extreme points.^[ref]

An exposed point is a point uniquely selected by maximizing a linear functional. In ${\mathbb{R}}^d$, a point $p$ of a convex set $C$ is exposed if some vector $c$ satisfiesGeometrically, a supporting hyperplane touches the convex set only at $p$. Every exposed point is an extreme point: a convex combination that attains the maximum can put positive weight only on maximizers, and there is only one.^[ref]

The unit disk calculation in extreme point exposes every point of the unit circle. For a corner $(a,b)$ of the square, $c=(a,b)$ exposes it: $ax+by$ attains two only at $(a,b)$. However, maximizing $x$ exposes no single point on the right edge, since all of them have the same objective value. A linear functional may have several optimal points, even when some of them are extreme.

The distinction appears at a smooth join between a straight segment and a curved boundary. Consider the convex hullThe upper tangent from $P$ meets the unit circle at $T=(1/2,\sqrt{3}/2)$. The supporting line isEvery point of the unit disk has $T\cdot z\le 1$, with equality only at $T$. Hence the convex face of $C$ where equality holds is exactly the line segment $TP$.

The point $T$ is extreme. If a nontrivial convex combination of two points of $C$ equals $T$, both must belong to the convex face $TP$. Since $T$ is an endpoint of that line segment, both must equal $T$.

Yet $T$ is not exposed. A nonzero linear functional maximizing at $T$ on $C$ must also maximize there on the included unit disk. Its vector must be a positive multiple of $T$, by the equality condition in the Cauchy-Schwarz inequality. It then gives $P$ the same value as $T$. No linear functional can select $T$ alone. Being an extreme point is a property of possible mixtures; being an exposed point adds the ability to distinguish it by one linear objective.

For the real l-infinity sequence space, every coordinate of an extreme point must be an endpoint of $[-1,1]$; any slack coordinate permits opposite perturbations. For the real absolutely summable sequence space, a unit vector with two nonzero coordinates permits a transfer of mass between them, so only signed coordinate vectors are extreme. For the real l2 sequence space, the parallelogram law makes every unit vector extreme. In all three cases interior points of the unit ball are nonextreme.

For compact Hausdorff $K$, the extreme points of the real unit ball in the space of continuous functions on a compact space are precisely its continuous sign-valued functions. A point with $|f|<1$ permits a nonzero continuous bump perturbation supported where there is uniform slack, while pointwise equality at an endpoint of $[-1,1]$ forces both functions in a midpoint decomposition to agree. For the Cantor set, clopen indicators give the perturbations directly.

Every real continuous function of supremum norm at most one on the Cantor set is a uniform limit of convex combinations of continuous sign functions. Approximate on a finite Cantor cylinder partition by values $a_j\in [-1,1]$. The sign vector $s$ has weight ${\prod }_j(1+s_j{a}_j)/2$, whose coordinate means are $a_j$. This proves a closed convex hull identity without weak compactness.

For real scalars the extremes are the almost-everywhere sign-valued functions. A positive-measure region uniformly inside $[-1,1]$ permits opposite nontrivial bounded perturbations, proving necessity. Equality at either endpoint forces both members of a convex decomposition to agree, proving sufficiency. For complex scalars the same criterion uses unit-modulus functions and the strict convexity of the complex unit disk.

Projections onto convex sets is an iterative feasibility method that successively applies a Euclidean projection onto a convex set to each closed convex constraint set. With two sets it uses $x_{n+1}=P_D(P_C(x_n))$. It seeks a point in the intersection; a single projection onto one set is a different operation, and the method does not generally compute the closest intersection point to the initial iterate.

For a nonempty closed convex subset $C$ of a finite-dimensional inner-product space, ${\Pi }_C(x)$ is the unique point of $C$ minimizing $\Vert x-z\Vert$.

This closest-point map is the metric projection onto a closed convex set. Repeated projections onto several sets form the separate projections onto convex sets method.

For $p\in C$,

The metric projection onto a nonempty closed convex set in a Hilbert space is nonexpansive:

For $C=\{x:0\le x\le 1,a^{T}x=b\}$, the projection of $y$ has coordinates $x_i=\min (1,\max (0,y_i-\nu a_i))$, where the scalar multiplier $\nu$ is chosen so that $a^{T}x=b$. Thus the projection reduces to a continuous one-dimensional root-finding problem.

The support function of a nonempty set $C$ is ${\sigma }_C(x)={\sup }_{v\in C}⟨x,v⟩$. It is convex and positively homogeneous, and for a closed convex set its convex conjugate is the indicator function of $C$.

For a nonempty closed convex set $C$, the finite-valued support function has subgradients exactly at the maximizing points of $C$. This follows from Fenchel–Young inequality and the conjugacy between the support function and the indicator functional of a constraint set. For compact $C$, the exposed maximizing set is nonempty.

If $x\notin \mathrm{range}{P}^T=(\ker P{)}^{\perp }$, the support function is infinite along a kernel line. Otherwise linear programming duality gives the displayed minimum, attained because the corresponding linear programs are feasible with finite values. Splitting $q=\alpha -\beta$ into nonnegative parts yields the equivalent minimum of $1^T(\alpha +\beta )$. Thus worst-case revenue over a polyhedral uncertainty set is $r_0^{T}x-{\sigma }_C(x)$, with value $-\infty$ off the row space.

The sum of the $k$ largest components of $x\in {\mathbb{R}}^n$ is the support function of the capped simplex: ${\sum }_{i=1}^k{x}_{[i]}=\max \{x^{T}v:0\le v\le 1,{\sum }_i{v}_i=k\}$.

For $1\le k\le n$, linear programming duality giveswhere $(\cdot {)}_{+}$ is the positive part of a real-valued function. To see equality directly, order the coordinates $x_{[1]}\ge \cdots \ge x_{[n]}$ and choose $x_{[k+1]}\le t\le x_{[k]}$ for $k<n$, or $t\le x_{[n]}$ for $k=n$. The threshold expression then equals the sum of the largest components. Introducing the variables $s_i$ turns this convex piecewise-linear objective into a linear program.

For a real symmetric matrix $X$ with eigenvalues ${\lambda }_1\ge \cdots \ge {\lambda }_n$, the sum of its $k$ largest eigenvalues is the support function of the fantope:Here $⪯$ is the Loewner order. In an orthonormal eigenbasis for $X$, the objective depends only on the diagonal entries of $Y$, which lie in the capped simplex. Thus the identity reduces to the sum of the largest components of the eigenvalues.

For a real symmetric matrix $X$ and $1\le k\le n$,Indeed $Y=Q{Q}^T$ is a rank-$k$ orthogonal projection matrix in the fantope, and projecting onto the eigenvectors of the largest eigenvalues attains the support function maximum. Equivalently, the largest matrix trace of a compression to a $k$-dimensional vector subspace is the sum of the largest eigenvalues.

For a finite-dimensional Hermitian operator $A$ with decreasing eigenvalues ${\lambda }_j$ and integer $0\le r\le d$, maximizing $\mathrm{Tr}(AB)$ over positive contractions $B$ with trace $r$ gives the sum of its leading $r$ eigenvalues. In an orthonormal eigenbasis, the diagonal entries of $B$ lie in $[0,1]$ and sum to $r$. Moving their weight to the largest eigenvalues can only increase the objective. An orthogonal projection onto their eigenvectors attains the maximum.

The sum of the largest eigenvalues has the semidefinite program representationFor every feasible $Y$ in the fantope, positive semidefinite trace nonnegativity gives $\mathrm{tr}(XY)\le kt+\mathrm{tr}S$. To attain equality, use an orthonormal eigenbasis of $X$ and choose $S=\mathrm{diag}(({\lambda }_i-t{)}_{+})$ in that basis, with the same threshold choice as in the threshold formula for the sum of the largest components. This argument also covers $k=n$, without requiring strict feasibility of the maximization program.

For an integer $0\le k\le n$, the capped simplexis the convex hull of the zero-one vectors having exactly $k$ entries equal to one. It is a convex polytope whose extreme points are precisely these vectors.

If a feasible vector has a fractional coordinate, the integer coordinate sum forces at least two fractional coordinates. Perturbing one upward and the other downward by a sufficiently small amount gives two distinct feasible vectors whose midpoint is the original vector. It is therefore not an extreme point. Conversely, a zero-one vector cannot be a nontrivial convex combination of points of $[0,1{]}^n$, since each coordinate is already at a bound.

The second-order cone, also called the Lorentz cone, is

For $(u,s),(v,t)$ in the second-order cone, the Cauchy-Schwarz inequality gives $u\cdot v+st\ge -\Vert u\Vert \Vert v\Vert +st\ge 0$. Thus the cone is contained in its dual cone. Conversely, if $s<\Vert u\Vert$ and $u\ne 0$, pairing $(u,s)$ with $(-u/\Vert u\Vert ,1)$ is negative. If $u=0$ and $s<0$, use $(0,1)$. Every point outside the cone therefore lies outside its dual, proving that it is a self-dual cone.

A second-order cone program has a linear objective and affine constraints taking values in products of second-order cones and nonnegative orthants. Norm epigraphs have the form $(t,z)\in \mathcal{Q}$; quadratic epigraphs admit the affine lift $((q+1)/2,(q-1)/2,a)\in {\mathcal{Q}}_3$, equivalent to $q\ge a^2$. Product-cone self-concordant barriers give interior-point methods.

The objective $\Vert u-g{\Vert }_2+\lambda {\sum }_i((Gu{)}_i{)}_{+}^2$ has the exact lift $\min t+\lambda {\sum }_i{q}_i$ with $(t,u-g)\in {\mathcal{Q}}_{n+1}$, $((q_i+1)/2,(q_i-1)/2,a_i)\in {\mathcal{Q}}_3$, $a_i\ge 0$ and $a_i\ge (Gu{)}_i$. Every lifted feasible value bounds the original objective, and choosing tight epigraph variables proves equality. The product-cone barrier parameter is $4n+2$: two for each Lorentz block and one for each orthant slack. The fidelity norm remains unsquared, and negative derivatives remain unpenalized.

For $x=(u,t)$ and $\rho =\Vert u{\Vert }_2$,

The convex hull of a set consists of every finite convex combination of its points. It collects all choices obtainable by mixing the original choices with nonnegative weights summing to one. For $S$ in a real vector space,Equivalently this is the smallest convex set containing $S$. Mixing two already mixed points produces another finite convex combination, so the displayed set is convex; every convex set containing $S$ must contain all these mixtures.^[ref]

In an original planar example, take four points $A=(0,0)$, $B=(4,0)$, $C=(3,3)$, $D=(0,2)$ and four additional samples $(1,1)$, $(2,1.7)$, $(3,0.5)$, $(1,0.5)$. Their convex hull is the filled convex polygon $ABCD$, including its boundary. None of the samples is $p=(2,1)$, butThe coefficients are nonnegative and sum to one, providing an explicit membership certificate. Geometrically, first form $U=(3/2,0)=\frac{5}{8}A+\frac{3}{8}B$ on the line segment $AB$, then mix $p=\frac{2}{3}U+\frac{1}{3}C$. The additional interior samples do not enlarge the convex hull.

For a finite nonempty $S\subset {\mathbb{R}}^d$, the convex hull is the image of a probability simplex of weights under the linear map $\lambda \mapsto {\sum }_i{\lambda }_i{s}_i$. The probability simplex is a compact set, and the map is continuous, so this convex hull is compact and closed. A one-point input stays one point; a collinear input stays in a line segment. Filling the convex hull does not necessarily produce a full-dimensional region.

The construction is useful whenever mixtures preserve the intended meaning of a choice. Mixing resource-allocation vectors, for example, interpolates their coordinate requirements. The convex hull describes the resulting feasible region. A coordinate-wise box can admit combinations that no mixture produces, as the outside-point certificate in linear optimization on a convex hull shows.

Start from a nondegenerate tetrahedron and insert remaining points one at a time. Discard a point inside the current convex polyhedron; otherwise replace faces visible from it by the cone from that point to the horizon of a convex polyhedron. Scanning every current face gives $O(n^2)$ worst-case time complexity and $O(n)$ current-hull storage in three dimensions. Coplanar input requires a separate degeneracy policy.

Every set of at least $d+2$ points in ${\mathbb{R}}^d$ can be partitioned into two nonempty parts with intersecting convex hulls. To see this, take a nonzero affine dependence on $d+2$ of its points. Its positive and negative coefficient sums have the same magnitude $L>0$. Dividing by $L$ expresses one point as a convex combination of the positive-coefficient points and also as a convex combination of the negative-coefficient points. Distribute zero-coefficient and remaining points arbitrarily between the parts. This theorem obstructs arbitrary labels for affine linear classifiers.

In a Banach space, the closed convex hull of a compact set is compact in the norm topology. Given $\epsilon >0$, choose a finite $\epsilon$-net $\{y_i\}$ for $K$. Every convex combination of points of $K$ is within $\epsilon$ in norm of $\mathrm{conv}\{y_i\}$, by replacing its terms by their approximating $y_i$. This finite-dimensional compact convex set has a finite $\epsilon$-net, giving a finite $2\epsilon$-net for $\mathrm{conv}K$. Its closure is therefore totally bounded and complete, hence compact. Completeness of the ambient space is used at this last step.

The lower boundary of the convex hull of points in the plane: the portion visible from points sufficiently far in the negative vertical direction. Sorting its vertices by horizontal coordinate gives a chain with nondecreasing edge slopes; collinear interior vertices can be omitted.

A linear functional cannot exceed its best original value by mixing. For a finite nonempty set $S$ and $x={\sum }_i{\lambda }_i{s}_i$ in its convex hull,Every original point is itself in the convex hull, so equality between the two maxima follows. Moreover, a mixture attains the maximum exactly when all its positive weights are assigned to maximizing original points. Multiple maximizers can therefore produce a whole line segment or a higher-dimensional region of equally good choices.

For the eight samples above, use the linear functional $f(x,y)=x+y$. Its largest sample value is $f(C)=6$, and $C$ is the only maximizing sample. Thus the unique maximum over the whole convex polygon is also at $C$. The line $x+y=6$ is a supporting line: every point of the convex hull lies in the half-space $x+y\le 6$, and $C$ touches its boundary.

The point $q=(3.8,2.5)$ passes the coordinate-wise bounds $0\le x\le 4$, $0\le y\le 3$, but $f(q)=6.3>6$. This single inequality certifies that $q$ is outside the convex hull. A weighted mixture could not have a larger linear functional value than all its ingredients.

This explains a basic feature of linear programming: searching all mixtures of finitely many candidate vectors cannot improve the objective beyond the best candidate, though mixing equally good candidates can give more optimal choices. The conclusion depends on linearity. For the concave function $g(x,y)=-(x-2{)}^2-(y-1{)}^2$, the new point $p=(2,1)$ instead attains zero, strictly above its value at every original sample. A nonlinear objective can favor a mixture.

The smallest closed convex set containing a set $C$, equivalently the closure of its convex hull in the specified topology. The topology must be stated: the norm topology, weak topology and weak-star topology need not give the same closure for an arbitrary set.

Even a bounded infinite input need not have a closed convex hull. In the real line, let $S=\{1/n:n\ge 1\}$. Every finite convex combination of these positive points is positive, so zero is absent. Conversely, any $x\in (0,1]$ lies between some $1/n$ and $1$, and is their convex combination. HenceThe closed convex hull adds the missing limit point zero. For the finite eight-point example in convex hull, the convex hull is already closed, so taking the closed convex hull adds nothing.

Every point in the convex hull of a subset of ${\mathbb{R}}^d$ is a convex combination of at most $d+1$ points of that subset. Thus in the plane three ingredients always suffice, however many samples were supplied. The representation of $p=(2,1)$ in convex hull illustrates this bound. Two ingredients need not suffice: the centroid of a triangle with only its three vertices as input is on none of their three pairwise line segments.