CS205A Lecture 11 Optimization; Multiple variables, constraints

课程主页：https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html

这次回顾第十一讲，这一讲介绍了BFGS和KKT条件。

黄金分割搜索

定义8.5 (Unimodular)

$$函数f:[a,b]\to \mathbb R是\text{unimodular}，如果存在x' \in [a,b]使得f在[a,x']递增，在x\in [x',b]递减$$

下面讨论如何求满足unimodular性质的函数$f$的最小值$x’​$，首先不难想象这种函数的图像是U字型的，所以可以使用类似二分法的思路求解。

假设我们有两个点$a<x_0<x_1<b​$，接下来分两种情形讨论：

• 如果$f(x_0 )\ge f(x_1)$，那么对$x\in [a, x_0]$，我们有$f(x)\ge f(x_1)$，最小值点$x’ \in [x_0, b]$，所以删除区间$[a, x_0]$
• 如果$f(x_1 )\ge f(x_0)$，那么对$x\in [x_1, b]$，我们有$f(x)\ge f(x_0)$，最小值点$x’\in [a,x_1]$，所以删除区间$[x_1, b]$

迭代上述算法即可求出最小值点。注意上述方法每一轮将区间需要计算两个函数值，如果计算$f$的成本很大，我们应该希望可以重复利用之前计算的结果，下面讨论如何实现这点。为了讨论方便，不妨假设$a=0, b=1​$，一般情形可以通过平移和伸缩化为该情形。假设第一轮选择的点为

$$x_0 =\alpha ,x_1 =1-\alpha, \alpha\in (0,\frac 12 )$$

如果第二轮的区间为

$$[a, x_1] =[0, 1-\alpha]$$

那么第二轮选择的点为

$$\alpha(1-\alpha) ,(1-\alpha)^2$$

如果

$$x_0 =\alpha =(1-\alpha)^2=x_1'$$

那么可以少计算一次函数值，解该方程可得

$$\begin{aligned} \alpha^2 -3\alpha +1 &=0\\ \alpha &=\frac{1}{2}(3-\sqrt{5}) \\ 1-\alpha &=\frac{1}{2}(\sqrt{5}-1) \end{aligned}$$

所以$1-\alpha =\tau​$是黄金分割比例。

如果第二轮的区间为

$$[x_0, 1]=[\alpha ,1]$$

那么第二轮选择

$$\alpha+\alpha(1-\alpha ) ,\alpha +(1-\alpha)^2$$

如果

$$x_1 =1-\alpha =\alpha+\alpha(1-\alpha )=x_0'$$

那么可以少计算一次函数值，解该方程可得：

$$\begin{aligned} \alpha^2 -3\alpha +1 &=0\\ \alpha &=\frac{1}{2}(3-\sqrt{5}) \\ 1-\alpha &=\frac{1}{2}(\sqrt{5}-1) \end{aligned}$$

$1-\alpha =\tau$依旧是黄金分割比例。

将上述讨论总结，即得到如下算法：

• 令$\tau =\frac 12 (\sqrt 5 -1)$，选择$a,b$使得$f$在$[a,b]$上unimodular

• 选择初始划分

  $$x_0 =a+(1-\tau )(b-a), x_1=a+\tau(b-a)$$

• 初始化

  $$f_0 =f(x_0), f_1=f(x_1)$$

• 迭代直至$b-a$充分小：

  • 如果$f_0 \ge f_1​$，那么按如下方式删除区间$[a, x_0]​$：
    • 移动左端点：$a\leftarrow x_0$
    • 重复使用上一轮的值：$x_0 \leftarrow x_1, f_0 \leftarrow f_1$
    • 生成新的样本点：$x_1 \leftarrow a+\tau(b-a), f_1 \leftarrow f(x_1)$
  • 如果$f_1 >f_0$,那么按如下方式删除区间$[x_1, b]$：
    • 移动右端点：$b\leftarrow x_1$
    • 重复使用上一轮的值：$x_1 \leftarrow x_0 ,f_1 \leftarrow f_0$
    • 生成行的样本点：$x_0 \leftarrow a+(1-\tau)(b-a),f_0 \leftarrow f(x_0)$

多变量情形

这一部分考虑

$$f:\mathbb R^n \to \mathbb R$$

的无条件优化问题。

梯度下降

上一讲我们讨论过，如果$\nabla f(\vec x )\neq \vec 0$，那么对于充分小的$\alpha >0$，我们必然有

$$f(\vec x -\alpha \nabla f(\vec x))\le f(\vec x )$$

所以考虑如下函数

$$g_k(t) =f(\vec x_k -t\nabla f(\vec x_k))$$

我们可以搜索$t$，使得上式达到最小值，于是有如下算法：

1. 选择初始估计值$\vec x_0 $
2. 迭代直至$\vec x_k$收敛：
   • 令$g_k(t)=f(\vec x_k -t\nabla f(\vec x_k))$
   • 使用一维搜索算法找到$t’$，使得$g_k $最小化（$t\ge 0$）
   • 令$\vec x_{k+1} =\vec x_k -t’ \nabla f(\vec x_k)$

牛顿法

多元情形也可以使用牛顿法，首先使用泰勒展开

$$f(\vec{x}) \approx f\left(\vec{x}_{k}\right)+\nabla f\left(\vec{x}_{k}\right)^T \cdot\left(\vec{x}-\vec{x}_{k}\right)+\frac{1}{2}\left(\vec{x}-\vec{x}_{k}\right)^T \cdot H_{f}\left(\vec{x}_{k}\right) \cdot\left(\vec{x}-\vec{x}_{k}\right)$$

对右边的式子关于$\vec x$求梯度可得

$$\nabla f(\vec x)\approx \nabla f\left(\vec{x}_{k}\right) + H_{f}\left(\vec x- \vec{x}_{k}\right)$$

令上式为$\vec 0​$可得

$$\vec{x}_{k+1}=\vec{x}_{k}-\left[H_{f}\left(\vec{x}_{k}\right)\right]^{-1} \nabla f\left(\vec{x}_{k}\right)$$

迭代该算法最终得到$\vec x ‘$。

注意如果$H_f$不是半正定矩阵，那么$\vec x ‘$可能是鞍点，所以使用牛顿法之前需要判断$H_f$是否是半正定矩阵。

拟牛顿法——$BFGS$

牛顿法需要计算$\left[H_{f}\left(\vec{x}_{k}\right)\right]^{-1}$，而这往往需要很大计算量和存储量，类似折线法，我们可以认为Hessian矩阵满足

$$B_{k+1}\left(\vec{x}_{k+1}-\vec{x}_{k}\right)=\nabla f\left(\vec{x}_{k+1}\right)-\nabla f\left(\vec{x}_{k}\right)$$

令

$$\begin{aligned} \vec{s}_{k} &= \vec{x}_{k+1}-\vec{x}_{k}\\ \vec{y}_{k} &=\nabla f\left(\vec{x}_{k+1}\right)-\nabla f\left(\vec{x}_{k}\right) \end{aligned}$$

注意$B_k$是对称矩阵，所以可得得到如下优化问题：

$$\begin{aligned} {\text { minimize }_{B_{k+1}}} & {\left\|B_{k+1}-B_{k}\right\|} \\ {\text { such that }} & {B_{k+1}^T=B_{k+1}}\\ & B_{k+1} \vec{s}_{k}=\vec{y}_{k} \end{aligned}$$

注意到我们最终需要计算的是

$$\delta \vec{x}=-B_{k}^{-1} \nabla f\left(\vec{x}_{k}\right)$$

而${\left|B_{k+1}-B_{k}\right|}$很小并不能推出$\left|H_{k+1}-H_{k}\right|$很小，所以应该求解如下问题：

$$\begin{aligned} {\text { minimize }_{H_{k+1}}} & {\left\|H_{k+1}-H_{k}\right\|} \\ {\text { such that }} & {H_{k+1}^T=H_{k+1}}\\ & \vec{s}_{k}=H_{k+1}\vec{y}_{k} \end{aligned}$$

求解该优化问题后，我们计算下式即可

$$\delta \vec{x}=-H_{k+1}\nabla f\left(\vec{x}_{k+1}\right)$$

选择不同的范数会得到不同结果，下面推导著名的BFGS算法。假设$A,W$是$n$阶对称矩阵，定义

$$\begin{aligned} \| A\|_W^2 &= \text{Tr}(A^TW^T AW)\\ &=\sum_{ij} (A^TW^T)_{ji} (AW)_{ij}\\ &= \sum_{ij} (WA)_{ij} (AW)_{ij}\\ &=\sum_{ij} (\vec w_i .\vec a_j) (\vec w_j .\vec a_i) \end{aligned}$$

记

$$\begin{aligned} H&= H_{k+1},H'= H_k\\ H&= \left[ \begin{matrix} \vec h_1 & \ldots & \vec h_n \\ \end{matrix} \right] \\ H'&= \left[ \begin{matrix} \vec h_1' & \ldots & \vec h_n' \\ \end{matrix} \right] \\ W&= \left[ \begin{matrix} \vec w_1 & \ldots & \vec w_n \\ \end{matrix} \right] \end{aligned}$$

这里我们假定

$$\begin{aligned} H^T&= H\\ (H')^T&= H'\\ W^T&= W\\ H \vec{y} &=\vec{s}\\ W \vec{s}&=\vec{y} \end{aligned}$$

在上述范数的情形下，可以构造如下拉格朗日乘子：

$$\begin{aligned} \Lambda &= \sum_{i j}\left(\vec{w}_{i} \cdot\left(\vec{h}_{j}-\vec{h}_{j}'\right)\right)\left(\vec{w}_{j} \cdot\left(\vec{h}_{i}-\vec{h}_{i}'\right)\right)-\sum_{i<j} \alpha_{i j}\left(H_{i j}-H_{j i}\right)-\vec{\lambda}^T\left(H \vec{y}_{k}-\vec{s}_{k}\right) \\ &=\sum_{i j}\left(\vec{w}_{i} \cdot\left(\vec{h}_{j}-\vec{h}_{j}'\right)\right)\left(\vec{w}_{j} \cdot\left(\vec{h}_{i}-\vec{h}_{i}'\right)\right)-\sum_{i j} \alpha_{i j} H_{i j}-\vec{\lambda}^T\left(H \vec{y}_{k}-\vec{s}_{k}\right) & \alpha_{ij}=-\alpha_{ji} \end{aligned}$$

在上述条件下，取矩阵$A$满足

$$\begin{aligned} A_{ij}&= a_{ij} \end{aligned}$$

那么

$$A^T =-A$$

因为

$$\begin{aligned} \frac{\partial} {\partial H_{st}} \left(\sum_{i j}\left(\vec{w}_{i} \cdot\left(\vec{h}_{j}-\vec{h}_{j}'\right)\right) \left(\vec{w}_{j} \cdot\left(\vec{h}_{i}-\vec{h}_{i}'\right)\right)\right) &=\sum_{i j}\frac{\partial} {\partial H_{st}}\left( \vec{w}_{i} \cdot\left(\vec{h}_{j}-\vec{h}_{j}'\right)\right) \left(\vec{w}_{j} \cdot\left(\vec{h}_{i}-\vec{h}_{i}'\right)\right)\\ &+\sum_{i j}\left(\vec{w}_{i} \cdot\left(\vec{h}_{j}-\vec{h}_{j}'\right)\right) \left(\frac{\partial} {\partial H_{st}}\vec{w}_{j} \cdot \left(\vec{h}_{i}-\vec{h}_{i}'\right)\right) \\ &=\sum_{i j}\left(\frac{\partial} {\partial H_{st}}\sum_k w_{ik} (H_{kj}- H_{kj}')\right) \left(\vec{w}_{j} \cdot\left(\vec{h}_{i}-\vec{h}_{i}'\right)\right)\\ &+\sum_{i j}\left(\vec{w}_{i} \cdot\left(\vec{h}_{j}-\vec{h}_{j}'\right)\right) \left(\frac{\partial} {\partial H_{st}}\sum_k w_{jk} (H_{ki}- H_{ki}')\right)\\ &=\sum_{i} w_{is} \left(\vec{w}_{t} \cdot\left(\vec{h}_{i}-\vec{h}_{i}'\right)\right) + \sum_{j} w_{js}\left(\vec{w}_{t} \cdot\left(\vec{h}_{j}-\vec{h}_{j}'\right)\right) \\ &= 2\sum_{i} w_{is} \left(\vec{w}_{t} \cdot\left(\vec{h}_{i}-\vec{h}_{i}'\right)\right) \end{aligned}$$

那么关于$H_{ij}$求偏导并令其为$0​$可得

$$\begin{aligned} 0=\frac{\partial \Lambda}{\partial H_{i j}} &=\sum_{\ell} 2 w_{ \ell i}\left(\vec{w}_{j} \cdot\left(\vec{h}_{\ell}-\vec{h}_{\ell}'\right)\right)-\alpha_{i j}-\lambda_{i} y_{j} \\ &=2 \sum_{\ell} w_{\ell i}\left(W^{T}\left(H-H'\right)\right)_{j \ell}-\alpha_{i j}-\lambda_{i} y_{j} \\ &=2 \sum_{\ell}\left(W^{T}\left(H-H'\right)\right)_{j \ell} w_{\ell i}-\alpha_{i j}-\lambda_{i} y_{j} \\ &=2\left(W^{T}\left(H-H'\right) W\right)_{j i}-\alpha_{i j}-\lambda_{i} y_{j} \\ &=2\left(W\left(H-H'\right) W\right)_{i j}-\alpha_{i j}-\lambda_{i} y_{j} &由W和H的对称性\end{aligned}$$

矩阵形式为

$$\begin{eqnarray*} 0 &=2 W\left(H-H'\right) W-A-\vec{\lambda} \vec{y}^{T} \tag 1 \end{eqnarray*}$$

对(1)取转置，结合这些矩阵的性质可得

$$0=2 W\left(H-H'\right) W+A-\vec{y} \vec{\lambda}^{T} \tag 2$$

(1)+(2)可得

$$0 =4 W\left(H-H'\right) W-\vec{\lambda} \vec{y}^{T}-\vec{y} \vec{\lambda}^{T} \tag 3$$

右乘$\vec s​$得到

$$\begin{eqnarray*} \vec 0 &&=4 W\left(H-H'\right) W \vec s-\vec{\lambda} \vec{y}^{T}\vec s- \vec{y} \vec{\lambda}^{T}\vec s\\ &&=4 W\left(H-H'\right) \vec{y}-\vec{\lambda} (\vec{y}.\vec s)- \vec{y} (\vec{\lambda}.\vec s) &&W \vec{s}=\vec{y}\\ &&=4(WH\vec y -WH'\vec y)-\vec{\lambda} (\vec{y}.\vec s)- \vec{y} (\vec{\lambda}.\vec s) &&H \vec{y}=\vec{s}\\ &&=4(W\vec s -WH'\vec y)-\vec{\lambda} (\vec{y}.\vec s)- \vec{y} (\vec{\lambda}.\vec s) &&W \vec{s}=\vec{y}\\ &&=4(\vec y -WH'\vec y)-\vec{\lambda} (\vec{y}.\vec s)- \vec{y} (\vec{\lambda}.\vec s) \tag 4 \end{eqnarray*}$$

对上述向量关于$\vec s$做内积可得

$$\begin{aligned} 0 &=\left(4(\vec y -WH'\vec y)-\vec{\lambda} (\vec{y}.\vec s)- \vec{y} (\vec{\lambda}.\vec s) \right) .\vec s \\ &= 4\vec s^T\vec y - 4 \vec s^T WH'\vec y -(\vec{\lambda}.\vec s)(\vec{y}.\vec s) -(\vec{y}.\vec s)(\vec{\lambda}.\vec s)\\ &=4(\vec y .\vec s) - 4(W\vec s)^T H'\vec y - 2(\vec{y}.\vec s)(\vec{\lambda}.\vec s) & W对称\\ &=4(\vec y .\vec s) - 4 (\vec y^TH'\vec y)-2(\vec{y}.\vec s)(\vec{\lambda}.\vec s) &W \vec{s}=\vec{y} \end{aligned}$$

令

$$\rho =\frac 1 {\vec y .\vec s}$$

那么

$$\begin{aligned} \vec{\lambda}.\vec s &= 2\rho(\vec y .\vec s-\vec y^TH'\vec y)\\ &=2\rho(\vec y^T\vec s-\vec y^TH'\vec y)\\ &=2\rho\vec y^T (\vec s -H'\vec y) \end{aligned}$$

带回(4)式可得

$$\begin{eqnarray*} \vec 0 &&=4(\vec y -WH'\vec y)-\vec{\lambda} (\vec{y}.\vec s)- \vec{y} (\vec{\lambda}.\vec s) \\ &&= 4(\vec y -WH'\vec y)-\vec{\lambda} (\vec{y}.\vec s)-\vec{y} [2\rho\vec y^T (\vec s -H'\vec y)]\\ \Rightarrow \vec \lambda &&=4\rho(\vec y -WH'\vec y) -2\rho^2 \vec y^T (\vec s -H'\vec y)\vec y \end{eqnarray*}$$

右乘$\vec y ^T$得到

$$\vec \lambda \vec y^T =4\rho(\vec y -WH'\vec y) \vec y^T -2\rho^2 \vec y^T (\vec s -H'\vec y)\vec y \vec y^T \tag 5$$

注意

$$\left ( \vec y^T H'\vec y\vec y \vec y^T \right)^T= \vec y^T H'\vec y(\vec y \vec y^T)^T =\vec y^T H'\vec y\vec y \vec y^T$$

所以转置原式得到

$$\vec{y} \vec{\lambda}^{T}=4 \rho \vec{y}\left(\overline{y}^{T}-\overline{y}^{T} H'W\right)-2 \rho^{2} \overline{y}^{T}\left(\vec{s}-H' \overline{y}\right) \vec{y} \vec{y}^{T} \tag 6$$

(4)+(5)得到

$$\frac 1 4(\vec \lambda \vec y^T+\vec{y} \vec\lambda^{T})=\rho\left(2 \vec{y} \vec{y}^{T}-W H' \vec{y} \vec{y}^{T}-\vec{y} \vec{y}^{T} H' W\right)-\rho^{2} \vec{y}^{T}\left(\vec{s}-H' \vec{y}\right) \vec{y} \vec{y}^{T} \tag 7$$

因为

$$W\vec s = \vec y$$

所以

$$\begin{aligned} \vec s & = W^{-1} \vec y \\ \vec s ^T&=\vec y^T W^{-1} \end{aligned}$$

对(7)左乘$W^{-1}$右乘$W^{-1}$得到

$$\begin{aligned} \frac 1 4W^{-1}(\vec \lambda \vec y^T+\vec{y} \vec\lambda^{T})W^{-1} &=\rho W^{-1}\left(2 \vec{y} \vec{y}^{T}-W H' \vec{y} \vec{y}^{T}-\vec{y} \vec{y}^{T} H' W\right)W^{-1}- \rho^{2}W^{-1} \vec{y}^{T}\left(\vec{s}-H' \vec{y}\right) \vec{y} \vec{y}^{T}W^{-1}\\ &=2 \rho \vec s \vec s^T -\rho H'\vec y \vec s^T -\rho \vec s \vec{y}^{T} H' -\rho^2 (\vec y^T\vec s) W^{-1}\vec{y} \vec{y}^{T}W^{-1} + \rho^2 (\vec{y}^{T}H' \vec{y}) W^{-1}\vec{y} \vec{y}^{T}W^{-1}\\ &=2 \rho \vec s \vec s^T -\rho H'\vec y \vec s^T -\rho \vec s \vec{y}^{T} H' - \rho \vec s \vec s^T + \rho^2 (\vec{y}^{T}H' \vec{y}) \vec s \vec s^T & \rho =\frac 1 {\vec y^T\vec s}\\ &=\rho \vec s \vec s^T -\rho H'\vec y \vec s^T -\rho \vec s \vec{y}^{T} H' + \rho^2 \vec s(\vec{y}^{T}H' \vec{y}) \vec s^T & \vec{y}^{T}H' \vec{y}\in \mathbb R \end{aligned}$$

回顾(3)式

$$0 =4 W\left(H-H'\right) W-\vec{\lambda} \vec{y}^{T}-\vec{y} \vec{\lambda}^{T}$$

我们可得

$$\begin{aligned} H &=\frac{1}{4} W^{-1}\left(\vec{\lambda} \vec{y}^{T}+\vec{y} \vec{\lambda}^{T}\right) W^{-1}+H' \\ &=\rho \vec s \vec s^T -\rho H'\vec y \vec s^T -\rho \vec s \vec{y}^{T} H' + \rho^2 \vec s(\vec{y}^{T}H' \vec{y}) \vec s^T +H'\\ &=H'\left(I-\rho \vec{y}{\vec s}^{T}\right)+\rho \vec s \vec s^T-\rho \vec{s} \vec{y}^{T} H'+\left(\rho {\vec s \vec y^{T}}\right) H'\left(\rho \vec{y} \vec{s}^{T}\right)\\ &=H'\left(I-\rho \vec{y} \vec{s}^{T}\right)+\rho \vec s \vec s^T-\rho \vec{s} \vec{y}^{T} H'\left(I-\rho \vec{y} \vec{s}^{T}\right)\\ &=\rho \vec s \vec s^T+\left(I-\rho \vec{s} \vec{y}^{T}\right) H'\left(I-\rho \vec{y} \vec{s}^{T}\right) \end{aligned}$$

Chapter 9 条件优化

这一部分将讨论条件优化问题：

$$\begin{aligned} \text { minimize }& f(\vec{x}) & \\ \text { such that } & g(\vec{x})=\vec{0} \\ &h(\vec{x}) \geq \vec{0} \end{aligned}$$

其中

$$\begin{aligned} f : &\mathbb{R}^{n} \rightarrow \mathbb{R}\\ g : &\mathbb{R}^{n} \rightarrow \mathbb{R}^m \\ h : &\mathbb{R}^{n} \rightarrow \mathbb{R}^p \end{aligned}$$

注意这是对之前讨论的很多问题的推广。如果取$f(\vec x) =0​$，那么该问题即为$g​$的求根问题；如果取$g(\vec x) =h(\vec x) =0​$，那么该问题即为无条件优化问题。

条件优化的理论

定义9.1(可行点和可行集)

$$条件优化问题的可行点为满足g(\vec{x})=\vec{0},h(\vec x) \ge \vec 0的\vec x 。\\ 可行集为满足所有可行点的集合。$$

定义9.2(条件优化的关键点)

$$既是可行点，又是$f$的极值点或鞍点的点被称为条件优化的关键点。$$

现在假设我们找到$f​$的最小值点$\vec x ‘​$，那么对于约束条件$h(\vec x’)\ge \vec 0​$的每个分量$h_i(\vec x ‘)​$，我们有两种情形：

• $h_i(\vec x’)=0 $，这种情形被称为边界解。这时称该约束是active。
• $h_i(\vec x’)>0 $，这种情形被称为内部解，注意这种情形该条件不起作用。这时称该约束是inactive。

这两种情形分别对应如下两图：

如果所有约束都是active，那么该问题等价于

$$\begin{aligned} \text { minimize }& f(\vec{x}) & \\ \text { such that } & g(\vec{x})=\vec{0} \\ &h(\vec{x}) = \vec{0} \end{aligned}$$

此时使用拉格朗日乘子法即可：

$$\Lambda(\vec{x}, \vec{\lambda}, \vec{\mu}) \equiv f(\vec{x})-\vec{\lambda} \cdot g(\vec{x})-\vec{\mu} \cdot h(\vec x)$$

求梯度并令其为$\vec 0​$得到：

$$\vec{0}=\nabla f(\vec{x})-\sum_{i} \lambda_{i} \nabla g_{i}(\vec{x})-\sum_{j} \mu_{j} \nabla h_{j}(\vec{x}) \tag 1$$

如果部分约束是inactive，那么该如何处理呢？由之前的讨论可知这部分约束不起作用，所以我们可以增加如下约束条件：对于inactive的约束，

$$\mu_j \nabla h_j(\vec x) =0$$

注意对于active的约束，我们有

$$\nabla h_j(\vec x) =0$$

此时必然有

$$\mu_j \nabla h_j(\vec x) =0$$

所以我们可以增加如下条件：对于所有$j$，

$$\mu_j \nabla h_j(\vec x) =0$$

到目前为止，我们的处理没有区别

$$h_j(\vec{x}) \geq 0$$

和

$$h_j(\vec{x}) \le 0$$

所以最后需要考虑这点。注意

$$g(\vec{x})=\vec{0}$$

等价于

$$\begin{aligned} g(\vec{x})&\ge \vec{0} \\ -g(\vec{x})&\ge \vec{0} \end{aligned}$$

所以我们只需要考虑如下情形：

$$\begin{aligned} \text { minimize }& f(\vec{x}) & \\ \text { such that } &h(\vec{x}) \ge \vec{0} \end{aligned}$$

此时拉格朗日乘子为

$$\Lambda(\vec{x}, \vec{\lambda}, \vec{\mu}) \equiv f(\vec{x})-\vec{\mu} \cdot h(\vec x)$$

求梯度并令其为$\vec 0​$得到：

$$\nabla f(\vec{x})=\sum_{j} \mu_{j} \nabla h_{j}(\vec{x}) =\sum_{j\text{ active}} \mu_{j} \nabla h_{j}(\vec{x})\tag 2$$

注意可行点的集合为

$$A=\{\vec x | h(\vec x)\ge \vec 0\}$$

而active的点所处的集合为

$$\{\vec x | h_j(\vec x)= 0,j\text{ active}\}$$

因为$\nabla h_j(\vec x)$的方向指向$A$内部，所以要使得$f$最小化，$\nabla f(\vec{x})$应该和$\nabla h_j(\vec x)$同向（否则就会离开可行点集），因此$\forall j $

$$\begin{aligned} \nabla f(\vec{x}).\nabla h_j(\vec x) &=\left(\sum_{j} \mu_{j} \nabla h_{j}(\vec{x})\right).\nabla h_j(\vec x)\\ &= \left(\nabla h_j(\vec x)\right)^T M \mu \\ &\ge 0 \end{aligned}$$

其中

$$M= \left[ \begin{matrix} \nabla h_1(\vec x) &\ldots & \nabla h_p(\vec x) \end{matrix} \right],\vec \mu = \left[ \begin{matrix} \mu_1 &\ldots & \mu_p \end{matrix} \right] ^T \in \mathbb R^p$$

将上述内容写成向量的形式可得

$$D^T D \vec \mu \ge \vec 0$$

因为$D^T D$半正定，所以

$$\vec \mu \ge \vec 0$$

即

$$\forall j, \mu_j \ge 0$$

将上述内容总结即得到KKT条件：

定理9.1 (Karush-Kuhn-Tucker (KKT)条件)

向量$\vec x’ \in \mathbb R^n$是如下问题的关键点(critical point)

$$\begin{aligned} \text { minimize }& f(\vec{x}) & \\ \text { such that } & g(\vec{x})=\vec{0} \\ &h(\vec{x}) \geq \vec{0} \end{aligned}$$

如果存在$\vec \lambda \in \mathbb R^m $和$\vec \mu \in \mathbb R^p$，使得

• $\vec{0}=\nabla f\left(\vec{x}’\right)-\Sigma_{i} \lambda_{i} \nabla g_{i}\left(\vec{x}’\right)-\sum_{j} \mu_{j} \nabla h_{j}\left(\vec{x}’\right)$(“stationarity”)
• $g(\vec x’) =\vec 0, h(\vec x ‘)\ge \vec 0$(“primal feasibility”)
• $\mu_j h_j(\vec x’)=0$(“complementary slackness”)
• $\mu_j \ge 0$(“dual feasibility”)

例1

$$\begin{aligned} \text { minimize }& xy& \\ \text { such that } & x+y^2 \le 2 \\ &x,y \ge 0 \end{aligned}$$

令

$$\begin{aligned} f(x,y)&=-xy\\ h_1(x,y)&=2-x-y^2\\ h_2(x,y) &= x\\ h_3(x,y)&=y \end{aligned}$$

所以KKT条件为

$$\begin{aligned} \text{Stationarity:} &{0=-y+\mu_{1}-\mu_{2}} \\ &{0=-x+2 \mu_{1} y-\mu_{3}} \\ \text{Primal feasibility:}&{x+y^{2} \leq 2} \\ &{x, y \geq 0} \\ \text{Complementary slackness:} &{\mu_{1}\left(2-x-y^{2}\right)=0} \\ &{\mu_{2} x=0} \\ &{\mu_{3} y=0} \\ \text{Dual feasibility:} &{\mu_{1}, \mu_{2}, \mu_{3} \geq 0} \end{aligned}$$