拉格朗日函数与拉格朗日对偶
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$的驻点 ...