近端点方法

每一步最小化“原目标加距离惩罚”。原目标鼓励向更低的函数值移动，二次项则提高远离当前点的代价；步长 ${\lambda }_k$ 越大，距离惩罚越弱。

最优性条件在新点 $x_{k+1}$ 计算次梯度，所以更新是隐式的。若 $f(x)=|x|$，子问题可直接用软阈值求解；若变量之间通过复杂损失耦合，计算一次 prox 本身就是一个优化问题。因此算法的每轮成本取决于近端子问题的结构。

在显式存储的 $n$ 维实现中，每个外层步骤调用一次 prox，另需 $O(n)$ 的向量操作与状态存储；prox 自身的时间、工作空间以及近似求解所需的内层精度工作另计。下述各向同性二次函数的缩放更新，以及逐坐标绝对值之和对应的软阈值更新，都可用 $O(n)$ 次算术操作计算。

对 $f(x)=\frac{\mu }{2}\Vert x{\Vert }^2$（$\mu >0$），近端子问题可直接求导，得到

固定步长 $\lambda$ 下，$\Vert x_k\Vert =(1+\lambda \mu {)}^{-k}\Vert x_0\Vert$，序列以几何速度收缩到唯一最小点 $0$。这个计算也说明它不同于梯度步 $x_{k+1}=(1-\lambda \mu )x_k$：前者的分母形式对任意正步长都保持收缩，后者则受稳定步长范围限制。

同一个目标也能看出两种近端算法的差别。在耦合 Lasso 算例理路Lasso 的最优性与对偶间隙Lasso optimality conditions · Lasso duality gap · Lasso primal-dual certificate从残差相关性核验 Lasso 的零与非零坐标，并用可行对偶值认证剩余优化误差。中，取 $f=P$、$x_0=0$、${\lambda }_0=1/3$，整个目标的近端点求解 $\underset{x}{min}\{P(x)+(3/2)\Vert x{\Vert }^2\}$。猜测两坐标均为正，最优性方程为

两坐标确实为正，而且 $A^T(b-Ax)-(1,1)=(19/16,1/16)=3x$，故满足完整的凸最优性条件。这不同于只对 ${\ell }_1$ 取 prox 的近端梯度理路近端梯度法Proximal gradient method对复合目标的光滑项取显式梯度步、对非光滑凸项取隐式近端步的算法。第一步 $(2/3,1/6)$；两者处理同一目标，却解不同的子问题。

步长的累积决定了二次例子能推进多远。若 ${\lambda }_k=2^{-k-1}$，则 $\sum _k{\lambda }_k=1$，而

当 $x_0\ne 0$ 时，迭代始终与最小点保持正距离。统一正下界排除了这种总步长有限的情形；最小点存在则为固定点论证提供目标。

可求和的近端点误差控制的是迭代点，不自动保证近似点的函数值也收敛。例如令 $f={\delta }_{\{0\}}$、${\lambda }_k=1$，每次精确近端点都是零；却可取近似序列 $x_k=2^{-k}$，其逐步近端误差 $2^{-k-1}$ 可求和。序列确实趋于最小点零，但每个 $f(x_k)=+\mathrm{\infty }$。因此要对非精确迭代报告目标值，还需另外保证候选在有效域内并控制函数值误差。

有限维时，近端点方法把凸优化问题理路凸优化问题Convex optimization problem在凸可行域上最小化凸目标且不等式约束为凸函数的优化模型。写成近端算子的固定点迭代；其形式陈述还允许一般 Hilbert 空间。对精确迭代，近端算子的牢固非扩张性给出

每一步都使到任意最小点的距离不增，并控制相邻位移的平方和。若 $f-\mu \Vert \cdot {\Vert }^2/2$ 凸（$\mu >0$），两条带二次余量的次梯度不等式相加，得到 $⟨u-v,p-q⟩\ge \mu \Vert p-q{\Vert }^2$。代入近端关系 $u=(x-p)/\lambda$、$v=(y-q)/\lambda$，再用Cauchy–Schwarz 不等式理路Cauchy–Schwarz 不等式Cauchy–Schwarz inequality · 柯西–施瓦茨不等式内积的绝对值不超过两向量范数之积，且等号精确刻画线性相关。，可得 $\Vert p-q\Vert \le \Vert x-y\Vert /(1+\lambda \mu )$。因此固定步长 prox 的收缩因子为 $1/(1+\lambda \mu )$，Banach 不动点定理理路Banach 不动点定理Banach fixed-point theorem · Contraction mapping theorem完备空间中的统一压缩给出唯一不动点；用几何尾和证明收敛，并把后验误差与残差转成停止证书。进一步给出唯一最小点与几何收敛。

对固定步长的有限维情形，也可直接应用单调算子页的预解迭代收敛定理理路单调算子与极大单调性Monotone operator · Maximal monotone operator · 极大单调算子用图上的内积不等式统一凸次微分与旋转关系，并以极大性保证稳定隐式步对每个输入都有唯一解。，取 $A=\partial f$。Rockafellar 将这一迭代推广到极大单调算子理路单调算子与极大单调性Monotone operator · Maximal monotone operator · 极大单调算子用图上的内积不等式统一凸次微分与旋转关系，并以极大性保证稳定隐式步对每个输入都有唯一解。的 resolvent，从而覆盖变分不等式与鞍点系统。该条目的二维旋转算例完整展示了一个不来自凸次微分的隐式迭代：显式步使长度增长，预解算子却使轨道旋转并收缩到零点。Douglas–Rachford、ADMM 等分裂方法则把相关问题组织成若干较易计算的子步骤，利用各部分的结构降低一次完整近端求解的成本。交替方向乘子法理路交替方向乘子法（ADMM）Alternating direction method of multipliers · ADMM将凸目标拆成两个近端子问题，用乘子累积一致性误差，并以原始与对偶残差检查最优性的算法。具体推导了约束 $x=z$ 下的两次 prox 与乘子更新，并用双残差及 Fejér 不等式证明有限维点收敛；其中的耦合 Lasso 例子可以与本页对整个目标求 prox 的第一步直接比较。

复合凸问题的原对偶系统理路Fenchel 对偶与原对偶单调包含Fenchel duality · Primal-dual monotone inclusion从复合凸问题的相对内部资格推出对偶乘子，以两份 Fenchel 等号认证最优，再构造极大单调系统并手算完整预解轨道。进一步把次微分与斜对称耦合放入乘积空间，在同一个新点求解两行隐式关系。它给出每步可解和有限维整列收敛的完整论证，并把一个具体预解算子消元为区间投影，得到 $(x_k,y_k)=(1-2^{-k},1)$（$k\ge 1$）的轨道。那是整个原对偶系统的 resolvent，其计算成本与对单个函数求 prox 仍需分别判断。

若能分别计算两个单调部分的预解，Douglas–Rachford分裂理路Douglas–Rachford 分裂Douglas–Rachford splitting · Douglas Rachford method · DR splitting分别计算两个极大单调算子的预解，通过反射平均恢复和算子的零点，证明状态与影子点的收敛，并用周期反例说明平均的作用。将两次反射的复合做平均，并从近端影子恢复原零点。它的内部状态通常不等于原解；固定点的识别与本页对整个关系直接取预解的成本，须分别判断。