龙空技术网

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

青海说 1054

前言:

如今看官们对“拉格朗日算法的c程序”大致比较讲究,朋友们都想要分析一些“拉格朗日算法的c程序”的相关知识。那么小编在网摘上收集了一些关于“拉格朗日算法的c程序””的相关文章,希望咱们能喜欢,咱们快快来学习一下吧!

选自贪心学院NLP训练营

作者:Hideonbush

拉格朗日乘数法约束条件的集中形式求解不同约束条件问题的最优方法

本文讨论带有约束条件的最优化问题,约束条件分为两种,一种是等式约束;另一种是不等式约束。对于第一种等式约束的优化问题,可以直接利用拉格朗日乘子法去获得最优解;对于不等式约束的优化问题,可以转化未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 区域内取得(如下图)

图二

标签: #拉格朗日算法的c程序