优化理论

1.拉格朗日乘数法 1.1 基本定义 拉格朗日最早提出的是针对等式约束的拉格朗日乘数法 考虑如下的优化问题： $$ \begin{aligned} & \text{minimize} \quad & f_0(x)& \\\\ & \text{subject to} \quad & h_i(x) & = 0, \quad i=1, \cdots, m \end{aligned} $$则有拉格朗日函数： $$ L(x, \nu) = f(x) + \sum_{i=0}^m \mu_i h_i(x) $$其中$\mu$为对应等式约束的拉格朗日乘子(或拉格朗日乘数)。拉格朗日函数的形式化表达会在稍后介绍。 拉格朗日乘数法的一般求解步骤如下： 构造拉格朗日函数 求取拉格朗日函数对每一个变量的偏导（梯度），令其为0。这一步并不要求函数是凸的 求解2.中得到的方程组，得到最优点 具体的原理在稍后的小节介绍 由此可见，拉格朗日乘数法在一定程度上将问题转化为了无约束优化问题，整个求解步骤无需额外考虑约束方程带来的影响，其效果已经被拉格朗日函数考虑在内 1.2 最优性条件 最优性必要条件为：在局部最优解 $x^\*$ 处要满足： 1.2.1 平稳性条件 最优点一定是(拉格朗日函数的)驻点 $$ \nabla_x L(x^\*, \mu^\*) = \nabla f(x^\*) + \sum_j \mu_j^\*\nabla h_j(x^\*)=0 $$补充概念：驻点与鞍点 驻点： 对于函数$\mathbb{R}^n\rightarrow \mathbb{R}$，若在点$x^\*$处梯度为零，即： $$ \nabla f(x^\*) = 0 $$ 则称$x^*$为函数$f$的驻点 ...

1. 通用下降方法 1.1 下降方法基本形式 注：下降方法不会要求凸性，但拥有凸性会让求解得到显著保障。对凸性的定义见[[凸集与凸函数深入#2.1 凸函数定义|凸函数定义]] 我们先来回顾梯度下降的原型 - 下降方法 下降算法会产生优化点列 $x^{(k)}, k=1, \cdots$，其中 $$ x^{(k+1)} = x^{(k)} + t^{(k)}\Delta x^{(k)} $$且 $t^{(k)} > 0$（除非 $x^{(k)}$ 已经最优了）。该概念参考自[[Convex Optimization.pdf|Convex Optimization]]1 此处 $\Delta x^{(k)}$ 是一个向量，称为搜索方向，$t^{(k)}\Delta x^{(k)}$ 称为步径（实践中常为和参数同尺寸的多维数组）；$k$ 代表迭代次数；标量 $t^{(k)}$ 是更新步长。 1.2 下降条件 对于所有下降方法，只要 $x^{(k)}$ 不是最优点，则都有： $$ f(x^{(k+1)}) < f(x^{(k)}) $$ 注意：下降算法默认为最小化目标函数，一切最初形式为"最大化目标函数"的问题(例如TD误差)均可被描述为如此形式 以下是下降方法的下降条件： 凸函数情况下，若选择 $d=y-x$ 方向更新，现考虑凸函数的[[凸集与凸函数深入#2.2.1 一阶条件|一阶条件]]2 $f(y) \geq f(x)+\nabla f(x)^T(y-x)$，要使函数下降，即 $f(y) < f(x)$，则必须有 $\nabla f(x)^{T}(y-x) < 0$。 此处，$\nabla f(x)^{T}(y-x)$ 即为方向导数 特征 搜索方向 步径 方向导数 数学定义 $d^{(k)}$ $\alpha^{(k)} d^{(k)}$ $\nabla f(x)^{T}(y-x)$ 几何含义 移动的方向 实际的位移向量 函数沿方向的变化率 1.3 通用下降法算法框架 通用下降方法通常有如下的步骤： ...