约束优化之Lagrange乘子法KKT条件对偶问题最容易理解解读

本文主要是介绍约束优化之Lagrange乘子法KKT条件对偶问题最容易理解解读,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.无约束优化的常用方法

在讲带约束优化方法之前,我们先简单回顾一下常用的无约束优化方法。

1.梯度下降法
2.牛顿法/拟牛顿法
3.共轭梯度法

上面梯度系列的无约束条件下的最优化,基本解法是根据极值的必要条件一阶导数为0,通过泰勒展开等形式,构造不同数列不断逼近最优解。

2.带约束的优化

实际情况中,不带约束的场景比较少见,大部分都为带约束的优化问题。看一个大家都用的图:
在这里插入图片描述
上图中,蓝色的圈圈表示二元函数f(xy)投影在平面上的等高线,而蓝色的箭头则表示函数梯度方向。如果是不带预约条件的优化,我们直接用梯度下降法,沿着梯度方向找到使得函数值最小的点即可,这种解法我们已经很熟悉了,不再多说。

如果我们加上约束,即图中的黑线,该条线的意思是表示(x, y)的数值要落在黑线上才能满足约束条件。而蓝色圈圈(目标函数)与黑线(约束)有三种情况:
1.相离
说明两个函数没有交点,就是无解,此时不符合条件。
2.相交
两条曲线相交,说明是两个函数的解,但此时得到的一定不是最优解。因为相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部,使得新的等高线与目标函数的交点的值更大或者更小。
3.相切
如果两条曲线相切,说明是可行解。

假设目标函数为f(x),约束条件为g(x)=0,则两条曲线相交用数学式子可以表示为
∇ f ( x ) = − λ ∇ g ( x ) \nabla f(x) = -\lambda \nabla g(x) f(x)=λg(x)

其中,负号表示两者梯度方向相反。

3.等式约束与Lagrange乘子法

有如下优化问题:
m i n f ( x ) s . t . g ( x ) = 0 \begin{aligned} & min \quad f(x) \\ & s.t. \quad g(x) = 0 \end{aligned} minf(x)s.t.g(x)=0
为方便讨论,设f与g均为连续可导。Lagrange函数为
L ( x , λ ) = f ( x ) + λ g ( x ) L(x, \lambda) = f(x) + \lambda g(x) L(x,λ)=f(x)+λg(x)
其中, λ \lambda λ为Lagrange乘数。

通过上面的转换,我们将带约束优化的问题,转换成了无约束优化问题。

分别计算Lagrange函数对x与 λ \lambda λ的偏导,并令其为0,就可以求得最优解。
∇ x L = ∂ L ∂ x = ∇ f + λ ∇ g = 0 ∇ λ L = ∂ L ∂ λ = g ( x ) = 0 \begin{aligned} & \nabla_xL = \frac{\partial L}{\partial x} = \nabla f + \lambda \nabla g = 0 \\ & \nabla_{\lambda}L = \frac{\partial L}{\partial \lambda} = g(x) = 0 \end{aligned} xL=xL=f+λg=0λL=λL=g(x)=0

其中第一式为定常方程式(stationary equation),如果我们将第二部分得到的结果移项,就会发现得到的结果与定常方程式完全一样。第二部分为约束条件。如果x为n维向量,则上面最终得到的是n+1个方程,包含有有n+1个变量,解这个线性方程组即可。

4.不等式约束与KKT条件

上面我们提到的是等式约束,实际情况中,可能还会有不等式约束条件。
先放一张大家都使用的图,方便理解。
在这里插入图片描述
对于不等式的条件,有两种情况:可行解 x ∗ x^* x在g(x)<0的区域或者g(x)=0的边界上。
如果 x ∗ x^* x在g(x)<0的区域,此时有没有g(x)<0这个条件,都是在 x ∗ x^* x处取得极小值,相当于此时约束条件无效,原问题 退化成无约束优化问题。换句话说相当于不等式约束条件没有起到作用,此时可以直接最小化目标函数即可。
所以有:
∇ L ( x ∗ ) = 0 , λ = 0 , g ( x ∗ ) < 0 \nabla L(x^*) = 0, \lambda=0, g(x^*)<0 L(x)=0,λ=0,g(x)<0
其中, λ = 0 \lambda=0 λ=0相当于不等式约束没起作用。

如果 x ∗ x^* x在g(x)=0的区域, 此时需要条件起作用, λ ≠ 0 \lambda \neq 0 λ=0。因此当可行解在g(x)=0上时,就变成了前面的等式约束,就可以用前面的朗格朗日乘子法求解。根据前面的分析不难得出此时需要满足的条件为
∇ L ( x ∗ ) = 0 , λ > 0 , g ( x ∗ ) = 0 \nabla L(x^*) = 0, \lambda>0, g(x^*)=0 L(x)=0,λ>0,g(x)=0

如果将上面两个情况综合考虑,得到的条件为
λ ≥ 0 g ( x ∗ ) ≤ 0 λ g ( x ∗ ) = 0 \lambda \geq 0 \\ g(x^*) \leq 0 \\ \lambda g(x^*) = 0 λ0g(x)0λg(x)=0

下面我们将带不等式约束的优化问题做一般总结
有如下优化问题

m i n f ( x ) s . t . g j ( x ) = 0 , j = 1 , 2 , ⋯ , m h k ( x ) ≤ 0 , k = 1 , 2 , ⋯ , n \begin{aligned} min \quad & f(x) \\ s.t. \quad & g_j(x) = 0, \quad j=1, 2, \cdots, m \\ & h_k(x) \leq 0, \quad k = 1, 2, \cdots, n \end{aligned} mins.t.f(x)gj(x)=0,j=1,2,,mhk(x)0,k=1,2,,n

我们可以将Lagrange函数写为
L ( x , λ j , μ k ) = f ( x ) + ∑ j = 1 m λ j g j ( x ) + ∑ k = 1 n μ k h k ( x ) L(x, \lambda_j, \mu_k) = f(x) + \sum_{j=1}^m \lambda_j g_j(x) + \sum_{k=1}^n \mu_k h_k(x) L(x,λj,μk)=f(x)+j=1mλjgj(x)+k=1nμkhk(x)

其中, λ j \lambda_j λj是对应的等式约束 g j ( x ) = 0 g_j(x)=0 gj(x)=0的拉格朗日乘子, μ k \mu_k μk对应的是 h k ( x ) ≤ 0 h_k(x) \leq 0 hk(x)0的拉格朗日乘子(或者叫KKT乘子)。则KKT条件为:
∇ x L = 0 g j ( x ) = 0 , j = 1 , 2 , ⋯ , m h k ( x ) ≤ 0 , k = 1 , 2 , ⋯ , n μ k ≥ 0 , μ k h k ( x ) = 0 \begin{aligned} & \nabla_x L = 0\\ & g_j(x) = 0, \quad j=1, 2, \cdots, m \\ & h_k(x) \leq 0, \quad k=1,2,\cdots, n \\ & \mu_k \geq 0, \\ & \mu_k h_k(x) = 0 \end{aligned} xL=0gj(x)=0,j=1,2,,mhk(x)0,k=1,2,,nμk0,μkhk(x)=0

KKT条件看着好像挺复杂的,本人当初学优化方法的时候,也感觉这玩意挺复杂的。但是经过仔细分析梳理,发现理解起来没那么麻烦:

第一条为拉格朗日函数导数为0,很好理解。
第二、三条为本身的约束条件,不解释。
第四、五条为针对不等式约束的两种情况,综合得到的结果。本质上就是最后一条 μ k h k ( x ) = 0 \mu_k h_k(x) = 0 μkhk(x)=0。如果约束在小于范围内,则 μ k = 0 \mu_k=0 μk=0相当于约束自动生效没起作用,此时 μ k = 0 \mu_k=0 μk=0。当约束在边界上时,此时需要满足 h k ( x ) = 0 , μ k > 0 h_k(x) = 0, \mu_k>0 hk(x)=0,μk>0,综合起来就得到最后两条!

5.对偶问题

第四部分我们介绍了KKT条件,可以用来将带约束的优化问题,转化为不带约束的优化问题,从而来求解。但是很多时候直接用KKT求解也不是很容易,甚至没有解。此时我们可以通过求解原问题的对偶问题来得到原问题的一个下界估计。

由第四部分得到拉格朗日函数:
L ( x , λ j , μ k ) = f ( x ) + ∑ j = 1 m λ j g j ( x ) + ∑ k = 1 n μ k h k ( x ) L(x, \lambda_j, \mu_k) = f(x) + \sum_{j=1}^m \lambda_j g_j(x) + \sum_{k=1}^n \mu_k h_k(x) L(x,λj,μk)=f(x)+j=1mλjgj(x)+k=1nμkhk(x)

一般定义原始问题primal:

m i n x m a x μ > 0 , λ L ( x , λ , μ ) \underset {x}{min} \quad \underset {\mu>0, \lambda}{max} L(x, \lambda, \mu) xminμ>0,λmaxL(x,λ,μ)

令:
z ( x ) = m a x μ > 0 , λ L ( x , λ , μ ) z(x) = \underset {\mu>0, \lambda}{max} L(x, \lambda, \mu) z(x)=μ>0,λmaxL(x,λ,μ)

因为 μ ≥ 0 , g ( x ) = 0 , h ( x ) ≤ 0 \mu \geq 0, g(x)=0, h(x) \leq 0 μ0,g(x)=0,h(x)0, 则 z ( x ) = f ( x ) z(x) = f(x) z(x)=f(x)。因此,若原始问题存在最优解, m i n ( L ) = m i n ( z ) min(L) = min(z) min(L)=min(z),即最初的优化问题与定义的原始为primal等价。

再定义primal问题的对偶问题dual:

m a x μ > 0 , λ m i n x L ( x , λ , μ ) \underset {\mu>0, \lambda}{max} \quad \underset {x}{min} L(x, \lambda, \mu) μ>0,λmaxxminL(x,λ,μ)

设primal问题的最小值为 p ∗ p^* p ,对偶问题的最小值为 d ∗ d^* d,有
p ∗ ≥ d ∗ p^* \geq d^* pd

为什么会有上面的结论,其实很好理解:
primal问题是求最大值中的最小值,而dual问题是求最小值中的最大值,那么primal问题大于等于dual问题就是很自然的事情。

需要注意的是,primal问题的变量是x,dual问题的变量是 λ , μ \lambda, \mu λ,μ

引用参考文献3的一段说法:
因为 dual problem 的变量是 lamda 和 v,dual problem 肯定是能优化的,在某些条件(如 原始函数是凸函数,约束条件是仿射函数)下,d*=p*, 强对偶成立,这时优化 dual problem 完全等价于优化 primal problem,其他情况下,我们可以通过优化 dual problem 得到 primal problem 的一个下界(比如我们求直接求 primal problem 无法求解,不知道其解的范围,假设我们求出其 dual problem 的最小值是 t, 那 primal problem 的最小值的解空间的范围可以确定,是 >= t 的)。

另外需要区分的是KKT条件跟对偶之间的关系,简单来说,两者没半毛钱关系。

首先对于一个不等式约束问题,他有最优解的必要条件是满足KKT条件,通过KKT条件可以将不等式约束转化为等式约束,再利用拉格朗日方法转化为无约束优化问题求解,这是KKT条件的意义。

而对偶性,是为了将原问题转化为对偶问题,方便求解。一个问题具体要满足哪些条件才能有强对偶性,可以去研究。但是只要记住,几乎所有的凸优化问题都满足强对偶性。

最后参考文献四有一张图,画得相当直观清晰,引用过来,方便大家理解。
在这里插入图片描述

参考文献

1.https://www.jiqizhixin.com/articles/2019-02-12-10
2.https://zhuanlan.zhihu.com/p/38163970
3.https://zhuanlan.zhihu.com/p/475956132
4.https://zhuanlan.zhihu.com/p/46944722

这篇关于约束优化之Lagrange乘子法KKT条件对偶问题最容易理解解读的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/431484

相关文章

解读为什么@Autowired在属性上被警告,在setter方法上不被警告问题

《解读为什么@Autowired在属性上被警告,在setter方法上不被警告问题》在Spring开发中,@Autowired注解常用于实现依赖注入,它可以应用于类的属性、构造器或setter方法上,然... 目录1. 为什么 @Autowired 在属性上被警告?1.1 隐式依赖注入1.2 IDE 的警告:

解决java.lang.NullPointerException问题(空指针异常)

《解决java.lang.NullPointerException问题(空指针异常)》本文详细介绍了Java中的NullPointerException异常及其常见原因,包括对象引用为null、数组元... 目录Java.lang.NullPointerException(空指针异常)NullPointer

Android开发中gradle下载缓慢的问题级解决方法

《Android开发中gradle下载缓慢的问题级解决方法》本文介绍了解决Android开发中Gradle下载缓慢问题的几种方法,本文给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、网络环境优化二、Gradle版本与配置优化三、其他优化措施针对android开发中Gradle下载缓慢的问

关于Nginx跨域问题及解决方案(CORS)

《关于Nginx跨域问题及解决方案(CORS)》文章主要介绍了跨域资源共享(CORS)机制及其在现代Web开发中的重要性,通过Nginx,可以简单地解决跨域问题,适合新手学习和应用,文章详细讲解了CO... 目录一、概述二、什么是 CORS?三、常见的跨域场景四、Nginx 如何解决 CORS 问题?五、基

Rust中的注释使用解读

《Rust中的注释使用解读》本文介绍了Rust中的行注释、块注释和文档注释的使用方法,通过示例展示了如何在实际代码中应用这些注释,以提高代码的可读性和可维护性... 目录Rust 中的注释使用指南1. 行注释示例:行注释2. 块注释示例:块注释3. 文档注释示例:文档注释4. 综合示例总结Rust 中的注释

MySQL安装时initializing database失败的问题解决

《MySQL安装时initializingdatabase失败的问题解决》本文主要介绍了MySQL安装时initializingdatabase失败的问题解决,文中通过图文介绍的非常详细,对大家的学... 目录问题页面:解决方法:问题页面:解决方法:1.勾选红框中的选项:2.将下图红框中全部改为英

解读Pandas和Polars的区别及说明

《解读Pandas和Polars的区别及说明》Pandas和Polars是Python中用于数据处理的两个库,Pandas适用于中小规模数据的快速原型开发和复杂数据操作,而Polars则专注于高效数据... 目录Pandas vs Polars 对比表使用场景对比Pandas 的使用场景Polars 的使用

Rust中的Drop特性之解读自动化资源清理的魔法

《Rust中的Drop特性之解读自动化资源清理的魔法》Rust通过Drop特性实现了自动清理机制,确保资源在对象超出作用域时自动释放,避免了手动管理资源时可能出现的内存泄漏或双重释放问题,智能指针如B... 目录自动清理机制:Rust 的析构函数提前释放资源:std::mem::drop android的妙

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

Nginx启动失败:端口80被占用问题的解决方案

《Nginx启动失败:端口80被占用问题的解决方案》在Linux服务器上部署Nginx时,可能会遇到Nginx启动失败的情况,尤其是错误提示bind()to0.0.0.0:80failed,这种问题通... 目录引言问题描述问题分析解决方案1. 检查占用端口 80 的进程使用 netstat 命令使用 ss