Convex optimization

Convex optimization minimizes a convex objective over a convex feasible set.

For a saddle point problem ${\min }_u{\max }_v\{F(u)+⟨Du,v⟩-G(v)\}$, one update ordering isThe proximal operators treat both nonsmooth convex terms, while the extrapolation $2u^{k+1}-u^k$ couples the primal and dual variables. The primal objective is $F(u)+G^{\ast }(Du)$, with $G^{\ast }$ the convex conjugate. A dual-first ordering is obtained by exchanging roles; consistent indexing is needed when comparing the formulas.

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.

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.

A nonzero $u$ satisfying this relation, with $Ku\ne 0$, generalizes the eigenfunction of an absolutely one-homogeneous functional to the quadratic geometry induced by the forward map. Pairing with $u$ yields $\lambda =J(u)/\Vert Ku{\Vert }^2$. With unit data norm it is a generalized singular vector. If $\lambda >0$, $0\le \alpha \lambda \le 1$ and the exact data are $Ku$, the vector $(1-\alpha \lambda )u$ minimizes the quadratic variational regularization objective. Substitute its raywise subgradient into the subgradient optimality condition. Every minimizing branch has the same predicted data, and injectivity of $K$ gives equality of vectors. The Bregman distance along this ray is zero even though the reconstruction is shrunk. For nonnegative $J$ the branch continues as $(1-\alpha \lambda {)}_{+}u$; nonnegativity supplies $0\in \partial J(0)$ for the threshold argument.

Background on these generalized singular vectors: Benning and Burger, Ground States and Singular Vectors of Convex Variational Regularization Methods.

Optimization of a linear function subject to affine constraints and membership in a closed convex cone. Choosing the positive semidefinite cone gives semidefinite programming; other choices include copositive optimization and completely positive optimization. Dual cones produce scalar-product bounds on feasible objectives.

Exactly one of the two displayed systems is feasible. Closedness of finitely generated cones and the Fenchel-Moreau theorem applied to a cone's indicator functional provide a proof through its polar cone. It yields a nonnegative multiplier certificate when a finite system of linear inequalities is inconsistent.

Such a vector certifies that $Cx\le d$ has no solution: the nonnegative weighted sum of the constraints would give $0\le d^{T}y<0$. Conversely, Farkas lemma supplies one whenever the system is inconsistent.

An interior-point method solves constrained mathematical optimization problems by maintaining variables in the interiors of their feasible cones or inequality domains. Barrier derivatives are defined there, and damped Newton methods keep subsequent iterates in their domains. A central path gives a family of barrier-regularized optima whose duality gap approaches zero; a conic phase-I problem can supply a strict feasible starting point.

An auxiliary conic optimization problem searches for strict feasibility before following a central path. Given $e\in \mathrm{int}K$, minimizing $t$ subject to $Ax-b+te\in K$ and $t\ge -1$ has a strict feasible start for sufficiently large $t$. Any feasible solution with $t<0$ certifies $Ax-b\in \mathrm{int}K$. If the original problem is strictly feasible, a small negative $t$ is feasible. Equality constraints and dual feasibility require their corresponding auxiliary procedures.

A convex three-times differentiable barrier $F$ is self-concordant whenA barrier of parameter $\nu$ additionally satisfies $|DF(x)[h]|\le \sqrt{\nu D^{2}F(x)[h,h]}$ and diverges at the domain boundary. Logarithmically homogeneous cone barriers satisfy $F(tx)=F(x)-\nu \log t$. The orthant barrier $-{\sum }_i\log x_i$ has parameter equal to the dimension, while the Lorentz-cone barrier $-\log (t^2-\Vert z{\Vert }^2)$ on $t>\Vert z\Vert$ has parameter two. Their Hessians define Dikin ellipsoids and control interior Newton steps.

A cone barrier with this scaling law satisfies $⟨\nabla F(s),s⟩=-\nu$ and $\nabla F(ts)=t^{-1}\nabla F(s)$. Therefore a central path with $y=-\mu \nabla F(s)$ has primal-dual gap $\nu \mu$. A product of orthant and Lorentz cone canonical barriers adds their parameters.

For a logarithmically homogeneous barrier on a proper cone, the convex conjugate with reversed argument defines a barrier on the interior dual cone. The inverse gradient relation makes $y=-\mu \nabla F(s)$ equivalent to $s=-\mu \nabla F_{†}(y)$. This gives a joint primal-dual central path without assuming the barrier is identical on a self-dual cone.

For a nondegenerate self-concordant barrier, the open local Hessian ballis contained in its barrier domain. This is the Dikin ellipsoid. It supplies a quantitative way to ensure that a damped Newton method stays interior, without relying on Euclidean distance to a possibly curved boundary.

For a strictly feasible primal-dual conic optimization problem and a logarithmically homogeneous barrier, the central path consists of solutionsThe primal-dual gap is $⟨s,y⟩=\nu \mu$. Existence requires appropriate feasibility and boundedness hypotheses, rather than merely a full-rank constraint matrix. Linearizing these equations gives a central-path Newton system.

At a target barrier parameter $\mu$, let $r_p=Ax-b-s$, $r_d=A^{\top }y-c$, $r_c=y+\mu \nabla F(s)$. The Newton direction solvesFull column rank of $A$ and a positive-definite barrier Hessian give a positive-definite reduced matrix. Backtracking must keep both cone variables interior; solving the linear equations alone does not guarantee that a full step stays inside the cones.

For ${\min }_x{c}^{\top }x$ subject to $Ax-b\in K$, the Lagrangian dual problem is ${\max }_y{b}^{\top }y$ subject to $A^{\top }y=c$ and $y\in K^{\ast }$. At feasible primal-dual points, the gap is $⟨Ax-b,y⟩\ge 0$. A self-dual cone has $K^{\ast }=K$, but self-duality alone does not imply feasibility or strong duality.

Conic optimization using the completely positive cone. For a real symmetric matrix $Q$, the trace-normalized program $\min \{⟨Q,X{⟩}_F:X\in {\mathrm{CP}}_n,\mathrm{tr}X=1\}$ minimizes a weighted average of nonnegative-unit-vector Rayleigh quotients. The weights are the squared norms of the factors in $X={\sum }_j{x}_j{x}_j^T$. Hence a minimizing rank-one factor attains the same value as the original orthant minimum.

Conic optimization using the copositive cone. The constraint $Q-\lambda I\in {\mathrm{COP}}_n$ supplies an exact reformulation of a Rayleigh quotient minimum on the nonnegative orthant. Exact conic formulation does not itself provide an efficient membership algorithm.

Let $\alpha =\min \{x^{T}Qx:x\ge 0,\Vert x{\Vert }_2=1\}$ for a real symmetric matrix $Q$. Compactness gives attainment. Homogeneity shows $Q-\lambda I$ is a copositive matrix exactly when $\lambda \le \alpha$, provingIts conic program dual is the trace-normalized completely positive optimization problem. A minimizing vector gives $X=x{x}^T$, which certifies equality and dual attainment directly. In general $\alpha$ differs from the unrestricted smallest eigenvalue.

Robust optimization chooses a decision while accounting for every parameter in a prescribed uncertainty set. A worst-case maximization takes the form ${\sup }_x{\inf }_{r\in \mathcal{U}}F(x,r)$ with the decision chosen before the uncertain parameter. With affine dependence on the uncertainty, the support function and linear programming duality often replace the inner optimization by explicit constraints.

Worst-case linear revenue over a polyhedral uncertainty set is optimized by the linear programHere ${\Delta }_n$ is the probability simplex. Finite decisions are exactly its intersection with $\mathrm{range}{P}^T$. If this intersection is empty, all decisions have worst-case value $-\infty$ and the displayed linear program is infeasible; its supremum over the empty feasible set is also $-\infty$. Full column rank of $P$ suffices to make all simplex decisions finite.

A polyhedral uncertainty set is specified by finitely many linear inequalities. The displayed centered example is the inverse image of a box under a linear map. It is nonempty because it contains $r_0$, and contains every line $r_0+td$ with $d\in \ker P$. Consequently it need not be bounded when $P$ is rank deficient. Its supremum norm constraint is equivalent to $-1\le P(r-r_0)\le 1$.

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

The infimal convolution is $(E\square F)(u)={\inf }_v\{E(v)+F(u-v)\}$. It optimizes a decomposition of $u$ between two costs. It is convex when both costs are convex functions, and its convex conjugate is $E^{\ast }+F^{\ast }$ whenever the extended-real operations are well defined.

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.

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 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 rate allocation is proportionally fair when the sum of proportional changes toward any feasible competitor is nonpositive. If route $r$ has $n_r$ identical active flows, this condition is ${\sum }_r{n}_r({\tilde{x}}_r-x_r)/x_r\le 0$ and is equivalent to maximizing weighted logarithmic utility subject to capacity constraints.

For the four routes consisting of adjacent pairs of a unit-capacity four-cycle, put $P=n_1+n_3$, $Q=n_2+n_4$, and $N=P+Q$. Every active route in the first group has total service $P/N$, and every active route in the second has total service $Q/N$. Its per-flow rate is this total divided by its active flow count.

The utility ${\sum }_r{n}_r\log x_r$ sums logarithmic utilities over individual flows. Its first-order condition gives proportional fairness. Its negative is a strictly convex function on active flow rates, giving uniqueness of those rates on a convex set of feasible allocations.

A semidefinite program optimizes a linear function subject to equalities between affine functions and positive semidefinite matrix inequalities. It generalizes linear programming: a diagonal matrix is a positive semidefinite matrix exactly when its diagonal entries are nonnegative. Matrix trace expresses the objective as $⟨C,X⟩=\mathrm{tr}(CX)$ for real symmetric matrices.

For real symmetric $A$, replace sign-vector lifts $x{x}^T$ by all matrices in the elliptope:Every sign vector gives a feasible rank-one matrix with the same objective, so the relaxed maximum is an upper bound. The omitted rank-one condition is substantive: an arbitrary feasible Gram matrix need not come from signs.

Replacing $x{x}^T$ by a general positive semidefinite matrix relaxes maximization of $\Vert x{\Vert }_2^2$ subject to $|a_i^{T}x|\le 1$. The relaxed value is an upper bound because $x{x}^T$ has trace $\Vert x{\Vert }_2^2$ and satisfies the same quadratic constraints. Both problems are unbounded if the $a_i$ fail to span the ambient space. If they span it, $H={\sum }_i{a}_i{a}_i^T$ is positive definite and ${\lambda }_{\min }(H)\mathrm{tr}X\le \mathrm{tr}(HX)\le m$, proving boundedness and attainment of the relaxation.

Use an orthogonal eigendecomposition $X=V\Lambda V^T$ and a vector $\xi$ of independent Rademacher random variables. Because $\Lambda$ is diagonal and ${\xi }_j^2=1$, every sign vector gives $\Vert \hat{x}{\Vert }_2^2=\mathrm{tr}X$, without taking an expectation. If the scaling denominator $M$ is positive, then $x$ satisfies every slab constraint and $\Vert x{\Vert }_2^2=\mathrm{tr}X/M^2$. Under spanning constraints and positive trace, $M>0$ automatically. A nonzero $\hat{x}$ with $M=0$ instead certifies an unbounded direction.

For spanning slab normals, apply the maximum of finitely many Rademacher linear forms bound to $u_i=(V{\Lambda }^{1/2}{)}^T{a}_i$, whose squared norms are $a_i^{T}X{a}_i\le 1$. Some sign vector has scaling denominator squared at most $2\log (2m)$. Rademacher rounding for a semidefinite relaxation then produces a feasible vector of squared norm at least the displayed fraction of the SDP optimum. This is an existence guarantee from the probabilistic method.

A water-filling algorithm allocates a fixed resource among concave-return channels by choosing one Lagrange multiplier and setting each allocation to a thresholded expression. The multiplier is adjusted until the allocations sum to the resource budget.

To maximize ${\sum }_i\log ({\alpha }_i+x_i)$ for positive baselines, nonnegative allocations and a positive budget $B$, the KKT conditions equalize the shifted values on allocated coordinates. The unique water level solves ${\sum }_i(\tau -{\alpha }_i{)}_{+}=B$. Inactive coordinates have baselines at least the water level. Strict convexity of the negative objective ensures uniqueness, and sorting the baselines gives an efficient water-filling algorithm.

Coordinate descent minimizes an objective by repeatedly optimizing one coordinate, or one block of coordinates, while holding all others fixed. Exact coordinate minimization is especially simple for separable penalties and quadratic objectives.

For a function $f$ on a real vector space, its convex conjugate isWhen $f$ is differentiable and strictly convex, the maximizing point satisfies $p=\nabla f(x)$.

For an increasing concave utility on positive wealth, its utility conjugate uses the indicated supremum and is a convex function of the positive price variable. If $F(x)=-U(x)$ on positive $x$, extended by infinity elsewhere, then $\hat{U}(y)=F^{\ast }(-y)$. Under the Inada conditions its optimizer is the inverse marginal utility, and its derivative is the negative of that optimizer. The sign convention is part of the definition.

For an increasing strictly concave differentiable utility satisfying Inada conditions, its utility conjugate has a unique optimizer $I(y)=(U^{\prime }{)}^{-1}(y)$ and derivative $-I(y)$. The dual is strictly decreasing and strictly convex. Twice differentiability of the dual additionally follows when $U^{\prime \prime }$ exists and is strictly negative everywhere. Strict concavity alone allows $U^{\prime \prime }$ to vanish and does not imply this additional assertion.

For $f(x)=x\log x$ on $x>0$, strict convexity and the stationary condition $p=1+\log x$ give the displayed convex conjugate for every real $p$. Biconjugation recovers $f$ on its original positive domain. Its closed extended-real extension has value zero at zero and infinity on negative arguments.

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.

If $g(x)=\lambda f(x-x_0)-\mu$ with $\lambda >0$, substitution into the supremum defining the convex conjugate givesThe positivity of $\lambda$ allows it to pass through the supremum without reversing it. Negative scaling need not obey this rule for the convex conjugate, even when a formal stationary-value transform does.

For a differentiable strictly concave function $f$ whose derivative is a bijection of $\mathbb{R}$, defineThe unique minimizing point is $h(z)$, and $g^{\prime }=h$ follows by comparing minimizers at adjacent arguments, even when $h$ is not differentiable. This dual is concave and equals $-(-f{)}^{\ast }(-z)$ in terms of the convex conjugate. If $f^{\prime \prime }<0$, then $g^{\prime \prime }=1/f^{\prime \prime }(h)$. For $f(s)=cs-s^2/2$, $g(z)=-(z-c{)}^2/2$.

Suppose $f(0)=0$, $f^{\prime }(0)=c$, $h=(f^{\prime }{)}^{-1}$ is differentiable, and $k_{-}<h^{\prime }/2<k_{+}<0$. Then $h(c)=g(c)=0$ for the concave Legendre dual $g$, andIntegrate the derivative bounds from $c$ to $z$, then integrate $g^{\prime }=h$. Multiplying the first inequality by a negative $z-c$ reverses both comparisons. A bound valid without cases is $|h(z)|\le -2k_{-}|z-c|$.

Maximize $px-x^2/2$ over $|x|\le 1$. The maximizer is $x=\max (-1,\min (p,1))$, giving the displayed Huber loss. The indicator functional of a constraint set is zero on the interval and infinity outside; it is not the zero-one indicator used in measure theory.

A proper lower-semicontinuous convex functional on a real Banach space equals its biconjugate, with the canonical embedding in the bidual understood. One inequality follows from the Fenchel–Young inequality; separation of a point below the closed convex epigraph gives the opposite inequality. This is the closed-convex analogue of recovering a function from all its affine supporting functions.

For a proper extended-real function with an affine minorant, biconjugate gives its greatest lower-semicontinuous convex minorant. Geometric separation of its epigraph turns containing closed half-spaces into affine lower bounds. Vertical half-spaces are recovered by adding multiples of a domain-separating inequality to one fixed affine minorant.

For a proper convex function $f$ and its convex conjugate $f^{\ast }$,Equality holds exactly when $p\in \partial f(x)$, or equivalently $x\in \partial f^{\ast }(p)$.

For a proper convex function $\Phi$ and its convex conjugate ${\Phi }^{\ast }$, this gap is nonnegative by the Fenchel–Young inequality. It vanishes exactly when $y\in \partial \Phi (x)$. Its integral against a transport plan is the difference between the half-squared-distance cost and the value of the integrable Kantorovich potentials $u=|x{|}^2/2-\Phi$, $v=|y{|}^2/2-{\Phi }^{\ast }$.

For a convex function $f$, the subdifferential at $x$ isThe point $x$ minimizes $f$ exactly when $0\in \partial f(x)$.

For a proper convex function finite at $x$, global minimality is equivalent to $0\in \partial f(x)$. This follows immediately from the defining subgradient inequality. Combined with a subdifferential sum rule, it converts a convex minimization problem into an inclusion, for example the equation defining a proximal operator.

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 a convex function and $\tau >0$, the forward step is the set-valued explicit update $F_{\tau f}(x)=\{x-\tau p:p\in \partial f(x)\}$. It reduces to the usual gradient step when differentiable. In contrast, a backward step uses a subgradient at the new point and is the proximal operator for a proper closed convex function.

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 a proper lower-semicontinuous convex functional on a real Hilbert space, $p\in \partial J(u)$ means $⟨v,p⟩-J(v)\le ⟨u,p⟩-J(u)$ for all $v$. Taking the supremum gives equality in the Fenchel–Young inequality: $J(u)+J^{\ast }(p)=⟨u,p⟩$. Apply the same argument to $J^{\ast }$ and use the Fenchel-Moreau theorem $J^{\ast \ast }=J$ to obtain the reciprocal subgradient condition.

For a finite convex function $h:\mathbb{R}\to \mathbb{R}$, the function $f(x)=h(c^{T}x+b)$ is convex. The subgradient inequality gives $c\partial h(u)\subseteq \partial f(x)$, where $u=c^{T}x+b$. Conversely, every subgradient $g$ of $f$ annihilates $\ker c^T$, because $f$ is constant on lines in those directions. For $c\ne 0$, write $g=cv$ and test the subgradient inequality at $y=x+(t-u)c/\Vert c{\Vert }_2^2$; this proves $v\in \partial h(u)$. For $c=0$, $f$ is constant and both sides are $\{0\}$ since a finite convex function on the real line has a nonempty subdifferential everywhere.

The subdifferential of the L1 norm consists of vectors $z$ with $z_j=\mathrm{sgn}({\beta }_j)$ when ${\beta }_j\ne 0$ and $z_j\in [-1,1]$ when ${\beta }_j=0$. These coordinate conditions give the Karush-Kuhn-Tucker conditions for Lasso and Square-root Lasso.

For proper convex functions under a standard relative-interior qualification,In particular, if $f$ is differentiable at $x$, then $\partial (f+g)(x)=\nabla f(x)+\partial g(x)$.

A functional $J$ is absolutely one-homogeneous when $J(cu)=|c|J(u)$ for every scalar $c$. For a convex such functional,

Let $K:U\to V$ be a bounded linear operator from a real Banach space to a real Hilbert space, and let $J$ be a proper lower-semicontinuous convex absolutely one-homogeneous functional on $U$. The normalization and source relation imply $\lambda =J(u_{\lambda })$ by the Euler identity for a convex one-homogeneous functional. For the norm penalty $J(u)=\Vert u\Vert$ on a Hilbert space, its nonzero-point subgradient is $u/\Vert u\Vert$. Hence $K^{\ast }K{u}_{\lambda }=u_{\lambda }/\Vert u_{\lambda }{\Vert }^2$: $v=u_{\lambda }/\Vert u_{\lambda }\Vert$ is a right singular vector with singular value $\sigma =1/\Vert u_{\lambda }\Vert$, and $K{u}_{\lambda }$ is the corresponding left singular vector. Thus the definition recovers the ordinary operator singular-vector relation using the one-homogeneous norm penalty. Uniqueness of the vector from its data requires extra hypotheses on $K$ and $J$.

For an absolutely one-homogeneous functional $J$ that is convex and $p\in \partial J(u)$,The subgradient inequality at zero gives $⟨p,u⟩\ge J(u)$, and at $2u$ gives the reverse inequality. This is an Euler identity that needs no differentiability.

A nonzero vector $f$ is an eigenfunction of an absolutely one-homogeneous convex functional $J$ with eigenvalue $\lambda$ when $\lambda f\in \partial J(f)$. This nonlinear analogue of an eigenvector underlies exact shrinkage formulas for several variational flows and proximal maps.

For a real matrix $P$, exactly one of the following holds: there is $\varphi$ with $P\varphi \ge 0$ and $P\varphi \ne 0$, or there is $q>0$ with $P^{T}q=0$. Separating $\mathrm{Im}P$ from the standard simplex proves the result; $q$ may then be normalized to sum to one.

For a convex set $C$ and a differentiable convex objective $F$, projected gradient descent uses

The projected subgradient method minimizes a possibly nonsmooth convex function over a closed convex set $C$ by iterating $x_{i+1}={\Pi }_C(x_i-t_i{g}_i)$ with $g_i\in \partial f(x_i)$. Nonexpansiveness of Euclidean projection onto a convex set and the subgradient inequality give its basic convergence bound.

If $\Vert \nabla F(x_i)\Vert \le G$ and $\Vert x_1-x_{\ast }\Vert \le D$, thenIt follows by expanding the squared distance after each projected step, using nonexpansiveness of projection, summing the resulting inequalities, and applying convexity.

The step size of an iterative optimization algorithm controls the distance moved in one update. Convergence conditions balance sufficient progress against instability from steps that are too large.

For a proper lower-semicontinuous convex function $f$, the proximal operator is ${\mathrm{prox}}_f(y)=\arg {\min }_x\{f(x)+\Vert x-y{\Vert }^2/2\}$. Its optimality condition is $y-x\in \partial f(x)$.

The proximal map of $\tau \Vert \cdot {\Vert }_2$ sends $x$ to $(1-\tau /\Vert x{\Vert }_2{)}_{+}x$, with zero assigned at $x=0$. This removes vectors inside the radius-$\tau$ ball and shortens all larger vectors by a fixed radial distance. It is useful for groupwise sparsity.

On a Banach space one can define the set of minimizers of $E(x)+\Vert x-q{\Vert }^2/2$, but existence and uniqueness need additional geometry or coercivity hypotheses. The optimality condition is $0\in \partial E(x)+\mathcal{J}(x-q)$, with the duality mapping $\mathcal{J}=\partial (\Vert \cdot {\Vert }^2/2)$. The Hilbert completion-of-square shift by a dual vector does not generalize unchanged. On $({\mathbb{R}}^2,\Vert \cdot {\Vert }_1)$ with $E(x)=x_1+x_2$ and $q=0$, every $x_1,x_2\le 0$ with $x_1+x_2=-1$ is a minimizer; the vector $(-1,-1)$ is not one.

For a real Hilbert space, $E(x)=\alpha J(cx-y)+⟨x,z⟩$, $\alpha >0$ and $c\ne 0$, identify $z$ with its vector by the Riesz representation theorem. Completing the square in $\Vert x-q{\Vert }^2/2+⟨x,z⟩$ shifts the input to $q-z$. Substitute $v=cx-y$ and multiply by $c^2$ to obtain the displayed formula, valid also for negative $c$. If $c=0$ and $J(-y)<\infty$, the answer is $q-z$; if $J(-y)=\infty$, the objective is identically infinite and no proper proximal problem remains.

The Moreau envelope of a proper closed convex function isIt is differentiable even when $f$ is not, with $\nabla M_{t}f(x)=[x-{\mathrm{prox}}_{tf}(x)]/t$ and $1/t$-Lipschitz gradient.

For $r=\Vert x{\Vert }_2$, the Moreau envelope of the Euclidean norm is $r^2/(2\tau )$ when $r\le \tau$ and $r-\tau /2$ otherwise. Its gradient is $x/\tau$ in the core and $x/r$ outside. The approximation error is between zero and $\tau /2$.

For proper lower semicontinuous convex functions, the Moreau envelope has gradient $\nabla f_{\tau }=(I-{\mathrm{prox}}_{\tau f})/\tau$. This follows by subgradient inversion under convex conjugacy and the quadratic conjugate. Firm nonexpansiveness of the proximal residual makes the gradient $1/\tau$-Lipschitz continuous.

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.

For a nonempty closed convex set $C$, the squared-distance function is the Moreau envelope of its indicator functional of a constraint set. It is convex and differentiable withand this gradient is one-Lipschitz.

The squared distance to a convex set is the infimal convolution of the set's indicator functional of a constraint set and the half-squared Hilbert space norm. Its convex conjugate is the sum of the half-squared norm and the support function of the set.

For $t>0$, the generalized Moreau decomposition is ${\mathrm{prox}}_{tf}(y)=y-t{\mathrm{prox}}_{t^{-1}{f}^{\ast }}(y/t)$, where $f^{\ast }$ is the convex conjugate.

For a nonempty closed convex set $C$, the Moreau decomposition and ${\sigma }_C^{\ast }={\iota }_C$ give ${\mathrm{prox}}_{t{\sigma }_C}(y)=y-t{\Pi }_C(y/t)$.

The proximal gradient method minimizes $g+h$, where $g$ has an $L$-Lipschitz gradient and $h$ is convex with a tractable proximal operator, by $x_{r+1}={\mathrm{prox}}_{\alpha h}(x_r-\alpha \nabla g(x_r))$. A standard choice $0<\alpha \le 1/L$ gives objective error $O(1/r)$ in the general convex case.

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.

For $f(x,y)=h(x,y)+\varphi (y)$, where $h$ is convex with an $L_h$-Lipschitz gradient and $\varphi$ is convex, use a proximal $y$-step for the full section and an explicit $x$-step for $h$. Monotonicity of the two selected subgradients of $\varphi$ combines with cocoercivity of $\nabla h$ to make the full update firmly nonexpansive for $0<\tau L_h\le 1$. Existence of a minimizer then gives convergence, even though the full objective is not smooth.

For two mixed points with difference $(p,q)$ and gradient difference $(a,b)$, the input difference is $(p,q+\tau b)$ and the output difference is $(p-\tau a,q)$. Their squared-norm difference is $-2\tau (⟨p,a⟩+⟨q,b⟩)+{\tau }^2(\Vert a{\Vert }^2-\Vert b{\Vert }^2)$. This exact identity is a reusable way to prove averagedness without assuming the two block maps are individually nonexpansive.