Affine linear classifier 2026-10-31
An affine linear classifier assigns binary labels according to the sign of an affine function. Its boundary is an affine hyperplane, and its positive region is a closed half-space under the displayed convention. On the full class has VC dimension : arbitrary signs interpolate on affinely independent points, while the intersecting convex hull partition theorem prevents shattering any points. Requiring gives the homogeneous case and a different VC dimension.
For a proper extended-real function with an affine minorant, biconjugate gives its greatest lower-semicontinuous convex minorant. Geometric separation of its epigraph turns containing closed half-spaces into affine lower bounds. Vertical half-spaces are recovered by adding multiples of a domain-separating inequality to one fixed affine minorant.
Consider a stipulated continuous-allocation problem. Amounts of two activities use units of a common resource, with budget six. The feasible region
is a triangle with extreme points , and . 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 and . Their resource totals are and . Every convex combination is nonnegative and has resource total
In particular the midpoint is , using units. This verifies the full line segment, rather than just a plotted sample of it.
Figure 1.
Feasible averages and convex weights in a continuous resource budget
. Original continuous-allocation model , , . The orange line segment joins two feasible allocations; the green point is the equal-weight convex combination of the three extreme points. The shaded region is their convex hull, not just the three generating points. Details.
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.
Convex geometry Created 2026-10-06 Updated 2026-10-13
The study of convex sets, their convex hulls, supporting closed half-spaces, and inequalities for their sizes.
Facet Created 2026-10-06 Updated 2026-10-07
A facet of a full-dimensional convex polytope in is a face of dimension . Each irredundant supporting closed half-space defines one facet.
Feasible triangle with a squared-distance objective Created 2026-10-14 Updated 2026-10-31
Take the decision domain and minimize the objective function
Each inequality permits a closed half-space; their intersection is the filled triangle with vertices , and , including its edges. The feasible region is a compact set and a convex set. The point is a feasible point, but its objective function value will not be best. Without the optimization constraints, the unique global minimum is at with value . That point is infeasible because .
The objective function is the squared Euclidean distance from . Its positive level sets are circles centered there. Expanding a circle from that center, the first contact with the feasible region is at , with objective function value . Thus the optimum is the Euclidean projection onto a convex set of the target . Squaring a nonnegative Euclidean distance preserves which point is nearest.[ref]
Here is a direct certificate, without relying on the picture. Put and . The objective function becomes
Equality requires and , so the unique optimum is . At this point is an active constraint, while and are strict. An active constraint identifies a tight restriction at a specified point; it alone does not establish optimality. For example, has the same tight sum restriction but objective function value .
For a check using the Karush-Kuhn-Tucker conditions, write the inequalities as , , . Their Lagrange multipliers at the optimum are . The gradient equation is
Feasibility, nonnegative Lagrange multipliers and complementary slackness also hold. With this strictly convex function and affine optimization constraints, the Karush-Kuhn-Tucker conditions certify the unique global minimum.[ref]
Halfspace depth 2026-11-05
The halfspace depth of for a probability measure is the least mass of any closed half-space containing :
For an empirical distribution, it is the smallest fraction of observations in such a closed half-space. The boundary is included, so observations exactly on it count.
In one dimension,
For observations , the depth at is , and the depth at either endpoint is . Atoms can therefore give depth greater than . An invertible affine map preserves halfspace depth, because it carries the family of closed half-spaces bijectively to itself and preserves their associated probabilities. A Tukey median maximizes this depth; the maximizing point need not be unique.
Half-space representation of a closed convex set Created 2026-10-06 Updated 2026-10-14
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.
Expanding the squared Euclidean norm gives
In lifted coordinates , this is the closed half-space
Every labelling of the original points obtainable by a Euclidean ball is therefore obtainable on their lifted images by an affine linear classifier. The feature map is injective, since it preserves the first coordinates; distinct original points remain distinct. If the original points are shattered, every labelling of the lifted points is realized, as required.
Here “linear separator” means a separator with an intercept, namely an affine hyperplane. If a convention demands strict separation on the finite sample, increase the constant term of the positive score by a sufficiently small positive amount. Positive points then have strictly positive score, and the finitely many negative scores remain strictly negative. A homogeneous separator can alternatively be obtained after adjoining one more constant coordinate; this distinction matters for dimension counts.
Let be the family of closed half-spaces containing . Certainly . To prove the reverse inclusion, exclude an arbitrary .
Suppose first that is nonempty. Its Euclidean projection onto a convex set exists: minimizing the continuous squared distance may be restricted to a sufficiently large closed ball, whose intersection with the closed set is compact. Put . For every , convexity puts in for . Minimality of gives
Thus the closed half-space
contains , while excludes . Since every point outside is excluded by some member of ,
This is the half-space representation of a closed convex set. If , every point can again be excluded by a containing half-space, so the intersection is empty. If , no proper half-space contains it and the empty intersection is, by convention, .
If , the family of proper containing half-spaces is empty and its intersection is, by convention, . If , every closed half-space contains it and their intersection is empty. Now suppose is a nonempty proper closed convex set. Take and let be its Euclidean projection onto a convex set. This projection exists: a minimizing sequence can be restricted to a bounded ball, and closedness gives attainment. It is unique by convexity and strict convexity of squared distance.
For , the segment remains in for . Minimality at implies
Thus the closed half-space contains but excludes , since . Every point outside is excluded by at least one containing half-space. The reverse inclusion is immediate, giving
This is the half-space representation of a closed convex set. The argument gives an explicit separating hyperplane rather than just citing a Hahn-Banach separation theorem.
Let be the number of facets of the convex polytope . Its facet description can be written
Because , each supporting closed half-space has . For any , follow the ray to its last point in . Its radius is at most one because . At least one facet is active there, giving
Thus the unit sphere is covered by the spherical caps centred at with angular radius . Since , this radius lies in and the spherical cap area upper bound applies. Subadditivity of surface area gives
Using for ,
The facet lower bound for ball approximations is exponential in the dimension.
Choose a maximal subset whose distinct points have Euclidean distance greater than one. The volumetric bound for Euclidean metric nets makes the construction finite: the open Euclidean balls of radius about the points of are disjoint and all lie in , so
Maximality means that is a metric net of radius one on the unit sphere. Thus every has some with . Since both are unit vectors,
Now intersect the corresponding closed half-spaces:
The Cauchy-Schwarz inequality shows that . Conversely, write any nonzero as and choose as above. Then , so . Hence , which also proves boundedness. This convex polytope has at most facets, since redundant inequalities can only reduce their number. It meets the required inclusions with .
For each fixed in the nonnegative orthant, the map is a continuous linear function on the vector space of real symmetric matrices. Thus
is an intersection of closed half-spaces, using the Frobenius inner product on this space. Arbitrary intersections of closed sets are closed, so is closed.
If and , then for every . Therefore , including the zero matrix when . Hence
The copositive cone is defined in the real space of symmetric matrices; symmetry is needed later to recover every matrix entry from these quadratic forms.
The origin belongs to , so is nonempty. Each displayed inequality defines a closed half-space, and every half-space is a convex set. An intersection of convex sets is convex: if and , each linear inequality remains valid for . Thus is a nonempty convex polytope.
Write . The core of a cooperative game is
Take any and , and form the convex combination . Its total payoff is . For every coalition ,
Hence remains in the core. The core is a convex set, even when the transferable utility game is not a convex cooperative game. An empty core is a convex set vacuously; the argument does not claim nonemptiness. Geometrically, the same conclusion follows because the constraints intersect an affine hyperplane with closed half-spaces.
Tukey median Created 2026-09-24 Updated 2026-11-05
A Tukey median maximizes halfspace depth. For a probability measure on , the depth of a point is
For a sample, is replaced by its empirical distribution, so is the fraction of observations in the closed half-space . Every direction is considered; choosing a single coordinate direction would give a different procedure.
In one dimension, the depth is the smaller of the masses in the closed rays to the left and right of . For the sample , point has depth , while has depth . The maximizing point is the sample median. In higher dimensions this gives a geometric extension of a central location that depends on how many observations lie on each side, rather than on their squared distances. Maximizers need not be unique, so a single-valued estimator needs a selection rule.