Optimization Theory - Lagrange Multiplier Method & KKT Conditions
Optimization Theory - Lagrange Multiplier Method & KKT Conditions
Optimization
在满足某些约束的条件下，最优化目标函数是最优化理论研究的问题。
这自然也是应用数学、计算数学和计算机科学研究的东西。
在程序设计我们常用的技术有
- 根据函数性质将最优化问题转为判定性问题的二分、三分；
- 研究数学上的函数的 LMM 和 KKT 条件；
- 规划：动态规划、线性规划；
- 近似算法：分块算法、模拟退火；
- 更加高精尖的技术（比方说机器学习？）。
本文研究的是多变量函数，自变量为 $ \mathrm x=(x_i)_{i=1}^n $ ，目标函数和限制的一般情形如下：
$$ \begin{align} \text{opt.} ~&f \\ \text{s.t.} ~&g_i=0 \\ ~&h_i\ge0 \end{align} $$
Lagrange Multiplier Method
在没有不等式约束的情况下，LMM 宣称存在最值解 $ (x_i)_{i=1}^n $ 的必要条件是 Lagrange 函数
$$ L(\mathrm x) = f+\sum_i\lambda_ig_i $$
对各个变量（$ \mathrm x,(\lambda_i)_{i=1}^n $） 的偏导均为 $ 0 $ ，即最值满足
$$ \begin{cases} {\partial f\over\partial x_i}+\lambda_i({\partial g_i\over\partial x_i})=0 \\ g_i=0 \end{cases} $$
这是一个一阶条件，用多元微积分的理论中的梯度算子和 Heissen 阵可以得到这个结果。
（此处证明）
梯度场是函数增长的方向，切空间处必满足所有法向量的线性组合均与其垂直。
又可知通过 Lagrange Multiplier $ \lambda $ 限制了目标函数的自由度，在自由度足够低的情况下极值点的个数越来越少。
KKT Conditions
接下来考虑不等式限制，则可视为 LMM 的拓展的 KKT Conditions 宣称最优解的必要条件是 KKT 函数
$$ K(\mathrm x)=f+\sum_i\lambda_ig_i+\sum_i\mu_ih_i $$
对各个 $ \mathrm x, (\lambda_i)_{i=1}^n $ 偏导为 $ 0 $ 且 $ \mu_ih_i=0 $ ，即最值得必要条件是满足
$$ \begin{cases} {\partial f\over\partial x_i}+\lambda_i{\partial g_i\over\partial x_i}=0 \\ g_i=0 \\ \mu_ih_i=0 \end{cases} $$
证明略。真的学会了 Convex Optimization 再来装逼。
话说去年暑假在清华的 Applied Analysis 课（其实应该叫 Optimization Theory 课，应该是比较基础不好意思叫这个名字）就讲了这些。当时还是能随手证的，现在就废了。