Hideonbush作者

约束优化的拉格朗日乘子(KKT)

  • 拉格朗日乘数法

  • 约束条件的集中形式

  • 求解不同约束条件问题的最优方法

本文讨论带有约束条件的最优化问题,约束条件分为两种,一种是等式约束;另一种是不等式约束。对于第一种等式约束的优化问题,可以直接利用拉格朗日乘子法去获得最优解;对于不等式约束的优化问题,可以转化未Karush–Kuhn–Tucker conditions(KKT条件)下去应用拉格朗日乘子法求解。也就是说都是应用拉格朗日乘数法求解。

一、拉格朗日乘数法

拉格朗日乘数法是一种优化算法,主要运用于解决优化问题,它的基本思想就是用过拉格朗日乘子来把含有m个变量和l个约束条件的约束优化问题转换成含有(m+l)个变量的无约束优化问题。

二、约束条件的集中形式


三、求解不同约束条件问题的最优方法

(1)等式条件下求最优解:

其实,高中的时候已经接触过等式条件机制求最优解的问题,都知道用拉格朗日乘数法可以求得最优解。首先构建一个Lagrange multiplier:

构建出 L(x,y,λ) 后,跟原来的问题对比一下,构建出的Lagrange multiplier把原来的等数条件约束情况变成含三个参数 (x,y,λ) 无条件极值的问题,最后可以通过求导数,令极值为零可以求出可行解 x 。

(拉格朗日乘子求的解不一定是最优解,其实只是局部最优解,这里称作可行解,只有在凸函数中才能保证最优解)至于为什么可以把原始的等式条件极值问题转化成求 L(x,y,λ) 的极值问题?可以观察一下下面的二维图:

图一

蓝色虚线是目标函数 f(x,y) 的等高线,绿色实现 g(x,y)=c 是约束条件。图中,目标函数和条件函数有三种情况:

1、相离

对于相离的情况,我们以前学过,两个函数有交点才说明是两个函数的解,所以相离明显不行。

2、相交

两个函数相交的才是两个函数的解,但是相交得到的一定不是最优值,因为相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部,使得新的等高线与目标函数的交点的值更大或者更小。

3、相切

图中,等高线与条件函数相切时候,只有一个交点,是可行解。

当等高线与条件函数在可行解处(相切时候)的梯度平行有下式:

对上式子移项后,可得到:

该式子恰好与令Lagrange multiplier的导数为零是式子相同。

举一个小栗子:

根据上式子可知是一个典型的约束优化问题,约束条件是等式,可以用拉格朗日乘子。

原来的条件约束问题,转化为无约束方程组问题。

(2)不等式条件下求最优解

上述都是等式条件约束的优化问题,但事实上,很多时候等式约束很难覆盖我们显示的问题,计算成本时候,通常说不能超过多少资金,不能超多多少时间,都是一个范围内,通常面对更多的是不等式条件约束的情况,面对这种情况,可以通过增加KKT条件后,通过拉格朗日乘子求解不等式约束的优化问题。

可以把目标函数和所有的约束条件写成一个式子:

对于不等式条件的情况有两种:即可行解在 g(x)<0 或者 g(x)=0 区域内取得(如下图)

图二

原文来自学员知乎作业

https://zhuanlan.zhihu.com/p/55532322

贪心科技
贪心科技

贪心科技是国内首家AI和大数据课程为主的自适应学习平台。我们追求最精炼的AI教育内容和个人量身定制的课堂。我们鼓励大家拥有“贪心精神”:对知识不断的渴望,对现状不满希望进步的愿望。贪心科技,满足贪心的你。

入门最优化问题拉格朗日乘数法KKT
3
相关数据
参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

导数技术

导数(Derivative)是微积分中的重要基础概念。当函数y=f(x)的自变量x在一点x_0上产生一个增量Δx时,函数输出值的增量Δy与自变量增量Δx的比值在Δx趋于0时的极限a如果存在,a即为在x0处的导数,记作f'(x_0) 或 df(x_0)/dx。

运筹优化技术

最优化问题(英语:Optimization problem)在数学与计算机科学领域中,是从所有可行解中寻找最优良的解的问题。根据变数是连续的或离散的,最佳化问题可分为两类:连续最佳化问题与组合优化。

目标函数技术

目标函数f(x)就是用设计变量来表示的所追求的目标形式,所以目标函数就是设计变量的函数,是一个标量。从工程意义讲,目标函数是系统的性能标准,比如,一个结构的最轻重量、最低造价、最合理形式;一件产品的最短生产时间、最小能量消耗;一个实验的最佳配方等等,建立目标函数的过程就是寻找设计变量与目标的关系的过程,目标函数和设计变量的关系可用曲线、曲面或超曲面表示。

知乎机构

知乎作为中文互联网知名知识内容平台,致力于构建一个人人都可接入的知识分享网络,让人们便捷地与世界分享知识、经验和见解,高效获得可信赖的解答。 目前,知乎已经覆盖「问答」社区、一站式知识服务平台「知乎大学」、短内容分享功能「想法」等一系列产品和服务,并建立了包括音频、视频在内的多元媒介形式。截止 2018 年 8 月底,知乎用户数已突破 2 亿,回答数超过 1.2 亿。未来,知乎进一步加大对 AI 技术和应用的投入,构建一个由 AI 驱动的智能社区,让知识普惠每一个人。

https://www.zhihu.com
推荐文章
暂无评论
暂无评论~