最优化方法_part2

第五讲 无约束优化问题（壹）

5.1 无约束优化问题

(一) 无约束优化问题：$ \min f(\boldsymbol x)$

• 最小二乘问题：$\min \| \boldsymbol{Ax-b} \|$；
• 采用适当的方法可将约束优化问题转换为无约束优化问题；
• 最优解的定义：
  • 局部最优解$\overline{\boldsymbol x}$：$\forall \boldsymbol x \in \boldsymbol N_{\epsilon}(\overline{\boldsymbol x}), f({\boldsymbol x}) \geq f(\overline{\boldsymbol x})$
  • 全局最优解$\boldsymbol x^*$：$\forall \boldsymbol x \in \mathbb{R}^n, f({\boldsymbol x}) \geq f(\boldsymbol x^*)$
  • 严格局部/全局最优解：即上面式子提到的$\geq \to >$

(二) 无约束优化问题最优性条件

考虑无约束优化问题：$\min f(\boldsymbol x)$：

• 若$f(\boldsymbol x)$为凸函数，则$\boldsymbol x^*$是最优解等级于$\triangledown f(\boldsymbol x^*) = \boldsymbol 0$
• 若$f(\boldsymbol x)​$为一般函数(即不一定是凸函数)：
  • 必要条件：若$\boldsymbol x^*$是最优解，则$\triangledown f(\boldsymbol x^*) = \boldsymbol 0$；$\triangledown^2 f(\boldsymbol x^*) \succeq \boldsymbol 0, (即黑塞矩阵半正定)$
    • 上面两条分别对应“一阶必要条件”、“二阶必要条件”
    • 泰勒展开形式
  • 充分条件：若$\triangledown f(\boldsymbol x^*) = \boldsymbol 0$且$\triangledown^2 f(\boldsymbol x^*) \succ \boldsymbol 0, (即黑塞矩阵半正定)$，则$\boldsymbol x^*$是严格最优解(局部？)

修改：判定(半)正定矩阵的特殊大于(等于)简写符号为：$\succ, \succeq$，并不是$>, \geq$

5.2 无约束优化算法概要

(一) 迭代下降算法

给定初始点$\boldsymbol x_0$，产生点列$\begin{Bmatrix} \boldsymbol x_k \end{Bmatrix}_{k=1}^{\infty}$，并且$f(\boldsymbol x_{k+1}) < f(\boldsymbol x_k)$。

• 如何从当前点$\boldsymbol x_k$得到下一个迭代点$\boldsymbol x_{k+1}$？

  • 策略1：线搜索方法

    • 当前点$\boldsymbol x_k$，从这个点出发，先找到某一个下降方向$\boldsymbol d_k$(即沿着该方向函数值减小)，然后需要设置在下降方向走多远(步长)$\alpha_k$，最终，得到下一个点为：$\boldsymbol x_{k+1} = \boldsymbol x_{k} + \alpha_k \boldsymbol d_k$

  • 策略2：信赖域方法

    • 该方法有点和线搜索步骤反过来的意味，即先确定好需要前进的区域，然后选择前进的方向。

    • 设前进区域设为$\boldsymbol p$，给定其约束为$\Delta$，可以表述为

    • $$\begin{cases}\text { min } & f(\boldsymbol x_{k} + \boldsymbol p) \\ \text{ s.t.} & \| \boldsymbol p \|_2 \leq \Delta \end{cases}$$

      注意：在线搜索方法中，选择步长是一个一元/一维的问题；但信赖域方法是一个N维问题($f$可能是一个比较复杂的函数)，因此信赖域方法直接求解复杂度较大。所以信赖域方法在求解时并不是直接求解上述优化，而是需要先用一个简单的函数$m_k(\boldsymbol p)$对$f$在$\boldsymbol x_k$点进行近似，比如用泰勒展开等方法。

      $$\begin{cases}\text { min } & m_k(\boldsymbol p) \\ \text{ s.t.} & \| \boldsymbol p \|_2 \leq \Delta \end{cases}$$

      信赖域方法有几点需要考虑：

      (1) $\Delta$如何确定；(2) $m_k(\boldsymbol p)$如何选择，误差较大怎么办。

(二) (基于线搜索)下降算法基本思路

• STEP1：给定初始点$\boldsymbol x_0, k=0$
• STEP2：判断$\boldsymbol x_k$是否满足终止条件；是则终止
• STEP3：否则寻找$\boldsymbol x_k$处的下降方向$\boldsymbol d_k$
• STEP4：设置步长$\alpha_k$，使得$f(\boldsymbol x_{k} + \alpha_k \boldsymbol d_k) < f(\boldsymbol x_{k+1})$
• STEP5：令$\boldsymbol x_{k+1} = \boldsymbol x_k + \alpha_k \boldsymbol d_k$；令$k=k+1$，转STEP1。

1 终止条件

常用的终止条件：

$$\| \triangledown f(\boldsymbol x_k) \|_2 \leq \varepsilon$$

其中，$\varepsilon$理论上取0，但在实际编程中一般取一个量级很小的数。此外要注意对与凸函数，此条件一定是最优解，但是非凸函数该终止条件找到的点就不一定是最优解了。

其他终止条件：

$$\|\boldsymbol x_k - \boldsymbol x_{k-n} \|_2 \leq \varepsilon$$ $$f(\boldsymbol x_k) - f(\boldsymbol x_{k-n}) \leq \varepsilon$$

2 下降方向

常用的下降方向——负梯度方向

$$\boldsymbol d_k = -\triangledown f(\boldsymbol x_k)$$

该方法又称最速下降法（Steepest descent）是梯度下降法的一种更具体实现形式。

其他下降方向选择：牛顿方向、共轭梯度方向等。

3 步长

令$\phi(\alpha) := f(\boldsymbol x_{k} + \alpha \boldsymbol d_k)$，为一元函数。则可建模为：

$$\min \text{ }\phi(\alpha)$$

在确定$\alpha_k$的过程称为一维线搜索。

4 点列收敛性/收敛速度

我们的算法会产生一个点列$\begin{Bmatrix} \boldsymbol x_k \end{Bmatrix}_{k=1}^{\infty}$，若点列不收敛，则可认为该算法不好。另外，收敛速度越快，算法越好。

(三) 求解步长——线搜索方法详解

求解一元问题：

$$\begin{cases}\text { min } & \phi(\alpha) := f(\boldsymbol x_{k} + \alpha \boldsymbol d_k) \\ \text{ s.t.} & \alpha > 0 \end{cases}$$

其解记为$\alpha^*$。

1 $f(\boldsymbol x)$为一个简单函数

若$f(\boldsymbol x)$为一个简单函数，如二次函数：$f(\boldsymbol x) = \dfrac{1}{2} \boldsymbol x^{\mathrm T} \boldsymbol H \boldsymbol x + \boldsymbol c^{\mathrm T} \boldsymbol x + b, \text{} \boldsymbol H(黑塞矩阵) \succ 0$。黑塞矩阵正定则$f$为凸函数，则$\phi(\alpha)$也是凸函数。代入可得：

$$\begin{align*} \phi(\alpha) & = \dfrac{1}{2} {(\boldsymbol x_{k} + \alpha \boldsymbol d_k)}^{\mathrm T} \boldsymbol H {(\boldsymbol x_{k} + \alpha \boldsymbol d_k)} + \boldsymbol c^{\mathrm T} {(\boldsymbol x_{k} + \alpha \boldsymbol d_k)} + b \\ &= \dfrac{1}{2} (\boldsymbol d_k^{\mathrm T} \boldsymbol H {\boldsymbol d_k})\alpha^2 +(\boldsymbol d_k^{\mathrm T} \boldsymbol H {\boldsymbol x_k} + \boldsymbol c^{\mathrm T}\boldsymbol d_k) \alpha + b \\ \end{align*}$$

对于开口向上的二次函数，求最小，即导数为零即可。

$$\phi(\alpha)' = 0$$

2 $f(\boldsymbol x)$为一个复杂非线性函数

若$f(\boldsymbol x)$为一个复杂非线性函数，则$\min \phi(\alpha)$问题就变得复杂起来了。下面简单介绍几种常见的处理方法：

• 基于搜索区间的直接搜索法

  • 首先找到一个搜索区间，想办法缩小搜索区间(注意缩小时不用吧$\alpha^*$扔掉)，缩小到一定程度时，则可将区间内的一点作为最优解的近似。
  • 搜索区间$[ a_0, b_0]$：需要包含$\alpha^*$；单谷(即在搜索区间内，函数只有一个下凸，且要注意以下推导都基于此前提)
  • 方法：选取$\lambda, \mu \in (a_0, b_0)$且满足$\lambda < \mu$
    • 若$\phi(\lambda) < \phi(\mu)$，则得到新的搜索区间为$[ a_1, b_1] = [ a_0, \mu]$
    • 若$\phi(\lambda) > \phi(\mu)$，则得到新的搜索区间为$[ a_1, b_1] = [ \lambda, b_0]$
  • 常见的直接搜索法：
    • 均匀搜索法：
      • 令$\delta = (b_0 - a_0)/N, \alpha_i = a_0 + i \delta, \text{ } i=1,2, \cdots, N-1$
      • 比较相邻3个点对应的函数值，若对于某个$i$，有$\phi(\alpha_{i-1})>\phi(\alpha_i)<\phi(\alpha_{i+1})$，则$\alpha^* \in [\alpha_{i-1}, \alpha_{i+1}]$；
      • 得到新的搜索区间$[ a_1, b_1] = [\alpha_{i-1}, \alpha_{i+1}]$
    • 黄金区间法(0.618法)：
      • 令$\tau = (\sqrt 5 - 1)/2 =0.618, \text{ }\lambda = a_0 + (1 - \tau)(b_0-a_0), \text{ } \mu = a_0 + \tau (b_0 - a_0)$
      • 若$\phi(\lambda) < \phi(\mu)$，则$\alpha^* \in [a_0, \mu]$，即新的搜索区间；
    • 基于导数信息的二分法
      • 记区间中点$\lambda = \dfrac{b_0+a_0}{2}$，计算该点的导数值$\phi'(\lambda)$；
      • 若$\phi'(\lambda) = 0$，则$\alpha^* = \lambda$；
      • 若$\phi'(\lambda) < 0$，则$\alpha^* \in[\lambda, b_0]$；
      • 若$\phi'(\lambda) > 0$，则$\alpha^* \in [a_0, \lambda]$；

• 非精确线搜索

  实际下降算法中，步长的选取除了直接搜索法以外，还有其他一下方法，我们认为只要$\alpha$满足一定的准则，此时即使$\alpha$不是精确解也可以作为最终解的近似解。

  • Armijo条件：$\phi(\alpha) \leq \phi(0) + c_1\alpha \phi'(0), \text{ } 0 \leq c_1 \leq 1$

  

  • Goldstein法则：除Armijo条件外还要去$\mu$满足：$\phi(\alpha) > \phi(0) + c_2\alpha \phi'(0), \text{ } 0 \leq c_1 \leq c_2\leq 1$

(四) 补充：收敛性

基于线搜索的迭代下降算法

• 为保证全局收敛，步长$\alpha_k​$和下降方向$\boldsymbol d_k​$的选取均需满足定的条件：
  • 记当前点$\boldsymbol x_k$处所选取下降方向$\boldsymbol d_k$与负梯度方向$-\triangledown f(\boldsymbol x_k)$的夹角为$\theta_k$：
  • $$\cos \theta_k = \dfrac{-\triangledown f(\boldsymbol x_k)^{\mathrm T}\boldsymbol d_k}{\|\triangledown f(\boldsymbol x_k) \| \| \boldsymbol d_k\|}$$

Zoutendijk定理说明：

为了保证全局收敛，需要在选取步长和下降方向时候注意满足一定的条件

此外注意区分：全局收敛与收敛到全局最优解的区别

(1) 全局收敛是指在迭代下降算法初始点选取时，任意随机选取初始点都能保证所产生的点列满足收敛性；

(2) 收敛到全局最优解

• 在适当条件下，迭代点列$\boldsymbol x_k$满足：$\sum\limits_{k=1}^{\infty} \cos^2 \theta_k \|\triangledown f(\boldsymbol x_k) \|^2 < \infty$，点列收敛

• 当每次选取$\boldsymbol d_k$时均保证$\theta_k$满足$\cos \theta_k \geq \delta, \delta>0$，则：$\|\triangledown f(\boldsymbol x_k) \| \to 0$

  通俗讲就是不要让下降方向$\boldsymbol d_k$与负梯度方向$-\triangledown f(\boldsymbol x_k)$的夹角太接近$\dfrac{\pi}{2}$，夹角尽量小。

Zoutendijk定理中的适当条件和证明：

假设函数$f(\boldsymbol x)$有下界(保证有解存在)，且$\triangledown f(\boldsymbol x)$是Lipschitz连续的，即存在$L>0$使得：

$$\|\triangledown f(\boldsymbol x) - \triangledown f(\tilde{\boldsymbol x}) \| \leq L \|\boldsymbol x - \tilde{\boldsymbol x} \|, \forall \boldsymbol x, \tilde{\boldsymbol x}$$

记迭代过程为$\boldsymbol x_{k+1} = \boldsymbol x_k + \alpha_k \boldsymbol d_k$，则

$$\sum\limits_{k=1}^{\infty} \cos^2 \theta_k \|\triangledown f(\boldsymbol x_k) \|^2 < \infty$$

证明部分没有细看，太复杂了。。。！！！

此外，这里感觉很难理解，找了一些参考材料，有时间看看吧

漫步最优化二十一——全局收敛、约束优化方法_1_——Zoutendijk可行方向法、数值优化|笔记整理（2）——线搜索：步长选取条件的收敛性 - 学弱猹的文章 - 知乎

第六讲 无约束优化问题（贰）

6.1 收敛速度

设序列$\begin{Bmatrix} \boldsymbol x_k \end{Bmatrix}_{k=1}^{\infty}$收敛到$\boldsymbol x^*$，若存在极限：

$$\lim_{k \to \infty} \dfrac{\|\boldsymbol x_{k+1} - \boldsymbol x^* \|}{\|\boldsymbol x_{k} - \boldsymbol x^* \|} = \beta$$

• 当$0 < \beta < 1$时，则称$\begin{Bmatrix} \boldsymbol x_k \end{Bmatrix}_{k=1}^{\infty}$为线性收敛；
• 当$\beta = 0$时，则称$\begin{Bmatrix} \boldsymbol x_k \end{Bmatrix}_{k=1}^{\infty}$为超线性收敛。

若存在某个 $p \geq 1$，有：

$$\lim_{k \to \infty} \dfrac{\|\boldsymbol x_{k+1} - \boldsymbol x^* \|}{\|\boldsymbol x_{k} - \boldsymbol x^* \|^p} = \beta < +\infty$$

则称$\begin{Bmatrix} \boldsymbol x_k \end{Bmatrix}_{k=1}^{\infty}$为$p$阶收敛。当$p > 1$时，$p$阶收敛必定为超线性收敛，但反之不一定成立。

评价一个算法除了收敛速度，还可以考虑把一个算法用于求解一个简单问题，如果该算法在求解简单问题时都会有较大的计算成本，那么说明该算法可能存在问题。一般用凸二次函数作为简单问题：

$$\min \frac{1}{2} \boldsymbol x^{\mathrm T} \boldsymbol Q \boldsymbol x + \boldsymbol c^{\mathrm T} \boldsymbol x, \boldsymbol Q \succeq 0$$

如果算法用于求解该凸二次函数能够在有限步内找到最优解，那么称该算法具有“二次终止性”。

6.2 坐标轴交替下降法

(一) 基本思想

给定初始点$\boldsymbol x_0$，依次沿着坐标轴$\boldsymbol e_1, \boldsymbol e_2, \cdots, \boldsymbol e_n$进行搜索。

(二) 算法框架/流程

• STPE 1：给定初始点$\boldsymbol x_0, k:=0, \varepsilon>0$；

• STPE 2：判断是否满足$\| \triangledown f(\boldsymbol x_k) \| \leq \varepsilon$，是，则终止算法；

• STPE 3：记$\boldsymbol y_0 = \boldsymbol x_k$，令$\boldsymbol y_i = \boldsymbol y_{i-1} + \alpha_i \boldsymbol e_i$

  其中，$\alpha_i := \arg \min f(\boldsymbol y_{i-1} + \alpha_i \boldsymbol e_i), i=1,2,\cdots, n$

  arg是argument（自变量、参数）的缩写，那么由此可知：

  argmax F(x):使目标函数F(x)能够取到最大值时的变量x的值

  argmin F(x):使目标函数F(x)能够取到最小值时的变量x的值

  (只是用F(x)举个栗子，实际使用中的函数可能不止x这一个变量，不过意思还是这个意思~)

• STPE4：令$\boldsymbol x_{k+1} = \boldsymbol y_n, k:=k+1$，转STPE1。

(三) 优缺点

优点：不需要成本即可得到搜索方向。当变量之间的交叉程度较小时非常有效(极端情况——可分离函数)；

缺点：对于一般问题所得到的点列未必收敛。

(四) 改进方法

比如：在交替下降过程中间每一步都加入一个线搜索。

6.3 梯度下降法(最速下降法)

(一) 基本思想

选择$\boldsymbol x_k$处负梯度作为搜索方向，即$\boldsymbol d_k = - \triangledown f(\boldsymbol x_k)$。

(二) 优缺点

优点：简单直观；收敛；搜索方向计算简单(即只需计算梯度)；

缺点：(1) 收敛速度慢(线性收敛)；(2) Zigzag现象(“之”字形)；(3) 不具备二次终止性(在有限步内求得凸二次函数的最优解)。

• 缺点一：收敛速度慢(线性收敛)

  • 原因1：只利用了该点处的一阶导数，而没有利用二阶导数信息；

  • 原因2：若迭代中步长$\alpha_k$是$\phi(\alpha):=f(\boldsymbol x_k + \alpha \boldsymbol d_k)$的精确最小点，则$\phi'(\alpha_k) = 0$，即

    $$\phi'(\alpha_k) = \triangledown f(\boldsymbol x_k + \alpha_k \boldsymbol d_k)^{\mathrm T}\boldsymbol d_k= -\triangledown f(\boldsymbol x_{k+1}) \triangledown f(\boldsymbol x_k) = 0$$

    根据上式，可以看到前后两个点之间的梯度垂直，呈现“之”字形。示例如下图所示。

6.4 牛顿法

(一) 基本思想

当前点$\boldsymbol x_k$处选择$\boldsymbol d_k = - [\triangledown^2 f(\boldsymbol x_k)]^{-1} \triangledown f(\boldsymbol x_k)$作为下降方向，可以理解为：对$\boldsymbol x_k$处的二次逼近函数(泰勒展开式)进行最小化。

$$\min f(\boldsymbol x_k) + \triangledown f(\boldsymbol x_k)^{\mathrm T}(\boldsymbol x - \boldsymbol x_k) + \frac{1}{2}(\boldsymbol x - \boldsymbol x_k)^{\mathrm T} \triangledown^2 f(\boldsymbol x_k) (\boldsymbol x - \boldsymbol x_k)$$

令上式求导等于零，可以得到：

$$\triangledown f(\boldsymbol x_k) + \triangledown^2 f(\boldsymbol x_k) (\boldsymbol x - \boldsymbol x_k) = \triangledown f(\boldsymbol x_k) + \triangledown^2 f(\boldsymbol x_k) \boldsymbol d_k = 0$$

• 纯牛顿法：步长$\alpha_k = 1$

  因为$\boldsymbol d_k = - [\triangledown^2 f(\boldsymbol x_k)]^{-1} \triangledown f(\boldsymbol x_k) \Longleftrightarrow \boldsymbol x_{k+1} = \boldsymbol x_k - [\triangledown^2 f(\boldsymbol x_k)]^{-1} \triangledown f(\boldsymbol x_k)$

(二) 算法框架/流程

• STPE 1：给定初始点$\boldsymbol x_0, k:=0, \varepsilon>0$；
• STPE 2：判断是否满足$\| \triangledown f(\boldsymbol x_k) \| \leq \varepsilon$，是，则终止算法；
• STPE 3：计算$\boldsymbol d_k = - [\triangledown^2 f(\boldsymbol x_k)]^{-1} \triangledown f(\boldsymbol x_k)$
• STPE4：令$\boldsymbol x_{k+1} = \boldsymbol x_{k} + \boldsymbol d_k, k:=k+1$，转STPE1。

(三) 优缺点

优点：牛顿法同时考虑了一阶导数信息和和二阶导数信息(黑塞矩阵)；当初始点$\boldsymbol x_0$取得比较接近于收敛点$\boldsymbol x^*$，且$\triangledown^2 f(\boldsymbol x)$满足较好性质时，二阶收敛；二次终止性(一步终止)。

缺点：计算量大(需计算Hesse矩阵)；适用范围较窄。

此外，牛顿法还存在一个问题：二阶导数矩阵不一定是正定的，此时$\boldsymbol d_k$就不一定再是下降方向了。

6.5 修正牛顿法

• 修改点1：步长
  • 对于步长$\alpha_k​$的修正：首先判断$\alpha_k = 1​$是否让目标函数充分下降；否，则采用线搜索方法重新确定$\alpha_k​$;
• 修改点2：方向
  • 对于方向(Hesse矩阵)的修正：选取$\boldsymbol d_k = - \boldsymbol B_k^{-1} \triangledown f(\boldsymbol x_k)$
    • 若$\triangledown^2 f(\boldsymbol x_k) \succ 0$，则选取$\boldsymbol B_k = \triangledown^2 f(\boldsymbol x_k)$
    • 否则，采取修正方法(多种)：
      • $\boldsymbol B_k := \triangledown^2 f(\boldsymbol x_k) + \lambda \boldsymbol I$，其中，$\lambda$为适当正数保证$\boldsymbol b_k$正定。
      • 考虑特征值分解：$\triangledown^2 f(\boldsymbol x_k) = \boldsymbol Q^{\mathrm T} \boldsymbol \Lambda \boldsymbol Q$，令$\boldsymbol b_k = \boldsymbol Q^{\mathrm T} \text{diag} (\tau_i) \boldsymbol Q$
        • $\tau_{i}= \begin{cases}\lambda_{i}, & \text { if } \lambda_{i} \geq \delta \\ \delta, & \text { otherwise }\end{cases}$，其中$\delta$为一适当正数。

6.6 拟牛顿法

(一) 基本思想

当前点$\boldsymbol x_k$处对$f(\boldsymbol x_k)$使用二次函数进行近似：

$$m_k(\boldsymbol x) := f(\boldsymbol x_k) + \triangledown f(\boldsymbol x_k)^{\mathrm T}(\boldsymbol x - \boldsymbol x_k) + \frac{1}{2}(\boldsymbol x - \boldsymbol x_k)^{\mathrm T} \boldsymbol B_k (\boldsymbol x - \boldsymbol x_k), \boldsymbol B_k \succ 0$$

利用$\min m_k(\boldsymbol x)$的搜索方向：$\boldsymbol d_k = - \boldsymbol B_k^{-1} \triangledown f(\boldsymbol x_k)$；我们希望$\boldsymbol B_k$尽量包含一些二阶信息，然后计算要相对简单。

$\boldsymbol B_k \succ 0$为正定矩阵时，$m_k(\boldsymbol x)$是一个凸二次函数，求其最小值即可让$m_k(\boldsymbol x)$的梯度为0即可，求解即可得到：

$$\boldsymbol x_{k+1} = \boldsymbol x = \boldsymbol x_k - \boldsymbol d_k = \boldsymbol x_k - \boldsymbol B_k^{-1} \triangledown f(\boldsymbol x_k)$$

(二) 算法框架/流程

• STPE 1：给定初始点$\boldsymbol x_0, k:=0, \varepsilon>0, \boldsymbol B_0$；
• STPE 2：判断是否满足$\| \triangledown f(\boldsymbol x_k) \| \leq \varepsilon$，是，则终止算法；
• STPE 3：计算$\boldsymbol d_k = - \boldsymbol B_k^{-1} \triangledown f(\boldsymbol x_k)$；
• STPE 4：使用线搜索法确定步长$\alpha_k$；
• STPE 5：令$\boldsymbol x_{k+1} = \boldsymbol x_{k} + \alpha_k \boldsymbol d_k, k:=k+1$，确定$\boldsymbol B_{k+1}$，转STPE1。

(三) $\boldsymbol B_{k+1}$矩阵的确定方法

1 拟牛顿方程(基本要求)

$$\triangledown f(\boldsymbol x_{k+1}) - \triangledown f(\boldsymbol x_k) = \boldsymbol B_{k+1} (\boldsymbol x_{k+1} - \boldsymbol x_{k})$$

对上式的简单理解：

首先由中值定理可得：$\triangledown f(\boldsymbol x_{k+1}) - \triangledown f(\boldsymbol x_k) = \triangledown^2 f(\boldsymbol \xi ) (\boldsymbol x_{k+1} - \boldsymbol x_{k}) , \text{ }\xi = \lambda \boldsymbol x_k + (1-\lambda)\boldsymbol x_k, \text{ } \lambda \in (0,1)$

对比发现：也就是我们希望$\boldsymbol B_{k+1}$能够体现$\triangledown^2 f(\boldsymbol \xi )$的作用。

分析易知，$\boldsymbol B_{k+1}$大小为$n \times n$，其中变量个数为$\dfrac{n(n+1)}{2}$(对称阵)，但是等式只要$n$个方程，因此$\boldsymbol B_{k+1}$会有多个满足条件。

记$\boldsymbol y_k := \triangledown f(\boldsymbol x_{k+1}) - \triangledown f(\boldsymbol x_k)$，$\boldsymbol s_k := \boldsymbol x_{k+1} - \boldsymbol x_{k}$，则拟牛顿方程简记为：

$$\boldsymbol y_k = \boldsymbol B_{k+1} \boldsymbol s_k$$

此外，若记$\boldsymbol H_k = \boldsymbol B_k^{-1}$，拟牛顿方程也可以表示为：$\boldsymbol s_k = \boldsymbol H_{k+1} \boldsymbol y_k$。

下面我们将对利用已有信息具体获得$\boldsymbol B_{k+1}$或者$\boldsymbol H_{k+1}$

2 第一类方法

选择满足拟牛顿方程且与$\boldsymbol B_k$近似的矩阵。

$$\begin{cases}\text { min } & \| \boldsymbol B - \boldsymbol B_k \| \\ \text{ s.t. } & \boldsymbol B \boldsymbol s_k = \boldsymbol y_k, \boldsymbol B = \boldsymbol B^T \end{cases}$$ $$\begin{cases}\text { min } & \| \boldsymbol H - \boldsymbol H_k \| \\ \text{ s.t. } & \boldsymbol H \boldsymbol y_k = \boldsymbol s_k, \boldsymbol H = \boldsymbol H^T \end{cases}$$

矩阵范数小知识：向量范数与矩阵范数

3 第二类方法

对$\boldsymbol B_k$、$\boldsymbol H_k$进行校正，如：令$\boldsymbol B_{k+1} = \boldsymbol B_k + \Delta \boldsymbol B$。

• rank-1校正：要求$\Delta \boldsymbol B$的秩为1；

  • SR-1方法：可以看作是对$\boldsymbol B_k$进行rank-1校正

    • $$\boldsymbol B_{k+1} = \boldsymbol B_k + \dfrac{(\boldsymbol y_k - \boldsymbol B_k \boldsymbol s_k) (\boldsymbol y_k - \boldsymbol B_k\boldsymbol s_k)^{\mathrm T}}{(\boldsymbol y_k - \boldsymbol B_k \boldsymbol s_k)^{\mathrm T} \boldsymbol s_k}$$

    • 如何得到上式：

    • 

    • 该方法相对rank-2方法迭代公式更简单，但是不能保证正定性；适当条件下能达到$n$步超线性收敛。

      $n$步超线性收敛：

      $$\lim_{k \to \infty} = \dfrac{\| \boldsymbol x_{k+1+n} - \boldsymbol x^* \|}{\boldsymbol x_{k} - \boldsymbol x^*}$$

• rank-2校正：要求$\Delta \boldsymbol B$的秩为2；

  • DFP方法：可以看作是对$\boldsymbol H_k$进行rank-2校正
    • $$\boldsymbol H_{k+1} = \boldsymbol H_k + \dfrac{\boldsymbol H_k \boldsymbol y_k \boldsymbol y_k^{\mathrm T}\boldsymbol H_k}{\boldsymbol y_k^{\mathrm T}\boldsymbol H_k\boldsymbol y_k} + \dfrac{\boldsymbol s_k \boldsymbol s_k^{\mathrm T}}{\boldsymbol y_k^{\mathrm T}\boldsymbol s_k}$$
    • 如何得到上式：注意下面图中的证明用到了对称秩1矩阵$\boldsymbol A$的性质：$\boldsymbol A = \boldsymbol {uv}^T = \boldsymbol {uu}^T$
    • 
  • BFGS方法：可以看作是对$\boldsymbol B_k$进行rank-2校正
    • $$\boldsymbol B_{k+1} = \boldsymbol B_k + \dfrac{\boldsymbol B_k \boldsymbol s_k \boldsymbol s_k^{\mathrm T}\boldsymbol B_k}{\boldsymbol s_k^{\mathrm T}\boldsymbol B_k\boldsymbol s_k} + \dfrac{\boldsymbol y_k \boldsymbol y_k^{\mathrm T}}{\boldsymbol y_k^{\mathrm T}\boldsymbol s_k}$$
    • 如何得到上式：原理同上面DFP推导类似。
    • 拟牛顿方向需要计算$\boldsymbol B_{k+1}^{-1}$，可以利用Sherman-Morrison公式显示写出；
    • BFGS方法是被认为最有效的拟牛顿法；(适当前提下可证明)超线性收敛。
    • Broyden族：DFP与BFGS的线性组合！

第七讲 无约束优化问题（叁）

7.1 共轭梯度法背景

1950年代，求解一类优化问题中：

$$\min \dfrac{1}{2} \boldsymbol x^{\mathrm T} \boldsymbol Q \boldsymbol x + \boldsymbol c^{\mathrm T} \boldsymbol x, \boldsymbol Q \succ 0, \boldsymbol c \in \mathbb{R}^n$$

该类问题可直接通过求梯度然后令梯度为零即可：

$$\triangledown f(\boldsymbol x) = \boldsymbol Q \boldsymbol x + \boldsymbol c = \boldsymbol 0$$

可知，需要求解线性方程组。当矩阵比较大时候，计算复杂，因此有人提出使用迭代法求解方程组，因此就有了”(线性)共轭梯度法”。

1960年代，该方法推广到求解一般性优化问题，此时该方法也被称为”(非线性)共轭梯度法”。

7.2 线性共轭梯度法

考虑以下优化问题：

$$\min \dfrac{1}{2} \boldsymbol x^{\mathrm T} \boldsymbol Q \boldsymbol x + \boldsymbol c^{\mathrm T} \boldsymbol x, \boldsymbol Q \succ 0, \boldsymbol c \in \mathbb{R}^n$$

• 当$\boldsymbol Q$特殊一点为对角矩阵时：

$$f(\boldsymbol x) = \dfrac{1}{2} \boldsymbol x^{\mathrm T} \left[\begin{array}{ccc} q_{1} & \cdots & 0 \\ \vdots & \ddots & 0 \\ 0 & 0 & q_{n} \end{array}\right] \boldsymbol x + \boldsymbol c^{\mathrm T}\boldsymbol x$$

• 当$\boldsymbol Q$为一般情况(非对角矩阵)时：

拿到一个普通二次型，就要想办法将其转换为标准二次型，即就是只有平方项没有交叉项。常用的方法有线性替换，最常见的线性替换又是：对$\boldsymbol Q$矩阵进行特征值和特征向量分解：

$$\boldsymbol Q = \boldsymbol S^{\mathrm T} \boldsymbol \Lambda \boldsymbol S$$

其中，$\boldsymbol S$是由标准正交化之后的特征向量组成。

将$\dfrac{1}{2} \boldsymbol x^{\mathrm T} \boldsymbol Q \boldsymbol x + \boldsymbol c^{\mathrm T} \boldsymbol x$中$\boldsymbol x$用$\hat{\boldsymbol x} = \boldsymbol{Sx}$进行替换：

$$f(\hat{\boldsymbol x}) = \dfrac{1}{2} \hat{\boldsymbol x}^{\mathrm T} \boldsymbol \Lambda \hat{\boldsymbol x} + \boldsymbol{(Sc)}^{\mathrm T} \hat{\boldsymbol x}$$

此时就可以像对角矩阵情况类似，求解变得简单。求解得到$\hat{\boldsymbol x}^*$后即可得到最终解：$\boldsymbol x^* = \boldsymbol P^{-1} \hat{\boldsymbol x}^* = \boldsymbol P^{\mathrm T} \hat{\boldsymbol x}^*$

一定要记住，线性共轭梯度法被设计出来就是用来求解线性方程组。

(一) 共轭方向

考虑正定矩阵$\boldsymbol Q$和非零向量$\boldsymbol d_i, \boldsymbol d_j$，若：

$$\boldsymbol d_i^{\mathrm T} \boldsymbol Q \boldsymbol d_j = \boldsymbol 0$$

则称$\boldsymbol d_i, \boldsymbol d_j$关于矩阵$\boldsymbol Q$共轭。

向量组$\boldsymbol d_0, \boldsymbol d_1, \cdots, \boldsymbol d_k$关于矩阵$\boldsymbol Q$共轭，两两共轭。

(二) 共轭 VS 正交

• 若向量组$\boldsymbol d_0, \boldsymbol d_1, \cdots, \boldsymbol d_k$关于$\boldsymbol I$共轭，则向量组$\boldsymbol d_0, \boldsymbol d_1, \cdots, \boldsymbol d_k$是正交向量组；

• 若向量组$\boldsymbol d_0, \boldsymbol d_1, \cdots, \boldsymbol d_k$关于正定矩阵$\boldsymbol Q$共轭，令$\boldsymbol{Q = P}^2$，则有：

  • $\boldsymbol d_i^{\mathrm T} \boldsymbol Q \boldsymbol d_j = \boldsymbol d_i^{\mathrm T} \boldsymbol P^{\mathrm T} \boldsymbol P \boldsymbol d_j = (\boldsymbol P \boldsymbol d_i)^{\mathrm T} (\boldsymbol P \boldsymbol d_j) = \boldsymbol 0$正交

  涉及小知识点：

  一个正定矩阵一定能分解为另一个正定矩阵的平方：$\boldsymbol{Q = P}^2$；

  共轭向量组线性无关。

(三) 共轭方向法

$$\min \text{ } \dfrac{1}{2} \boldsymbol x^{\mathrm T} \boldsymbol Q \boldsymbol x + \boldsymbol c^{\mathrm T} \boldsymbol x, \boldsymbol Q \succ 0, \boldsymbol c \in \mathbb{R}^n$$

给定初始点$\boldsymbol x_0$以及一组关于$\boldsymbol Q$共轭方向$\boldsymbol d_0, \boldsymbol d_1, \cdots, \boldsymbol d_{n-1}$，令：

$$\boldsymbol x_{k+1} := \boldsymbol x_k + \alpha_k \boldsymbol d_k, \text{ } k = 0, 1, \cdots, n-1$$

其中，$\alpha_k = \arg \min \phi(\alpha) := f(\boldsymbol x_k + \alpha \boldsymbol d_{k})$。计算可得步长为：

$$\phi'(\alpha_k) = 0 \Longrightarrow \alpha_k = -\dfrac{(\boldsymbol Q \boldsymbol x_k + \boldsymbol c)^{\mathrm T}\boldsymbol d_k}{\boldsymbol d_k^{\mathrm T}\boldsymbol Q \boldsymbol d_k} = -\dfrac{\triangledown f(\boldsymbol x)^{\mathrm T} \boldsymbol d_k}{\boldsymbol d_k^{\mathrm T}\boldsymbol Q \boldsymbol d_k}$$

共轭方向法为一类方法，不同的选取共轭方向的方式就对应不同的共轭方向法，共轭梯度法是其中一种。

(四) 共轭方向法具备的特征

以下特征均是基于问题：$\min \dfrac{1}{2} \boldsymbol x^{\mathrm T} \boldsymbol Q \boldsymbol x + \boldsymbol c^{\mathrm T} \boldsymbol x, \boldsymbol Q \succ 0, \boldsymbol c \in \mathbb{R}^n$

点列$\begin{Bmatrix} \boldsymbol x_k \end{Bmatrix}_{k=1}^{\infty}$具有如下特征：

• 特征1：$\triangledown f(\boldsymbol x_k )^{\mathrm T} \boldsymbol d_i = 0, i = 0, 1, \cdots, k-1$
• 特征2：$\boldsymbol x_k := \arg \min \begin{Bmatrix} \dfrac{1}{2} \boldsymbol x^{\mathrm T} \boldsymbol Q \boldsymbol x + \boldsymbol c^{\mathrm T} \boldsymbol x \mid \boldsymbol x \in \boldsymbol X_k \end{Bmatrix}$
  • 其中，$\boldsymbol X_k = \begin{Bmatrix} \boldsymbol x_ 0 + \sum\limits_{i=0}^{k-1} a_i \boldsymbol d_i \mid a_i \in \mathbb{R}, i = 1, 2, \cdots, k-1 \end{Bmatrix}$

证明：参考视频。

7.3 共轭梯度法具体

(一) 基本思想

在迭代下降过程中，借助当前点$\boldsymbol x_k$处的梯度信息构造共轭方向。

(二) 算法框架/流程

• STPE 1：给定初始点$\boldsymbol x_0, k:=0, \varepsilon>0$，记$\boldsymbol d_0 := -\triangledown f(\boldsymbol x_0)$
• STPE 2：判断是否满足$\| \triangledown f(\boldsymbol x_k) \| \leq \varepsilon$，是，则终止算法；
• STPE 3：计算$\alpha_k = -\dfrac{\triangledown f(\boldsymbol x)^{\mathrm T} \boldsymbol d_k}{\boldsymbol d_k^{\mathrm T}\boldsymbol Q \boldsymbol d_k}$；
• STPE4：令$\boldsymbol x_{k+1} = \boldsymbol x_{k} + \alpha_k \boldsymbol d_k$，计算方向$\boldsymbol d_{k+1} = -\triangledown f(\boldsymbol x_{k+1}) + \text{some-term}$，$k:=k+1$转STPE1。
  • 其中，$\boldsymbol d_{k+1} = -\triangledown f(\boldsymbol x_{k+1}) + \beta_k \boldsymbol d_k$，$\beta_k = \dfrac{\triangledown f(\boldsymbol x_{k+1}) \boldsymbol Q \boldsymbol d_k}{\boldsymbol d_k^{\mathrm T}\boldsymbol Q \boldsymbol d_k}$

(三) 公式简化

简化的目的：将这些表达式与目标函数的梯度比较直观地表现出来。

共轭梯度法的步长公式：

$$\alpha_k = -\dfrac{\triangledown f(\boldsymbol x)^{\mathrm T} \boldsymbol d_k}{\boldsymbol d_k^{\mathrm T}\boldsymbol Q \boldsymbol d_k}$$

可简化为：

$$\alpha_k = \dfrac{\triangledown f(\boldsymbol x)^{\mathrm T}\triangledown f(\boldsymbol x)}{\boldsymbol d_k^{\mathrm T}\boldsymbol Q \boldsymbol d_k}$$

共轭梯度法的步长公式中的系数：

$$\beta_k = \dfrac{\triangledown f(\boldsymbol x_{k+1}) \boldsymbol Q \boldsymbol d_k}{\boldsymbol d_k^{\mathrm T}\boldsymbol Q \boldsymbol d_k}$$

可简化为：

$$\beta_k = \dfrac {\triangledown f(\boldsymbol x_{k+1})^{\mathrm T}[\triangledown f(\boldsymbol x_{k+1}) - \triangledown f(\boldsymbol x_{k+1})]} {\triangledown f(\boldsymbol x_k)^{\mathrm T}\triangledown f(\boldsymbol x_k)}$$

进一步简化为：

$$\beta_k = \dfrac {\triangledown f(\boldsymbol x_{k+1})^{\mathrm T} \triangledown f(\boldsymbol x_{k+1}) } {\triangledown f(\boldsymbol x_k)^{\mathrm T}\triangledown f(\boldsymbol x_k)}$$

7.4 非线性共轭梯度法

注意注意注意：上述推导全部是建立在线性共轭梯度法，基本函数是二次函数。

• STPE 1：给定初始点$\boldsymbol x_0, k:=0, \varepsilon>0$，记$\boldsymbol d_0 := -\triangledown f(\boldsymbol x_0)$
• STPE 2：判断是否满足$\| \triangledown f(\boldsymbol x_k) \| \leq \varepsilon$，是，则终止算法；
• STPE 3：利用线性搜索计算$\alpha_k$；
• STPE4：令$\boldsymbol x_{k+1} = \boldsymbol x_{k} + \alpha_k \boldsymbol d_k$，计算方向$\boldsymbol d_{k+1} = -\triangledown f(\boldsymbol x_{k+1}) + \beta_k \boldsymbol d_k$，$k:=k+1$转STPE1。
  • PRP方法：$\beta_k = \dfrac{\triangledown f(\boldsymbol x_{k+1})^{\mathrm T}[\triangledown f(\boldsymbol x_{k+1}) - \triangledown f(\boldsymbol x_{k+1})]} {\triangledown f(\boldsymbol x_k)^{\mathrm T}\triangledown f(\boldsymbol x_k)}$
  • FR方法：$\beta_k = \dfrac{\triangledown f(\boldsymbol x_{k+1})^{\mathrm T} \triangledown f(\boldsymbol x_{k+1}) }{\triangledown f(\boldsymbol x_k)^{\mathrm T}\triangledown f(\boldsymbol x_k)}$

7.5 一些说明

• 在实践中，为保证每次产生的方向为下降方向，可能会对$\beta_k$进行调整；

• 具有二次终止性；

• 实现过程中常采用$n$步重启策略，可达到$n$步二阶收敛；

  n步二阶收敛：$\lim\limits_{k \to \infty}\dfrac{\| \boldsymbol x_{k+n} - \boldsymbol x^*\|}{\| \boldsymbol x_{k+n} - \boldsymbol x^*\|^2} = 某一有限值 \gamma$

  • 原因1：较远的点对当前点贡献很小，可以忽略，因此重启；
  • 原因2：可能会将非线性共轭转变为线性共轭梯度法；

第八讲 约束优化理论(壹)—最优性条件

本讲要讨论的约束优化问题为：

$$(P) \text{ }\begin{cases}\text { min } & f(\boldsymbol x) \\ \text{ s.t.} & g_{i}(\boldsymbol x) \leq 0, \text{ } i=1, \cdots, m \\ & h_{i}(\boldsymbol x) = 0, \text{ } i=1, \cdots, l\end{cases}$$

记问题(P)的可行集为集合$\boldsymbol S = \begin{Bmatrix} \boldsymbol x \mid g_{i}(\boldsymbol x) \leq 0, \text{ } i=1, \cdots, m, h_{i}(\boldsymbol x) = 0, \text{ } i=1, \cdots, l \end{Bmatrix}$。

本讲讨论问题的基本假设/前提：

• 问题(P)中函数$f(\boldsymbol x), g_i(\boldsymbol x), h_i(\boldsymbol x)$均为连续可微函数；

  注意，有几类特殊的非光滑函数存在不可微点，但是可以将其转化，例如：

  $$f(x) = \max \begin{Bmatrix} x, x^2 \end{Bmatrix} $$，绘图易知该函数存在两个不可微的点，那么优化问题：$$

  \min f( x)

  $$可以转化为：令$$t = f(\boldsymbol x) $$：$$

  \min f( x) \\
  \Downarrow \\
  \begin{cases}\text { min } &t \\
  \text{ s.t.} & f( x) \leq t\end{cases} \\
  \Downarrow \\
  \begin{cases}\text { min } &t \\
  \text{ s.t.} & x \leq t\\
  & x^2\leq t\end{cases}
  $推广来看：$f(x) = \max \begin{Bmatrix} a_i x + b_i \end{Bmatrix}$$这一类函数可以进行转换。

  >

8.1 最优解的一阶必要条件(KKT条件)

(一) KKT条件的内容

假设$\boldsymbol x^*$是问题(P)的局部最优解，且$\boldsymbol x^*$处某个“适当条件”成立，则存在$\boldsymbol \lambda \in \mathbb{R}^m, \boldsymbol \mu \in \mathbb{R}^l$($m$是不等式约束个数，$l$是等式约束个数)使得：

$$\triangledown f(\boldsymbol x^*) + \sum_{i=1}^{m}\lambda_i \triangledown g_i(\boldsymbol x^*) + \sum_{i=1}^{l} \mu_i \triangledown h_i(\boldsymbol x^*) = 0 \\ \lambda_i > 0, i = 1,2, \cdots, m \\ g_i(\boldsymbol x^*) \leq 0, i = 1,2, \cdots, m \\ h_i(\boldsymbol x^*) = 0, i = 1,2, \cdots, l \\ \lambda_i g_i(\boldsymbol x^*) = 0, i = 1,2, \cdots, m$$

其中，以上5个条件就是著名的KKT条件。$\lambda_i, \mu_i$是两组系数，又称为“拉格朗日乘子”。

针对非凸问题设计优化算法时，如果能证明算法收敛到一个KKT点，那么就说明算法达到了一个基本要求，KKT点相当于无约束优化问题中的梯度为零的作用。

(二) 证明KKT必要条件

1 几个概念

• 对于$\boldsymbol x^* \in \boldsymbol S$，若点列$\begin{Bmatrix} \boldsymbol x_k \end{Bmatrix} ⊂ \boldsymbol S$满足所有$\boldsymbol x_k \neq \boldsymbol x^*, \lim\limits_{k \to \infty} \boldsymbol x_k = \boldsymbol x^*$，则称为可行点列。

• 基本思路：若$\boldsymbol x^* \in \boldsymbol S$是局部最优解，则沿着任意可行点列目标函数不会下降(即当$k$充分大时，有$f(\boldsymbol x_k) > f(\boldsymbol x^*)$)。

• 考虑$\boldsymbol x^*$处集合$\boldsymbol D(\boldsymbol x^*) = \begin{Bmatrix} \boldsymbol d \mid \triangledown f(\boldsymbol x^*)^{\mathrm T} \boldsymbol d < 0 \end{Bmatrix} : \forall \boldsymbol d \in \boldsymbol D$均为$f(\boldsymbol x_k)$是$\boldsymbol x^*$处的下降方向。

• 考虑$\boldsymbol x^*$处集合$\boldsymbol T(\boldsymbol x^*) = \begin{Bmatrix} \alpha \boldsymbol d \mid \alpha > 0, \boldsymbol d = \lim\limits_{k \to \infty}\dfrac{\boldsymbol x_k- \boldsymbol x^*}{\| \boldsymbol x_k- \boldsymbol x^* \|} , \boldsymbol x_k \to \boldsymbol x^*, \boldsymbol x_k \neq \boldsymbol x^*, \boldsymbol x_k \in \boldsymbol S \end{Bmatrix}$，该集合称为$\boldsymbol x^*$处的切锥。切锥里面包含的方向可以告诉我们：从$\boldsymbol x^*$点可以验证哪一些方向/曲线可以移动，示意图如下：

  

  上图中，红色箭头夹住部分为切锥包含的可行方向。

2 最优解的必要条件

若$\boldsymbol x^*$是问题(P)的局部最优解，则有：

$$\boldsymbol D(\boldsymbol x^*) ∩ \boldsymbol T(\boldsymbol x^*) = \boldsymbol \emptyset$$

只要证明上述表达式中描述的两个集合交集为空，等价于：任取$\alpha \boldsymbol d \in \boldsymbol T(\boldsymbol x^*)$，都有$\triangledown f(\boldsymbol x^*)^{\mathrm T} \boldsymbol d \geq 0$

(三) 与切锥关系紧密的两个集合

• 可行方向集合：
  • $$\boldsymbol F(\boldsymbol x^*) = \begin{Bmatrix} \boldsymbol d \mid \boldsymbol x^* + \lambda \boldsymbol d \in \boldsymbol S, \forall \lambda \in (0, \delta), \text{ some } \delta > 0 \end{Bmatrix}$$
  • 易知：$\boldsymbol F(\boldsymbol x^*) ⊆ \boldsymbol T(\boldsymbol x^*)$，即可行方向一定在切锥中。

• 集合2：记$\boldsymbol x^*$处的有效指标集$\boldsymbol I = \begin{Bmatrix} i \mid g_i(\boldsymbol x^*)=0 \end{Bmatrix}$，定义下面集合

  • $$\boldsymbol F_1(\boldsymbol x^*) = \begin{Bmatrix} \boldsymbol d \mid \triangledown g_i(\boldsymbol x^*)^{\mathrm T} \boldsymbol d \leq 0, i \in \boldsymbol I, \triangledown h_j(\boldsymbol x^*)^{\mathrm T} \boldsymbol d = 0, j = 1,2,\cdots, l \end{Bmatrix}$$
  • 易知：$\boldsymbol T(\boldsymbol x^*) ⊆ \boldsymbol F_1(\boldsymbol x^*)$
  • 证明：
    • 

• 综上：$\boldsymbol F(\boldsymbol x^*) ⊆ \boldsymbol T(\boldsymbol x^*) ⊆ \boldsymbol F_1(\boldsymbol x^*)$

(二) 适当条件：约束规范(constrain qualification)

上文KKT条件描述中提到的适当条件就是此处要讨论的约束规范。在适当条件(约束规范下)：$\boldsymbol T(\boldsymbol x^*) = \boldsymbol F_1(\boldsymbol x^*)$

• 常用的约束规范有：
  • 函数——$g_i(\boldsymbol x^*), i \in \boldsymbol I, h_j(\boldsymbol x^*), j = 1,2,\cdots, l$均为线性函数；
  • 向量组——$\triangledown g_i(\boldsymbol x^*), i \in \boldsymbol I, \triangledown h_j(\boldsymbol x^*), j = 1,2,\cdots, l$线性无关(LICQ)；
  • Slater Condition
  • ……

若$\boldsymbol x^* \in \boldsymbol S$是问题(P)的局部最优解，在满足上述某一种约束条件下，有：

$$\boldsymbol D(\boldsymbol x^*) ∩ \boldsymbol T(\boldsymbol x^*) = \boldsymbol D(\boldsymbol x^*) ∩ \boldsymbol F_1(\boldsymbol x^*) = \boldsymbol \emptyset$$

即KKT条件的一种形式。

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

若$\boldsymbol x^* \in \boldsymbol S$是问题(P)的局部最优解，在满足上述某一种约束条件下，则KKT条件成立。

因为：根据Farkas引理，$\boldsymbol D(\boldsymbol x^*) ∩ \boldsymbol F_1(\boldsymbol x^*) = \boldsymbol \emptyset$当且仅当KKT条件成立。

证明：观看视频，太难了。。。

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

8.2 KKT条件的解释说明

(一) KKT条件中各部分的名字

$$\triangledown f(\boldsymbol x^*) + \sum_{i=1}^{m}\lambda_i \triangledown g_i(\boldsymbol x^*) + \sum_{i=1}^{l} \mu_i \triangledown h_i(\boldsymbol x^*) = 0 \\ \lambda_i > 0, i = 1,2, \cdots, m \\ g_i(\boldsymbol x^*) \leq 0, i = 1,2, \cdots, m \\ h_i(\boldsymbol x^*) = 0, i = 1,2, \cdots, l \\ \lambda_i g_i(\boldsymbol x^*) = 0, i = 1,2, \cdots, m$$

各部分组合的名字如下：

$$(\text{对偶可行(Dual Feasible, DF)}) \text{ }\begin{cases} & \triangledown f(\boldsymbol x^*) + \sum_{i=1}^{m}\lambda_i \triangledown g_i(\boldsymbol x^*) + \sum_{i=1}^{l} \mu_i \triangledown h_i(\boldsymbol x^*) = 0 \\ & \lambda_i > 0, i = 1,2, \cdots, m \end{cases}$$ $$(\text{原问题可行(Primal Feasible, PF)}) \text{ }\begin{cases} & g_i(\boldsymbol x^*) \leq 0, i = 1,2, \cdots, m \\ & h_i(\boldsymbol x^*) = 0, i = 1,2, \cdots, l \end{cases}$$ $$(\text{互补松弛条件(Complementary Slack, CS)}) ) \text{ }\begin{cases} & \lambda_i g_i(\boldsymbol x^*) = 0, i = 1,2, \cdots, m \end{cases}$$

不知道前面有没有说互补松弛的作用：保证那些不起作用的不等式约束在第一行中对应的乘子为零；

传统的互补问题就是：两个向量都是非负的，求内积等于0，其要求为对应分量相乘为0。

(二) KKT条件中拉格朗日乘子意义

KKT条件中拉格朗日乘子可反映约束条件右端项发生扰动时最优目标函数值的变化情况。

设$\boldsymbol x^*$是问题(P)的局部最优解，且设$\boldsymbol x^*$满足KKT条件：

$$(P) \text{ }\begin{cases}\text { min } & f(\boldsymbol x) \\ \text{ s.t.} & g_{i}(\boldsymbol x) \leq 0, \text{ } i=1, \cdots, m \\ & h_{i}(\boldsymbol x) = 0, \text{ } i=1, \cdots, l\end{cases}$$

(三) KKT条件充分性

以上好像都是在讨论KKT条件的必要性，即已经知道$\boldsymbol x^*$是局部最优解，那么在满足某一种约束条件下，KKT条件成立。

但我们也想知道什么时候会变成充分条件，即一个点满足KKT条件，则该点是问题(P)的最优解。

• 当问题(P)中满足：

  • (1) $f(\boldsymbol x), g_i(\boldsymbol x), i =1,2,\cdots, m$均为凸函数；
  • (2) $h_i(\boldsymbol x), i =1,2,\cdots, l$为线性函数；

• 则满足条件的KKT点也是问题(P)(此两条条件限制下，问题P就是凸问题)的局部(全局)最优解。

  注意2点：

  一、凸问题局部最优解即为全局最优解；

  二、可能在一些其他问题，不满足上述两条条件(即问题P非凸)，KKT点也有可能是局部最优解，但判断方法需要借助黑塞矩阵，下面会讲到。

第九讲 约束优化理论(贰)—最优性条件—二阶充分条件

9.1 本讲基础

由第八讲(三)KKT条件充分性部分内容可知：

• 当问题(P)中满足：
  • (1) $f(\boldsymbol x), g_i(\boldsymbol x), i =1,2,\cdots, m$均为凸函数；
  • (2) $h_i(\boldsymbol x), i =1,2,\cdots, l$为线性函数；
• 则满足条件的KKT点也是问题(P)(此两条条件限制下，问题P就是凸问题)的局部(全局)最优解。

本将要解决的问题是，若通过验证，发现上面的条件(1)或者(2)不满足，那么还有没有什么其他条件说明当$\boldsymbol x^*$满足KKT条件时，KKT点$\boldsymbol x^*$是问题(P)的最优解。

假设$\boldsymbol x^*$满足KKT条件：

$$\triangledown f(\boldsymbol x^*) + \sum_{i=1}^{m}\lambda_i \triangledown g_i(\boldsymbol x^*) + \sum_{i=1}^{l} \mu_i \triangledown h_i(\boldsymbol x^*) = 0 \\ \lambda_i > 0, i = 1,2, \cdots, m \\ g_i(\boldsymbol x^*) \leq 0, i = 1,2, \cdots, m \\ h_i(\boldsymbol x^*) = 0, i = 1,2, \cdots, l \\ \lambda_i g_i(\boldsymbol x^*) = 0, i = 1,2, \cdots, m$$

令：

$$L(\boldsymbol x) = f(\boldsymbol x) + \sum_{i=1}^{m}\lambda_i g_i(\boldsymbol x) + \sum_{i=1}^{l} \mu_i h_i(\boldsymbol x)$$ $$L(\boldsymbol x)$$称为**<font color=red>拉格朗日函数</font>**。 简单分析$$L(\boldsymbol x)$$可知其具备几个特征： - **(1) 梯度为0**：$$\triangledown L(\boldsymbol x^*) = \triangledown f(\boldsymbol x^*) + \sum_{i=1}^{m}\lambda_i \triangledown g_i(\boldsymbol x^*) + \sum_{i=1}^{l} \mu_i \triangledown h_i(\boldsymbol x^*) = 0$$

• (2)：$L(\boldsymbol x^*) = f(\boldsymbol x^*) + \sum_{i=1}^{m}\lambda_i g_i(\boldsymbol x^*) + \sum_{i=1}^{l} \mu_i h_i(\boldsymbol x^*) = f(\boldsymbol x^*)$
• (3)：$L(\boldsymbol x) = f(\boldsymbol x) + \sum_{i=1}^{m}\lambda_i g_i(\boldsymbol x) + \sum_{i=1}^{l} \mu_i h_i(\boldsymbol x) \leq f(\boldsymbol x), \forall \boldsymbol x \in \boldsymbol S$

由上面(2)、(3)可知：若$\boldsymbol x^*$是$L(\boldsymbol x)$的最优解(局部或者全局最优解都可以)，则$\boldsymbol x^*$是问题(P)的最优解。

若$\boldsymbol x^*$是$L(\boldsymbol x)$的局部最优解，则$\boldsymbol x^*$是问题(P)的局部最优解；

若$\boldsymbol x^*$是$L(\boldsymbol x)$的全局最优解，则$\boldsymbol x^*$是问题(P)的全局最优解。

小证明：

局部最优解情况：$f(\boldsymbol x^*) = L(\boldsymbol x^*) = L(\boldsymbol x) = f(\boldsymbol x), \forall \boldsymbol x \in \boldsymbol S ∩ \boldsymbol N_\delta(\boldsymbol x^*)$

全局最优解情况：$f(\boldsymbol x^*) = L(\boldsymbol x^*) = L(\boldsymbol x) = f(\boldsymbol x), \forall \boldsymbol x \in \boldsymbol S$

假设$\boldsymbol x^*$满足KKT条件，则有：

• (1)：若$\triangledown^2 L(\boldsymbol x) \succeq 0, \forall \boldsymbol x \in \boldsymbol S$，则$L(\boldsymbol x)$在集合$\boldsymbol S$上是凸函数，则$\boldsymbol x^*$是问题(P)的全局最优解；
• (2)：若$\triangledown^2 L(\boldsymbol x) \succeq 0, \forall \boldsymbol x \in \boldsymbol S ∩ \boldsymbol N_\delta(\boldsymbol x^*)$，则$L(\boldsymbol x)$在上$\boldsymbol x^*$某一邻域是凸函数，则$\boldsymbol x^*$是问题(P)的局部最优解；
• (3)：若$\triangledown^2 L(\boldsymbol x^*) \succ 0$，则$\boldsymbol x^*$是问题(P)的严格局部最优解；

视频课程中这里有一部分分析推导，有时间记录

9.2 二阶充分条件

下面是本讲内容的核心：

(一) 二阶充分条件定义

假设$\boldsymbol x^*$是KKT点，易知：

• $$\triangledown L(\boldsymbol x^*) = 0$$
• $$\boldsymbol d^T \triangledown^2 L(\boldsymbol x^*) \boldsymbol d > 0, \forall \boldsymbol d \in F_2(\boldsymbol x^*)$$

则$\boldsymbol x^*$是问题(P)的严格局部最优解。

(二) 证明

反证：假设$\boldsymbol x^*​$是KKT点，但$\boldsymbol x^*​$不是问题(P)的严格局部最优解。则能找到一个点$\boldsymbol x_k \to \boldsymbol x^* ​$，使得：

$$f(\boldsymbol x_k) \leq f(\boldsymbol x^*), \forall \boldsymbol x_k \in \boldsymbol S$$

记$\boldsymbol d_k = \dfrac{\boldsymbol x_k- \boldsymbol x^*}{\| \boldsymbol x_k- \boldsymbol x^* \|}$，$\alpha_k = {\| \boldsymbol x_k- \boldsymbol x^* \|}$，则会得到两个点列：$\begin{Bmatrix} \boldsymbol d_k \end{Bmatrix}$，$\begin{Bmatrix} \alpha_k \end{Bmatrix}$，易得：

• 因为$\boldsymbol x_k \to \boldsymbol x^*$，因此$\begin{Bmatrix} \alpha_k \end{Bmatrix} \to 0$
• $$\begin{Bmatrix} \boldsymbol d_k \end{Bmatrix}$$是有界的，因此必然存在收敛子列，设最终$$\begin{Bmatrix} \boldsymbol d_k \end{Bmatrix} \to \boldsymbol d$$

则有：$\boldsymbol x_k = \boldsymbol x^* + \alpha_k \boldsymbol d_k$，

$$f(\boldsymbol x_k) - f(\boldsymbol x^*) \xlongequal{泰勒展开} \triangledown f(\boldsymbol x^*)^{\mathrm T}(\boldsymbol x_k - \boldsymbol x^*) +\dfrac{\alpha_k^2}{2} \boldsymbol d_k^{\mathrm T}\triangledown f(\boldsymbol x^*)\boldsymbol d_k+\text{o}(\alpha_k^2) \\= \alpha_k \triangledown f(\boldsymbol x^*)^{\mathrm T} \boldsymbol d_k +\dfrac{\alpha_k^2}{2} \boldsymbol d_k^{\mathrm T}\triangledown f(\boldsymbol x^*)\boldsymbol d_k+\text{o}(\alpha_k^2) \leq 0$$ $$g_i(\boldsymbol x_k) - g_i(\boldsymbol x^*) \xlongequal{泰勒展开} \triangledown g_i(\boldsymbol x^*)^{\mathrm T}(\boldsymbol x_k - \boldsymbol x^*) +\dfrac{\alpha_k^2}{2} \boldsymbol d_k^{\mathrm T}\triangledown g_i(\boldsymbol x^*)\boldsymbol d_k+\text{o}(\alpha_k^2) \\= \alpha_k \triangledown g_i(\boldsymbol x^*)^{\mathrm T} \boldsymbol d_k +\dfrac{\alpha_k^2}{2} \boldsymbol d_k^{\mathrm T}\triangledown g_i(\boldsymbol x^*)\boldsymbol d_k+\text{o}(\alpha_k^2) \leq 0$$ $$h_i(\boldsymbol x_k) - h_i(\boldsymbol x^*) \xlongequal{泰勒展开} \triangledown h_i(\boldsymbol x^*)^{\mathrm T}(\boldsymbol x_k - \boldsymbol x^*) +\dfrac{\alpha_k^2}{2} \boldsymbol d_k^{\mathrm T}\triangledown h_i(\boldsymbol x^*)\boldsymbol d_k+\text{o}(\alpha_k^2) \\= \alpha_k \triangledown h_i(\boldsymbol x^*)^{\mathrm T} \boldsymbol d_k +\dfrac{\alpha_k^2}{2} \boldsymbol d_k^{\mathrm T}\triangledown h_i(\boldsymbol x^*)\boldsymbol d_k+\text{o}(\alpha_k^2) = 0$$