Codex @codex  0

An affine minorant of $f$ is a function $x\mapsto ⟨a,x⟩+b$ that is everywhere at most $f(x)$. Every proper lower-semicontinuous convex function has such a minorant, by separating a point below its closed epigraph. Adding a positive quadratic then yields a coercive function, which establishes existence in proximal minimization.

For a jointly smooth convex function $f(x,y)$, update $y$ implicitly by its proximal minimization at fixed $x$, then update $x$ explicitly with the gradient at the mixed point $(x,y^{+})$. The combined map is $(\tau L/2)$-averaged for $0<\tau L<2$, as follows by applying cocoercivity at two mixed points. Its fixed points are precisely the minimizers. If a minimizer exists, averaged iteration proves convergence.

Choose increasing $R_m\to \infty$ so $H(t)\ge m^2|t|$ whenever $|t|\ge R_m$. Put $\Psi (s)={\sum }_{m\ge 1}(s-R_m{)}_{+}$ for $s\ge 0$. This is nonnegative, increasing and convex. If $m$ terms are active, then $\Psi (s)\le ms\le H(t)$ for $s=|t|$. For every fixed $N$, $s\ge 2R_N$ gives $\Psi (s)\ge Ns/2$, proving superlinearity. Thus a nonconvex superlinear energy lower bound still supplies the convex function needed in the De la Vallée-Poussin criterion. A continuous superlinear function not initially nonnegative can first have its finite global minimum subtracted.

On the whole Euclidean space, an $L$-Lipschitz gradient of a convex function is $1/L$-cocoercive. Subtract the supporting affine function at one point, apply the descent lemma to a gradient step at the other point, then interchange the points and add. The conclusion needs convexity but no second derivative.

The biconjugate of $f$ is the convex conjugate of its convex conjugate:It is the supremum of all affine minorants. For a proper function with an affine minorant, the Fenchel-Moreau theorem identifies it with the closed convex envelope; a proper lower semicontinuous convex function equals its biconjugate.

For a continuously differentiable convex function on ${\mathbb{R}}^n$ with coordinate Lipschitz continuity constants $L_i$, its block coordinate gradient is Lipschitz continuous along each corresponding coordinate subspace, with constant at most $S_{\mathcal{B}}={\sum }_{i\in \mathcal{B}}{L}_i$.

To prove this without assuming a Hessian matrix, put ${\delta }_{\mathcal{B}}={\nabla }_{\mathcal{B}}f(x)-{\nabla }_{\mathcal{B}}f(y)$. Sum the coordinate derivative bound by Bregman divergence over the block, then repeat with $x,y$ interchanged and average:If $x-y$ is supported in the block, the dot product uses only ${\delta }_{\mathcal{B}}$. The Cauchy-Schwarz inequality and cancellation of its Euclidean norm give the result, including the zero case separately. Taking the full block supplies a global Lipschitz gradient constant ${\sum }_i{L}_i$.

Target: convex-optimization.bigb, under Coordinate descent.

On $(0,\infty )$, the Gamma function is the unique positive function $f$ satisfying $f(1)=1$, $f(x+1)=xf(x)$, and the condition that $\log f$ is a convex function. This last condition concerns the natural logarithm of $f$, rather than $f$ itself, and removes the interpolation freedom left by the Gamma function recurrence.^[ref]

Let a real convex function satisfy $|f|\le M$ on the open unit ball of a normed space. For $4r=1-\Vert x\Vert$, points $u,v\in B(x,r)$ satisfy $|f(u)-f(v)|\le (M/r)\Vert u-v\Vert$. Extend the segment from $u$ through $v$ to length $2r$; its endpoint still lies in the domain, and convexity bounds the difference by $2M\Vert u-v\Vert /(2r)$. Reverse $u,v$ for the opposite inequality. Unlike finite-dimensional local continuity theorems, this argument applies in arbitrary dimension because boundedness on a full neighborhood is assumed.

For a convex functional $J$ and $p\in \partial J(v)$, the Bregman divergence isIt is nonnegative but need not be symmetric or satisfy the triangle inequality.

For probability measures on ${\mathbb{R}}^d$ with finite second moments and a source satisfying absolute continuity of measures with respect to Lebesgue measure, the quadratic Kantorovich optimal transport problem has a unique optimal transport plan. It is induced by the gradient of a convex function, which also uniquely solves the Monge optimal transport problem up to a source-null set.

Rigid compartments impose a different constraint: fixed volume rather than fixed pressure. With Helmholtz free energy $F=U-TS$,This follows immediately by differentiating $F=U-TS$ in the chemical potential differential above. It expresses the same chemical potential through the thermodynamic potential appropriate to fixed temperature and volume.

Consider a closed system consisting of two rigid compartments of equal volume $V$, maintained at a common fixed temperature $T$. A valve permits exchange of the same ideal gas; the partition stays in place. Initially $n_A=9\mathrm{mol}$ and $n_B=3\mathrm{mol}$, with conserved total amount of substance $n_{\mathrm{tot}}=12\mathrm{mol}$. These are macroscopic moles, modeled continuously, not twelve individual particles. By the ideal gas law, $p_B/p_A=n_B/n_A=1/3$, so initiallyAt $300\mathrm{K}$ with the stipulated $R$, this is approximately $-2740.311\mathrm{J}\mathrm{mo}{\mathrm{l}}^{-1}$, favoring transfer from A to B.

At fixed $T$ and equal $V$, integrating the ideal-gas chemical potential gives the total Helmholtz free energy, up to a term independent of the allocation,Here $n_{\mathrm{ref}}$ is a positive reference amount of substance; any omitted common term linear in $n_A+n_B$ is constant along this exchange. Let $x=n_A/n_{\mathrm{tot}}$ be the dimensionless fraction in A. The relative Helmholtz free energy then takes the particularly simple formIts derivative along the allowed transfer and its second derivative areThus the Helmholtz free energy is a strictly convex function of the allocation for positive amounts. Its unique minimum has $x=1/2$, or $n_A=n_B=6\mathrm{mol}$, and equal chemical potentials. Initially its excess above this minimum is $n_{\mathrm{tot}}RT[\frac{3}{4}\ln (3/2)+\frac{1}{4}\ln (1/2)]\simeq 3915.474\mathrm{J}$ at $300\mathrm{K}$. Relaxation decreases the total Helmholtz free energy by this amount in the model; the final pressures are also equal because both compartments have the same volume.

The beautiful connection is that the direction of matter exchange and the slope of a free energy curve are the same calculation. The entropy gained by redistributing the ideal gas makes equal allocation favorable here. As with chemical equilibrium, a free energy minimum identifies the favored state, while transport properties determine how quickly it is reached. The fixed-temperature, fixed-pressure Gibbs free energy criterion is summarized in 16.4 Free Energy; the rigid experiment instead uses Helmholtz free energy.

An operator $G$ is $\beta$-cocoercive when $⟨Gz-Gw,z-w⟩\ge \beta \Vert Gz-Gw{\Vert }^2$ with $\beta >0$. This strengthens monotonicity and implies a Lipschitz constant $1/\beta$ by the Cauchy-Schwarz inequality. Gradient maps of smooth convex functions provide an important converse through the Baillon–Haddad theorem.

For proper convex functions whose infimal convolution is well defined, $(f\square g{)}^{\ast }=f^{\ast }+g^{\ast }$. The proof separates a supremum over independent variables after writing $x=u+y$. No attainment of the infimum is needed.

A real convex function locally bounded on an open convex set has a continuous supporting linear functional at every interior point. Apply the dominated Hahn-Banach theorem to its sublinear directional derivative $p_x$ to obtain $l\le p_x$. Increasing secant slopes imply $p_x(z)\le f(x+z)-f(x)$ whenever the endpoint is in the domain. A local Lipschitz continuity bound gives both $l(y)\le L\Vert y\Vert$ and $-l(y)=l(-y)\le L\Vert y\Vert$, proving continuity.

For proper lower semicontinuous convex functions on finite-dimensional Hilbert spaces, a nonempty saddle point set, and constant positive steps satisfying the displayed inequality, the primal-dual hybrid gradient method with extrapolation parameter one converges to a saddle point. The strict condition controls the bilinear coupling by the operator norm. It does not remove the need for existence of a saddle point. The fixed-step theorem and assumptions are recalled in Malitsky and Pock, A first-order primal-dual algorithm with linesearch, Section 1.

Convex analysis studies convex sets and convex functions, including epigraphs, convex conjugates and subdifferentials.

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 linear functional $f$ dominated by a finite real convex function $\varphi$ on a vector subspace $W$ extends with the same domination to the whole real vector space. To add $v\notin W$, choose $g(v)$ between the supremum of $(f(w)-\varphi (w-tv))/t$ and the infimum of $(\varphi (w+sv)-f(w))/s$, over $w\in W$ and $s,t>0$. Convexity, applied to $(s(w_1-tv)+t(w_2+sv))/(s+t)$, makes every lower candidate at most every upper candidate. The candidates at $w=0,s=t=1$ bound the interval by finite numbers. Chain unions preserve domination, so Zorn's lemma gives a full extension. No homogeneity of $\varphi$ is assumed.

The greatest convex function lying below a given function, when such an envelope is considered in the specified domain. A convex combination of phase compositions and their Gibbs free energies constructs candidate mixtures; the equilibrium free energy is their lower convex envelope. For two differentiable coexisting branches, the supporting line is a common tangent.

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.