Affine maps preserve affine combinations Created 2026-10-14 Updated 2026-10-31
For coefficients with sum one, the defining identity follows from linearity:The translation appears once on both sides precisely because . In particular, midpoints map to midpoints, and a parameterized line segment , , maps to . A whole line has the same formula with ; its image is a line if , and a single point otherwise.
Arc (topology) Created 2026-10-25 Updated 2026-11-05
An arc is a space homeomorphic to , or a subset with that property. A continuous injective map from into a Hausdorff space is a homeomorphism onto its image because its domain is compact. A line segment and a semicircle are arcs; a full circle is not. A continuous path may retrace points or cross itself, so its image need not be an arc.
Bresenham's line algorithm Created 2026-10-31 Updated 2026-11-05
Jack Bresenham's raster graphics algorithm selects a thin sequence of pixels to represent a line segment by exact incremental integer arithmetic. For a first-octant segment with , a scaled midpoint line decision chooses between the next same-row and next higher-row pixels.
Brouwer fixed-point theorem Created 2026-09-24 Updated 2026-10-14
The Brouwer fixed-point theorem says that every continuous map has a fixed point when is a nonempty compact set and a convex set in a finite-dimensional vector space over the real numbers. Equivalently, take for a finite , with the usual Euclidean space structure: there is some such that . The conclusion guarantees at least one fixed point, without asserting uniqueness or telling us how quickly to find one. [ref]
https://courses.csail.mit.edu/6.5440/fall23/lectures/L23_images.pdf. MIT lecture slides on Brouwer's theorem
The standard pictures are a closed ball, including a closed unit ball, and a simplex. A filled disk qualifies; its bounding circle alone does not. A probability simplex also qualifies even though its dimension is smaller than that of its ambient Euclidean space. The hypotheses have concrete meanings: being a convex set keeps every line segment between allowed points inside , and compactness prevents escape or loss of a limiting point. In Euclidean space, the Heine-Borel theorem identifies compact sets with closed sets that are bounded sets. Crucially, every output must belong to the same as the input.
For a fully computable example, let be the filled unit disk. Apply a counterclockwise quarter-turn rotation, shrink by , and add a translation:This affine map is a continuous map. Because the rotation preserves the Euclidean norm, the triangle inequality gives, for every ,Thus the whole image lies strictly inside . More precisely, it is a disk of radius centred at . This containment check is what makes the Brouwer fixed-point theorem applicable; a formula being a continuous map by itself would not suffice.
The fixed point can now be found by a system of linear equations:Indeed, substitution gives . Its Euclidean norm is , safely inside . The figure shows arrows from sample inputs to their outputs; an arrow disappears at the fixed point because the displacement vanishes there.
Repeated iterations of a map happen to succeed for this example. Starting at and setting gives , , and . Subtracting the fixed point equation yields , so the Euclidean distance to shrinks by exactly each step. This extra fact follows from the contraction mapping property and the Banach fixed-point theorem. It is additional information beyond the Brouwer fixed-point theorem.
The distinction becomes visible with two simpler continuous maps of the same disk. The pure rotation has exactly one fixed point, , since and force both to vanish. Yet iterations of a map starting at here cycle through , , and forever. Their Euclidean distance from stays one, so there is no convergence in a metric space. The reflection has an entire line segment of fixed points, namely . Starting off that line segment produces an alternating pair. Existence, uniqueness, and convergence of iterations of a map are separate questions.
Removing hypotheses changes the answer. Restrict the same quarter-turn rotation to the circle . It remains a continuous map into that compact set, but its only possible fixed point, , has been removed. The circle is not a convex set. Conversely, on the unbounded convex set , the translation has no fixed point; on the open interval , also has none. Neither domain is a compact set. The finite-dimensional closed ball statement should likewise not be extended to arbitrary infinite-dimensional vector spaces, where a closed ball need not be a compact set.
The one-dimensional version explains the connection to the intermediate value theorem. For a continuous map , put . Then and , so the intermediate value theorem gives for some . In higher dimensions, the Brouwer fixed-point theorem supplies a corresponding existence principle when this scalar sign argument is unavailable. Its practical value is ensuring that a proposed equation has a solution once a suitable domain is found; it supplies no general promise of a fast algorithm.
A useful application is positive matrix eigenvector from simplex normalization: rescale the output of a strictly positive matrix to make its entries sum to one. For example, takeOn this probability simplex, has entry sum , so the normalized continuous map is . Both entries are positive and sum to one, keeping the image inside the probability simplex. Its fixed point equation is , hence . Consequently satisfies : a strictly positive eigenvector with eigenvalue . In larger dimensions, the Brouwer fixed-point theorem guarantees the corresponding positive eigenvector without requiring us to solve a system of linear equations in advance. The fixed point expresses preservation of relative weights, rather than preservation of their unnormalized size.
Proofs can be approached through the no-retraction theorem or Sperner's lemma. In the latter approach, increasingly fine triangulations locate approximate fixed points; compactness supplies a convergent subsequence, and continuous maps turn its limit into an exact fixed point. [ref]
https://www.mit.edu/~6.7980/brouwer.html. Daskalakis and Farina, Brouwer and Sperner
A primary historical reference is L. E. J. Brouwer's 1911 paper Über Abbildung von Mannigfaltigkeiten, whose digitized original is hosted by Zenodo under DOI 10.1007/BF01456812. This gives a direct route to the early literature behind the Brouwer fixed-point theorem. [ref]
https://zenodo.org/records/1428286. Brouwer, Über Abbildung von Mannigfaltigkeiten, 1911
Carathéodory's theorem (convex hull) Created 2026-10-14 Updated 2026-10-18
Every point in the convex hull of a subset of is a convex combination of at most points of that subset. Thus in the plane three ingredients always suffice, however many samples were supplied. The representation of 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.
A short proof outline removes redundant ingredients. With more than points, the augmented vectors are linearly dependent. A dependence lets the weights vary while preserving both their sum and the represented point. Move along it until one positive weight first becomes zero; all weights stay nonnegative. Repeating leaves at most positive weights.
In his 1911 paper, Constantin Carathéodory used convex geometry to investigate the possible Fourier coefficients of positive harmonic functions. Its introduction interprets convex mixtures through the center of mass, connecting finite-dimensional geometry to constraints on a function's coefficients.[ref]
Über den Variabilitätsbereich der Fourier’schen Konstanten von positiven harmonischen Funktionen by Constantin Carathéodory. English translation by Nicholas J. Williams, Introduction §4, original printed p. 195; §I concerns the smallest containing convex domain
Chaikin subdivision 2026-10-14
Chaikin subdivision generates a rounded subdivision curve by repeatedly cutting the corners off a control polygon. Each edge contributes two new control points, one a quarter of the way along the edge and the other three quarters of the way along it. Connecting these new control points in edge order replaces the old corners by shorter line segments. This makes Chaikin subdivision a useful way to draw a smooth outline from a small, editable set of control points, without evaluating B-spline basis functions at each drawing step. Joy presents both the corner-cutting rule and its closed version.[ref]
https://www.cs.unc.edu/~dm/UNC/COMP258/LECTURES/Chaikins-Algorithm.pdf. Kenneth I. Joy, Chaikin's Algorithms for Curves, §§Chaikin's Method and Example — A Closed Curve, UC Davis authored notes
For a closed control polygon with control points , set and interpret indices cyclically. One refinement givesand the new control polygon is the ordered sequenceClose it by joining back to . Use the old control points for every average in the same refinement; updating them in place would define a different algorithm. One refinement produces stored control points, and refinements produce , counting entries even if some coordinates coincide. Open control polygons need an explicit endpoint convention: applying only the interior edge rule discards the original endpoints, whereas retaining endpoints changes the boundary rule. The closed analysis below uses cyclic indices throughout.
For a worked example, start with the rectangular control polygonThe first edge gives and . Applying Chaikin subdivision to all four edges, including the closing edge, gives exactly eight control points in this order:Thus the rectangle becomes an octagonal control polygon. Two refinements have control points, and five have . The illustration shows finite control polygons at stages ; the last is already visually rounded but still consists of line segments.
The convex hull property follows directly from the weights. Each new control point is a convex combination of the endpoints of one old edge, because the weights are nonnegative and sum to one. Consequently, if is the convex hull of the stage- control points, then . Every later line segment, and every limit point, stays in the original convex hull. This gives a useful geometric enclosure. It also explains why Chaikin subdivision is approximating rather than an interpolation rule: the rectangle's four original corners are outside the first octagon's convex hull, so the limiting curve cannot pass through them. A refinement control polygon generally lies off the limiting curve as well.
For the cyclic uniform rule, the closed limit is the periodic quadratic uniform B-spline curve determined by the original control points. Uniform refers to equal spacing in the spline knot sequence, not equal physical lengths of edges of the control polygon. An infinite uniform control sequence has the corresponding local description; arbitrary open endpoint conventions need separate treatment. Joy derives the quarter-point refinement by splitting quadratic uniform B-spline spans.[ref]
https://www.cs.unc.edu/~dm/UNC/COMP258/LECTURES/Quadratic-B-Spline-Curve-Refinement.pdf. Kenneth I. Joy, Quadratic Uniform B-Spline Curve Refinement, §§Splitting and Refinement and The General Refinement Procedure, UC Davis authored notes
Here is an explicit description of that closed limit, with cyclic indices and a unit parameter span for each original control point:Each coordinate is a quadratic polynomial, and the three coefficients form a nonnegative partition of unity. The span runs from to . Differentiating gives and , so adjacent spans have matching values and matching first derivatives. Their second derivatives generally differ. Thus the parameterized curve is , generally not ; degenerate control points can still make its tangent vector vanish. For the rectangle, the span around iswhich rounds the original corner between edge midpoints and . For equally spaced abscissae, the centered Chaikin basis function gives the scalar graph version of this quadratic B-spline representation and has support of width three original grid intervals.
Another useful property is affine equivariance of a geometric basis: refining and applying an affine map commute. For ,and the same calculation holds for . The sum-to-one weights account for the translation. Therefore at every refinement, and also for the limit. A designer can apply a shear mapping, translation, or other affine map to the original control polygon and obtain exactly the transformed outline.
For example, compose the shear mapping with the translation to obtain . The rectangle's control points become . On its right edge, cutting first gives and then . Transforming first and cutting instead gives , the same control point.
Shearing and translating a control polygon commutes with one Chaikin refinement
. Left: the rectangle and its first refinement. Right: the transformed control polygon, with blue dots from cutting after the affine map and orange rings from applying the affine map after cutting. All eight pairs coincide. Details.Historically, George M. Chaikin published “An algorithm for high-speed curve generation” in Computer Graphics and Image Processing 3(4), December 1974, pages 346–349. Its emphasis was practical curve generation through a recursive algorithm using simple arithmetic, with applications including machine control and three-dimensional curves. The lasting appeal of Chaikin subdivision is how an elementary local average creates an entire smooth B-spline curve.[ref]
https://doi.org/10.1016/0146-664X(74)90028-8. G. M. Chaikin, An algorithm for high-speed curve generation, Computer Graphics and Image Processing 3(4), 346–349, 1974; publisher metadata and abstract
Closest points on two line segments 2026-10-14
For line segments and , , 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 .
Let two positive-radius circles have external tangency at and lie in the closed strip between two parallel lines, touching opposite boundaries at . Then are collinear. To prove this, choose coordinates with the boundaries , put and , and write the centres as , . The contact point isThe closed line segment is contained in the union of the two closed disks: its portions from to and from to are chords. The strip and external tangency hypotheses are essential to this particular formulation.
Computational geometry 2026-11-05
Computational geometry designs and analyzes algorithms for geometric objects represented by coordinates or combinatorial structure. Problems include finding a convex hull, intersecting segments and locating points in a subdivision. The representation and numerical predicates are part of correctness, not merely implementation details.
For points in the plane, the orientation predicate uses the sign ofA positive sign places to the left of the directed line from to ; zero means collinearity. The points give a positive determinant. Near-collinear inputs can make round-off error reverse the sign and corrupt an algorithm's combinatorial decisions. Shewchuk's adaptive predicates increase arithmetic precision only as needed to certify the correct sign.[ref]
Control point Created 2026-10-14 Updated 2026-10-14
A control point is an editable geometric handle used to specify a curve or surface through a basis or refinement rule. The handle is part of the representation; it need not be a point on the resulting curve. In a Bézier curve, the control points are the geometric coefficients of the Bernstein basis. Joining them in order gives a control polygon, which makes the handles easy to manipulate without drawing the curve as a chain of line segments.[ref]
Curves and Surfaces in Geometric Modeling: Theory and Algorithms by Jean Gallier. §4.3, pp. 132–133: control points and Bernstein representation; §5.1, p. 148: control polygon
For example, use the cubic Bézier curve with control pointsIts Bernstein basis representation givesThe greatest height is , so neither interior control point, both at height , lies on this curve. The endpoint control points do lie on it: and . This separates interpolation, which requires passage through prescribed data, from an approximating representation, which uses handles to shape a curve without requiring passage through every handle. If measured points must be interpolated, choose control points to satisfy those constraints; simply using the measured points as the handles of a Bézier curve does not enforce interpolation.
Original cubic and the curve after moving only the interior control point P1 upward by one unit, with fixed endpoints and a smaller displacement at the same parameter
. Details. Now move only by the vector , giving . With the Bernstein basis and parameter unchanged, the new curve isAt this gives , a displacement despite moving the handle by a full unit. Both endpoints stay fixed because the coefficient vanishes there. Thus dragging a control point shapes a whole range of the curve; it does not generally drag an arbitrary selected point on the curve by the same vector. The control-point influence on a curve tells us exactly how much each parameter value moves.
Control polygon 2026-10-14
A control polygon joins successive control points by line segments. It gives an editable geometric skeleton, not usually the exact curve. An open control polygon has two ends; a closed control polygon also joins the last control point to the first. Store the first control point only once when using cyclic indices, so the closing edge is counted exactly once. Positive partition of unity basis functions place the curve inside the convex hull of its active control points; a convergent subdivision curve rule refines the control polygon toward its limit, with a certified error when an appropriate bound is available.
Convex body 2026-10-14
A convex body in is a compact convex set with nonempty interior in the ambient Euclidean space. It consequently has positive finite Lebesgue measure. A filled rectangle with positive side lengths and a closed positive-radius Euclidean disk are planar convex bodies. A line segment in has empty ambient interior and is not a convex body under this convention. This is the convention used in the Brunn-Minkowski theorem. [ref]
https://sites.stat.washington.edu/jaw/COURSES/520s/523/HO.523.20/Gardner.BullAMS.02.pdf. Gardner (2002), introduction
Convex combination Created 2026-09-24 Updated 2026-10-14
A convex combination is a finite weighted average of points in a real vector space. For , 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]
Convex Optimization by Stephen Boyd and Lieven Vandenberghe. §2.1.4, p. 24: finite combinations, weighted-average interpretation and convex hull
The distinction from a linear combination is concrete. Combining and with coefficients and gives , outside their line segment, despite the unit coefficient sum. Using two coefficients both equal to one gives 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.
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 function Created 2026-09-24 Updated 2026-10-14
A function on a convex set is a convex function if, for every and ,Geometrically, a line segment joining two points of its graph of a function lies on or above that graph of a function. The convex set condition ensures that the intermediate input stays in the domain of a function. An affine function satisfies the defining inequality with equality.
For the quadratic function , the inputs and have equally weighted arithmetic mean . Evaluating at the arithmetic mean gives , whereas averaging the outputs gives . Averaging first saves one unit in this example. More generally, direct expansion givesThis identity proves convexity and also shows exactly when its defining inequality is strict.
The graph of a convex quadratic lies below its endpoint interpolation and above its supporting tangent
. For , the line segment through and has height at , while the graph of a function has height . The tangent line is an affine minorant: everywhere. Details.For a differentiable convex function, the tangent line in one dimension, or the corresponding supporting affine function in several dimensions, lies below the entire graph of a function. This is the subgradient inequality. The equivalent geometric statement is that the epigraph, consisting of points on or above the graph of a function, is a convex set. These characterizations are developed in Boyd and Vandenberghe's convex-function slides, sections 3.1–3.4.
Convexity does not require differentiability: the absolute value function is a convex function with a corner at . When a function is twice continuously differentiable on an open interval, it is a convex function exactly when its second derivative is nonnegative throughout that interval. In several dimensions, the corresponding criterion on an open convex set is that its Hessian matrix is positive semidefinite everywhere. The domain of a function matters: is a convex function on , but not on all of . A strictly positive second derivative is sufficient for strict convexity, but is not necessary: is a strictly convex function although its second derivative vanishes at .
The usefulness of convexity is that local information can certify a global conclusion. Every local minimum of a convex function on a convex set is a global minimum: if a lower value existed elsewhere, the defining inequality would produce lower values arbitrarily close to the proposed local minimum. For a differentiable convex function on an open convex set, a zero gradient therefore certifies a global minimum. Strict convexity gives uniqueness when a global minimum exists; it does not supply existence by itself. These facts explain the role of convex functions in convex optimization.
Convex hull Created 2026-09-24 Updated 2026-10-18
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 in a real vector space,Equivalently this is the smallest convex set containing . Mixing two already mixed points produces another finite convex combination, so the displayed set is convex; every convex set containing must contain all these mixtures.[ref]
Convex Optimization by Stephen Boyd and Lieven Vandenberghe. §2.1.4, printed p. 24: convex hull and smallest containing convex set
In an original planar example, take four points , , , and four additional samples , , , . Their convex hull is the filled convex polygon , including its boundary. None of the samples is , butThe coefficients are nonnegative and sum to one, providing an explicit membership certificate. Geometrically, first form on the line segment , then mix . The additional interior samples do not enlarge the convex hull.
For a finite nonempty , the convex hull is the image of a probability simplex of weights under the linear map . 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.
Convex optimization Created 2026-09-24 Updated 2026-10-13
Convex optimization is a minimization problem with a convex function as its objective function and a convex set of feasible points. For a finite-valued , the problem is to find with for every . The displayed infimum describes its value even when no minimizing point exists. The two convexity requirements concern different objects: the allowed decisions and the scores assigned to them.
A convex set contains the whole line segment between any two of its points:A convex function lies below the interpolation of its endpoint values:Thus mixing two allowed decisions preserves feasibility, and the mixed score is no worse than the same mixture of endpoint scores. The objective function may have flat regions or corners. For a strictly convex function, the second inequality is strict when and .
A useful constraint representation iswhere are convex functions on a common convex set , and the equalities are affine functions. Each inequality defines a convex sublevel set; their intersection with and the equality set is a convex set. An equality involving a general convex function need not preserve this geometry: allows and but excludes their midpoint . See Boyd and Vandenberghe, Convex Optimization (2004), §4.2.1 for the standard problem form.
Why local information can certify a global answer. Every local minimum of a convex optimization problem is a global minimum, including minima on the boundary. If a feasible point had , points would remain feasible and have value strictly below for every . Taking arbitrarily small contradicts a local minimum at . This argument explains the special power of convexity: a better distant decision would reveal an improving direction immediately nearby.
If a minimizer exists and the objective function is strictly convex on , it is unique. Two distinct minimizers of value would have a feasible midpoint with value strictly below . Existence is a separate question: the exponential function is strictly convex on , but its infimum is approached only as . Even a bounded convex set need not suffice: on also has unattained infimum . A continuous function on a nonempty compact set attains its minimum by the extreme value theorem.
Nor does strict convexity imply differentiability. For , the squared term gives the strict inequality while the triangle inequality gives the weak inequality for the absolute value. At zero the left and right derivatives are and , so no derivative exists there, although zero is the unique minimizer. Such objectives require subgradients or proximal operators rather than an ordinary gradient at every point.
For a differentiable convex function on an open convex set containing , the constrained first-order condition isIndeed, the subgradient inequality makes this sufficient; taking the one-sided derivative along feasible line segments makes it necessary. At an interior minimizer, both directions are feasible and the gradient must vanish. At a boundary minimizer it can be nonzero: it only needs to make every feasible direction nondecreasing. See Boyd and Vandenberghe, §§3.1.3 and 4.2.3.
A fully computed nearest-point problem. Project onto the half-space by minimizing half the squared Euclidean distance:The Hessian matrix is the identity matrix, so the objective function is strictly convex. The unconstrained minimizer violates the inequality. With the convention , the optimization Lagrangian is , where the Lagrange multiplier satisfies . Its Karush-Kuhn-Tucker conditions areThe last two equations give , . The choice is infeasible, so complementary slackness forces . Consequently , giving , and . The Euclidean distance is , rather than the objective function value . The gradient at the answer balances ; the displacement from to is a normal vector to the boundary.
There is an exact certificate independent of numerical search. Completing squares givesFor every feasible point, implies . Thus every feasible objective is at least , and attains this bound. More generally the Lagrangian dual problem has objective for . Its maximum is also , illustrating strong duality through matching computed bounds. This makes the example a model for Euclidean projection onto a convex set and the projection step in projected gradient descent.
What the multiplier conditions require. For differentiable convex functions on an open convex set and equalities defined by affine functions, the KKT conditions combine feasibility, , complementary slackness , and stationaritywith unrestricted equality Lagrange multipliers . They suffice to certify a global minimum without an additional regularity assumption: the optimization Lagrangian is convex, stationarity minimizes it, and feasibility with complementary slackness gives the same certificate as above. To guarantee their necessity at an attained finite optimum, a regularity hypothesis suffices: Slater's condition requires some with and . The projection example has the strictly feasible point . See Boyd and Vandenberghe, §§5.2.3 and 5.5.3. This hypothesis guarantees suitable multipliers, not existence of a primal minimizer.
Without regularity, necessity can fail even for convex functions: minimize subject to . The sole feasible point is optimal, but stationarity would require . No Lagrange multiplier works. There is no strictly feasible point, and the gradient of the constraint vanishes at the answer.
The nonconvex contrast. The polynomial has derivative and second derivative . Numerically solving the cubic gives stationary points , , and . Their objective values are respectively , , and , with second derivatives , , and . Hence both outer points are local minima, and the middle point is a local maximum. Since at both ends, its global minimum exists and must be one of the stationary minima: it is the left one. A method stopping at the right local minimum misses a better value by approximately .
A strictly convex quadratic has one minimum; a tilted quartic has two local minima with different values
. Details. The practical appeal of convex optimization is the ability to check an answer globally using geometry and matching Lagrangian duality bounds. The projection certificate certifies every feasible alternative at once; the tilted quartic shows why a zero gradient alone cannot do that for general nonlinear optimization.
Historically, an early landmark is Kuhn and Tucker's [ref]
https://digicoll.lib.berkeley.edu/record/112776/files/math_s2_article-35.pdf. Nonlinear Programming, Second Berkeley Symposium (1951), pp. 481–492
. Its §3 explicitly states a regularity hypothesis for inequality-constrained Lagrange multipliers; its discussion of saddle points explains how concave functions support global conclusions for maximization. This documents an early formulation of the multiplier approach; it does not establish sole discovery of today's KKT conditions or of convex optimization as a whole. Convex set Created 2026-09-24 Updated 2026-10-24
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 of a real vector space is convex whenThe parameter 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]
Convex Optimization by Stephen Boyd and Lieven Vandenberghe. §2.1.4, pp. 23–25: convex sets and finite convex combinations
The triangle inequality verifies the disk example directly: if , then . For the open disk, the last inequality is strict. The unit circle fails the same test: and belong to it, but their midpoint 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.
De Casteljau's algorithm 2026-10-14
De Casteljau's algorithm evaluates a Bézier curve by repeated linear interpolation between neighboring control points. Fix , start with , and computeEach new row has one fewer point. The final point is . Use the same at every stage: it describes the fraction of each line segment traversed from its first endpoint toward its second. A cubic Bézier curve needs three levels containing , , and linear interpolations, respectively.[ref]
https://graphics.stanford.edu/courses/cs164-10-spring/Handouts/handout19.pdf. Stanford CS348a, Handout 19, §2.3, pp. 10–11
For the Bézier curve with control points , , , , evaluation at takes the midpoint of every neighboring pair. The first level givesThe second level givesand the third level givesThe intermediate control polygons shrink toward the evaluated point. Each step is a convex combination, giving a geometric explanation of the convex hull property; every step also commutes with an affine map.
Cubic Bézier curve, its convex hull and bounding box, and the three levels of De Casteljau's algorithm at t = 1/2
. Details. The same construction splits the Bézier curve exactly, with no approximation. The outer edges of the triangular array give the new control points: for a cubic, specify the left piece and specify the right piece.[ref]
https://graphics.stanford.edu/courses/cs164-10-spring/Handouts/handout19.pdf. Stanford CS348a, Handout 19, §2.3, p. 11, subsegment control points
At these two lists areWrite and for the Bézier curves defined by these lists, each with its own parameter . ThenTheir images reproduce the original curve, while their derivatives account for the shorter parameter intervals. At the join,The chain rule gives ; in the original parameter, both pieces have derivative . This is the interval scaling in the parametric first-derivative join of Bézier curves.Exact midpoint subdivision with two smaller control polygons, endpoint tangent directions, and equally spaced parameter samples
. Details. Repeated midpoint splitting is useful for drawing vector graphics paths: each piece has a smaller control polygon and its own convex hull enclosure. A renderer can refine pieces until they are sufficiently close to line segments at the chosen display scale. Evaluating and splitting it are thus two results of the same short algorithm.
For a proof outline, expanding the recursion givesPascal's identity proves this by induction; at , it is precisely the Bernstein basis formula for the Bézier curve. The geometric construction remains useful even when expanding the polynomial by hand would be cumbersome.
// Target: analysis.bigb
Descent lemma Created 2026-10-06 Updated 2026-10-25
Suppose is a differentiable function on an open convex set and has an -Lipschitz gradient there, in the Euclidean norm. For , the descent lemma statesA bounded continuous Hessian matrix gives one sufficient route to this estimate.[ref]
For a short proof, put . The fundamental theorem of calculus along the line segment givesThe Cauchy-Schwarz inequality and the Lipschitz gradient bound make the integrand at most ; its integral is . This proof needs no assumption that is a convex function.
For the gradient descent update , provided , substitution yieldsFor and , this ensures strict decrease whenever the gradient is nonzero. At it guarantees only nonincrease; the quadratic example has a nonshrinking alternating component at this endpoint. At the guaranteed decrease is . A bound valid only on cannot justify a step leaving .
If a fixed admissible step size is used forever, every iterate stays in , and has a finite lower bound, summing this inequality shows , hence . That conclusion alone gives neither convergence of the iterates nor a global minimum. For example, the smooth polynomial has and : gradient descent started at zero never moves, although . On , , so the Lipschitz gradient hypothesis holds on this domain. Convex functions and strongly convex functions provide additional structure; the exact quadratic convergence result above uses a positive-definite matrix.












