拉格朗日乘子与对偶性

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中就是因为这个原因要构造第二下界来求解)

(另外也要根据函数本身判断)