1. 梯度下降法
无约束最优化问题一般可以概括为：
\[\min_{x \in \mathbb{R}^n}f(x) \]通过不断迭代到达最优点 \(x^*\)，迭代过程为：
\[x^{k + 1} = x^k + \alpha_k d^k \]其中 \(d^k\) 为当前的 搜索方向，\(\alpha_k\) 为当前沿着搜索方向的 步长 。
我们需要寻找可以不断使得 \(f(x^{k + 1} < f(x^k)\) 的方法。
构造一元辅助函数：
\[\phi(\alpha) = f(x^{k + 1})= f(x^k + \alpha d^k) \]其中 \(d^k\) 是 下降方向，\(\alpha > 0\) 是辅助函数的 自变量。
由一阶泰勒展开式将目标函数进行泰勒展开：
\[f(x) = f(x^k) + \nabla f(x^k)^T (x - x^k) + o(||x - x^k||) \]（带皮亚诺余项的一阶泰勒展开）
可得：
\[\phi (\alpha) = f(x^k) + \alpha \nabla f(x^k) ^T d^k + o(||x^{k + 1} - x^k||) \]为了使得迭代过程 可行，能够达到 收敛，显然有 \(||x^{k + 1} - x^k|| \rightarrow 0\)，所以有：
\[f(x^{k + 1}) = f(x^k) + \alpha \nabla f(x^k)^T d^k \]显然，为了能够使得 \(f(x^{k + 1}) < f(x^k)\)，需要确保 \(\alpha \nabla f(x^k)^Td^k < 0\)，而 \(\alpha > 0\)，所以需要保证：
\[\frac{\partial f}{\partial \alpha} = \nabla f(x^k)^T d^k < 0 \]为了使得 下降速度尽可能快，即有关于下降方向的最优化问题：
\[(d^k)^* = \text{arg}\min_{d^k} \frac{\partial f}{\partial \alpha} = \text{arg}\max_{d^k} - \frac{\partial f}{\partial \alpha} \]由 柯西不等式：
\[-\frac{\partial f}{\partial \alpha} = - \nabla f(x^k)^Td^k \le ||\nabla f(x^k)|| \cdot ||d^k|| \]根据柯西不等式等号成立的条件，需要使 \(d^k\) 与 \(- \nabla f(x^k)\) 同向。所以，我们需要找到的 最快的下降方向 即：
\[(d^k)^* = - \nabla f(x^k) \]由此得出 梯度下降法 (最速下降法) 的迭代格式：
\[x^{k + 1} = x^k - \alpha_k \nabla f(x^k) \]其中 步长 \(\alpha_k\) 可以依据线搜索算法（精确解、直接搜索、非精确搜索的一些准则等）得到，也可以选取固定的步长 \(\alpha\) 。
终止条件 一般有 \(||x^{k + 1} - x^k|| < \varepsilon\) 或 \(|f(x^{k + 1}) - f(x^k)| < \varepsilon\) 。其中 \(\varepsilon\) 是一个很小的数。
如下图所示，为一个二元二次函数 \(f(x, y)\)，采用 梯度下降法 \(x^{k + 1} = x^k - \alpha_k \nabla f(x^k)\) 的迭代过程。
在机器学习领域，梯度下降法有非常广泛的应用。例如梯度下降法解决线性回归问题。[机器学习复习笔记] Grandient Descent 梯度下降法
2. Lipschitz 连续
2.1 梯度利普希茨连续定义
给定可微函数 \(f\)，若存在 \(L > 0\)，对于任意 \(x, y \in \text{dom} f\) 有：
\[||\nabla f(x) - \nabla f(y)|| \le L||x - y|| \]则称 \(f\) 是 梯度利普希茨连续 的。其中 \(L\) 为 利普希茨常数。
函数 \(f\) 满足 \(\text{Lipschitz}\) 连续可以理解为该函数的变化速率受到了限制。变化速率的上界即为 \(\text{Lipschitz}\) 常数 \(L\)。
2.2 下降引理（二次上界）
设可微函数 \(f\) 定义域 \(\text{dom} f = \mathbb{R}^n\)，且 梯度利普希茨连续，则 其 \(\text{Hessian}\) 矩阵满足：
\[\nabla ^2 f(x) \preceq LI \]其中 \(L\) 为 利普希茨常数，\(I\) 为单位阵。
导数 \(\nabla f(x)\) 变化 最快的方向 就是它的 \(\text{Hessian}\) 矩阵 \(\nabla ^2 f(x)\) 绝对值 最大特征值所对应的特征向量。
对函数 \(f\) 进行泰勒展开得：
\[\begin{split} f(y) &= f(x) + \nabla f(x)^T (y - x) + \frac{1}{2}(y - x)^T \nabla ^2 f(x) (y - x) \\\\ & \le f(x) + \nabla f(x)^T (y - x) + \frac{L}{2}||y - x||^2 \end{split} \]对任意 \(x, y \in \text{dom} f\) 成立，称 \(f(x)\) 有二次上界。
3. 梯度下降收敛性
梯度法迭代式：
\[x^{k + 1} = x^k - \alpha_k \nabla f(x^k) \]-
设函数 \(f(x)\) 为凸函数，且梯度利普希茨连续
-
极小值 \(f(x^*)\) 存在且可达
-
步长应满足 \(0 < \alpha < \frac{1}{L}\)
条件（2）是一个不可或缺的条件，它保证了原始的优化问题存在可行解。
条件（1）和条件（3）使得下降引理成立，保证了梯度下降算法在优化目标函数过程中的正确性。
参考
刘浩洋, 户将, 李勇锋, 文再文《最优化：建模、算法与理论》
最优化方法复习笔记（一）梯度下降法、精确线搜索与非精确线搜索（推导+程序）
标签：partial,梯度,nabla,笔记,下降,text,alpha,最优化 From： https://www.cnblogs.com/MAKISE004/p/17903765.html