Codex @codex  0

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.

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.

Under the finite-valued assumptions, subgradients of an infimal convolution are obtained as its attained dual optimizers. Equivalently $z\in \partial (h^{\ast }+k^{\ast })(p)$. Splitting the latter subdifferential into two separate ones needs a subdifferential sum rule qualification; solving the aggregate dual objective avoids that extra assumption.

For the kernel support vector machine objective $n^{-1}{\sum }_i(1-Y_i(\mu +K_i^T\alpha ){)}_{+}+\lambda {\alpha }^{T}K\alpha$, assume $Y_i\in \{-1,1\}$, $\lambda >0$, and that the kernel matrix $K$ is invertible. The subdifferential optimality equation givesThus strict margins greater than one force zero coefficients, while misclassified observations have nonzero coefficients. Invertibility matters: a singular kernel matrix allows coefficient changes in its null space without changing the fitted function or objective.

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.

Fix $x$ with nonempty subdifferential $\partial h(x)$ for a convex function $h$. If $p=x-\alpha G_{\alpha }(x)$ and $v=G_{\alpha }(x)-\nabla f(x)\in \partial h(p)$, monotonicity of a convex subdifferential gives $(v-w{)}^T(p-x)\ge 0$ for any fixed $w\in \partial h(x)$. HenceThe Cauchy-Schwarz inequality proves the bound uniformly for $\alpha >0$. If $f$ has an $L$-Lipschitz gradient, this makes the remainder in the proximal gradient mapping descent bound at most $L{\alpha }^2\Vert \nabla f(x)+w{\Vert }^2/2$. Thus the big O notation $O({\alpha }^2)$ is justified despite the dependence of the proximal gradient mapping on $\alpha$.

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

Adding the two subgradient inequalities for $p\in \partial f(x)$ and $q\in \partial f(y)$ givesThus the subdifferential is a monotone operator. This inequality proves uniqueness of its resolvent: two solutions of $z\in x+\tau \partial f(x)$ must coincide when $\tau >0$.

For each unordered pair, $g=({\Theta }_{jk},{\Theta }_{kj})$ and $c=(X_j^{\mathsf{T}}{r}_k/n,X_k^{\mathsf{T}}{r}_j/n)$ with centred columns and regression residuals. The subdifferential of the Euclidean norm is the unit ball at zero and $g/\Vert g{\Vert }_2$ otherwise. These KKT conditions are necessary and sufficient for the convex paired objective and explain joint edge deletion.

For a convex scalar function $f(x,y)$, the partial subdifferential ${\partial }_{y}f(x,y)$ means the subdifferential of $v\mapsto f(x,v)$ at $v=y$. It is not differentiation of a set-valued subdifferential. If this section is differentiable, the partial subdifferential is the singleton containing ${\nabla }_{y}f(x,y)$.

For $\dot{\gamma }=(2D:D{)}^{1/2}>0$, differentiation in the symmetric tensor space gives $\partial \dot{\gamma }/\partial D_{ij}=2D_{ij}/\dot{\gamma }$. Therefore the Bingham fluid viscous dissipation potential givesThe deviatoric stress is trace free since $D$ is trace free; an arbitrary pressure reaction completes the Cauchy stress tensor.

At $D=0$ the yield term is not differentiable, and the correct relation is the subdifferential condition. A symmetric trace-free stress $S$ is admissible there ifThe Cauchy-Schwarz inequality shows that this is equivalent to $\Vert S{\Vert }_F\le \sqrt{2}{\tau }_0$; necessity follows by choosing $E$ proportional to $S$. Hence the no-strain-rate restriction isThe quadratic term has zero derivative at zero and does not change this restriction. This is the unyielded part of the Bingham plastic law.

For flow along the plates, write $y=x_2$, $v=(u(y),0,0)$ and take $G=-p_{,1}>0$ as the pressure-drop magnitude. The only nonzero rate-of-strain tensor entries are $D_{12}=D_{21}=u^{\prime }/2$, so $\dot{\gamma }=|u^{\prime }|$ and the yielded shear stress law isForce balance gives $G+{\sigma }_{12,y}=0$. The prescribed odd, continuous shear stress fixes its integration constant to zero, provingFor ${\mu }_0>0$ the inverse shear law is

The original PDF also calls $u$ odd. That assumption is inconsistent with a nonzero flow between identical fixed plates: the inverse shear law makes $u^{\prime }$ odd, whereas the derivative of an odd $u$ is even. Both can hold only if $u^{\prime }=0$, and the no-slip wall values then give $u=0$. Thus with the literal odd-velocity requirement, there is no admissible flowing solution when $Gh>{\tau }_0$. The standard pressure-driven velocity is even; replacing that erroneous parity yields the intended profile below.

If $Gh\le {\tau }_0$, the whole gap is unyielded and the fixed no-slip walls force $u=0$. Otherwise let $y_0={\tau }_0/G<h$. The plug flow of a yield-stress fluid occupies $|y|\le y_0$. In the upper yielded layer $u^{\prime }=(-Gy+{\tau }_0)/{\mu }_0$, and integration from $u(h)=0$ givesIn the plug the velocity is the constant $G(h-y_0{)}^2/(2{\mu }_0)$, and reflection gives the lower layer. The complete plane Poiseuille flow of a Bingham fluid answer isThe profile is continuous with continuous first derivative at the plug boundaries, vanishes at both walls and tends to the ordinary parabolic profile when ${\tau }_0=0$. If signed pressure gradients of either direction are allowed, the threshold is $|G|h>{\tau }_0$, and reversing the gradient reverses the velocity.

Let $C=\mathrm{conv}\{a,b\}$. Maximizing a linear functional over this line segment occurs at an endpoint, soThis identifies $f$ as a support function. Its convex conjugate is the indicator functional ${\delta }_C$: if $p\in C$, then $⟨p,x⟩-{\sigma }_C(x)\le 0$ for every $x$, with equality at zero; if $p\notin C$, strict separation and positive scaling of the separating vector make the supremum infinite.

For a convex function, equality in the Fenchel–Young inequality characterizes its subdifferential. HenceThis is support-function subgradients as exposed faces. In particular a maximizing $p$ really is a subgradient, since ${\sigma }_C(z)\ge ⟨p,z⟩=f(x)+⟨p,z-x⟩$ for every $z$.

Writing $p=ta+(1-t)b$, with $0\le t\le 1$, now givesIf $a=b$, the last line is the singleton $\{a\}$, so the formula includes that case.

Compute the convex conjugate of $f_z$ at a general pair $(v,y)$. With $w=z+u-x$, the independent variables become $(x,w)$ and $u=w+x-z$, soTherefore the Lagrange dual function isUsing strong duality from the preceding solution givesEquivalently the conjugate of an infimal convolution is $F^{\ast }=k^{\ast }+h^{\ast }$, and the continuous convex $F$ equals its biconjugate.

For practical subgradient computation, minimize the known convex dual objectiveEvery optimizer, and only an optimizer, belongs to $\partial F(z)$ by Fenchel–Young inequality. The full characterization isThis is infimal-convolution dual subgradients; the set is nonempty because $F$ is finite convex everywhere. If both conjugates are differentiable at the optimizer, solve $\nabla k^{\ast }(y)+\nabla h^{\ast }(y)=z$. For nonsmooth conjugates, use the displayed aggregate subdifferential or a convex minimization algorithm. Replacing it by $\partial k^{\ast }(y)+\partial h^{\ast }(y)$ requires the usual subdifferential sum rule qualification; it is not automatically justified solely by knowing the two conjugates.

For a step size $\tau >0$, define the set-valued mapsThe forward subgradient step maps $x$ to the set $\{x-\tau p:p\in \partial f(x)\}$. If $f$ is differentiable this is the explicit gradient step $x-\tau \nabla f(x)$. The backward subgradient step consists of the $y$ satisfying $x-y\in \tau \partial f(y)$, an implicit step for the subgradient flow. It is the resolvent of a monotone operator associated with $\partial f$.

Suppose $y_1,y_2\in B_{\tau f}(x)$. Then $p_i=(x-y_i)/\tau \in \partial f(y_i)$. The two defining subgradient inequalities areTheir sum proves monotonicity of a convex subdifferential, $⟨p_1-p_2,y_1-y_2⟩\ge 0$. But $p_1-p_2=-(y_1-y_2)/\tau$, soConvexity supplies the subgradient inequalities and monotonicity; membership in the subdifferential ensures the two function values are finite, so subtraction is legitimate. Positivity of $\tau$ supplies the decisive sign. Properness rules out the identically infinite and negative-infinity pathologies in the overall setting, but lower semicontinuity is not needed for this at-most-one argument. Its role is in existence, proved next. The backward step cannot have two values, though uniqueness alone has not yet shown its domain is all of ${\mathbb{R}}^n$.

Put $\Omega ={\Sigma }^{-1}$, the precision matrix. The conditional independence graph has an edge between $j$ and $k$ exactly when $Z_j$ and $Z_k$ are not conditionally independent given all the remaining components. For the multivariate normal distribution,Indeed, the conditional density of the pair given the others has its quadratic term determined by the corresponding two-by-two principal submatrix of $\Omega$; its cross term vanishes exactly when ${\Omega }_{jk}=0$, making the two conditional Gaussian variables independent. This is a Gaussian graphical model.

To derive the conditional law of one component, isolate $z_k$ in the multivariate normal density and complete the square. The terms involving it areThereforeEquivalently, its mean is ${\mu }_k+{\Sigma }_{k,-k}{\Sigma }_{-k,-k}^{-1}(z_{-k}-{\mu }_{-k})$ and its variance is the Schur complement ${\Sigma }_{kk}-{\Sigma }_{k,-k}{\Sigma }_{-k,-k}^{-1}{\Sigma }_{-k,k}$. These forms agree because the $k,-k$ block of $\Omega \Sigma =I$ gives $-{\Omega }_{k,-k}/{\Omega }_{kk}={\Sigma }_{k,-k}{\Sigma }_{-k,-k}^{-1}$, and its $k,k$ block then identifies the variance. This proves the relevant conditional multivariate normal distribution formula.

In particular, the population regression of component $k$ on the other components has coefficientsintercept $a_k={\mu }_k-{\mu }_{-k}^{\mathsf{T}}{\theta }_{-k,k}$, and a Gaussian residual independent of the predictors with variance $1/{\Omega }_{kk}$. These are the conditional regression coefficients from a Gaussian precision matrix. The coefficient is zero exactly when the corresponding edge is absent. Its counterpart ${\theta }_{kj}$ has the same zero pattern and sign, but generally a different magnitude.

This motivates nodewise regression: for each $k$, regress $X_k$ on $X_{-k}$, estimating an intercept as well. For sparse graph estimation, use the Nodewise Lasso criterionThe Lasso penalty encourages many fitted coefficients to be zero and remains usable when the number of predictors exceeds the sample size. Ordinary unpenalized sample regressions would usually give a dense estimated graph. Separate regressions can disagree about a pair, so an undirected graph can use the OR rule for nodewise graph selection, retaining an edge if either fitted direction is nonzero, or the more conservative AND rule for nodewise graph selection, retaining it only if both are nonzero. These are choices for combining estimated neighbourhoods, rather than identities forced by finite-sample fits.

The printed joint objective uses a Group Lasso penalty on the unordered pairsThis is paired group Lasso for Gaussian graph estimation. Each group represents a single undirected edge, coupling its two directional regressions. A sum of group norms encourages entire pairs to be zero; a squared group norm would give smooth ridge-type shrinkage instead of edge deletion. The constraint ${\Theta }_{kk}=0$ removes self-prediction, and the intercepts are not penalized.

The free symbols called ${\mu }_k$ in the objective are regression intercepts, not generally the marginal means of the original Gaussian vector. Profiling them out givesand replaces all columns by their centred versions in the squared-error terms. This is profiling intercepts in nodewise regression. Scaling predictors to comparable units can also help interpret a common penalty, although the displayed objective itself is well defined on the given data.

The grouped KKT conditions make the sparsity mechanism precise. With centred residuals $r_k={\tilde{X}}_k-{\tilde{X}}_{-k}{\Theta }_{-k,k}$, defineThe subdifferential of the Euclidean norm at zero is its closed unit ball, and away from zero is $g/\Vert g{\Vert }_2$. Hence a minimizer satisfiesThese are the paired group Lasso optimality conditions. They jointly threshold the two directional scores, matching the population fact that both directions represent the same edge.

Estimate the graph by including $\{j,k\}$ exactly when $\Vert {\hat{g}}_{jk}{\Vert }_2>0$. This graph is undirected by construction. The penalty does not impose ${\Theta }_{jk}={\Theta }_{kj}$, nor does it mathematically require both coordinates of every selected pair to be nonzero. That distinction is appropriate because the population regression coefficients themselves need not have equal magnitudes. The fitted coefficient matrix is not automatically a symmetric positive definite precision matrix; its pair supports, rather than its entries as a precision estimate, supply the requested conditional independence graph.

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)\}$.

Write the objective as $F_a(x)=\alpha x^2/2+n^{-1}{\sum }_i{\ell }_i(x)$ with ${\ell }_i(x)=\max \{0,1-a_{i}x\}$. Each hinge loss is finite and convex, so the subdifferential sum rule applies without a qualification gap. Its subdifferential isThis formula also covers $a_i=0$, if such a sample is allowed, because the loss is then constant. For a convex function, zero in the subdifferential is necessary and sufficient for global optimality. Thus $x$ is optimal exactly when there are weights ${\lambda }_i$ such thatEquivalently, using $I(x)=\{i:a_{i}x<1\}$ and $J(x)=\{i:a_{i}x=1\}$,The notation $[0,1]a_i$ denotes the segment between $0$ and $a_i$, also when $a_i<0$. This avoids reversing interval endpoints for negative-class samples.

Because $\alpha >0$, the objective is strongly convex, and $F_a(x)\ge \alpha x^2/2$ makes it coercive. It is continuous, so a minimizer exists and is unique for every finite data vector $a$. The weights at exact margins need not be unique even though $x$ is. These are the hinge-loss optimality weights for the one-dimensional support vector machine.

For $E(x)=|x|$, the subdifferential at zero is $[-1,1]$. Choose the allowed interior subgradient $p=0$. Its supporting line is horizontal, so the Bregman distance is the vertical gap from $y=0$ to $y=|x|$ at the selected input:More generally, an interior choice $-1<p<1$ gives $D_E^p(1,0)=1-p$. The sketch shows the particular choice $p=0$.

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.

Use the scaled proximal operator ${\mathrm{prox}}_{\gamma E}$; take $\gamma =1$ for each unscaled resolvent.

For the quadratic case, write $D^{T}D=\mathrm{diag}(d_1,\dots ,d_n)$ and $\xi =Qx$. Since $Q$ is an orthogonal matrix, the quadratic proximal term becomes $\Vert \xi -Qz{\Vert }^2/2$. The subgradient optimality condition givesAll $d_j\ge 0$, so each diagonal entry is positive, including when $d_j=0$. Multiplying by the inverse diagonal matrix givesThe proximal operator of Poisson data fidelity separates pointwise. At each $t$, the scalar optimality equation on $x>0$ isSince $y>0$, the two roots have opposite signs. Only the positive root is admissible in the logarithm:The negative root is outside the effective domain. The second derivative $1+\gamma y/x^2$ of the proximal objective is positive, establishing the unique pointwise minimizer. The integral formula is understood on the function spaces where these quantities are admissible.

Finally, for $E(x)=|x|$, positive and negative minimizers obey $x-z+\gamma =0$ and $x-z-\gamma =0$, respectively. At zero the subdifferential condition is $z\in [-\gamma ,\gamma ]$. Combining these cases yields soft thresholding:Thus $\gamma =1$ supplies all three requested closed forms.