拉格朗日乘数法与KKT条件 拉格朗日乘数法（Lagrange Multiplier)是一种有效求解约束优化问题的 优化方法. 约束优化问题可以表示为 min f(x) hm(x)=0,m=1,…,M (C.10) S.t. gn(x)≤0，n=1,…,N 其中hm(x)为等式约束函数，gn(x)为不等式约束函数.x的可行域为 M N D=dom(f)n∩dom(hm)n∩dom(gn)sRD, (C.11) m=】 n=】 其中dom(f)是函数f的定义域
拉格朗⽇乘数法与 KKT 条件 哈尔滨工业大学计算机学院 刘远超 11
等式约束优化问题 如果公式(C.10)中只有等式约束，我们可以构造一个拉格朗日函数A(x,入) M A(x,)=fx)+∑mhm(x, (C.12) m=】 其中λ为拉格朗日乘数，可以是正数或负数.如果f(x)是原始约束优化问题的 局部最优值，那么存在一个*使得(x*,入*)为拉格朗日函数A(x,)的驻点.因此， 只需要令aAx》=0和AD=0,得到 6 M Vfx)+∑m Vhm(x)=0, (C.13) m=1 hm(x)=0, m=1,…,M. (C.14) 上面方程组的解即为原始问题的可能解.因为驻点不一定是最小解，所以在实际 应用中需根据具体问题来验证是否为最小解
等式约束优化问题 12
不等式约束优化问题 对于公式(C.10)中定义的一般约束优化问题，其拉格朗日函数为 M N A(x,a,b)=fx)+∑amhm()+∑bngn(x, (C.15) m=1 n=1 其中a=[a1,…,aM]T为等式约束的拉格朗日乘数，b=[b1,…,bw]r为不等式 约束的拉格朗日乘数 当约束条件不满足时，有maxa,bA(x,a,b)=o;当约束条件满足时并且 b≥0时，maxa,bA(x,a,b)=f(x).因此，原始约束优化问题等价于 min max A(x,a,b), (C.16) x a,b S.t. b≥0， (C.17) 这个min-max优化问题称为主问题(Primal Problem). 13
不等式约束优化问题 13
对偶问题 sup的定义：一个集合最小的上界 inf的定义：一个集合最大的下界 对偶问题 主问题的优化一般比较困难，我们可以通过交换min-max的顺序来 简化.定义拉格朗日对偶函数为 T(a,b)=inf A(x,a,b). (C.18) x∈D T(a,b)是一个凹函数，即使f(x)是非凸的. 当b≥0时，对于任意的元∈D,有 t(a,b)=infA(x,a,b)≤A(元，a,b)≤f(x), 令p*是原问题的最优值，则有 (a,b)≤p*, 即拉格朗日对偶函数「（α，b)为原问题最优值的下界 14
对偶问题 14 sup 的定义：一个集合最小的上界 inf 的定义：一个集合最大的下界
拉格朗日对偶问题 优化拉格朗日对偶函数（α，b)并得到原问题的最优下界，称为拉格朗日对 偶问题(Lagrange Dual Problem). max I(a,b), (C.21) a,b S.t. b≥0. (C.22) 拉格朗日对偶函数为凹函数，因此拉格朗日对偶问题为凸优化问题， 令d*表示拉格朗日对偶问题的最优值，则有d*≤p*,这个性质称为弱对偶 性(Weak Duality).如果d*=p*,这个性质称为强对偶性(Strong Duality). 15
拉格朗⽇对偶问题 15