↑↑↑↑↑点击上方蓝色字关注我们！

『运筹OR帷幄』原创
作者：苏向阳
编者按：
本文一共分为三个部分，第一部分为优化问题的求解，从无约束优化到等式约束优化再到不等式约束优化，采用图解的方式来阐述求解理论。第二部分为拉格朗日对偶问题的说明，介绍了强对偶和弱对偶及其证明。第三个部分KKT条件求解优化问题的例子。

1.优化问题的求解

优化问题的通用形式如下：
为求解(1)中问题，我们可以依据拉格朗日对偶理论将其构造为新问题：
为求解问题(2)，下面主要从简单的无约束的优化（0梯度条件），到等式约束优化(拉格朗日条件)，再到不等式约束优化（KKT条件）进行讲解。

1.1无约束优化

首先明确梯度概念：
梯度：在梯度方向上，自变量的细微变动，导致目标函数值增加超过其他任何方向。
最优解处梯度的模为0。
图1.  无约束优化三维图
    在图1中，展示了无约束优化的三维情况。根据图形可以看出当Z取值为图形的A点对应的z轴坐标时，
的值最小。
无约束优化的通用形式：
对于无约束优化问题，使用基本的高等数学求偏导再求极值就可以进行求解。为更好的解释优化问题，这里采用等高线的形式来进行说明。
图2. 无约束优化情况下函数的等高线图
图2中的等高线图可以看作是图1的投影图，图2中的红点可以看做是图1中A点的投影。显而易见红点为
的极小值点。

1.2带等式约束的优化

等式约束优化的一般形式如下：
对于带等式约束的优化问题可由图形表示为：
图3. 带等式约束情况下函数的等高线图
假定函数
切于图3中的红点处。由梯度的性质可知，梯度的方向与切线方向垂直，因此
在红点处的梯度方向共线。即：
其中
表示红点处的变量值。因此可以构造一个函数：
对公式(6)求偏导，就可以得到拉格朗日条件。
此时，带等式约束的优化问题就转化为了无约束的优化问题，只需要对拉格朗日条件解方程即可。这里的
为拉格朗日乘子，一般来说，有多少等式约束就有多少个拉格朗日乘子。
拉格朗日定理：设点
是函数
的一个极小点，约束条件为
，那么 
与
平行，如果
，则存在标量
，使得
公式(7)为拉格朗日条件，而且拉格朗日条件对极大值求解情况也同样成立。
在这里要说明一下，拉格朗日条件是必要条件而非充分条件。即拉格朗日条件满足但不一定代表该点为极值点。给出如下的例子：
图4.   四个拉格朗日条件满足的例子
在图4中一共有四幅子图，其中(a)中 
的表示极大点， (b)、(c)中的
表示极小点， (d)中的
即不是极大也不是极小。分别对上述情况进行解释：
首先由梯度方向来判断极小值点的位置，根据前面的分析可以了解到，极小值点的位置与梯度方向相反。因此，(a)中无约束情况下的极小值点位于图片的下方，图(a)中
点为
距离极小值最远点，因此
为带等式约束情况下的极大值点。图(b)中无约束情况下的极小值点位于图片的下方，
点为
距离极小值最近点，因此为带等式约束情况下的极小值点。图(c)中无约束情况下的极小值点位于图片的上方，
点为  
距离极小值最近点，因此为带等式约束情况下的极小值点。图(d)比较明显，既不是极大也不是极小。

1.3不等式约束优化问题

不等式约束优化问题的一般形式：
当只有一个不等式起作用时，如图5：
图5.一个不等式约束的优化问题
此时可行域变为了阴影部分，只需要将不等式约束看做等式约束便可求解。
如果是两个不等式约束，求解思路需要改变，首先还是给出一般形式：
此时用图形表示见图6所示：
图6. 两个不等式约束情况下的优化问题
参见对等式约束情况下的分析，我们可以画出
和
的梯度方向，为满足拉格朗日条件，因此需要构造标量
和
：
除此之外，为了满足条件(9)，红色箭头要在绿色箭头中间，因此还应该满足如下条件：
由于图6中极值点在
的交点上，因此应满足：
这里的(10)-(12)即为KKT条件（卡罗需-库恩-塔克）。其中
和 
叫做KKT乘子，有多少个不等式约束就有多少个KKT乘子。加上(9)中的不等式约束就是完整的KKT条件。满足KKT条件是拉格朗日法求得可行解的必要条件。

2.拉格朗日法对偶理论

2.1 对偶理论的阐述

凸优化：目标函数为凸函数且约束集为凸集的情况下为凸优化。目前来说，凸优化是一定可以求解出最优解的优化问题。（凸优化中，局部极小值点为全局最小值点。）
假设 
是定义在
上的连续可微函数，考虑约束最优化问题：
称为约束最优化问题的原始问题。现在如果不考虑约束条件，原始问题就是：
对
求导数，然后令导数为0，就可解出最优解。
引入广义拉格朗日函数：
是上文中的拉格朗日乘子，特别要求
 。
现在，如果把
看作是关于
的函数，求其最大值，即：
这时
是一个关于
的函数，假定
是常量，确定了
的值便可以得到
的最大值。而实际上
的值并不是固定的常量，如果说假定
的值确定，那么
是只与
有关的函数，定义这个函数为：
结合公式(15)可将(17)表达为如下形式：
下面通过
是否满足约束来分析公式(18)：
通过上述分析可知：
因此，当
满足约束时：
此时，
问题与
问题等价，可以采用
来代替原始问题，定义原始问题最优解为：
定义关于
的函数：
等式右边是关于
函数的最小化，因此
在确定
之后，其最小值只与
有关。考虑公式(23)的极大值求解：
公式(24)即为原始问题的对偶问题，原始问题形式如下：
可以看出，公式(24)和公式(25)形式上很对称，只不过原始问题是先固定
中的
，优化
的值，再优化最优
。而对偶问题是先固定
，优化
的值，再确定参数
。
定义对偶问题的最优值：
 若原问题与对偶问题都有最优值，则
总是成立的，这个我们也叫做弱对偶性，如果说我们能够使得
，那么这时候我们求解对偶问题就相当于求解原问题了。什么时候对偶问题等价于原问题（这种情况叫做强对偶）？一般情况下，如果原问题是凸优化的，那么这个问题具有强对偶，也就是对偶问题的最优解等于原问题的最优解（不绝对，也有例外）。对偶间隙是指
和
的差值。

2.2 对偶理论的证明

证明
恒成立：
即：
由于原问题与对偶问题都有最优值，所以：
至于，为什么要求对偶函数，是由于很多原函数并不是凸函数，所以需要转化为对偶函数求解，附上一张图：
图7.原函数与对偶函数
图7中，实线表示目标函数，虚线代表约束空间，彩点代表不同拉格朗日乘子时的拉格朗日函数。图7中，紫色的线条是很明显的凸函数，函数便能借助凸优化的问题进行求解。

3.例子-KKT条件求解优化问题

        已知图8中所示电路，试确定电阻
的值，使得该电阻消耗电能最大，列出问题的KKT条件并求解。
图8.电路示意图
按照电路理论的知识可知：
其中
即：
约束为：
，对公式(32)求导：
对目标函数构造拉格朗日函数为：
KKT条件为：
假设
，则
与条件1矛盾，因此假设
，由条件1得
，因此KKT条件的唯一解为
和
。
虽然我们用了一种看似很笨拙的方法求解了这个问题，但是在一些大规模实际问题的求解中，我们很难直接有效找到求解方法和理论，这个时候，KKT条件的重要性便得到了凸显。
参考文献：
Chong E K P , Stanislaw H. Żak. An Introduction to Optimization[J]. IEEE Antennas and Propagation Magazine, 1996, 38(2):60.（这本书有中文翻译版，看不懂英文的小伙伴可以直接搜"最优化导论（孙志强）"）
温馨提示
可以在 本公众号后台 回复关键词：“供应链”获取大量由我平台编辑精心整理的学习资料，如果觉得有用， 请勿吝啬你的留言和赞哦！~
—— 完 ——
文章申明
Sept. 2019
文章作者：苏向阳
责任编辑：王源
微信编辑：葡萄
文章由『运筹OR帷幄』原创发布，如需转载请在公众号后台获取转载须知
优质公众号推荐
点击查看详情
继续阅读
阅读原文