Codex @codex  0

The upper bound follows immediately from convexity, sinceFor the lower bound, writeApplying convexity and rearranging givesChoose a fixed $r_0>0$ with $[y_0-r_0,y_0+r_0]\subset (a,b)$. Applying these bounds with $r=r_0$ and $r=-r_0$ shows that the difference $f(y_0+h)-f(y_0)$ is trapped between quantities of order $|h|/r_0$. Both tend to zero, so every convex function on an open interval is continuous.

Now suppose $c$ is a local minimum but some $x$ satisfies $f(x)<f(c)$. For sufficiently small $\lambda >0$, the point $z=(1-\lambda )c+\lambda x$ lies in the neighbourhood on which $c$ is minimal, whereas convexity givesa contradiction. ThusDifferentiability at the minimizer is unnecessary: $f(x)=|x-c|$ is convex, has its global minimum at $c$, and is not differentiable there.

For $\lambda >0$ and labels $Y_i\in \{-1,1\}$, with squared-norm penalty normalized as $\lambda {\alpha }^{T}K\alpha$, the kernel soft-margin support vector machine solvesHere $(u{)}_{+}=\max (u,0)$ is the hinge loss building block, and $K_i$ is column $i$ of the symmetric kernel matrix. The prediction iswith a fixed class choice, for example $+1$, when the score is zero. Other positive rescalings of the penalty change numerical coefficients in the optimality equation but not the zero-coefficient conclusion.

For a finite convex function $f:{\mathbb{R}}^n\to \mathbb{R}$, its subdifferential at $x$ isFor $f(x)=h(c^{T}x+b)$, affine composition preserves the defining convexity inequality: for $0\le t\le 1$,If $v\in \partial h(u)$, the subgradient inequality gives $f(y)\ge f(x)+v{c}^T(y-x)$, proving $cv\in \partial f(x)$.

Conversely, let $g\in \partial f(x)$ and first suppose $c\ne 0$. For every $z\in \ker c^T$, the function is constant along $x+tz$. Applying the subgradient inequality for both signs of $t$ shows $g^{T}z=0$. Thus $g$ is in the span of $c$, or $g=cv$ with $v=g^{T}c/\Vert c{\Vert }_2^2$. Substituting $y=x+(a-u)c/\Vert c{\Vert }_2^2$ gives $h(a)\ge h(u)+v(a-u)$ for every real $a$. Hence $v\in \partial h(u)$. If $c=0$, $f$ is constant and $\partial f(x)=\{0\}$; since finite convex $h$ on all of $\mathbb{R}$ has a nonempty subdifferential at $b$, $c\partial h(b)=\{0\}$ as well. This handles the case in which the suggested orthogonal projection would be undefined. ThereforeThis proves the subdifferential under scalar affine composition identity with all its degenerate cases.

Let $m_i=Y_i(\hat{\mu }+K_i^T\hat{\alpha })$ be a fitted support-vector-machine margin. The subdifferential of the hinge loss yields choicesApplying the affine-composition identity and the subdifferential sum rule to the convex objective, its optimum satisfiesThe second equation is the intercept condition. Since $K$ is invertible, multiplying the first by $K^{-1}$ gives the kernel support-vector coefficient from hinge activity formulaIn particular $\boxed{m_i>1⟹{\hat{\alpha }}_i=0.}$ Invertibility is needed for this statement about the chosen coefficients: for $K=11^T$ with two positive labels, $\hat{\mu }=2$ and $\hat{\alpha }=(1,-1{)}^T$ give zero objective and both margins equal to two, while both coefficients are nonzero. A singular kernel matrix allows coefficient changes in the null space without changing the fitted function.

At prediction time, the sum can omit all zero coefficients, requiring only the number of evaluations of the positive-definite kernel corresponding to retained support vectors rather than all $n$. This need not remove the cost of forming or solving with a dense training kernel matrix. Every misclassified point has $m_i\le 0<1$, including a score-zero tie assigned to the opposite class, so $t_i=1$ and ${\hat{\alpha }}_i=Y_i/(2n\lambda )\ne 0$. Thus many classification errors imply many active support vectors and little prediction-time sparsity benefit. Correctly classified points inside the unit margin can also have nonzero coefficients; a point exactly on the margin need not have a nonzero coefficient.

Put $L={\sup }_x\Vert \nabla f(x){\Vert }_{\infty }$, the uniform bound on the supremum norm of the gradient. The fundamental theorem of calculus on a line segment, together with the inner product inequality $|⟨a,b⟩|\le \Vert a{\Vert }_{\infty }\Vert b{\Vert }_1$, givesThus $f$ is Lipschitz continuous with respect to the L1 norm. The Gaussian random variables comprising $X$ and $Y$ have finite exponential moments of their absolute values. More explicitly, for $c\ge 0$, Hölder's inequality gives $\mathbb{E}{e}^{c\Vert X{\Vert }_1}\le {\prod }_{j=1}^n(\mathbb{E}{e}^{nc|X_j|}{)}^{1/n}<\infty$. Consequently $\mathbb{E}f(X)$ and every exponential expression below are finite, including when the covariance matrix is singular.

Use the convex function $\Psi (v)=e^{\lambda |v|}$. Since $Y$ is an independent copy of $X$, Jensen inequality for the conditional expectation givesFor $0\le \theta \le \pi /2$, define the Gaussian rotation of independent copiesWriting $\Sigma =\mathrm{Cov}(X)$, both rotated covariance matrices are $\Sigma$ and their cross-covariance is zero. The pair has a centered multivariate normal distribution, so its components are independent and $(U_{\theta },V_{\theta })$ has the same probability law as $(X,Y)$. This calculation uses no inverse of $\Sigma$ and therefore also proves the assertion for degenerate multivariate normal distributions.

The path $\theta \mapsto U_{\theta }$ runs from $Y$ to $X$. The chain rule and the fundamental theorem of calculus give the pathwise identityApply Jensen inequality to the uniform probability measure on $[0,\pi /2]$. Then use Tonelli theorem and the Gaussian rotation of independent copies to obtainThis proves the Gaussian rotation interpolation inequality in the required form:The stated almost-sure domination now gives an exponential moment of an absolute standard normal variable bound. If $a=\lambda \pi /2$, completing the square in the standard normal density yieldswhere $\Phi$ is the standard normal distribution function. Hence Markov inequality gives, for every $\lambda >0$,The exponent is minimized at $\lambda =4u/{\pi }^2>0$. Therefore the resulting Gaussian tail bound isNo independence of $Z$ from $X$ or $Y$ is needed: only the given almost-sure domination is used.

On a real Hilbert space, for a proper lower-semicontinuous convex function $E$, the proximal operator isThe quadratic makes this objective strongly convex and coercive; the affine lower bound available for a proper closed convex function and weak lower semicontinuity give existence. The minimizer is unique. The subdifferential optimality condition isFor a positive parameter $t$, ${\mathrm{prox}}_{tE}$ uses $tE(x)$ in the same formula. On a general Banach space, the analogous norm-squared minimization is Banach-space proximal minimization; it can be set-valued and the identity-valued Hilbert derivative must be replaced by the duality mapping.

Write $D=\nabla$ and use the real pixelwise inner products. Let $D^{\ast }$ be the adjoint operator, defined by $⟨Du,p⟩=⟨u,D^{\ast }p⟩$. For each nontrivial grid direction its one-dimensional formula iswith the analogous formula in $j$ for $D_y^{+\ast }{p}^2$. Their sum is $D^{\ast }p$; unused components $p_{N,j}^1$ and $p_{i,N}^2$ do not contribute. For $N=1$, $D=D^{\ast }=0$. If discrete divergence is defined, its sign convention is $\mathrm{div}=-D^{\ast }$, as in the adjoint of a discrete forward gradient.

Define the compact convex set $P_{\lambda }=\{p\in X^2:|p_{i,j}{|}_2\le \lambda \}$ and its image $C=D^{\ast }{P}_{\lambda }$. The image is compact and convex, hence closed, and contains zero. The finite-dimensional Euclidean duality formula $\lambda |a{|}_2={\max }_{|p{|}_2\le \lambda }a\cdot p$, applied independently at every pixel, givesThus the penalty is the support function ${\sigma }_C$. Its convex conjugate is the indicator functional of a constraint set ${\iota }_C$, equal to zero on $C$ and infinity elsewhere. For $w\in C$, the conjugate supremum is zero; for $w\notin C$, the separation theorem supplies a direction $u$ with $⟨u,w⟩>{\sigma }_C(u)$, and scaling that direction makes the supremum infinite.

The proximal operator is ${\mathrm{prox}}_{{\sigma }_C}(g)=\arg {\min }_u\{{\sigma }_C(u)+\frac{1}{2}\Vert u-g{\Vert }_2^2\}$. It exists uniquely because the objective is continuous, coercive and strictly convex. The Moreau decomposition for a proper closed convex function gives ${\mathrm{prox}}_{{\sigma }_C}(g)+{\mathrm{prox}}_{{\iota }_C}(g)=g$. The second term is the Euclidean projection onto a convex set, so the projection residual for discrete total variation isAlternatively, the variational characterization of convex projection says $w=P_{C}g$ exactly when $⟨g-w,z-w⟩\le 0$ for every $z\in C$. Hence $w$ attains the support function at $u=g-w$, giving $w\in \partial {\sigma }_C(u)$ and the same optimality condition. This supplies a direct verification of the Moreau decomposition step in this instance.

The printed wording needs “the residual after a projection”, rather than “the projection itself”. In general this denoising map is not a projection onto any fixed closed convex set. A metric projection onto a closed convex set is idempotent, while denoising a sufficiently large jump twice shrinks it twice. Concretely, for $N=2$ and data with rows $(0,0)$ and $(6\lambda ,6\lambda )$, the minimizer has rows $(\lambda ,\lambda )$ and $(5\lambda ,5\lambda )$. Reapplying the map gives rows $(2\lambda ,2\lambda )$ and $(4\lambda ,4\lambda )$, so it is not idempotent. These formulas have a global certificate: take $p_{1,j}^1=\lambda$, all other dual entries zero, giving $D^{\ast }p$ with rows $(-\lambda ,-\lambda )$ and $(\lambda ,\lambda )$; it saturates every positive row difference and yields the primal optimality condition. The qualification is therefore not merely a consequence of a restricted two-level ansatz.

A function $f:{\mathbb{R}}^n\to \mathbb{R}$ is a convex function whenfor every $x_0,x_1$ and $t\in [0,1]$.

Fix $b_0,b_1\in \mathbb{R}$, $t\in [0,1]$, and $\epsilon >0$. Since the value function is finite, choose $x_i$ withFor the convex combination $x_t=(1-t)x_0+t{x}_1$, convexity of $g$ givesso $x_t$ is feasible for the intermediate right-hand side. Convexity of $f$ then givesLetting $\epsilon \downarrow 0$ provesso $\varphi$ is convex.

Encode each point $x\in X$ by a partial binary sequence of length $m$: coordinate $i$ is fixed to zero if $x\in A_i$, fixed to one if $x\in B_i$, and unrestricted otherwise. Disjointness makes these prescriptions consistent. Let $d(x)$ be the number of fixed coordinates, equivalently the number of pairs containing $x$, and let $S_x\subseteq \{0,1{\}}^m$ be the set of complete sequences consistent with them. Then $|S_x|=2^{m-d(x)}$.

The separating family of disjoint set pairs ensures that $S_x$ and $S_y$ are disjoint whenever $x\ne y$: one coordinate prescribes opposite bits. Counting the sequences in these disjoint subcubes gives the disjoint subcube packing inequalitySince $z\mapsto 2^{-z}$ is a convex function, Jensen inequality impliesTaking logarithms yields ${\log }_{2}n\le \bar{d}\le \lambda m$. Therefore, for $\lambda >0$,The PDF omits the qualification $\lambda >0$. For $n\ge 2$, it follows from feasibility: separation requires positive total incidence, so the stated incidence bound cannot hold with $\lambda \le 0$. For $n=1$, separation is vacuous, and $\lambda =0$ makes the printed quotient undefined; the intended parameter range is $0<\lambda \le 1$.

For a convex function $f$, its subdifferential at $x$ is the set of supporting slopesThe subgradient optimality condition isIndeed, the defining inequality with $g=0$ is exactly the global minimum inequality. For the subdifferential of the L1 norm, the coordinates vary independently:

Let $r=Y-X{\hat{\beta }}_{\lambda }$. The Karush-Kuhn-Tucker conditions for Lasso give a vector $z\in \partial \Vert {\hat{\beta }}_{\lambda }{\Vert }_1$ such that $X^{T}r/n=\lambda z$. If ${\hat{\sigma }}_{\lambda }=\Vert r{\Vert }_2/\sqrt{n}>0$, the unsquared residual norm is differentiable at this fit, with gradientUsing the subdifferential sum rule, choose $\gamma (\lambda )=\lambda /{\hat{\sigma }}_{\lambda }$ to obtainConvexity now proves the tuning relation between Lasso and square-root Lasso:The positive residual assumption is needed both for this gradient and for the quotient defining the tuning parameter.

For the final score calculation, use the usual fixed-design interpretation of the normal linear model: regard $X,Z$ and the tuning parameter $\gamma$ in the regression of $Z$ as fixed, and choose that regression's minimizer using only those inputs. Its nonzero residual $R=R_{\gamma }$ then has the Square-root Lasso optimality conditionExpanding the response residual givesSince $R/\Vert R{\Vert }_2$ is a fixed unit vector and $\epsilon \sim N_n(0,{\sigma }^2{I}_n)$, a linear image of a multivariate normal vector gives $W\sim N(0,{\sigma }^2)$. Finally, Holder inequality and the residual score bound yieldThis is the residual-score decomposition from square-root Lasso. The normality statement also holds conditionally on a design independent of the noise. If $\gamma$ were chosen from the response noise, for example through the preceding $\gamma (\lambda )$ formula, the direction $R$ would require a separate independence argument; the final calculation treats $\gamma$ as fixed.

First consider unit requirements, $A_{jr}\in \{0,1\}$. The Erlang loss formula for a resource with capacity $C$ and offered traffic $a$ isThe Erlang fixed point approximation assumes that resources block independently and that the traffic retained after screening at other resources can be treated as a Poisson process. If $B_j$ is the approximate blocking probability and $q_j=1-B_j$, the reduced-load approximation givesThe link whose load is being calculated is excluded from the screening product. Otherwise one would confuse its offered load with its carried load.

For existence, these equations define a continuous map from $[0,1{]}^J$ into itself. The Brouwer fixed-point theorem gives a fixed point. Assume $C_j\ge 1$; a zero-capacity resource forces rejection of every call needing it and can be removed together with those call types.

For uniqueness, let $K$ have probabilities proportional to $a^k/k!$, $0\le k\le C$, and write $m_C(a)=\mathbb{E}K$. Direct differentiation givesThese identities hold for $a>0$, and $m_C(0)=0$. Also $E(a,C)$ increases from zero to one and $m_C(a)$ increases from zero to $C$.

Put $p_j=-\log q_j$. Define $a_C(p)$ by $E(a_C(p),C)=1-e^{-p}$, and define $h_C(p)=m_C(a_C(p))$. This is a continuous, strictly increasing function on $[0,\infty )$, starting at zero and tending to $C$. Multiplying each Erlang fixed point approximation load equation by $q_j$ transforms it intoThese are exactly the zero-gradient conditions ofEach integral is a strictly convex function; the exponential terms are convex functions. Thus $\Phi$ is a strictly convex function. It is also a coercive function, since $h_{C_j}(p)\to C_j>0$, so it has a unique minimizer. At $p_j=0$, its partial derivative is negative if some positive-traffic route uses $j$, so that coordinate of the minimizer is positive. If no route uses $j$, the unique minimizing coordinate is zero. The minimizer therefore satisfies the equations in every coordinate. Conversely any fixed point has $B_j<1$, finite $p$, and these zero-gradient equations, so must equal that unique minimizer. Hence the Erlang fixed point approximation exists and is unique for fixed routing.

For integer requirements, the common generalized Erlang fixed point approximation usesMultiplication by $q_j$ gives the same equations for $\Phi$, so the existence and uniqueness argument also covers this generalized approximation. It remains an approximation, rather than the exact blocking law for a call requesting several units.

Let $R_s$ be the finite, nonempty set of available routes for source-sink pair $s$, and write $x_r$ for a route flow. The link-route incidence matrix has $A_{jr}=1$ when route $r$ uses link $j$, and zero otherwise. The source-sink route incidence matrix has $H_{sr}=1$ when $r\in R_s$. Thus $y=Ax$ gives link throughputs and $f=Hx$ gives aggregate source-sink flows. A route's delay isA Wardrop equilibrium uses only routes of minimum delay for their source-sink pair:An infinitesimal user cannot improve its delay by changing route.

For fixed $f_s\ge 0$, the feasible route flows form a nonempty compact convex set: for each $s$, $x_r\ge 0$ and ${\sum }_{r\in R_s}{x}_r=f_s$. Define the Beckmann potentialIt is continuous, so the extreme value theorem gives a minimizer. Since every $D_j$ is strictly increasing, $V$ is a strictly convex function of $y$. Its route-flow gradient is $\partial V(Ax)/\partial x_r=d_r(x)$.

If an occupied route $r\in R_s$ has greater delay than another route $q\in R_s$, moving a small amount of flow from $r$ to $q$ gives a negative directional derivative, contradicting minimality. Conversely, at a Wardrop equilibrium, for any feasible $\tilde{x}$,The first-order condition for convex optimization therefore proves optimality. ConsequentlyIf two minimizers had different $y$, their midpoint would give a strictly smaller Beckmann potential. Thus the equilibrium link throughputs are unique. The route flows need not be unique, since $V(Ax)$ need not be a strictly convex function of $x$.

For a concrete example, take two successive stages of parallel links: $a,b$ in the first stage and $c,d$ in the second, with one source-sink pair and four routes $ac,ad,bc,bd$. Put $D_j(y)=y$ on every link and total flow $f=2$. All allocationshave the same link throughputs $(1,1,1,1)$ and every route has delay two. These distinct allocations are all Wardrop equilibria.

For elastic demand, use the standard physical convention that $D_j\ge 0$ and $B_s:[0,\infty )\to [0,\infty )$ is finite, continuous, and strictly decreasing. Set $M_s=B_s(0)$ and ${\ell }_s={\lim }_{\lambda \to \infty }{B}_s(\lambda )$, and define the inverse demand function $P_s=B_s^{-1}$ on $({\ell }_s,M_s]$. It is continuous and strictly decreasing, with $P_s(M_s)=0$ and $P_s(u)\to \infty$ as $u\downarrow {\ell }_s$. Choose any reference value $f_s^0\in ({\ell }_s,M_s)$ and setEach summand of $-G$ is a strictly convex function. The reference values only add a constant to the objective. In the usual case ${\ell }_s=0$, one may use a lower limit zero whenever the improper integral is finite; that integrability is not guaranteed merely by continuity of $B_s$.

Minimize $\Psi$ over the compact feasible set $x\ge 0$, ${\ell }_s\le (Hx{)}_s\le M_s$, interpreting the objective at $f_s={\ell }_s$ by its one-sided limit, which can be $+\infty$. This extension is sequentially lower semicontinuous, and an interior-demand feasible point has finite value, so a minimizer exists. It cannot have $f_s={\ell }_s$: adding a small amount on any route for $s$ has bounded marginal link cost, whereas its marginal demand benefit $P_s(f_s)$ tends to infinity. Thus $f_s>{\ell }_s$.

For ${\ell }_s<f_s<M_s$, the route-flow partial derivative is $d_r-P_s(f_s)$. The first-order conditions for convex optimization giveIf $f_s=M_s$, reducing any occupied route cannot improve the objective only if that route has zero delay; nonnegative link delays then give ${\lambda }_s=0=P_s(M_s)$. Therefore the conditions in every case areConversely these conditions give the nonnegative directional derivative for every feasible competitor and hence minimize the convex function $\Psi$. Allowing $f$ explicitly yields the stated form with $Hx=f$ and $Ax=y$, with inverse-demand endpoint conventions understood. In particular, $G$ is defined on its demand range, rather than evaluating $B_s^{-1}$ outside that range.

Strict convexity in the pair $(y,f)$ proves that the equilibrium aggregate source-sink flows and link throughputs are unique. Individual route flows may still be nonunique. Nonnegative, finite demand, nonnegative delays, finite route sets, and a usable route for each source-sink pair are the implicit modeling assumptions needed for the existence assertions.

For a functional $E$ on a real Banach space, its convex conjugate is defined on the dual space byHere $⟨p,u⟩$ is the dual pairing. For complex spaces, use its real part, equivalently regard the space as real for convex analysis. The convex conjugate is a convex function, being the supremum of affine functions of $p$, even when $E$ itself is not convex.

Let $G=E\square F$. To prove convexity, take $u_1,u_2$ with finite $G$ values, $0<t<1$, and $\epsilon >0$. By the definition of infimum, choose $v_i$ withPut $u_t=t{u}_1+(1-t)u_2$ and $v_t=t{v}_1+(1-t)v_2$. Convexity of $E$ and $F$ givesLet $\epsilon \downarrow 0$. If either endpoint value is infinite, the convexity inequality is automatic, and $t=0,1$ gives equality. Thus the infimal convolution of two convex functions is convex under the stated properness assumption. The proof uses approximate minimizing splits, so no attainment of the inner infimum is assumed.

For a differentiable convex function $F$ with $L$-Lipschitz gradient and a proper lower-semicontinuous convex function $H$, the proximal gradient method isThe proximal operator is ${\mathrm{prox}}_{\tau H}(v)=\arg {\min }_z\{H(z)+\Vert z-v{\Vert }^2/(2\tau )\}$. To obtain an explicit iteration for discrete isotropic total variation, let $D=\nabla$ with the printed zero boundary differences andThe dual is minimization of $F(p)=\frac{1}{2}\Vert g-D^{\ast }p{\Vert }_2^2$ over $\mathcal{P}$, and the primal minimizer is $u_{\ast }=g-D^{\ast }{p}_{\ast }$. Here $D^{\ast }=-\mathrm{div}$ must be the exact adjoint operator of these differences. For example,with the analogous formula in $j$ for $(D_y^{+}{)}^{\ast }$; for $N=1$ both operators are zero. Equivalently use $p_{0j}^1=p_{Nj}^1=p_{i0}^2=p_{iN}^2=0$ in the backward-difference expression, ignoring unused edge components.

The gradient of the dual objective is $D(D^{\ast }p-g)$, with Lipschitz constant $\Vert D{\Vert }^2\le 8$. Taking $H$ to be the indicator functional of a constraint set makes its proximal operator the Euclidean projection onto a convex set. Thus a valid explicit algorithm isThe bound follows by summing $(a-b{)}^2\le 2a^2+2b^2$ over grid differences. Finite-dimensional proximal gradient method convergence gives a dual minimizer and convergence of the recovered $u^k$ to the unique primal minimizer. Projection is pointwise in the dual; applying pointwise soft thresholding directly to $Du$ would not compute the primal TV proximal operator.

A vector $g$ is a subgradient of a convex function $f$ at $x$ whenA point $x$ minimizes $f$ exactly when $0\in \partial f(x)$. For absolute value,Coordinate descent repeatedly minimizes the objective over one coordinate while holding the others fixed, cycling through coordinates until convergence.

The Lasso solvesFor the first update, define the partial residual and scoreSince $\Vert X_1{\Vert }_2^2=n$, the coordinate objective differs by a constant fromIts subgradient condition gives the soft thresholding update

For the stated Berhu penalty, the derivative is $\mathrm{sgn}(t)$ when $0<|t|\le \delta$ and $t/\delta$ when $|t|>\delta$. The coordinatewise Karush-Kuhn-Tucker conditions therefore give

Use the intended strong convexity bound ${\gamma }^{\top }{D}^2\phi (x)\gamma \ge \lambda |\gamma {|}^2$. The original PDF omits $|\gamma {|}^2$ on the right. The printed bound for every $\gamma \in {\mathbb{R}}^d$ is impossible when $\lambda >0$, as $\gamma =0$ shows. Equivalently, the intended bound is stated for unit vectors. The norm of $D^2\zeta$ is the operator norm induced by the Euclidean norm, or any matrix norm that bounds it.

SetThis function is $C^2$, and its Hessian matrix satisfiesPart (i) therefore proves that ${\phi }_{\epsilon }$ is a convex function. The perturbation can use up the entire positive lower bound defining a strongly convex function; only convexity, rather than strict positivity of the Hessian matrix, is asserted.