KKT条件

2020-11-18 本文已影响0人热爱生活的大川

定义

优化问题：
$\begin{aligned} & \max{f(x)} \\ s.t.\quad & h_j(x)=0, \quad j=1,2...q \\ & g_i(x) \le 0, \quad i=1,2,...p \end{aligned}$
的解 $x^*$ 满足如下条件
$\begin{aligned} & \nabla{f(x^*)}=\sum\lambda_j\nabla{h_j(x^*)}+\sum\mu_i\nabla{g_i(x^*)} \\ & \mu_i \ge 0,\quad \mu_ig_i(x^*) = 0 \end{aligned}$
该条件即KKT条件。

解释

无约束条件时，局部极值点在梯度为0时取得。例如，当 $x^*$ 为局部极大值点，则 $x^*$ 在任一方向移动（一个任意小距离）时函数值应不增加。

有约束条件时，局部极值点的梯度需满足在可行方向内无分量。例如，当 $x^*$ 为约束条件下的局部极大值点，则 $x^*$ 在可行域内任一方向移动（一个任意小距离）时函数值应不增加。

总可行方向是各个约束下可行方向的交集，于是各个约束不可行方向的并集就在总可行方向上无分量。

当 $h_j(x^*)=0$ 时，不可行方向为 $\lambda_j\nabla{h_j(x^*)}$ ；
当时，不可行方向为。可由以下两种情况整合而来。
- 当 $g_i(x^*)=0$ 时，不可行方向为 $\mu_i\nabla{g_i(x^*)}， \mu_i \ge 0$ ；
- 当 $g_i(x^*)<0$ 时，不可行方向为 $\emptyset$ ，可表示为 $\mu_i\nabla{g_i(x^*)}， \mu_i=0$ 。

于是 $\nabla{f(x^*)}$ 可表示为以上两种情况的线性组合。因为是或的关系，各个不可行方向上的分量可以是0（"或"表示只要某一个不为0，就已经满足可行方向无分量；当然，全为0表示f本身取到了极值点，任意方向无分量）。

KKT条件

定义

解释

猜你喜欢

热点阅读