Intro
假设$f(x),c_i(x),h_j(x)$是定义在$\mathbb R^n$上的连续可微函数。考虑约束最优化问题
称此约束最优化问题为原始最优化问题或原始问题
拉格朗日乘子法
对于原始问题，要求解就用拉格朗日乘子法：
$L(x,\alpha,\beta)=f(x)+\sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_jh_j(x)$
这里$x=(x^{(1)},x^{(2)},\cdots,x^{(n)})^T∈\mathbb R^n\quad\alpha_i≥0,\beta_j$是拉格朗日乘子。（不等式约束的乘子$\alpha$要规定$\alpha≥0$，是为了满足后文KKT的对偶可行条件）
「拉格朗日乘子法将有约束问题转化为了无约束问题」
那么我们就要对$L(x,\alpha,\beta)$求极值。这个式子$x,\alpha,\beta$都是变量，也就是说我们要求出多元变量式子的极值。
有的情况可以求出极值（给了足够多个方程可以解出算子，如HMM的EM中包含一个隐藏方程可以解出算子），但有的就无法直接求了。于是我们想要分离$x$和算子，于是我们将表达式改写为广义拉格朗日极小极大。
同时由于$\nabla_xL(x,\alpha,\beta)=\nabla_xf(x)$，所以这么转换是等价的，但$\nabla_\alpha L(x,\alpha,\beta)=0,则c(x)=0$，显然约束条件不等价，改写成了广义拉格朗日极小极大才使得式子和原式完全等价。
广义拉格朗日极小极大形式
尝试构造这个最大化
$\max_{\alpha,\beta:\alpha≥0} L(x,\alpha,\beta)=\max\{f(x)+\sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_jh_j(x)\}$
会发现一个特点：
如果原始问题的约束条件$c_i(x)≤0,h_j(x)=0$不成立，也就是说$c_i(x)≥0,h_j(x)≠0$，那为了让$L$最大，$\alpha_i$就会取$+∞$，$\beta_j$就会取$-sign(h_j(x))·∞$，这时候$\max_{\alpha,\beta:\alpha≥0}=+∞$
显然这是不可以的。
只有当约束条件$c_i(x)≤0,h_j(x)=0$成立的时候，才不会出现这种情况。因为这种情况下为了让$L$最大，$\alpha_i$就会取$0$，同时$h_j(x)=0$
所以当约束条件成立的时候，可以得到这个等式：$\max_{\alpha,\beta:\alpha≥0} L(x,\alpha,\beta)=f(x)$
也就是说，Intro中的那串定义，包含约束条件的$f(x)$可以由一个式子表示：$\max_{\alpha,\beta:\alpha_i≥0} L(x,\alpha,\beta)$，成功地将算子和$x$分离开来，同时与原式完全等价。里面求使$L$最大化的算子，外面求使$L$最小化的$x$。
于是我们要求约束$c_i(x)≤0,h_j(x)=0$下的最优化问题$\min_x f(x)$，即是要求$\min_x\max_{\alpha,\beta:\alpha_i≥0} L(x,\alpha,\beta)$
这就是广义拉格朗日极小极大问题：
设$d^o=\arg \min_x\max_{\alpha,\beta:\alpha≥0} L(x,\alpha,\beta)$
「为什么要转化为极小极大形式：使得与原式完全等价，且对所有情况都可以求解。如果直接求拉格朗日乘子式的极值，在乘子多于已知方程的情况下无法求解」
对偶问题
原始问题的广义拉格朗日极小极大问题$\min_x\max_{\alpha,\beta:\alpha≥0} L(x,\alpha,\beta)$的对偶问题为：
设$p^o=\max_{\alpha,\beta:\alpha≥0} \min_x L(x,\alpha,\beta)$
「为什么要有对偶问题：对偶问题都是凸优化问题，而凸优化问题局部极值=全局极值而且更好求解。」
（在ML中的凸优化是指函数呈U型！）
举例：在MEM中的含等式约束问题，就是先求里面的极小化问题以$x$为变量求出最小的$P_w$，然后回代，只需要再求出能使$P_w$极大化的$w$即可，外部极大化$P_w$可证等于MLE，具体的方法，如IIS，牛顿法与伪牛顿法，梯度下降。
弱对偶性
定理$1^o$：若原始问题和对偶问题都有最优值，则：
对偶问题≤原始问题（或其广义拉格朗日极小极大问题）
很容易理解，因为$L$中最小的一个的最大值肯定比最大的一个的最小值要小。此式即为弱对偶性。
此式就可以求出原始问题的下限。
何时相等（①强对偶性②是最优解）？即何时「解原始问题最优化=解对偶问题最优化」所以需要KKT定理，下面一步一步引出：
推论$1^o$： 设$x^o$和$\alpha^o,\beta^o$分别是原始问题和对偶问题的可行解，并且$d^o=p^o$，则$x^o$是原始问题的最优解，$\alpha^o,\beta^o$是对偶问题的最优解。
注意解是$\alpha,\beta,x$，值是式子的值$p^o,d^o$
翻译：如果原始问题的值和对偶问题的值相等，那么两个问题对应的参数是最优解
强对偶性（还不等价）-Slater条件
定理$2^o$：考虑原始问题和对偶问题，假设函数$f(x)$和$c_i(x)$是凸函数（凸优化问题），$h_j(x)$是仿射函数；并且假设不等式约束$c_i(x)$是严格可行的，即存在$x$，对所有$i$有$c_i(x)<0$，则存在$x^o$和$\alpha^o,\beta^o$，使$x^o$是原始问题的解，$\alpha^o,\beta^o$是对偶问题的解，并且有$p^o=d^o=L(x^o,\alpha^o,\beta^o)$。此即Slater条件。
翻译：在某些条件下，存在解（不一定是最优解）且使得原始问题=对偶问题，即强对偶性成立：
「也就是说只要满足目标函数和不等式约束为凸函数+等式约束为仿射函数，那么强对偶性就成立」
注意：强对偶性存在的参数解可能有很多个（鞍点），并不能保证是极值点（最优解）！
于是下面KKT条件便是确保鞍点便是原函数最优解的充分条件
强对偶性+是最优解=完全等价-KKT条件
一个问题是不等式约束/等式问题，它的最优解就一定满足KKT条件。（必要条件，非充分；但如果是凸函数约束优化（强对偶成立），就变成了充分必要条件）
定理$3^o$：在定理2的条件的基础上，$x^o,α^o,β^o$分别是原始问题和对偶问题的解（是最优解，且强对偶）的充分必要条件是$x^o,α^o,β^o$满足下面的KKT(Karush-Kuhn-Tucker)条件：
定理$3^o$：在定理2的条件的基础上，$x^o,\alpha^o,\beta^o$分别是原始问题和对偶问题的解的充分必要条件是，$x^o,\alpha^o,\beta^o$ 满足下面的KKT(Karush-Kuhn-Tucker)条件：
可以看出有几大类条件：①梯度为0条件；③⑤原约束条件（③是不等式约束，⑤是等式约束）；②对偶互补条件（ 互补松弛条件 ）；④ 对偶可行条件
（注意哪些是不等式约束条件，哪些是等式约束条件，不一样的）
第二个式子称为KKT的对偶互补条件，由此条件可知，若对偶可行条件成立：$\alpha_i^o＞0,则c_i(x^o)=0$。
（这个性质导出了SVM中的支持向量）
任何满足强对偶性的优化问题，只要其目标函数与约束函数可微，任一对原始问题与对偶问题的解都是满足 KKT 条件的。
「KKT条件是凸问题的充分必要条件」（凸函数=>KKT，KKT=>凸函数）
这是个充分必要条件， 一般仅用KKT条件来「验证」找到的解是最优解
对于凸优化，由于与KKT条件是充要条件，那么就可以用KKT条件求出最优解，也可以用回代原始问题求最优解（因为等价）
KKT的推导过程可以看 深入理解拉格朗日乘子法和KKT条件
关于零导数法求极值
对于极值问题，使用零导数法。
假定求$\min_{x,y,z}L(x,y,z),\quad L(x,y,z)=f(x)+g(y)+q(z)$
就可以对各个变量分别求偏导零导数：
$\nabla L(x,y,z)=0 \to \nabla_x f(x)=0,\nabla_y g(y)=0,\nabla_z q(z)=0 $
但如果各个子式之间变量无法分离，如：
$\min_{x,y,z}L(x,y,z),\quad L(x,y,z)=f(x,y)+g(y,z)+q(x,y,z)$
那就得考虑如$\nabla_{x,y}f(x,y)=0$同时满足$x,y$，需要用多元函数求极值的方法。
具体就是
①解$\nabla_{x}f(x,y)=0,\nabla_{y}f(x,y)=0$，求出一切驻点。
②对于每一个驻点$(x_0，y_0)$，求出二阶偏导数的值A、B、C
③定出$AC-B^2$的符号，按充分条件进行判定$f(x_0，y_0)$是否是极大值、极小值。
这只是二元不独立的情况，如果变量更多，是很难求甚至没法求的。所以这种情况下一般不用零导数法（比如IIS中就是因为这个原因要构造第二下界来求解）
（另外也要根据函数本身判断）
