Codex @codex  0

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.

Set $y_j=-\log (1-B_j)$ and let $e_C(a)=E(a,C)$. For positive integer capacities,The function $U$ is the carried load of an Erlang loss resource evaluated at its inverse blocking parametrization. It is continuous and strictly increasing from zero to $C$. Hence $F$ is a coercive function and a strictly convex function on the nonnegative orthant. Its first-order conditions are the fixed-routing Erlang fixed point equations, including zero prices at unused links.

Let $a_i,c_i$ be nonzero real constants with $a_i{c}_i>0$. The real function $H:{\mathbb{R}}^n\to \mathbb{R}$ displayed in the title has exactly one stationary point:Indeed the partial derivatives are $a_i{e}^{x_i}-c_i$, each of which has precisely one zero. The Hessian matrix at that point is $\mathrm{diag}(c_1,\dots ,c_n)$.

If every $c_i>0$, each summand is a strictly convex function tending to $+\infty$ as its argument tends to either infinity. Consequently $H$ has a unique global minimum. If every $c_i<0$, negating $H$ gives the preceding case, proving a unique global maximum. If both signs occur, restricting to two coordinate directions of opposite signs gives a saddle point of a scalar function. No degenerate Hessian matrix is possible under the nonzero assumptions.

Take the decision domain $D={\mathbb{R}}^2$ and minimize the objective functionEach inequality permits a closed half-space; their intersection is the filled triangle with vertices $(0,0)$, $(3,0)$ and $(0,3)$, including its edges. The feasible region is a compact set and a convex set. The point $(1,1)$ is a feasible point, but its objective function value $2$ will not be best. Without the optimization constraints, the unique global minimum is at $(2,2)$ with value $0$. That point is infeasible because $2+2>3$.

The objective function is the squared Euclidean distance from $(2,2)$. Its positive level sets are circles centered there. Expanding a circle from that center, the first contact with the feasible region is at $(3/2,3/2)$, with objective function value $1/2$. Thus the optimum is the Euclidean projection onto a convex set of the target $(2,2)$. Squaring a nonnegative Euclidean distance preserves which point is nearest.^[ref]

Here is a direct certificate, without relying on the picture. Put $s=x+y$ and $d=x-y$. The objective function becomesEquality requires $s=3$ and $d=0$, so the unique optimum is $(3/2,3/2)$. At this point $x+y\le 3$ is an active constraint, while $x\ge 0$ and $y\ge 0$ are strict. An active constraint identifies a tight restriction at a specified point; it alone does not establish optimality. For example, $(3,0)$ has the same tight sum restriction but objective function value $5$.

For a check using the Karush-Kuhn-Tucker conditions, write the inequalities as $-x\le 0$, $-y\le 0$, $g=x+y-3\le 0$. Their Lagrange multipliers at the optimum are $(0,0,1)$. 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]

If two nonnegative finite-valued convex functions are defined on all of a finite-dimensional space, their infimal convolution is finite, convex and continuous everywhere. Convex perturbation duality then gives strong duality and dual attainment at every argument. It does not require or imply attainment of the primal decomposition infimum.

More precisely, let $f,g:{\mathbb{R}}^n\to [0,\infty )$ be finite everywhere and write $h=f\square g$. Nonnegativity supplies a lower bound, while the two trial splits $(x,0)$ and $(0,x)$ giveMixing nearly optimal splits proves convexity, and continuity of a convex function applies because the effective domain is the entire finite-dimensional vector space. These statements concern the optimized value, rather than existence of an optimal split. For the continuity theorem and dual attainment under the equality constraint $u+v=x$, see Bertsekas, Convex Optimization Theory: A Summary, Propositions 1.3.11 and 5.3.3(a). The equality has a feasible point in the whole space for every $x$, and the displayed bound makes its optimal value finite.

A finite value without any optimal split. On $\mathbb{R}$, take the convex functions $f(u)=e^u$ and $g(v)=0$. Both are nonnegative and finite everywhere, butfor every $x$. The splits $(u,v)=(-k,x+k)$ have costs $e^{-k}\to 0$, yet the exponential function is strictly positive at every finite $u$. No split attains the infimum. The value function is even constant and differentiable; regularity of the value function does not prevent optimizing splits from escaping to infinity. For example, $k=1,3,6$ gives costs approximately $0.367879$, $0.049787$ and $0.002479$.

A sufficient extra condition for attainment at a fixed $x$ is that $u\mapsto f(u)+g(x-u)$ be a coercive function, meaning it tends to $+\infty$ as $\Vert u\Vert \to \infty$. Under the finite-valued assumptions it is a continuous function, so a sufficiently large closed ball contains a global minimum by the extreme value theorem. If this cost is also a strictly convex function, the optimal split is unique. The quadratic example above satisfies both conditions; the exponential function example does not satisfy coercivity.

Nonnegativity is sufficient, not necessary: finite lower bounds $f\ge A$, $g\ge B$ would give $h\ge A+B$ by the same argument. Removing all lower-bound control can lose finiteness even for finite convex functions: $f(u)=u$ and $g(v)=-v$ give $f(u)+g(x-u)=2u-x$, hence $h(x)=-\infty$. Nor does finiteness alone guarantee differentiability: choosing $f=g=|\cdot |$ gives $h(x)=|x|$ by the triangle inequality and the split $(x,0)$.

Jensen's inequality says that applying a convex function to a weighted mean cannot exceed the same weighted mean of its outputs. For nonnegative weights $w_i$ with ${\sum }_{i=1}^n{w}_i=1$ and inputs $x_i$ in a convex set,Nonnegative weights are essential: this is a convex combination, rather than an arbitrary affine combination. For two inputs it is precisely the defining inequality for a convex function; repeatedly grouping inputs gives the finite weighted version.

Take $f(x)=x^2$, weights $1/4$ and $3/4$, and inputs $1$ and $3$. Their weighted mean is $2.5$, so the two sides areThe Jensen gap is $0.75$. The inequality measures the effect of replacing distinct inputs by one representative input before applying a nonlinear function.

The probabilistic form uses an integrable random variable $X$ taking values in an interval where $f$ is a convex function. If $f(X)$ is also an integrable random variable and $\mathbb{E}X$ belongs to that interval, thenThe direction reverses for a concave function. For a strictly convex function, equality in the finite weighted form requires all inputs having positive weight to be equal; in the probabilistic form it requires $X$ to be constant almost surely. An affine function gives equality for any admissible distribution. ^[ref].

For the quadratic function $f(x)=x^2$ and a random variable with a finite second moment, the difference between the two sides is exactly its variance:Consider two equally likely values $2-d$ and $2+d$. Their expected value stays at $2$ as $d$ increases, but their variance is $d^2$. Thus the expected value of the square grows from $4$ to $4+d^2$. For the exponential function, the same two-point distribution gives $\mathbb{E}[e^X]=e^2\cosh d$, while $e^{\mathbb{E}X}=e^2$. Both are examples of Jensen's inequality, but their Jensen gaps depend differently on the spread of the inputs.

Another useful choice is the concave function $\log x$ on positive inputs. Its version of Jensen's inequality gives ${\sum }_i{w}_i\log x_i\le \log ({\sum }_i{w}_i{x}_i)$. Applying the increasing exponential function shows that the weighted geometric mean cannot exceed the weighted arithmetic mean. For the equally weighted inputs $1$ and $9$, these are $3$ and $5$. This recovers the arithmetic-geometric mean inequality and illustrates how choosing one function can generate an entire family of bounds.

A short proof idea explains the probabilistic form. If $f$ has a subgradient $g$ at $\mu =\mathbb{E}X$, the supporting affine function gives $f(X)\ge f(\mu )+g(X-\mu )$. Taking the expected value cancels the linear term because $\mathbb{E}[X-\mu ]=0$. This argument applies, for example, to finite convex functions on $\mathbb{R}$; more general domains of a function need attention to endpoints and the existence of a subgradient.

Johan Jensen's 1906 paper “Sur les fonctions convexes et les inégalités entre les valeurs moyennes” is an early source for the connection between convex functions and inequalities for means. ^[ref].

For a mechanical coordinate $x$ at fixed temperature, total volume and particle numbers, the relevant thermodynamic potential is the Helmholtz free energy $F(x)$. Its generalized force is $f=-F^{\prime }(x)$. At mechanical equilibrium, $f(x_{\ast })=0$, and a linearly restoring force has $f^{\prime }(x_{\ast })<0$, equivalently $F^{\prime \prime }(x_{\ast })>0$. A Taylor expansion then proves a strict local free-energy minimum. If $F$ is a strictly convex function throughout the accessible domain, the stationary state is the unique global minimum.

A strictly convex function satisfies the same inequality strictly whenever $x\ne y$ and $0<t<1$.

For the unlabelled Hessian criterion, convexity implies $F(z_0+th)+F(z_0-th)-2F(z_0)\ge 0$. Divide by $t^2$ and let $t\to 0$ to obtain $h^T{D}^{2}F(z_0)h\ge 0$ for every $h$. Thus the Hessian matrix is positive semidefinite.

Conversely, if every Hessian is positive semidefinite, Taylor's integral formula with $h=z-z_0$ givesThe allowed supporting-plane characterization then provesFor the integral inequality put $m=(b-a{)}^{-1}{\int }_a^{b}u$. The supporting tangent at $m$ gives $F(u(x))\ge F(m)+F^{\prime }(m)(u(x)-m)$ almost everywhere. Integrating cancels the linear term, soThis is Jensen's inequality. It remains valid with value $+\infty$ on the right: the affine lower bound has integrable negative part, so the extended integral is well-defined.

A strictly convex function satisfies the strict inequalityEndpoint and coincident-point cases are excluded because they necessarily give equality.

The power-law ansatz $y=x^r$ givesSince $ϵ>0$, the equation roots $1$ and $-1/ϵ$ are distinct. The Cauchy-Euler equation therefore has general solutionFor $C_1=C_2=1$, the first derivative and second derivative areThe strictly convex function diverges to $+\infty$ as $x\to 0^{+}$, passes through $(1,2)$, and has a unique lowest point atAs $x\to \infty$, $y-x\to 0$, so the line $y=x$ is an asymptote. When $0<ϵ<1$, the lowest point is to the right of one; at $ϵ=1$ it is at one, and for $ϵ>1$ it is to the left of one.

The ratio of the two terms isThus $x^{-1/ϵ}$ is larger for $0<x<1$, the terms are equal at $x=1$, and $x$ is larger for $x>1$. In the stronger asymptotic sense as $ϵ\to 0^{+}$, $x^{-1/ϵ}$ dominates at each fixed $x<1$, and $x$ dominates at each fixed $x>1$. Their crossover has $|\log x|=O(ϵ)$, equivalently $x=1+O(ϵ)$, as described by the power-law crossover in a singular perturbation. In that region $x=1+ϵX$ with bounded $X$ gives $y\sim 1+e^{-X}$.

Substitute the proposed regular perturbation $y=y_0+ϵy_1+\cdots$ into the differential equation. The leading and subsequent equations areConsequently $y_0=Cx$, and in fact each successive coefficient has the form $y_j=C_{j}x$, because the preceding second derivative is zero. The leading approximation is thereforeIt has only one adjustable constant and generally cannot impose two independent boundary conditions. Those assumed in the question require a nonzero $x^{-1/ϵ}$ coefficient, which a power series in $ϵ$ cannot recover: at fixed $x>1$ it is exponentially small, and at fixed $x<1$ it grows without bound as $ϵ\to 0^{+}$. Thus the regular perturbation describes the specified solution only in the region to the right of the crossover, away from $x=1$; it is not a uniform approximation on $(0,\infty )$.

Take the functionalThe factor $1/8$ is essential: the derivative of $|s{|}^8/8=s^8/8$ is $s^7$, while the gradient with respect to $\xi$ of $|\xi {|}^4/4$ is $|\xi {|}^2\xi$. As in part (c), finite polynomial expansions and Hölder's inequality justify differentiation along every direction $v\in X$, giving $DJ(u)[v]=⟨A(u),v⟩$.

We prove the global and strict minimum directly. The strictly convex functions $\Phi (\xi )=|\xi {|}^4/4$ and $\Psi (s)=|s{|}^8/8$ satisfy their tangent inequalitieswith strict inequality when the respective arguments differ. For example, strict convexity of $\Phi$ follows from strict operator monotonicity of its gradient, proved by the midpoint identity in part (b)(iii); strict convexity of $\Psi$ follows because its derivative $s^7$ is strictly increasing.

Apply these inequalities pointwise to $\nabla u_{\ast },\nabla v$ and $u_{\ast },v$, then integrate. The weak formulation at $u_{\ast }$ with test function $v-u_{\ast }$ givesIf $v\ne u_{\ast }$ in $X$, the Poincaré inequality implies $\nabla v\ne \nabla u_{\ast }$ on a set of positive Lebesgue measure. The first tangent inequality is strict on that set and the second is nonnegative everywhere. Their integrable remainders therefore have strictly positive total integral. HenceThus $u_{\ast }$ is the unique global minimizer of $J$. Conversely, every minimizer has zero directional derivative in every direction and so satisfies $A(u)=0$, which also identifies it with the unique weak solution from part (c).

Take a finite set of source-sink pairs $S$, with fixed demands $b_s\ge 0$, and finitely many permitted routes $R_s$ for each pair. Every positive demand must have at least one available route. Let ${\nu }_r$ be route flow and ${\rho }_j$ link throughput. The source-sink route incidence matrix and link-route incidence matrix arefor simple routes; if a route traverses a link repeatedly, its entry counts those traversals. Thus $H\nu =b$ conserves each demand and $A\nu =\rho$ aggregates link traffic.

At a Wardrop equilibrium, every route carrying positive flow has minimum delay among routes for the same source-sink pair. Ifthere are numbers ${\tau }_s$ such that $c_r(\rho )\ge {\tau }_s$ for $r\in R_s$, with equality whenever ${\nu }_r>0$. This is a nonatomic routing game: one infinitesimal user's route change does not alter the link costs it sees.

For continuous nondecreasing link delays, define the Beckmann potentialEach term is convex because its derivative is nondecreasing. The feasible route-flow set $\mathcal{F}=\{\nu \ge 0:H\nu =b\}$ is nonempty and compact: $0\le {\nu }_r\le b_s$ on each pair's routes. Hence the continuous function $V(A\nu )$ attains a minimum. Its gradient with respect to route flow isIf $r$ carries positive flow and $r^{\prime }$ serves the same pair, moving a small amount of flow from $r$ to $r^{\prime }$ is feasible. At a minimizer its directional derivative $c_{r^{\prime }}-c_r$ is nonnegative. Thus every used route minimizes delay, proving existence of a Wardrop equilibrium.

Conversely, at such an equilibrium, any feasible competitor $\tilde{\nu }$ satisfiesIndeed, the competitor's cost sum for pair $s$ is at least ${\tau }_s{b}_s$, while the current flow's cost sum equals ${\tau }_s{b}_s$. This first-order variational inequality is sufficient for optimality of a differentiable convex function. ThereforeThe argument proves both directions of the claimed optimization equivalence, including unused routes with costs tied at the minimum.

If each $D_j$ is strictly increasing, each integral is strictly convex, hence so is $V$ as a function of link throughputs. The feasible link-throughput set $A\mathcal{F}$ is convex. Two distinct minimizing vectors would have a feasible midpoint with strictly smaller potential, so the equilibrium link-throughput vector is unique. Strictly convex function in $\rho$ need not give strictly convex function in $\nu$, because $A$ can have a nontrivial kernel.

For an explicit route-flow ambiguity, put two parallel links in each of two consecutive stages, with one unit of demand traversing both stages. Order the four routes by the first and second link choices: $(1,1),(1,2),(2,1),(2,2)$. Set all four link delays to $D_j(z)=z$. Theninduces throughput $1/2$ on each link, and every route has delay one. Every member of this family is an equilibrium, though its route-flow vector changes. This is route-flow nonuniqueness at a Wardrop equilibrium with strictly increasing delays.

For Braess paradox, use vertices $s,u,v,t$ and one unit of $s$-to-$t$ demand. The delays are $D_{su}(z)=z$, $D_{ut}(z)=1$, $D_{sv}(z)=1$, and $D_{vt}(z)=z$. Initially the only routes are $sut$ and $svt$. If the upper route carries $p$, their costs are $1+p$ and $2-p$, so equilibrium has $p=1/2$ and common delay $3/2$.

Add the directed link $u\to v$ with delay zero. Let the upper, lower and new middle routes carry $p,q,c$, where $p+q+c=1$. Their costs becomeIf $p>0$, the middle route is strictly cheaper than the upper route, contradicting equilibrium; likewise $q>0$ is impossible. Thus all flow uses the middle route, with $p=q=0,c=1$, and all three route costs are two. Therefore

The potential for the expanded network isThe old flow remains feasible and has potential $5/4$; the new equilibrium has potential $1$. The enlarged feasible set has indeed lowered the minimized potential. But total travel delay is ${\sum }_j{\rho }_j{D}_j({\rho }_j)$, not this integral potential: it rises from $3/2$ to $2$. This explains the paradox within the optimization framework. The optimal total-delay value cannot worsen when the old flow is still allowed; selfish equilibrium minimizes a different function.

The phenomenon also survives strictly increasing delays on every link. Replace each constant-one delay by $1+\epsilon z$ and the new-link delay by $\epsilon z$. Symmetry gives upper and lower flows $p=\epsilon /(1+3\epsilon )$ after expansion, with middle flow $(1+\epsilon )/(1+3\epsilon )$. The common new delay is $2-\epsilon (1-\epsilon )/(1+3\epsilon )$, while the old delay was $3/2+\epsilon /2$. For $\epsilon =1/10$, these are $251/130>31/20$. Thus the example does not depend on interpreting increasing delays as merely nondecreasing.

Let the bank account be $B_r=R^r$, where $R>0$ is the one-period riskless gross return. In the binomial market, $S_{r+1}$ is either $u{S}_r$ or $d{S}_r$, with $0<d<1<u$ and both successors having positive physical probability. The information at time $r$ consists of the first $r$ moves. A trading strategy chooses its holdings using only this information. A self-financing portfolio funds rebalancing from its current value; there is no external contribution.

Absence of arbitrage requires $d<R<u$. If $R\le d$, borrowing to buy the stock yields a nonnegative gain, strictly positive on the up branch; if $R\ge u$, shorting the stock and investing its price yields the reverse arbitrage. When $d<R<u$, define the risk-neutral probability in a binomial marketGiving each successive up move conditional probability $q$ defines an equivalent martingale measure $Q$, since every finite path has positive probability and ${\mathbb{E}}_Q[S_{r+1}\mid {\mathcal{F}}_r]=R{S}_r$.

For a contingent claim with successor values $V_u,V_d$ at a node of current stock value $s$, solve the two replication equations. The number of shares and current cash value areThen $\Delta us+RC=V_u$ and $\Delta ds+RC=V_d$, so the replicating strategy costsHold $C/B_r$ bank-account units over that period. Starting with the terminal payoff and applying these equations backwards supplies an adapted self-financing strategy replicating every path-dependent contingent claim. This proves market completeness. A different claim price would permit an arbitrage by buying the cheaper claim or replica and selling the dearer one. Iterating the backward pricing relation gives the unique risk-neutral pricing formulaThe physical up probability affects real-world frequencies but does not enter this replication price.

For a terminal payoff $f(S_n)$, write $k=n-r$. Its current price is the restriction to the available nodes of the functionIf $f$ is convex, each summand is convex in $s$ and each weight is positive; summing their defining convexity inequalities proves that $g_r$ is convex. This provides an explicit convex extension between the actual stock nodes, so “convex on the nodes” is unambiguous. If $f$ is strictly convex, each positive scaling preserves strict convexity, so $g_r$ is strictly convex as well.

For the replicating portfolio in a binomial market, the stock holding isFor $r+1<n$, let $F=g_{r+2}$. The next down and up holdings are the secant slopes of $F$ on the adjacent intervals with endpoints $d^{2}s,uds,u^{2}s$:For any convex function and $a<b<c$, its defining inequality at $b=(1-t)a+tc$ rearranges to $(F(b)-F(a))/(b-a)\le (F(c)-F(b))/(c-b)$. The inequality is strict for a strictly convex function. Applying this to the three stock values orders the two next holdings. Meanwhile the backward pricing relation gives, by subtracting its values at $us$ and $ds$,The coefficients are strictly positive and sum to one. Therefore the current share holding lies between the next two holdings:Both inequalities are strict for a strictly convex payoff. For an affine payoff the share holding is constant, explaining the required weak interpretation. These are numbers of shares, not the fraction of portfolio wealth invested in the stock.

For maximization of $f(x)$ subject to $g_j(x)\le 0$ and $h_k(x)=0$, the Lagrangian sufficiency theorem says: if a feasible $x^{\ast }$ globally maximizes $L(x)=f(x)-{\sum }_j{\lambda }_j{g}_j(x)+{\sum }_k{\nu }_k{h}_k(x)$, where ${\lambda }_j\ge 0$, and ${\lambda }_j{g}_j(x^{\ast })=0$, then $x^{\ast }$ globally maximizes $f$ over the feasible set. Indeed, at every feasible $x$,This requires a global maximum of the optimization Lagrangian; a stationary point alone is not sufficient without additional concavity or another justification.

Put $q=p/(p-1)$ and $C=({\sum }_i|a_i{|}^q{)}^{1/q}$. If every $a_i=0$, the maximum is zero and every feasible vector is optimal. Otherwise setSince $p(q-1)=q$, ${\sum }_i|x_i^{\ast }{|}^p=1$. For $g(x)={\sum }_i|x_i{|}^p-1$, the optimization Lagrangian is $L(x)={\sum }_i{a}_i{x}_i-\lambda g(x)$. Its gradient vanishes at $x^{\ast }$ becauseThe function ${\sum }_i|x_i{|}^p$ is a strictly convex function for $p>1$, so $L$ is a strictly concave function. Its supporting-hyperplane inequality proves that this stationary point is its global maximum. Complementary slackness and feasibility hold, so the sufficiency theorem applies. Substitution givesThe maximizing vector is unique when $a\ne 0$. It is the norming vector for Holder inequality, and the value is the corresponding dual norm.

Use finite sets of links $J$, source-sink pairs $S$, and admissible routes $R$, with at least one route for each pair. Route $r$ carries aggregate flow $x_r$. The link-route incidence matrix has $A_{jr}=1$ if route $r$ uses link $j$ and zero otherwise; repeated traversals, if allowed, are counted with their multiplicity. The source-sink route incidence matrix has $H_{sr}=1$ if $r$ serves pair $s$. Thus $y=Ax$ gives link throughputs and $f=Hx$ gives source-sink demands. Write $R_s$ for the routes serving $s$ andA Wardrop equilibrium routes positive flow only on minimum-delay routes:This is a nonatomic equilibrium: an individual infinitesimal user's route change does not alter the aggregate link delays.

For fixed nonnegative demand $f$, the feasible route-flow set $\{x\ge 0:Hx=f\}$ is a nonempty product of finite-dimensional simplexes and hence a compact set. The Beckmann potentialis continuous, so it attains a minimum over this feasible set. Each primitive is a strictly convex function, since its derivative $D_j$ is continuous and strictly increasing. Its route-flow derivative is exactly the corresponding route delay:If a minimizer had positive flow on $r$ and a lower-delay alternative $q\in R_s$, transferring a small amount from $r$ to $q$ would give directional derivative $L_q-L_r<0$, contradicting minimality. Hence every minimizer is a Wardrop equilibrium.

Conversely, let $x$ be a Wardrop equilibrium and $z$ any feasible competitor. Convexity givesFor each $s$, subtract ${\lambda }_s$ inside this sum. The demand constraint makes ${\sum }_{r\in R_s}{\lambda }_s(z_r-x_r)=0$, and the remaining terms are nonnegative: used routes have $L_r-{\lambda }_s=0$, while unused routes have $x_r=0$, $z_r\ge 0$ and $L_r-{\lambda }_s\ge 0$. Thus $V(Az)\ge V(Ax)$. We have proved both existence and the optimization characterization.

Strict convexity in the link vector makes $y$ unique: two different minimizing link vectors would have a feasible midpoint of strictly smaller potential. Thus link delays and the minimum route delays at the Wardrop equilibrium are also unique. The route vector need not be unique, because different route decompositions may have the same $Ax$ and $Hx$. For example, two successive stages with two parallel links at each stage have four routes. With unit demand and link delay $D(u)=u$, the vectorsall give throughput $1/2$ on each of the four links and delay one on every route. This exhibits route-flow nonuniqueness at a Wardrop equilibrium. The equilibrium link throughputs are unique; the individual route flows need not be.

For elastic demand, make the usual physical assumptions explicit: delays are nonnegative on $[0,\infty )$, every route is nonempty, and $B_s:[0,\infty )\to [0,\infty )$ is finite, continuous and strictly decreasing. PutThe limit exists by monotonicity; it need not be zero. The inverse demand function $P_s$ is continuous, strictly decreasing, satisfies $P_s(M_s)=0$, and tends to infinity as $v\downarrow {\ell }_s$.