如何证明无约束优化的梯度下降可表示为二次函数的argmin？求FISTA等价性指引

嘿，卡在这个等价性问题上确实挺挠头的，我来一步步给你拆解清楚：

问题1：无约束梯度下降迭代等价于二次函数的Argmin证明 #

无约束梯度下降的每一步迭代，本质上是在当前点用一阶泰勒近似+二次正则化构造局部近似函数，然后最小化这个近似函数。具体推导如下：

1. 先写出梯度下降的迭代规则：
   假设当前迭代点为 $x_k$，目标函数为 $f(x)$（光滑可导），梯度下降的更新公式为：

   x_{k+1} = x_k - η ∇f(x_k)
   

   其中 $\eta > 0$ 是步长，$\nabla f(x_k)$ 是 $f$ 在 $x_k$ 处的梯度。

2. 构造对应的二次函数：
   我们构造关于 $x$ 的二次函数 $q(x)$：
   $$q(x) = f(x_k) + \nabla f(x_k)^T (x - x_k) + \frac{1}{2\eta} |x - x_k|_2^2$$
   这个函数由三部分组成：$f$ 在 $x_k$ 处的函数值、一阶泰勒近似的线性项，以及控制步长的二次正则项。

3. 求解二次函数的最小值点：
   因为 $q(x)$ 是凸二次函数，最小值点满足导数为0的条件。对 $x$ 求导并令导数等于0：
   $$\nabla q(x) = \nabla f(x_k) + \frac{1}{\eta}(x - x_k) = 0$$
   解这个线性方程，得到：
   $$x = x_k - \eta \nabla f(x_k)$$
   这正好和梯度下降的更新公式完全一致。因此，梯度下降的每一步迭代等价于求解上述二次函数 $q(x)$ 的最小值点。

问题2：FISTA中相关等价性的推导指引 #

FISTA是加速复合梯度方法，针对的是形如 $f(x) = g(x) + h(x)$ 的复合目标（$g$ 是Lipschitz光滑函数，$h$ 是闭凸且proximal算子易计算的函数），它的迭代中同样存在“某二次函数+非光滑项”的Argmin等价性，核心推导思路如下：

1. 先明确FISTA的迭代框架：

   • 计算动量点：

     y_k = x_k + \frac{t_{k-1} - 1}{t_k} (x_k - x_{k-1})
     

     其中 $t_k$ 是满足递推关系 $t_k = \frac{1 + \sqrt{1 + 4t_{k-1}^2}}{2}$ 的序列，初始值 $t_1 = 1$。
   • 更新迭代点：

     x_{k+1} = \arg\min_x \left( g(y_k) + \nabla g(y_k)^T(x - y_k) + \frac{L}{2}\|x - y_k\|_2^2 + h(x) \right)
     

     这里 $L$ 是 $g$ 的Lipschitz常数（即 $|\nabla g(x) - \nabla g(y)| \leq L|x - y|$ 对所有 $x,y$ 成立）。

2. 关键等价性分析：
   上述Argmin中的前三项 $g(y_k) + \nabla g(y_k)^T(x - y_k) + \frac{L}{2}|x - y_k|_2^2$ 是 $g(x)$ 在动量点 $y_k$ 处的带Lipschitz上界的二次近似（这来自Lipschitz光滑函数的“下降引理”：$g(x) \leq g(y_k) + \nabla g(y_k)^T(x - y_k) + \frac{L}{2}|x - y_k|_2^2$）。

3. 推导验证步骤：

   • 若为无约束情况（$h(x) = 0$），直接对Argmin中的表达式求导并令导数为0，可得：
     $$x = y_k - \frac{1}{L}\nabla g(y_k)$$
     代入动量点 $y_k$ 的定义，就能得到FISTA的加速迭代公式，验证了等价性。
   • 若为复合情况（$h(x) \neq 0$），则Argmin的解对应 $h(x)$ 关于该二次函数的proximal算子，这也是FISTA能处理非光滑项的核心——通过最小化“二次近似+非光滑项”来得到迭代更新。

内容的提问来源于stack exchange，提问作者Olórin