搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 酷酷的群 > 约束优化问题|机器学习推导系列(六)

约束优化问题|机器学习推导系列(六)

酷酷的群 2020-08-02

一、简介

约束优化问题的原问题(Primal Problem)的一般形式如下:

求解约束优化问题需要用到拉格朗日乘子法,定义拉格朗日函数:

约束优化问题|机器学习推导系列(六)

然后原问题可以转化为以下优化问题,这两个优化问题具有同样的解:

约束优化问题|机器学习推导系列(六)

可以说明一下为什么上述约束优化问题可以求得原问题的最优解:

约束优化问题|机器学习推导系列(六)

也就是说虽然拉格朗日函数对约束优化问题|机器学习推导系列(六)没有约束,但是在求解过程中会过滤掉不符合原问题约束优化问题|机器学习推导系列(六)的约束的约束优化问题|机器学习推导系列(六)

二、对偶关系证明

原问题的对偶问题(Dual Problem)为

约束优化问题|机器学习推导系列(六)

可以看到原问题是关于约束优化问题|机器学习推导系列(六)的函数,对偶问题是关于约束优化问题|机器学习推导系列(六)的函数。有如下定理:

约束优化问题|机器学习推导系列(六)

这个关系可以简单地得到证明:

约束优化问题|机器学习推导系列(六)

三、对偶性的几何解释

约束优化问题|机器学习推导系列(六)

对于上述约束优化问题,可以写出它的拉格朗日函数:

约束优化问题|机器学习推导系列(六)

然后表示出原问题和对偶问题的最优解约束优化问题|机器学习推导系列(六)约束优化问题|机器学习推导系列(六)

约束优化问题|机器学习推导系列(六)

接着定义集合G:

约束优化问题|机器学习推导系列(六)

集合G在二维坐标系下表示的空间假设为下图:

约束优化问题|机器学习推导系列(六)

因此约束优化问题|机器学习推导系列(六)可以表示为:

约束优化问题|机器学习推导系列(六)

约束优化问题|机器学习推导系列(六)在图中可以表示为:

约束优化问题|机器学习推导系列(六)

同样地约束优化问题|机器学习推导系列(六)也可以用约束优化问题|机器学习推导系列(六)约束优化问题|机器学习推导系列(六)来表示:

约束优化问题|机器学习推导系列(六)

约束优化问题|机器学习推导系列(六)表示以约束优化问题|机器学习推导系列(六)为斜率,以约束优化问题|机器学习推导系列(六)为截距的直线,而约束优化问题|机器学习推导系列(六)即为与区域约束优化问题|机器学习推导系列(六)相切最小截距的直线约束优化问题|机器学习推导系列(六)。如下图所示:

约束优化问题|机器学习推导系列(六)

结合上图来看,而约束优化问题|机器学习推导系列(六)也就可以认为是调整斜率约束优化问题|机器学习推导系列(六)使得直线约束优化问题|机器学习推导系列(六)截距约束优化问题|机器学习推导系列(六)最大时的约束优化问题|机器学习推导系列(六)的值。可以想象无论直线怎么变动,所取得的极值约束优化问题|机器学习推导系列(六)都不可能比约束优化问题|机器学习推导系列(六)大,这也就解释了为什么对偶问题最优解总是小于等于原问题最优解。

如果约束优化问题|机器学习推导系列(六)则为弱对偶关系;如果约束优化问题|机器学习推导系列(六)则为强对偶关系。

在某些特殊情况下可以使得强对偶关系成立,在图中表示如下:

约束优化问题|机器学习推导系列(六)

如果一个约束优化问题是凸优化问题且同时满足Slater条件,那么可以使得约束优化问题|机器学习推导系列(六)

约束优化问题|机器学习推导系列(六)

但是约束优化问题|机器学习推导系列(六)并不能推出该约束优化问题是凸优化问题且同时满足Slater条件,这是因为Slater条件是约束优化问题|机器学习推导系列(六)的充分不必要条件,还有其他的条件可以使得约束优化问题满足约束优化问题|机器学习推导系列(六)

四、Slater条件

Slater条件指的是约束优化问题|机器学习推导系列(六)使得约束优化问题|机器学习推导系列(六)

约束优化问题|机器学习推导系列(六)指的是定义域除去边界的部分。

有以下两点说明:
①对于大多数凸优化问题,Slater条件是成立的;
②放松的Slater条件:M个约束优化问题|机器学习推导系列(六)中的仿射函数可以不用验证。因为在定义域内寻找一个满足所有约束优化问题|机器学习推导系列(六)的点是比较困难的,因此放松的Slater条件会减少一些复杂度。

五、KKT条件

对于原问题:

约束优化问题|机器学习推导系列(六)

以及其对偶问题:

约束优化问题|机器学习推导系列(六)

如果原问题和对偶问题满足强对偶关系,则原问题和对偶问题具有相同的最优解,另外它们还天然地满足KKT条件(Karush-Kuhn-Tucker条件)。假设原问题最优解约束优化问题|机器学习推导系列(六)对应约束优化问题|机器学习推导系列(六),对偶问题最优解约束优化问题|机器学习推导系列(六)对应约束优化问题|机器学习推导系列(六)和 约束优化问题|机器学习推导系列(六),则KKT条件为:

可以进行以下证明:


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《约束优化问题|机器学习推导系列(六)》的版权归原作者「酷酷的群」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注酷酷的群微信公众号

酷酷的群微信公众号:CcQun19990728

酷酷的群

手机扫描上方二维码即可关注酷酷的群微信公众号

酷酷的群最新文章

精品公众号随机推荐