2018年3月

Optimization Theory - Lagrange Multiplier Method & KKT Conditions

Optimization

在满足某些约束的条件下,最优化目标函数是最优化理论研究的问题。

这自然也是应用数学、计算数学和计算机科学研究的东西。

在程序设计我们常用的技术有

  1. 根据函数性质将最优化问题转为判定性问题的二分、三分;
  2. 研究数学上的函数的 LMM 和 KKT 条件;
  3. 规划:动态规划、线性规划;
  4. 近似算法:分块算法、模拟退火;
  5. 更加高精尖的技术(比方说机器学习?)。

本文研究的是多变量函数,自变量为 $ \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 课,应该是比较基础不好意思叫这个名字)就讲了这些。当时还是能随手证的,现在就废了。

Polynomial Techniques

多项式技术。

本来叫做多项式理论的,但仔细审视发现并没有太多值得被称作理论的东西:全都是多项式环内的计算技术。

算了。本来就是为计数理论生成函数服务的技术。由更深的视点再写多项式理论吧。

- 阅读剩余部分 -