专栏文章汇总


文章结构如下:

1: 等式约束优化问题

2: 不等式约束优化问题

3: 一个例子


注:本文来自台湾周志成老师《线性代数》及其博客

Karush-Kuhn-Tucker (KKT)条件是非线性规划(nonlinear programming)最佳解的必要条件。KKT条件将Lagrange乘数法(Lagrange multipliers)所处理涉及等式的约束优化问题推广至不等式。在实际应用上,KKT条件(方程组)一般不存在代数解,许多优化算法可供数值计算选用。这篇短文从Lagrange乘数法推导KKT条件并举一个简单的例子说明解法。


1: 等式约束优化问题

给定一个目标函数 [公式] ,我们希望找到 [公式] ,在满足约束条件 [公式] 的前提下,使得 [公式] 有最小值。这个约束优化问题记为

[公式]
为方便分析,假设 [公式][公式] 是连续可导函数。Lagrange乘数法是等式约束优化问题的典型解法。定义Lagrangian函数

[公式]
其中 [公式] 称为Lagrange乘数。Lagrange乘数法将原本的约束优化问题转换成等价的无约束优化问题

[公式]
计算 [公式][公式][公式] 的偏导数并设为零,可得最优解的必要条件:

[公式]
其中第一式为定常方程式(stationary equation),第二式为约束条件。解开上面 [公式] 个方程式可得 [公式] 的stationary point [公式] 以及 [公式] 的值(正负数皆可能)。


2: 不等式约束优化问题

接下来我们将约束等式 [公式] 推广为不等式 [公式] 。考虑这个问题

[公式]
约束不等式 [公式] 称为原始可行性(primal feasibility),据此我们定义可行域(feasible region) [公式] 。假设 [公式] 为满足约束条件的最佳解,分开两种情况讨论:

(1) [公式] ,最佳解位于 [公式] 的内部,称为内部解(interior solution),这时约束条件是无效的(inactive);

(2) [公式] ,最佳解落在 [公式] 的边界,称为边界解(boundary solution),此时约束条件是有效的(active)。

这两种情况的最佳解具有不同的必要条件。

(1)内部解:在约束条件无效的情形下, [公式] 不起作用,约束优化问题退化为无约束优化问题,因此驻点 [公式] 满足 [公式][公式]

(2)边界解:在约束条件有效的情形下,约束不等式变成等式 [公式] ,这与前述Lagrange乘数法的情况相同。我们可以证明驻点 [公式] 发生于 [公式] ,换句话说,存在 [公式] 使得 [公式] ,但这里 [公式] 的正负号是有其意义的。因为我们希望最小化 [公式] ,梯度 [公式] (函数 [公式] 在点 [公式] 的最陡上升方向)应该指向可行域 [公式] 的内部(因为你的最优解最小值是在边界取得的),但 [公式] 指向 [公式] 的外部(即 [公式] 的区域,因为你的约束是小于等于0),因此 [公式] ,称为对偶可行性(dual feasibility)

因此,不论是内部解或边界解, [公式] 恒成立,称为互补松弛性(complementary slackness)。整合上述两种情况,最佳解的必要条件包括Lagrangian函数 [公式] 的定常方程式、原始可行性、对偶可行性,以及互补松弛性:

[公式]
这些条件合称为Karush-Kuhn-Tucker (KKT)条件。如果我们要最大化 [公式] 且受限于 [公式] ,那么对偶可行性要改成 [公式]

上面结果可推广至多个约束等式与约束不等式的情况。考虑标准约束优化问题(或称非线性规划):

[公式]

定义Lagrangian 函数

[公式]
其中 [公式] 是对应 [公式] 的Lagrange乘数, [公式] $是对应 [公式] 的Lagrange乘数(或称KKT乘数)。KKT条件包括

[公式]

注:感谢评论区 追梦的lin 提出,在使用KKT条件时需要满足Regularity conditions (or constraint qualifications),维基在第三部分有了介绍: Karush-Kuhn-Tucker conditions 。比较常见的是Linearity constraint qualification (LCQ),即约束条件是仿射函数。

3: 一个例子

考虑这个问题

[公式]
其中 [公式] 为实数。写出Lagrangigan函数

[公式]
KKT 方程组如下:

[公式]
求偏导可得 [公式][公式] ,分别解出 [公式][公式] 。代入约束等式 [公式][公式] 。合并上面结果,

[公式]
最后再加入约束不等式 [公式][公式] 。底下分开三种情况讨论。

(1) [公式] :不难验证 [公式] 满足所有的KKT条件,约束不等式是无效的, [公式] 是内部解,目标函数的极小值是 [公式]

(2) [公式] :如同1, [公式] 满足所有的KKT条件, [公式] 是边界解,因为 [公式]

(3) [公式] :这时约束不等式是有效的, [公式] ,则 [公式][公式] ,目标函数的极小值是 [公式]


4: 参考文献

周志成:《线性代数》,国立交通大学出版社

Karush-Kuhn-Tucker (KKT) 條件

Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐