拉格朗日乘数法
在数学最优问题中，拉格朗日乘数法（以数学家约瑟夫·路易斯·拉格朗日命名）是一种寻找变量受一个或多个条件所限制的多元函数的极值的方法。这种方法将一个有n 个变量与k 个约束条件的最优化问题转换为一个有n + k个变量的方程组的极值问题，其变量不受任何约束。本文介绍拉格朗日乘数法（Lagrange multiplier）。
概述
- 我们擅长解决的是无约束极值求解问题，这类问题仅需对所有变量求偏导，使得所有偏导数为0，即可找到所有极值点和鞍点。我们解决带约束条件的问题时便会尝试将其转化为无约束优化问题
- 事实上如果我们可以通过g得到某个变量的表示，例如x_1 = h(x_2, …, x_n)，将该式带入y即可抓换为无约束优化（初高中就是这么做的，所谓消元法是也），但有的时候我们无法得到这样的表示，便需要借助拉格朗日乘数法来避免消元法的困境。
作为一种优化算法，拉格朗日乘数法主要用于解决约束优化问题，它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有（n+k）个变量的无约束优化问题。拉格朗日乘子背后的数学意义是其为约束方程梯度线性组合中每个向量的系数。
思想
- 考虑二元函数f(x,y)，在约束g(x,y)=c下的极值
- 首先我们可以绘制出f(x,y)的一层层等高线，当等高线与g(x,y)=c相切时即可能是该问题的极值点
拉格朗日乘数法
单个等式约束
考虑n元函数y=f(x_1, x_2,…,x_n)，在等式约束g(x_1, x_2,…,x_n)=0 下的极值点求解问题
- 在极值点，必有y和g法向量平行
- y的法向量为：
- g的法向量为：
二者平行，则存在常数\lambda使得：
- 即：
- 这样我们就得到了n个等式方程，再加上g(x_1, x_2,…,x_n)=0一起构成n+1个方程的方程组，未知数为[x_1,x_2,…,x_n,\lambda]共n+1个，方程组的解即为所有极值点和鞍点的集合，每组解中的\lambda即为两个平行法向量的倍数，该值在等式约束轨迹穿过y的极值点时为0。
多个等式约束
原理与单个等式约束情况类似 考虑n元函数y=f(x_1, x_2,…,x_n)，在m个等式约束(g_i(x_1, x_2,…,x_n)=0, 1 \le i \le m) 下的极值点求解问题
- n维空间由m个条件约束，会确定一个n-m维的曲面，我们讨论y在这个曲面上的极值问题
- 这个曲面由m个n-1维曲面交织而成，存在m个法向量，这m个法向量构成了n-m维曲面的法空间
- 在问题的极值点，y的法向量必然落在n-m维曲面的法空间之内，也就是说y的法向量可以由n-m维曲面的m个法向量的线性组合表示：
- 即：
- 此时我们得到了n个等式方程，再加上m个等式约束(g_i(x_1, x_2,…,x_n)=0, 1 \le i \le m) 一起构成n+m个方程的方程组，未知数为[x_1,x_2,…,x_n,\lambda_1,\lambda_2,…,\lambda_m]共n+m个，方程组的解即为所有极值点和鞍点的集合，每组解中的\lambda_i的值即为y的法向量在n-m维曲面的法空间中的线性组合系数。
单个不等式约束
不等式约束其实是等式约束的扩展，等式约束表示一组确定的等高线（面），不等式约束则表示等高线（面）的某一边区域 考虑n元函数y=f(x_1, x_2,…,x_n)，在不等式约束g(x_1, x_2,…,x_n) \le 0 下的极值点求解问题
- 若该问题有解，那么有两种情况
- 解在 g(x_1, x_2,…,x_n) = 0 曲面上
- 解在g(x_1, x_2,…,x_n) < 0
- 当解在 g(x_1, x_2,…,x_n) = 0 曲面上时，说明该不等式对y取最小值的区域进行了限制，最终解落在了y和约束相切的位置，那么此时二者的法向量方向必然相反（否则y会在g(x_1, x_2,…,x_n) < 0
- 便有结论：\lambda \ge 0
- 当解在g(x_1, x_2,…,x_n) < 0y的求解起到约束作用，此时相当于\lambda = 0
- 而且两种情况下分别有 g(x_1, x_2,…,x_n) = 0和\lambda = 0，也就是二者必有一方为0
- 因此对于单个不等式约束的拉格朗日乘数法，仅需增加限制条件： \lambda \ge 0和\lambda g(x_1, x_2,…,x_n) = 0
多个不等式约束
考虑n元函数y=f(x_1, x_2,…,x_n)，在m个不等式约束(g_i(x_1, x_2,…,x_n)\le0, 1 \le i \le m) 下的极值点求解问题
- 本质上与单个不等式约束相同，只是数量变多了
- 此情况下需要在等式拉格朗日乘数法基础上增加条件：
算法描述
- 基于上述原理，提出了拉格朗日乘数法：
- 考虑n元函数y=f(x_1, x_2,…,x_n)，在m_1个等式约束(g_i(x_1, x_2,…,x_n)=0, 1 \le i \le m_1) 、m_2个不等式约束(h_j(x_1, x_2,…,x_n)\le0, 1 \le j \le m_2) 下的极值点求解问题
- 加入常数\lambda,\mu构造方程：
2. 对所有变量求偏导，并令导数为0：
其中：1 \le k \le n
- 将上述n个方程与m_1个等式约束方程g_i(x_1, x_2,…,x_n)=0, 1 \le i \le m_1 联立
- 将上述n+m_1个方程与\mu_j h_j=0, 1 \le j \le m_2联立，得到n+m_1+m_2个方程
- 加上限制条件\mu_j \ge 0，h_j \le 0, 1 \le j \le m_2
- 在限制条件下解n+m_1+m_2元方程即可得到极值点与鞍点集合
- 从所有解中筛选出极值点
KKT条件
- 上述n+m_1+m_2元方程与限制条件即为KKT条件
KKT条件是拉格朗日函数取极值时的必要条件
其中 i \in { 1,2, \cdots, m_1} ，j \in { 1,2, \cdots, m_2}
- 总结一下所有条件的含义：
