约束优化之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

相关文章

Vue3 的 shallowRef 和 shallowReactive:优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉,那么对 shallowRef 和 shallowReactive 是否了解呢? 在编程和数据结构中,“shallow”(浅层)通常指对数据结构的最外层进行操作,而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素,而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层(Shallow) 定义

SQL中的外键约束

外键约束用于表示两张表中的指标连接关系。外键约束的作用主要有以下三点: 1.确保子表中的某个字段(外键)只能引用父表中的有效记录2.主表中的列被删除时,子表中的关联列也会被删除3.主表中的列更新时,子表中的关联元素也会被更新 子表中的元素指向主表 以下是一个外键约束的实例展示

HDFS—存储优化(纠删码)

纠删码原理 HDFS 默认情况下,一个文件有3个副本,这样提高了数据的可靠性,但也带来了2倍的冗余开销。 Hadoop3.x 引入了纠删码,采用计算的方式,可以节省约50%左右的存储空间。 此种方式节约了空间,但是会增加 cpu 的计算。 纠删码策略是给具体一个路径设置。所有往此路径下存储的文件,都会执行此策略。 默认只开启对 RS-6-3-1024k

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

使用opencv优化图片(画面变清晰)

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化,使其看起来更清晰,同时保持尺寸不变,通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多,主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器:相机传

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

MySQL高性能优化规范

前言:      笔者最近上班途中突然想丰富下自己的数据库优化技能。于是在查阅了多篇文章后,总结出了这篇! 数据库命令规范 所有数据库对象名称必须使用小写字母并用下划线分割 所有数据库对象名称禁止使用mysql保留关键字(如果表名中包含关键字查询时,需要将其用单引号括起来) 数据库对象的命名要能做到见名识意,并且最后不要超过32个字符 临时库表必须以tmp_为前缀并以日期为后缀,备份

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k