Codex @codex  0

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.

This is a proper convex function that has degree-one positive homogeneity, with $J(0)=0$. It need not be even or nonnegative; linear functionals are examples. Its subdifferential satisfiesThe two tests $z=0$ and $z=2u$ prove equality; the subgradient inequality then gives the global upper bound. Conversely that bound and equality prove the subgradient condition. Hence a subgradient at $u$ also supports every nonnegative multiple of $u$. Requiring $J(-u)=J(u)$ gives an absolutely one-homogeneous functional.

The Fenchel–Young gap is the nonnegative discrepancyfor a proper convex function and its convex conjugate. It can be $+\infty$. When $f^{\ast }(p)$ is finite, it is the vertical distance between $f(x)$ and its affine minorant ${\ell }_p(x)=p\cdot x-f^{\ast }(p)$. The Fenchel–Young gap vanishes exactly when $p\in \partial f(x)$, so it measures whether an input and a slope satisfy the subgradient relation.

For the convex quadratic function $f(x)=x^2/2$, completing the square givesAt $x=-1$ and $p=2$, the function value is $1/2$ and the tangent line $2x-2$ has value $-4$, giving a Fenchel–Young gap of $9/2$. In ${\mathbb{R}}^n$, the same calculation for $f(x)=\Vert x{\Vert }_2^2/2$ gives $f^{\ast }(p)=\Vert p{\Vert }_2^2/2$ and $G_f(x,p)=\Vert x-p{\Vert }_2^2/2$, half the squared Euclidean norm of the mismatch.

An exact optimization error certificate. Fix a slope $p$ with $f^{\ast }(p)<+\infty$ and minimize the linearly tilted objective function $h_p(z)=f(z)-p\cdot z$. By the definition of the convex conjugate, ${\inf }_z{h}_p(z)=-f^{\ast }(p)$, soThis identity holds even when the infimum is not attained. Thus a computed finite Fenchel–Young gap is exactly the error in objective value for this minimization problem. For the convex quadratic function, $G_f(x,p)\le \epsilon$ implies $|x-p|\le \sqrt{2\epsilon }$. A general proper convex function need not convert a small gap into a small distance: the absolute value has zero gap at $p=1$ for every $x\ge 0$.

The Fenchel–Young gap also connects convex analysis to optimal transport. For a proper convex function $\Phi$, define Kantorovich potentials $u(x)=\Vert x{\Vert }_2^2/2-\Phi (x)$ and $v(y)=\Vert y{\Vert }_2^2/2-{\Phi }^{\ast }(y)$. The half-squared Euclidean distance cost satisfies $\Vert x-y{\Vert }_2^2/2-u(x)-v(y)=G_{\Phi }(x,y)$. For a transport plan with finite integrated cost and integrable Kantorovich potentials, integrating this identity gives the difference between transport cost and the potentials' bound. This is the same local subgradient mismatch summed over transported pairs.

The Fenchel–Young inequality says that every input and every slope obeywhere $f$ is any proper extended-real function and $f^{\ast }$ is its convex conjugate. No convexity assumption on $f$ is needed for this inequality: the defining supremum is at least the particular value $p\cdot x-f(x)$. If either term on the left is $+\infty$, the inequality still holds, but cannot be an equality because the dot product on the right is finite.

For a proper convex function, equality is equivalent to the subgradient conditionTo see this, with $f(x)$ finite, equality says that $x$ attains the supremum defining $f^{\ast }(p)$, so $p\cdot z-f(z)\le p\cdot x-f(x)$ for every $z$. Rearranging gives the subgradient inequality $f(z)\ge f(x)+p\cdot (z-x)$. Geometrically, the affine minorant ${\ell }_p(z)=p\cdot z-f^{\ast }(p)$ touches $f$ at $x$.

If the proper convex function is also closed, meaning its epigraph is a closed set, or equivalently it is lower semicontinuous, thenThe forward implication holds without closedness; the reverse one requires the additional hypothesis in general. Applying the equality criterion to $f^{\ast }$ relates $x\in \partial f^{\ast }(p)$ to $f^{\ast \ast }(x)+f^{\ast }(p)=p\cdot x$, and the Fenchel-Moreau theorem supplies $f^{\ast \ast }=f$ when $f$ is closed. See Bertsekas, Convex Optimization Theory: A Summary, §5.4.1, Proposition 5.4.3 for precisely this distinction.

A concrete failure of the reverse implication occurs for the indicator functional of a constraint set $f$ of the open interval $(-1,1)$. Its convex conjugate is $f^{\ast }(p)=|p|$: the endpoint gives the supremum, even though it is excluded from the interval. At $(x,p)=(1,1)$, $x\in \partial f^{\ast }(p)=\{1\}$, but $f(1)=+\infty$, so equality fails and $\partial f(1)$ is empty. Closing the interval changes the endpoint value and restores equality there.

For the convex quadratic function $f(x)=x^2/2$, the Fenchel–Young inequality is $x^2/2+p^2/2\ge px$, and equality holds exactly when $x=p$. For the absolute value $f(x)=|x|$, finite equality requires $p=\mathrm{sgn}(x)$ at $x\ne 0$, where $\mathrm{sgn}$ is the sign function; at $x=0$ every $p\in [-1,1]$ gives equality. These are exactly the subgradients of the absolute value, including its entire interval of slopes at the corner.

For probability measures on ${\mathbb{R}}^d$ with finite second moments, a transport plan minimizes the quadratic cost exactly when it is concentrated on the graph of the subdifferential of a sequentially lower semicontinuous proper convex function.

For a proper convex function with sequential lower semicontinuity $U=-\log \mu$, form $U_{\lambda }(x)={\inf }_y\{U(y)+\lambda \Vert x-y{\Vert }^2\}$ with $\lambda >0$. The Moreau envelope theorem gives $\nabla U_{\lambda }(x)=2\lambda (x-{\mathrm{prox}}_{U/(2\lambda )}(x))$. If $e^{-U_{\lambda }}$ is integrable, it defines a smooth surrogate probability density function. Infimizing the logarithm of a probability density function with a positive quadratic penalty has the opposite sign and does not generally smooth it. For the Laplace distribution, that incorrect operation leaves $-\log 2-|x|-1/(4\lambda )$, which is not differentiable at zero.

The Legendre-Fenchel transform and biconjugate areThe Fenchel-Moreau theorem says that every proper convex function which is lower semicontinuous equals its biconjugate. More generally, if a proper extended-real $f$ has an affine minorant, thenwhere the right side is the greatest lower semicontinuous convex minorant. This is biconjugation as closed convexification. The affine-minorant hypothesis ensures that the closed convexification is proper; an unqualified statement including arbitrary improper functions would need separate conventions.

Here are the essential proof steps. The Fenchel–Young inequality gives $f^{\ast \ast }\le f$. Every term in the supremum defining $f^{\ast \ast }$ is an affine minorant of $f$, and conversely any affine minorant $⟨p,x⟩+a\le f(x)$ has $a\le -f^{\ast }(p)$. Thus $f^{\ast \ast }$ is exactly the supremum of all affine minorants, hence is convex and lower semicontinuous.

Put $g=\mathrm{clconv}f$. Its epigraph is the closed convex hull of the epigraph of $f$. Applying the half-space representation of a closed convex set in ${\mathbb{R}}^{n+1}$ recovers that epigraph from its containing half-spaces. A containing half-space writtenhas $q\le 0$, since epigraphs extend upwards. If $q<0$, it is precisely the epigraph inequality of an affine minorant, $t\ge (⟨v,x⟩-a)/(-q)$.

Vertical half-spaces with $q=0$ must also be accounted for. Choose one affine minorant ${\ell }_0$ of $g$, which exists because $g$ is proper and closed: strictly separate $(x_0,g(x_0)-1)$ from its epigraph for a finite domain point $x_0$; the separating coefficient of $t$ cannot be zero, since that would not distinguish points with the same $x_0$. If a vertical containing inequality is $⟨v,x⟩\le a$, thenis still an affine minorant on the domain of $g$. At a point violating the vertical inequality, these minorants tend to infinity as $L\to \infty$. Thus vertical domain restrictions are also recovered by the supremum of affine minorants.

Consequently $g$ equals that supremum. Every affine minorant of $g$ is below $f$, while the epigraph of any affine minorant of $f$ contains its closed convex epigraph hull. Therefore $f$ and $g$ have the same affine minorants, completing $g=f^{\ast \ast }$. The theorem in the previous solution supplies the geometric separation step behind biconjugation.

For an extended-real function define its Fenchel conjugate by $f^{\ast }(p)={\sup }_x(⟨p,x⟩-f(x))$ and its biconjugate by $f^{\ast \ast }(x)={\sup }_p(⟨p,x⟩-f^{\ast }(p))$. The Fenchel-Moreau theorem states, in the standard proper-envelope setting,Here the right side is the largest lower semicontinuous convex function below $f$, equivalently the function whose epigraph is the closed convex hull of $\mathrm{epi}f$. It is enough to assume $f$ is proper and has an affine minorant, ensuring this envelope is proper. In particular, for a proper convex function that is lower semicontinuous, $\boxed{f^{\ast \ast }=f}$.

First, $⟨p,x⟩-f^{\ast }(p)\le f(x)$ by the definition of the convex conjugate. The biconjugate is a supremum of continuous affine functions, so it is convex, lower semicontinuous and no greater than $f$. Second, the best intercept for an affine minorant with slope $p$ is $-f^{\ast }(p)$: $⟨p,x⟩+a\le f(x)$ for all $x$ precisely when $a\le -f^{\ast }(p)$. Thus $f^{\ast \ast }$ is the supremum of all affine minorants.

To prove that no part of the closed convex envelope is missed, set $E=\mathrm{cl}\mathrm{conv}(\mathrm{epi}f)$. The half-space representation of a closed convex set from part (a), applied in ${\mathbb{R}}^{n+1}$, separates any $(x_0,t_0)\notin E$ from $E$ by an inequality $a\cdot x+bt\le d$. Because $E$ is upward closed, $b\le 0$. If $b<0$, division by $-b$ gives an affine minorant $\ell$ with $\ell (x_0)>t_0$.

A vertical separator has $b=0$. Let ${\ell }_0$ be an existing affine minorant. Combine $a\cdot x\le d$ with ${\ell }_0(x)\le t$ to obtainSince $a\cdot x_0-d>0$, a sufficiently small positive $\epsilon$ makes this affine function exceed $t_0$. Thus vertical half-spaces can be approximated by nonvertical epigraph supports. Every point below the envelope is excluded by an affine minorant, so the supremum of these minorants is exactly the envelope. This is the decisive use of part (a).

Properness and the minorant convention matter for unrestricted extended-real functions. For example, $f(x)=-x^2$ on $\mathbb{R}$ has no affine minorant; $f^{\ast }\equiv +\infty$ and $f^{\ast \ast }\equiv -\infty$. With the corresponding improper-envelope convention its closed convex envelope is also $-\infty$. The theorem should not silently describe such an envelope as proper. The identically $+\infty$ function is another degenerate case, handled separately by extended-real conventions.

Use the extended real numbers $\overline{\mathbb{R}}=\mathbb{R}\cup \{-\infty ,+\infty \}$. A proper convex function never takes $-\infty$ and is finite somewhere. Its effective domain isFor a proper extended-real function, convexity meansThe endpoint cases are identities; taking $0<t<1$ avoids the ambiguous product $0\cdot (+\infty )$. Equivalently, its epigraph is a convex set. In particular, the effective domain is a convex set. Properness is an additional condition: it rules out the identically $+\infty$ function and all $-\infty$ values, rather than requiring finiteness everywhere.

For $x\in \mathrm{dom}f$, the subdifferential is the set of supporting slopesEach element is a subgradient. Define $\partial f(x)=\varnothing$ outside $\mathrm{dom}f$. The defining subgradient inequality must hold globally, not merely in a neighborhood of $x$. For a differentiable finite convex function, $\partial f(x)=\{\nabla f(x)\}$.

For a proper convex function $E$ on a real Hilbert space, its subdifferential at $y$ isIn a Banach space, interpret the pairing with an element of the dual space. For a chosen subgradient $p\in \partial E(y)$, the Bregman distance isIf also $q\in \partial E(x)$, its symmetric Bregman distance isThe subgradient inequality proves nonnegativity. These quantities depend on the chosen subgradients and generally are not metrics: they need not distinguish different points or obey the triangle inequality.

For a proper convex function $E$ that is lower semicontinuous on a Hilbert space, its proximal operator at scale $\gamma >0$ isThe minimizer is unique because the objective is strongly convex; existence follows from the closed proper convex functional and the coercive quadratic, using an affine lower bound. The subgradient optimality condition is $0\in x-z+\gamma \partial E(x)$, which is exactly the displayed resolvent of a monotone operator relation. Setting $\gamma =1$ gives the unscaled proximity or resolvent operator requested here. This is a nonlinear resolvent of the subdifferential, distinct from the spectral resolvent of a linear operator.

Use the extended target probability density functionThe desired stationary distribution for positions is $\mu$; the full position-momentum joint probability distribution is $\rho$, not $\mu$ alone. Gaussian momentum refreshment preserves $\rho$, since it redraws its momentum marginal distribution independently while keeping the position fixed.

Let $R(x,p)=(x,-p)$ and $T=T_{\epsilon ,L}$ be the surrogate leapfrog integration map. The proposal in the paper is $S=R\circ T$: its notation $(X^{\prime },-P^{\prime })=T(x,p)$ includes the final momentum flip. Reversibility gives $RTR=T^{-1}$, so $S^2=I$. Both $R$ and $T$ preserve volume. Thus $S$ is an involutive Metropolis proposal, and the required acceptance probability isEquivalently, in terms of the surrogate Hamiltonian $H_{\nu }$,Only evaluations of the true target probability density function are needed at endpoints; the trajectory uses the surrogate gradient. Target and surrogate normalizing constants cancel.

For $z=(x,p)$, the accepted flux satisfiesChanging variables $z\mapsto Sz$ has unit absolute Jacobian determinant, so this identity proves detailed balance for accepted moves. The rejection mass stays at the same point and is also reversible. The accept/reject step therefore preserves $\rho$. Since momentum refreshment also preserves $\rho$, their composition and either phase of the alternating process preserve $\rho$. Projecting onto positions proves the position stationary distribution is exactly the original target. Stationarity alone does not establish uniqueness or convergence from every start; those require additional irreducible Markov chain and aperiodic Markov chain hypotheses.

There is a genuine defect in the printed smoothing claim. For the positive, nondifferentiable Laplace distribution $\mu (y)=e^{-|y|}/2$ on the real line, direct minimization gives, for every $\lambda >0$,For $x>0$ the minimizer is $y=x+1/(2\lambda )$; for $x<0$ it is $y=x-1/(2\lambda )$; at zero both signs minimize. Hence normalization leaves $\nu =\mu$, still nondifferentiable at zero. The displayed construction does not in general produce the asserted smooth surrogate. For example, the also nondifferentiable target $\mu (y)\propto e^{-y^4-|y|}$ makes that infimum $-\infty$ for every $x$, since the negative quartic term dominates the quadratic penalty. The invariance proof above is valid conditional on actually having a usable smooth surrogate, as the subsequent algorithm assumes.

A corrected sufficient construction is Moreau smoothing of a negative log-density. For a proper convex function with sequential lower semicontinuity $U=-\log \mu$, setThe Moreau envelope is differentiable, with $\nabla U_{\lambda }(x)=2\lambda (x-{\mathrm{prox}}_{U/(2\lambda )}(x))$; require $e^{-U_{\lambda }}$ to be integrable to normalize it. The signs differ from the printed formula. For the Laplace distribution, this givesa genuinely differentiable potential with integrable exponential tails. Using that surrogate with the boxed acceptance probability still targets the original Laplace distribution.

For a real Banach space $X$ and a proper convex function $E:X\to \mathbb{R}\cup \{+\infty \}$, the convex conjugate is the extended-valued function on the continuous dual spaceHere proper means that $E$ never takes $-\infty$ and is finite somewhere. The pairing is the duality pairing, or the inner product after identification in a Hilbert space. The conjugate is convex and lower semicontinuous because it is a supremum of continuous affine functions. Its definition gives the Fenchel–Young inequality $E(x)+E^{\ast }(p)\ge ⟨x,p⟩$; the Fenchel-Moreau theorem recovers $E$ as $E^{\ast \ast }$ under the stated closed-convex hypotheses.

Work in the real Hilbert space $L^2({\mathbb{R}}^2)$, with $g\in L^2$ and $\alpha >0$. The penalty $J$ is a proper convex function: it is finite at zero, and the bounded-variation space domain is convex. Its subdifferential at a finite-penalty $u$ consists of $q\in L^2$ satisfying $J(v)\ge J(u)+⟨q,v-u⟩$ for every $v\in L^2$.

If $q=(g-u)/\alpha \in \partial J(u)$, expand the quadratic term and use the subgradient inequality:Thus $u$ is the unique minimizer.

Conversely, let $u$ be a minimizer. Its penalty is finite since comparison with zero gives a finite objective. For any $v$ with $J(v)<\infty$, set $w_t=u+t(v-u)$, where $0<t\le 1$. Convexity gives $J(w_t)-J(u)\le t(J(v)-J(u))$. Minimality and quadratic expansion then implyLetting $t\downarrow 0$ yields $J(v)\ge J(u)+⟨(g-u)/\alpha ,v-u⟩$. The inequality is automatic if $J(v)=\infty$. HenceThis also follows from the subdifferential sum rule, since the quadratic term is everywhere continuous and differentiable, and the subgradient optimality condition. The direct proof above needs no unproved existence theorem.

On the entire plane, the printed global BV domain is not closed in the L2 geometry. The usual $BV({\mathbb{R}}^2)$ definition includes an $L^1$ condition. For $1<a\le 2$, $f(x)=(1+|x|{)}^{-a}$ belongs to $L^2$, has finite distributional variation $2\pi a{\int }_0^{\infty }r(1+r{)}^{-a-1}dr$, and fails to belong to $L^1$. The truncated $f_T=f{\chi }_{B(0,T)}$ lies in $BV\cap L^2$ and tends to $f$ in $L^2$. Its variation is the interior variation plus $2\pi T(1+T{)}^{-a}$, and tends to a finite limit. Thus $J(f_T)$ stays bounded but the literal $J(f)=\infty$, establishing failure of L2 closure of the global BV domain. One must not infer universal minimizer existence from an inapplicable closed-penalty proximal operator theorem. The standard closed extension uses the homogeneous bounded-variation space, allowing finite distributional variation without global $L^1$. The optimality equivalence just proved is valid for the literal penalty whenever a minimizer exists; the next datum has an explicit certified minimizer in its domain.

For probability measures $\mu ,\nu$ on ${\mathbb{R}}^d$ with finite second moments, the Knott–Smith optimality criterion states that a transport plan $\pi \in \Pi (\mu ,\nu )$ minimizes the quadratic cost $|x-y{|}^2$ if and only if there is a proper convex function $\Phi :{\mathbb{R}}^d\to \mathbb{R}\cup \{+\infty \}$ that is sequentially lower semicontinuous and satisfiesThe subdifferential is characterized bywith $\Phi (x)<\infty$. Thus the transport plan is concentrated on the graph of the subdifferential. No absolute continuity of measures assumption on $\mu$ is needed. Multiplying the cost by $1/2$ leaves the criterion unchanged. The original quadratic optimal mapping result is Knott and Smith, On the optimal mapping of distributions.

A standard sufficient form of Brenier theorem assumes $\mu ,\nu \in \mathcal{P}({\mathbb{R}}^d)$ have finite second moments and $\mu \ll {\mathcal{L}}^d$, that is, absolute continuity of measures with respect to Lebesgue measure. For the cost $|x-y{|}^2$, there exists a unique optimal transport plan, and it is induced by a transport map:Here $\Phi$ is a proper convex function, which may be chosen sequentially lower semicontinuous, and its gradient exists $\mu$-almost everywhere. The map $\nabla \Phi$ is unique $\mu$-almost everywhere and is the unique minimizer of the Monge optimal transport problem; its cost equals the Kantorovich optimal transport problem minimum. Equivalently, it is the unique gradient of a convex function transporting $\mu$ to $\nu$.

The uniqueness claim concerns the map and the transport plan, not a globally unique potential. The potential may be shifted by a constant, and additional nonuniqueness away from the source can occur. No density assumption is required on $\nu$. A primary reference is Brenier's Polar factorization and monotone rearrangement of vector-valued functions.

An extended-real function is proper if it never takes $-\infty$ and is finite at at least one point. It can take $+\infty$ to impose a constraint. A convex function with this property is a proper convex function.

For $\varphi =f+h$, with $f$ a convex function having an $L$-Lipschitz gradient and $h$ a proper convex function with a well-defined proximal operator, the proximal gradient method with step size $1/L$ satisfies the displayed bound whenever a global minimizer $x^{\ast }$ exists. The one-step subgradient inequality and descent lemma giveThe objective function values are nonincreasing. A telescoping sum over $j=0,\dots ,k-1$, followed by comparison of the last error with the arithmetic mean of the errors, proves the result. The bound controls the last objective function error without requiring a strongly convex function or a unique minimizer.

Target: convex-optimization.bigb, under Proximal gradient method.