寻找“最好”(4)——不等约束和KKT条件

时间:2023-01-23 20:13:21

不等约束

  上篇文章介绍了如何在等式约束下使用拉格朗日乘子法,然而真实的世界哪有那么多等式约束?我们碰到的大多数问题都是不等约束。对于不等约束的优化问题,可以这样描述:

寻找“最好”(4)——不等约束和KKT条件

  其中f(x)是目标函数,g(x)为不等式约束,h(x)为等式约束,x = x1, x2, …… xk

  对于不等约束来说,无非是大于(包括大于等于)和小于(包括小于等于),常见的不等约束是这样:

寻找“最好”(4)——不等约束和KKT条件

  就像等式约束总是转换成g(x) = 0一样,我们也希望所有的不等约束都用小于号表达,所以首先将两个不等约束转换为小于0的形式:

寻找“最好”(4)——不等约束和KKT条件

优化问题的几何解释

  等式约束g(x) = 0可以在平面上画出等高线,它与f(x)相切的地方就是最小值。比如下面这个:

寻找“最好”(4)——不等约束和KKT条件

寻找“最好”(4)——不等约束和KKT条件

  f(x)和g(x)的等高线都是圆,在切点处二者的梯度梯度平行,因此可以引入拉格朗日乘子形成新的方程组求解。

  对于不等约束来说,g(x) ≤ 0是一个区域,而不是一条线,更准确地说,是很多条等高线堆叠而成的区域,我们把这块区域称为可行域。如果不考虑边界,不等约束有两种情况,一种是极小值点落在可行域内;另一种是极小值点落在可行域外。

  第一种情况相当于约束是多余的,直接求f(x)的极值即可,例如:

寻找“最好”(4)——不等约束和KKT条件

寻找“最好”(4)——不等约束和KKT条件

  f(x)极小值(0, 0)一定是符合约束的,它落在g(x)内,此时极小值点满足:

寻找“最好”(4)——不等约束和KKT条件

  其中条件1是求临界点,条件2是约束条件本身,只不过这个条件没有起到任何作用。拉格朗日乘子法当然少不了拉格朗日乘子,所以上式可以改写成:

寻找“最好”(4)——不等约束和KKT条件

  λg(x) = 0意味着g(x)是多余的,g(x)无论取什么值,最终结果都将是0。

  

  第二种情况才是正真需要考虑的,例如:

  寻找“最好”(4)——不等约束和KKT条件

寻找“最好”(4)——不等约束和KKT条件

  f(x)极小值(0, 0)落在g(x)外,这时候g(x)起了作用,需要考虑f(x)在g(x)区域内的极小值点。同等约束一样,在达到极小值点时,f(x)和g(x)的梯度平行,只不过这次是g(x)的梯度和f(x)的负梯度方向相同:

寻找“最好”(4)——不等约束和KKT条件

  此时,在极小值处满足:

寻找“最好”(4)——不等约束和KKT条件

  g(x) = 0表示极小值位于可行域边界。根据新的方程组可以求得极小值点。

  联合①和②,同时考虑极值点落在可行域内和可行域外两种情况,可以将方程组写成:

寻找“最好”(4)——不等约束和KKT条件

  在此之上加上约束条件g(x):

寻找“最好”(4)——不等约束和KKT条件

  更进一步,条件1可以看作新函数的梯度:

寻找“最好”(4)——不等约束和KKT条件

  方程组的解就是f(x)的极小值点,准确地说是候选极小值点。

  如果约束是g(x) < 0,方程组中同样需要用g(x) ≤ 0,否则就变成了λ = 0,引入拉格朗日乘子将没有任何意义。从几何意义上看,如果极值刚刚好满足g(x) < 0,也就是无限靠近边界,那么此时边界的极限就是g(x) = 0。

KKT条件

  KKT来源于人名,Karush-Kuhn-Tucker,其实是三个人,L arush、Kuhn和Tucker,这哥仨研究了不等约束下的最优化条件,所以叫KKT条件。

  带约束的优化可能同时包含等式优化约束和不等约束:

寻找“最好”(4)——不等约束和KKT条件

  求解问题的第一步是将所有约束和目标函数联立,其中λ和μ是拉格朗日乘子:

寻找“最好”(4)——不等约束和KKT条件

  再加使用上一节的结论③:

寻找“最好”(4)——不等约束和KKT条件

  这些求解条件就是KKT条件——带约束最优化问题的必要条件。KKT 条件看起来很多,其实很好理解:

  (1):目标函数和所有约束函数组成的拉格朗日函数;

  (2):学名叫互补松弛条件,不用在意叫什么。它的来历在上一节介绍过,实际上忘了来历也没关系,知道有它就行;

  (3)~(4):约束条件;

  (5)~(6):拉格朗日系数,符号与约束条件的相反(等号约束的拉格朗日系数λ用不等号,小于等于约束的拉格朗日系数μ用大于等于)。

  KKT条件可推广到更多的条件约束:

寻找“最好”(4)——不等约束和KKT条件

  将所有约束和目标函数联立:

寻找“最好”(4)——不等约束和KKT条件

  KKT条件:

寻找“最好”(4)——不等约束和KKT条件

regularity条件

  如果不等约束的一组解不满足KKT条件,它一定不是最优解;然而满足KKT条件的解也未必是最优解,这就如同鞍点一样。KKT是否是最优解的必要条件是通过regularity条件(Regularity Conditions)判断的。regularity条件要求所有起作用的g(x)和h(x)在极值点的梯度是线性无关的。在使用求解方程组时应当首先验证是否满足regularity条件。

示例

  求(x1 – 1)2 + (x2 + 2)2在满足约束条件x1 –x2 = 1和x1 + 10 x2 > 10下的极小值。

  将问题转换成数学语言:

寻找“最好”(4)——不等约束和KKT条件

寻找“最好”(4)——不等约束和KKT条件

  通过图像可以看出,存在唯一的极小值点,并且该点就是两个约束条件的交点,由此可以得到方程组:

寻找“最好”(4)——不等约束和KKT条件

  由于极值点在g(x)的边界,所以第二个条件可以改成等于,这就可以求得最终解:

寻找“最好”(4)——不等约束和KKT条件

  作图虽然直观,但并不总是能够作图,这就需要拉格朗日乘子法登场了。

  首先校验是否满足regularity条件:

寻找“最好”(4)——不等约束和KKT条件

  二者线性无关满足regularity条件。接下来将目标函数和约束条件转换成拉格朗日函数:

寻找“最好”(4)——不等约束和KKT条件

  再通过KKT条件建立方程组:

寻找“最好”(4)——不等约束和KKT条件

  方程一可以将x1和x2用λ和μ表示:

寻找“最好”(4)——不等约束和KKT条件

  将x1和x2代h(x):

寻找“最好”(4)——不等约束和KKT条件

  再将x1和x2代μg(x):

寻找“最好”(4)——不等约束和KKT条件

  当μ = 0时,

寻找“最好”(4)——不等约束和KKT条件

  这不满足约束条件g(x) ≤ 0。再来看μ = 80/99:

寻找“最好”(4)——不等约束和KKT条件

  所以当μ = 80/99能够得到极值点(20/11, 9/11),此时f(x)的极小值是:

寻找“最好”(4)——不等约束和KKT条件

相关代码

  带有不等式的方程组计算太过麻烦,好在Python的cvxpy包可以帮助我们解决优化问题。

  从https://www.lfd.uci.edu/~gohlke/pythonlibs/#cvxpy中下载cvxpy.whl.为保证cvxpy安装成功,还要将numpy升级到最新版,如果cvxpy是通过cvxpy.whl安装的,numpy也要通过下载.whl安装,否则将出现“ImportError: cannot import name 'NUMPY_MKL'”错误。

  下面是使用cvxpy求解示例1:

import cvxpy as cp

# 定义变量x1,x2
x1, x2 = cp.Variable(), cp.Variable()
# 定义目标函数
obj = cp.Minimize(cp.square(x1 - 1) + cp.square(x2 + 2))
# 定义约束条件
constraints = [x1 - x2 == 1, x1 + 10*x2 >= 10] # 求解
prob = cp.Problem(obj, constraints)
prob.solve() # status 的值:
# OPTIMAL: 问题被成功解决
# INFEASIBLE:问题无解
# UNBOUNDED:无边界
# OPTIMAL_INACCURATE:解不精确
print('status: ', prob.status)
print('Min value = ', prob.value)
print('(x1, x2) = (', x1.value, x2.value , ')')

  打印结果:

寻找“最好”(4)——不等约束和KKT条件


   作者:我是8位的

  出处:http://www.cnblogs.com/bigmonkey

  本文以学习、研究和分享为主,如需转载,请联系本人,标明作者和出处,非商业用途!

  扫描二维码关注公众号“我是8位的”

寻找“最好”(4)——不等约束和KKT条件