约束优化之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条件对偶问题最容易理解解读的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:https://blog.csdn.net/bitcarmanlee/article/details/124959936
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/431484

相关文章

关于pandas的read_csv方法使用解读

《关于pandas的read_csv方法使用解读》:本文主要介绍关于pandas的read_csv方法使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录pandas的read_csv方法解读read_csv中的参数基本参数通用解析参数空值处理相关参数时间处理相关

SpringBoot条件注解核心作用与使用场景详解

《SpringBoot条件注解核心作用与使用场景详解》SpringBoot的条件注解为开发者提供了强大的动态配置能力,理解其原理和适用场景是构建灵活、可扩展应用的关键,本文将系统梳理所有常用的条件注... 目录引言一、条件注解的核心机制二、SpringBoot内置条件注解详解1、@ConditionalOn

MySQL 中查询 VARCHAR 类型 JSON 数据的问题记录

《MySQL中查询VARCHAR类型JSON数据的问题记录》在数据库设计中,有时我们会将JSON数据存储在VARCHAR或TEXT类型字段中,本文将详细介绍如何在MySQL中有效查询存储为V... 目录一、问题背景二、mysql jsON 函数2.1 常用 JSON 函数三、查询示例3.1 基本查询3.2

Pyserial设置缓冲区大小失败的问题解决

《Pyserial设置缓冲区大小失败的问题解决》本文主要介绍了Pyserial设置缓冲区大小失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录问题描述原因分析解决方案问题描述使用set_buffer_size()设置缓冲区大小后,buf

resultMap如何处理复杂映射问题

《resultMap如何处理复杂映射问题》:本文主要介绍resultMap如何处理复杂映射问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录resultMap复杂映射问题Ⅰ 多对一查询:学生——老师Ⅱ 一对多查询:老师——学生总结resultMap复杂映射问题

java实现延迟/超时/定时问题

《java实现延迟/超时/定时问题》:本文主要介绍java实现延迟/超时/定时问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java实现延迟/超时/定时java 每间隔5秒执行一次,一共执行5次然后结束scheduleAtFixedRate 和 schedu

如何解决mmcv无法安装或安装之后报错问题

《如何解决mmcv无法安装或安装之后报错问题》:本文主要介绍如何解决mmcv无法安装或安装之后报错问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mmcv无法安装或安装之后报错问题1.当我们运行YOwww.chinasem.cnLO时遇到2.找到下图所示这里3.

浅谈配置MMCV环境,解决报错,版本不匹配问题

《浅谈配置MMCV环境,解决报错,版本不匹配问题》:本文主要介绍浅谈配置MMCV环境,解决报错,版本不匹配问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录配置MMCV环境,解决报错,版本不匹配错误示例正确示例总结配置MMCV环境,解决报错,版本不匹配在col

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.

Vue3使用router,params传参为空问题

《Vue3使用router,params传参为空问题》:本文主要介绍Vue3使用router,params传参为空问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录vue3使用China编程router,params传参为空1.使用query方式传参2.使用 Histo