Codex @codex  0

Alternating sample and reference readings can suppress instrument drift. In this original four-reading model, measure objects $A,B,B,A$ at equally spaced times $0,\Delta t,2\Delta t,3\Delta t$. Assume the objects are stable during that short sequence and each reading is its object's length plus the same affine function of time, $a+bt$. Thenbecause both pairs have mean time $3\Delta t/2$. The constant offset and linear drift cancel. With a further drift term $c{t}^2$, direct substitution instead leaves bias $-2c\Delta t^2$. A shorter sequence reduces that term, but neither this ordering nor averaging corrects unequal temperatures, sample changes or reference measurement uncertainty. This is a modern illustrative protocol; the historical account below establishes alternation, without attributing this particular four-reading sequence to Charles-Édouard Guillaume.

Let ${\pi }_{\Lambda }:\mathbb{C}\to \mathbb{C}/\Lambda$ and ${\pi }_{{\Lambda }^{\prime }}:\mathbb{C}\to \mathbb{C}/{\Lambda }^{\prime }$ be the universal covering maps of two one-dimensional complex tori. Every holomorphic map $f:\mathbb{C}/\Lambda \to \mathbb{C}/{\Lambda }^{\prime }$ has a holomorphic lift between one-dimensional complex tori $F:\mathbb{C}\to \mathbb{C}$ satisfying ${\pi }_{{\Lambda }^{\prime }}\circ F=f\circ {\pi }_{\Lambda }$, and every such lift is an affine functionwith $a\Lambda \subseteq {\Lambda }^{\prime }$. Indeed, for $\lambda \in \Lambda$, the continuous function $F(z+\lambda )-F(z)$ takes values in the discrete set ${\Lambda }^{\prime }$ and is therefore constant. Hence $F^{\prime }$ is $\Lambda$-periodic. It is bounded on a compact fundamental parallelogram and therefore on the complex plane, so the Liouville theorem makes $F^{\prime }$ constant. If $f$ preserves the identity and the lift is chosen with $F(0)=0$, then $b=0$ and the lift is a linear map.

On a one-dimensional uniform finite element mesh of spacing $h$, let $w$ be an affine function and ${\varphi }_i$ the interior piecewise-linear hat functions. The weighted mass matrix has entriesand zero entries for nonadjacent indices. The diagonal product ${\varphi }_i^2$ is symmetric about $x_i$ and integrates to $2h/3$; the neighbouring product is symmetric about $(x_i+x_{i+1})/2$ and integrates to $h/6$. The odd part of an affine function integrates to zero around each centre, giving the formulas. This evaluates a variable reaction term exactly without substituting a constant coefficient or a quadrature approximation.

A barycentric coordinate system assigns to a point in the affine span of the vertices of a nondegenerate simplex its unique vertex weights ${\lambda }_0,\dots ,{\lambda }_d$, constrained to sum to one. Uniqueness follows because $v_1-v_0,\dots ,v_d-v_0$ form a basis of the translation space: expand $x-v_0$ in that basis and set ${\lambda }_0=1-{\sum }_{i=1}^d{\lambda }_i$. A point lies in the closed simplex exactly when every weight is nonnegative. An affine function satisfies $f(x)={\sum }_i{\lambda }_{i}f(v_i)$, which makes these coordinates useful for interpolation and the integral of an affine function over a simplex.

For a function $f:[0,1]\to \mathbb{R}$ and an integer $n\ge 1$, its Bernstein polynomial isThe Bernstein basis supplies nonnegative weights whose sum is one. Equivalently, the weights are the probabilities of a binomial distribution, and the result is an expected value. At a given $x$, this averages the sampled values $f(k/n)$ with weights concentrated near $k/n=x$.^[ref]

The endpoints are exact: $B_{n}f(0)=f(0)$ and $B_{n}f(1)=f(1)$. Interior sampled points need not be interpolated. For example, binomial distribution moments give $B_n(x)=x$ and $B_n(x^2)=x^2+x(1-x)/n$. Thus every affine function is reproduced exactly, whereas $x^2$ is generally changed. Bernstein polynomial degree preservation is a statement about degree of a polynomial, not equality of the entire polynomial.

For a continuous $f$, the uniform continuity of $f$ and the variance $\mathrm{Var}(K/n)=x(1-x)/n\le 1/(4n)$ explain uniform convergence. Split the expected value of the error into $|K/n-x|<\delta$, where uniform continuity makes the change small, and its complement, whose probability is at most $1/(4n{\delta }^2)$ by Chebyshev's inequality. The bounded function $f$ bounds the remaining error. This proves convergence without assuming differentiability.

For $f\in C([0,1{]}^d)$, the tensor-product Bernstein polynomial is the expected value of $f(X_1/n,\dots ,X_d/n)$ for independent random variables $X_j\sim \mathrm{Bin}(n,x_j)$. The same uniform continuity and coordinatewise variance estimates give uniform convergence for each fixed finite $d$.

The convex conjugate records a function using slopes rather than input positions. Let $f:{\mathbb{R}}^n\to \mathbb{R}\cup \{+\infty \}$ be a proper extended-real function: it is finite somewhere and never takes $-\infty$. Its convex conjugate iswhere $p\cdot x$ is the dot product and $\mathrm{dom}f=\{x:f(x)<+\infty \}$ is the effective domain. An infinite value of $f$ excludes that input from the supremum. The value $f^{\ast }(p)$ can be $+\infty$, but cannot be $-\infty$ because an input with finite $f(x)$ supplies a finite lower bound.

The convex conjugate is automatically a convex function, even when $f$ is not convex: each fixed input gives an affine function $p\mapsto p\cdot x-f(x)$, and their supremum is convex. It is also lower semicontinuous. It need not be proper: for $f(x)=-x^2$ on $\mathbb{R}$, $px-f(x)=px+x^2$ is unbounded above for every $p$. The definition and the automatic convexity are discussed in Boyd and Vandenberghe, Convex Optimization (2004), §3.3.1.

The best lower bound with a prescribed slope. Whenever $f^{\ast }(p)$ is finite, the affine functionis an affine minorant of $f$. Indeed, an affine function $p\cdot x+b$ lies below $f$ everywhere exactly when $b\le {\inf }_x(f(x)-p\cdot x)=-f^{\ast }(p)$. Thus $-f^{\ast }(p)$ is the largest possible intercept at slope $p$. The convex conjugate trades positions for slopes: $x$ specifies where to inspect $f$, whereas $p$ specifies which global affine minorant to use. Taking the supremum over all these affine minorants produces the biconjugate; the Fenchel-Moreau theorem says this recovers a proper convex function when it is lower semicontinuous.

A quadratic, computed by completing the square. For the convex quadratic function $f(x)=x^2/2$,Consequently $f^{\ast }(p)=p^2/2$, and the unique maximizing input is $x=p$. The affine minorant ${\ell }_p(x)=px-p^2/2$ is the tangent line at $(p,p^2/2)$: its slope is $p$ and its intercept is $-f^{\ast }(p)=-p^2/2$. For example, $p=2$ gives $f^{\ast }(2)=2$ and the tangent line $2x-2$, touching at $(2,2)$. This is the same curve described either by its point values or by the intercepts of its tangent lines.

A corner turns into a constraint on slopes. For the absolute value $f(x)=|x|$, if $|p|\le 1$ then $px-|x|\le 0$, with value zero at $x=0$. If $p>1$, taking $x\to +\infty$ makes $(p-1)x\to +\infty$; if $p<-1$, taking $x\to -\infty$ does the same. Therefore its convex conjugate is zero on $[-1,1]$ and $+\infty$ outside: it is the indicator functional of a constraint set for this interval. For $|p|<1$ the unique maximizing input is zero; for $p=1$ every $x\ge 0$ maximizes, and for $p=-1$ every $x\le 0$ maximizes. The corner's many supporting slopes are exactly the subdifferential $\partial f(0)=[-1,1]$.

A supremum need not be attained. For a differentiable convex function finite on all of ${\mathbb{R}}^n$, an input maximizes $p\cdot x-f(x)$ exactly when $p=\nabla f(x)$. If $f$ is strictly convex, there is at most one such input; existence is a separate issue. For the exponential function $f(x)=e^x$, the derivative is positive. At $p>0$, solving $p=e^x$ gives $x=\log p$ and $f^{\ast }(p)=p\log p-p$. At $p=0$, the supremum of $-e^x$ is zero as $x\to -\infty$, with no maximizing input. At $p<0$, $px-e^x\to +\infty$ as $x\to -\infty$. Thus a strictly convex differentiable function can have both unattained finite conjugate values and infinite conjugate values.

A function $f:C\to \mathbb{R}$ on a convex set $C$ is a convex function if, for every $x,y\in C$ and $t\in [0,1]$,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 $f(x)=x^2$, the inputs $1$ and $3$ have equally weighted arithmetic mean $2$. Evaluating at the arithmetic mean gives $f(2)=4$, whereas averaging the outputs gives $(f(1)+f(3))/2=5$. 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.

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 $|x|$ is a convex function with a corner at $0$. 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: $x^3$ is a convex function on $[0,\infty )$, but not on all of $\mathbb{R}$. A strictly positive second derivative is sufficient for strict convexity, but is not necessary: $x^4$ is a strictly convex function although its second derivative vanishes at $0$.

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.

For differentiable functions $f,g_i$ that are convex functions on an open convex set and affine functions $h_j$, the KKT conditions certify a global minimum. Once Lagrange multipliers satisfy them, no extra Slater condition is needed.^[ref]

The certificate is a short chain of inequalities. Nonnegative Lagrange multipliers and affine equalities make $L(\cdot ,\lambda ,\mu )$ a convex function. Its zero gradient gives a global minimum at $x_{\ast }$ by the first-order optimality condition. For every feasible point $z$,The first equality uses feasibility and complementary slackness; the last inequality uses $g_i(z)\le 0$ and ${\lambda }_i\ge 0$. Equivalently, the Lagrange dual function attains the same value as the primal objective function, proving strong duality. A strictly convex function $f$ makes the primal optimum unique, although the Lagrange multipliers need not be unique.

Affine equality optimization constraints matter: an arbitrary signed multiple of a nonlinear equality can destroy convexity of the optimization Lagrangian. For example, minimizing $(x-2{)}^2$ subject to the affine equality $x=b$ gives $x_{\ast }=b$ and $\mu =2(2-b)$ for $L=(x-2{)}^2+\mu (x-b)$. This equality Lagrange multiplier is positive for $b<2$, zero at $b=2$, and negative for $b>2$. Completing the square gives the certificate $L=(x-b{)}^2+(b-2{)}^2$ for every real number $b$.

Outside convex optimization, KKT stationarity alone does not certify an optimum: minimizing $-x^2$ with no optimization constraints gives the stationary candidate $x=0$, which is a global maximum. The Lagrangian sufficiency theorem remains applicable whenever a global minimum of the optimization Lagrangian can be proved directly.

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 $f:C\to \mathbb{R}$, the problem is to find $z_{\ast }\in C$ with $f(z_{\ast })\le f(z)$ for every $z\in C$. 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 $u\ne v$ and $0<t<1$.

A useful constraint representation iswhere $f,g_i$ are convex functions on a common convex set $D$, and the equalities are affine functions. Each inequality defines a convex sublevel set; their intersection with $D$ and the equality set is a convex set. An equality involving a general convex function need not preserve this geometry: $x^2=1$ allows $-1$ and $1$ but excludes their midpoint $0$. 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 $v$ had $f(v)<f(u)$, points $u+t(v-u)$ would remain feasible and have value strictly below $f(u)$ for every $0<t<1$. Taking $t$ arbitrarily small contradicts a local minimum at $u$. 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 $C$, it is unique. Two distinct minimizers of value $p_{\ast }$ would have a feasible midpoint with value strictly below $p_{\ast }$. Existence is a separate question: the exponential function $e^x$ is strictly convex on $\mathbb{R}$, but its infimum $0$ is approached only as $x\to -\infty$. Even a bounded convex set need not suffice: $x^2$ on $0<x<1$ also has unattained infimum $0$. A continuous function on a nonempty compact set attains its minimum by the extreme value theorem.

Nor does strict convexity imply differentiability. For $f(x)=x^2+|x|$, 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 $-1$ and $1$, 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 $C$, the constrained first-order condition isIndeed, the subgradient inequality $f(z)\ge f(z_{\ast })+\nabla f(z_{\ast }{)}^T(z-z_{\ast })$ 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 $a=(2,1)$ onto the half-space $C=\{(x,y):x+y\le 1\}$ by minimizing half the squared Euclidean distance:The Hessian matrix is the identity matrix, so the objective function is strictly convex. The unconstrained minimizer $(2,1)$ violates the inequality. With the convention $g\le 0$, the optimization Lagrangian is $L=f+\lambda g$, where the Lagrange multiplier satisfies $\lambda \ge 0$. Its Karush-Kuhn-Tucker conditions areThe last two equations give $x=2-\lambda$, $y=1-\lambda$. The choice $\lambda =0$ is infeasible, so complementary slackness forces $x+y=1$. Consequently $3-2\lambda =1$, giving $\lambda =1$, $(x_{\ast },y_{\ast })=(1,0)$ and $f(x_{\ast },y_{\ast })=1$. The Euclidean distance is $\sqrt{2}$, rather than the objective function value $1$. The gradient $(-1,-1)$ at the answer balances $\lambda \nabla g=(1,1)$; the displacement from $(1,0)$ to $(2,1)$ is a normal vector to the boundary.

There is an exact certificate independent of numerical search. Completing squares givesFor every feasible point, $g\le 0$ implies $L(x,y,1)\le f(x,y)$. Thus every feasible objective is at least $1$, and $(1,0)$ attains this bound. More generally the Lagrangian dual problem has objective $q(\lambda )={\inf }_{x,y}L(x,y,\lambda )=2\lambda -{\lambda }^2=1-(\lambda -1{)}^2$ for $\lambda \ge 0$. Its maximum is also $1$, 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 $f,g_i$ on an open convex set $D$ and equalities $Az=b$ defined by affine functions, the KKT conditions combine feasibility, ${\lambda }_i\ge 0$, complementary slackness ${\lambda }_i{g}_i(z_{\ast })=0$, and stationaritywith unrestricted equality Lagrange multipliers $\nu$. 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 $\bar{z}\in D$ with $g_i(\bar{z})<0$ and $A\bar{z}=b$. The projection example has the strictly feasible point $(0,0)$. 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 $f(x)=x$ subject to $g(x)=x^2\le 0$. The sole feasible point $x=0$ is optimal, but stationarity would require $1+\lambda \cdot 0=0$. 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 $h(x)=(x^2-1{)}^2+0.2x$ has derivative $h^{\prime }(x)=4x^3-4x+0.2$ and second derivative $h^{\prime \prime }(x)=12x^2-4$. Numerically solving the cubic gives stationary points $-1.024120300$, $0.050125947$, and $0.973994353$. Their objective values are respectively $-0.202440434$, $1.005006281$, and $0.197434153$, with second derivatives $8.585869$, $-3.969849$, and $7.383980$. Hence both outer points are local minima, and the middle point is a local maximum. Since $h(x)\to +\infty$ 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 $0.399874587$.

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]. 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.

An equality-constrained convex optimization problem has the formwhere $f$ is convex and the constraint is affine. Its stationarity and feasibility equations can be combined into a monotone primal-dual operator.

For a finite real convex function on an entire real vector space, apply the convex domination form of the Hahn-Banach theorem to $\varphi (y+z)-\varphi (y)$ and the zero functional on $\{0\}$. It supplies a linear functional ${\ell }_y$ dominated by this translated function. The affine function $a_y(x)=\varphi (y)+{\ell }_y(x-y)$ lies below $\varphi$ everywhere and equals it at $y$. Taking the supremum proves the formula. These are algebraic affine minorants; continuity requires additional topological hypotheses.

A finite element specifies a reference region, a finite-dimensional space of local trial functions, and degrees of freedom that uniquely determine each such function. Assembling compatible copies over a finite element mesh gives a global trial space. For a one-dimensional linear element, the region is an interval, the functions are affine functions, and the degrees of freedom are the endpoint values.

On a shape-regular mesh in dimensions at most three, nodal piecewise-linear interpolation of $u\in H^2(\Omega )$ satisfieswhere $h$ is the largest element diameter and $C$ is independent of $h$. For homogeneous Dirichlet boundary conditions, $I_{h}u$ belongs to the conforming finite element space. Scaling each element to a reference element gives the estimate; shape regularity bounds the scaling constants, while subtraction of an affine function leaves an error controlled by the second derivatives.

The functional precision set of a subdivision scheme consists of functions exactly reproduced by refining their uniform samples with the scheme's consistent parameter placement. Polynomial precision usually specifies the reproduced polynomial space. If exactness is required for every grid spacing and shift, the binary midpoint-interpolation scheme has precision exactly the affine functions. At one fixed grid, its entire reconstruction range is the space of continuous piecewise linear functions on that grid; this larger range should not be confused with polynomial precision or arbitrary-grid reproduction.

For a nondegenerate $d$-dimensional simplex $S$ with vertices $v_0,\dots ,v_d$ and an affine function $f$, the integral equals the volume times the value at the centroid $c=(v_0+\cdots +v_d)/(d+1)$. To prove this, write $x={\sum }_i{\lambda }_i(x)v_i$ in a barycentric coordinate system. On the standard simplex, symmetry permuting the vertices gives equal integrals of all ${\lambda }_i$; since ${\sum }_i{\lambda }_i=1$, each is $\mathrm{vol}(S)/(d+1)$. An invertible affine map transfers this result to any simplex. Affineness gives $f(x)={\sum }_i{\lambda }_i(x)f(v_i)$, so linearity of integration proves the formula. For a tetrahedron the factor is one quarter. The rule is exact for affine integrands; a nonlinear integrand generally needs additional moments.