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.
Biconjugation as closed convexification 2026-10-07
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.
Convex feasible region for a resource budget 2026-10-14
Consider a stipulated continuous-allocation problem. Amounts of two activities use units of a common resource, with budget six. The feasible regionis 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]
Convex Optimization by Stephen Boyd and Lieven Vandenberghe. §2.2.1, p. 27: half-spaces; §2.3.1, p. 36: intersections preserve convexity
For an original numerical check, take and . Their resource totals are and . Every convex combination is nonnegative and has resource totalIn particular the midpoint is , using 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.
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 functionEach 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]
Convex Optimization by Stephen Boyd and Lieven Vandenberghe. §8.1.1, printed p. 398: squared Euclidean projection onto a polyhedron and half-space projection formula
Feasible triangle with a squared-distance objective: the first attainable level set has value 0.5 at (1.5,1.5)
. Details. Here is a direct certificate, without relying on the picture. Put and . The objective function becomesEquality 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 isFeasibility, 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]
Convex Optimization by Stephen Boyd and Lieven Vandenberghe. §5.5.3, printed pp. 243–244, equation (5.49) and sufficiency for convex problems
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 givesIn lifted coordinates , this is the closed half-spaceEvery 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.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 62 1 a Solution Created 2026-10-03 Updated 2026-10-07
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 givesThus the closed half-spacecontains , 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, .
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 65 1 a Solution Created 2026-10-03 Updated 2026-10-06
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 impliesThus 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, givingThis 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.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 112 2 iii Solution Created 2026-10-03 Updated 2026-10-06
Let be the number of facets of the convex polytope . Its facet description can be writtenBecause , 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, givingThus 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 givesUsing for ,The facet lower bound for ball approximations is exponential in the dimension.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 112 2 iv Solution Created 2026-10-03 Updated 2026-10-06
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 , soMaximality 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 .
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 339 1 c Solution Created 2026-10-03 Updated 2026-10-06
For each fixed in the nonnegative orthant, the map is a continuous linear function on the vector space of real symmetric matrices. Thusis 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 . HenceThe copositive cone is defined in the real space of symmetric matrices; symmetry is needed later to recover every matrix entry from these quadratic forms.
Past exam of the mathematics course of the University of Cambridge 2023 ib Paper 3 19H a Solution Created 2026-09-24 Updated 2026-09-25
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 isTake 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 isFor 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.

