上一节笔记：数值优化（B）——二次规划（上）：Schur补方法，零空间法，激活集方法
————————————————————————————————————————————————
大家好！
这一节会是我们的这一个系列的最后一节正课内容，我们会继续说上一节二次规划 没说完的内容，也会介绍一些现代优化算法 和它们背后设计的思想。同时因为习题不算多，所以我们会将这些内容合并在一起，在这一节为大家介绍完。
那么我们开始吧。
目录 二次规划中的内点法 现代优化中的带约束光滑优化概述交替方向乘子法（ADMM） 罚项法 增广拉格朗日方法（ALM） 习题课 Source J. Nocedal, S.J. Wright, Numerical Optimization 课堂笔记，教授主页：https://www.math.fsu.edu/~whuang2/index.html 二次规划中的内点法 说的没错，二次规划也可以采用内点法来解决，而且设计思路也基本上相同。回忆一下二次规划问题的形式
\min_x q(x) = \frac 12 x^T G x + x^T c
s.t. \quad a_i^T x = b_i, i \in \mathcal{E} \\ a_i^T x \ge b_i, i \in \mathcal{I}
我们写出它的拉格朗日函数。
\mathcal{L}(x, s, \lambda) = \frac 12 x^T G x + x^T c - \sum_{i \in \mathcal{E}}s_i(a_i^Tx - b_i) - \sum_{i \in \mathcal{I}}\lambda_i (a_i^T x - b_i) 其中
x \in \mathbb{R}^n, s \in \mathbb{R}^{m_1}, \lambda \in \mathbb{R}^{m_2} 。
\mathcal{E} 代表等式约束的指标集，
\mathcal{I} 代表不等式约束的指标集。
求解它的KKT条件我们可以得到
Gx + c - A_\mathcal E^T s - A_\mathcal{I}^T \lambda = 0 a_i^T x = b_i, i \in \mathcal{E} a_i^T x \ge b_i, i \in \mathcal{I} \lambda_i \ge 0, i \in \mathcal{I} \lambda_i (a_i^T x - b_i) = 0, i \in \mathcal{I} 这里的
A_\mathcal E = \{a_i^T\}_{i \in \mathcal{E}} \in \mathbb{R}^{m_1 \times n} ，
A_\mathcal I = \{a_i^T\}_{i \in \mathcal{I}} \in \mathbb{R}^{m_2 \times n} ，相当于把两组不同的约束做了拆分。
注意到这里有不等式约束，所以可以按照第A节的说法（这里是链接：（链接））化成标准形式，也就是添加一组松弛变量，这样的话可以把我们的KKT条件写成
Gx + c - A_\mathcal E ^T s - A_\mathcal{I}^T \lambda = 0 A_\mathcal{E} x - b_\mathcal{E} = 0 A_\mathcal{I} x - b_\mathcal{I} - y = 0 (\lambda, y) \ge 0, \lambda_i y_i = 0, i \in \mathcal{I} 这里的
b_\mathcal{E}, b_\mathcal{I} 和之前的意思类似，就是根据不同的指标集把
b 区分成不同的两个列向量。
跟之前的内点法一样的思路，我们考虑一下把它写成一个函数的形式，也就是写成
F(x, y, s, \lambda) = \begin{bmatrix}Gx + c - A_\mathcal E^T s - A_\mathcal I^T \lambda \\ A_\mathcal{E} x - b_\mathcal{E} \\ A_\mathcal{I} x - b_\mathcal{I} - y \\ \Lambda Y \mathbf 1\end{bmatrix}
其中
\Lambda, Y 的大小都是
n_2 \times n_2 的。这对应了上面的
\lambda_i y_i = 0, i \in \mathcal{I} 这个条件的意思，所以我们最终的目标就是希望
F(x, y, s, \lambda) = 0 ，而加上
(\lambda, y) \ge 0 ，就是完整的KKT条件了。
还是一样的原因，我们实际上会稍微做一些松弛，解下面这样的一个方程组
F(x, y, s, \lambda) = \begin{bmatrix}0 \\ 0 \\ 0 \\ \tau \mathbf 1\end{bmatrix}
并且要求
(\lambda, y) > 0 。然后我们通过考虑每一次都缩小
\tau ，因为
\tau \to 0 就意味着我们找到了解。
还是一样的原因，我们要解这个方程的根，就需要求解Jacobi矩阵，也就是说要求解下面这个问题
\begin{bmatrix}G & 0 & -A_\mathcal E^T & -A_\mathcal I^T \\ A_\mathcal{E} & 0 & 0 & 0 \\ A_\mathcal{I} & -I & 0 & 0 \\ 0 & \Lambda & 0 & Y\end{bmatrix}\begin{bmatrix}\Delta x \\ \Delta y \\ \Delta s \\ \Delta \lambda\end{bmatrix} = \begin{bmatrix}-r^d \\ -r^p \\ -r^y \\ -\Lambda Y \mathbf 1 + \sigma \mu \mathbf 1\end{bmatrix}
这里的
\mu = \frac{y^T \lambda}{m_2} ，
\sigma \in (0, 1) 为一个系数，
r^d = Gx + c - A_\mathcal{E}^T s - A_\mathcal{I}^T \lambda ，
r^p = A_\mathcal{E} x - b_\mathcal{E} ，
r^y = A_\mathcal{I} x - b_\mathcal{I} - y 。
这个方程组的求解自然是不容易的，但是大量的笔墨如果花在这里，可能其他内容就说不完了。所以这一部分大家可以看看资料，找一找对应的解法。
算法实现 和线性规划中内点法的处境相同，二次规划的内点法的算法也是一个实操优秀，却没有理论保障 的一个算法，它利用的也是主对偶 （primal-dual）的一个思路，我们直接把算法贴在下面。
好的，到此为止二次规划的内容就算正式结束了。
现代优化中的带约束光滑优化概述 欢迎来到现代优化的世界！
我们给它起名叫“现代优化”而不是“近代优化”啥的，原因在于优化这个学科真的不能算上历史悠久 ，对于运筹优化学科产生巨大需求的时候差不多是在二战，那个时候距离新中国成立也不远了（因为中国史上定义近代是到建国为止的）。比方说大名鼎鼎的Numerical Optimization （每一节Source都有它）就是一本06年的书籍，就我自己来说，我看过的成体系的一阶优化的方法的书，也是17年，18年这个时间才出版的，所以我们现在介绍的各种内容，我把它归类为现代优化，我认为还是有道理的。
如果要说光滑优化 (Smooth Optimization)可能还是挺多人不熟悉的，但是它其中蕴含的罚项，一阶信息 等思想其实已经被广泛运用到相当多的领域了。而我们在线性规划（还是第A节，链接看上面的文本）中也给大家解释过光滑的含义，而且也和大家说过，其实对于约束非光滑的情况，一般都会有方法把它改造成光滑的约束。当然了，要细说这一部分的话，完完全全可以再开一个系列，所以这一部分只是一个概述，在可能的很多细节上会有省略。
光滑优化本质上就是解决这样的问题
\min_{x \in \mathbb{R}^n} f(x)
s.t. \quad c_i(x) = 0 , i \in \mathcal{E}
c_i(x) \ge 0, i \in \mathcal{I}
其中
f, c_i(i \in \mathcal{E} \cup \mathcal{I}) 足够光滑。所以在一般的光滑优化里，对于约束和目标函数都没有很明显的形式限制，换句话说这是一个非常一般化 的问题。
罚项法 罚项法 (Penalty Method) 的含义就是通过罚项来转换优化问题的性质。比方说对于我们这一节所研究的问题，我们只需要构造这样的函数
Q(x; \mu) = f(x) + \frac \mu 2 \sum_{i \in \mathcal{E}} c_i^2(x) + \frac \mu 2 \sum_{i \in \mathcal{I}} ([c_i(x)]^{-})^2 其中
[y]^- = \max(-y, 0) ，换句话说对于不等式约束，只有它的对应的值为负的时候才会有惩罚。而对于等式约束，其实只要它非零，就会产生惩罚。换句话说，只要函数的约束条件不满足，就会根据它脱轨的情况来做一定的惩罚 。所以如果要最小化这个函数，势必不能够不考虑约束条件的存在。这样做一个最明显的特点就是把一个带约束优化的问题重新变回了无约束优化问题 。
下面一个定理说明了这个方法的可行性。
Theorem 1:
考虑一个序列
\{\mu_k\} 并且
\mu_k \to \infty ，并且考虑设
x_k 为对应的
Q(x; \mu_k) 的全局极小值，那么
\{x_k\} 的极限点
x^* 就是原始带约束光滑优化问题的解。
我们不证明这个结论，可以参考Numerical Optimization 的定理17.1。
大部分人看到这里，似乎觉得岁月静好，一切顺利。然而下一个定理告诉我们，事情没这么简单。
Theorem 2:
设每一个子问题（也就是求
Q(x; \mu_k) 的极小值，极小值点为
x_k ）都可以被优化到
\|\nabla_x(Q(x, \mu_k))\| \le \tau_k 的程度，并且
\tau_k \to 0, \mu_k \to \infty ，那么如果
x^* 是非可行解，那么它就是
\|c(x)\|^2 的驻点，如果它的极限点是可行点，且
\nabla c_i(x^*) 线性无关，那么
x^* 是一个满足KKT条件的点。除此之外，对任意的满足
\lim_{k \in \mathcal{K}}x_k = x^* 的子序列集合
\mathcal K ，都有
\lim_{k \in \mathcal K} -\mu_k c_i(x_k) = \lambda_i^*, \forall i \in \mathcal E ，其中
\lambda^* 就是KKT条件满足的拉格朗日乘数向量。
这个就是书上的定理17.2，这个地方说明了，即使我们最终做到了梯度趋于0，也就是算法收敛，我们也不一定能够保证收敛到一个可行解 。这个看似和theorem 1是冲突的，但是其根本上在于“全局极小值”与“驻点”的区别。而且因为极限式子的存在，相当于说我们必须在
\mu_k \to \infty 的时候，才能保证
c_i(x_k) \to 0 ，而且这还不一定是严格的为0。换句话说，对于一般的问题，这样子解是可以的，只是它的性质可能没有那么好。
对于这个问题的优化还存在一个问题，就是它的海塞矩阵的性质往往很差 。为了解释我们去掉我们的不等式约束。在去掉不等式的约束之后呢，它的海塞矩阵就是
\nabla_{xx}^2 Q(x; \mu_k) = \nabla ^2 f(x) + \sum_{i \in \mathcal E}\mu_k c_i(x) \nabla ^2 c_i(x) + \mu_k A(x)^T A(x) 其中
A(x)^T = [\nabla c_i(x)]_{i \in \mathcal E} ，观察到如果说我们的
\mu_k \to \infty ，那么最终的一个海塞矩阵就可以写为
\nabla_{xx}^2 \mathcal L(x, \lambda^*) + \mu_k A(x)^T A(x) ，而注意到我们的约束条件很少，而我们的变量维数很高的时候，
A(x)^T A(x) 是低秩 的（理解这一点需要注意的是，假如说我们有
m 个约束条件，变量是
n 维的，那么
A(x)^T \in \mathbb R^{n \times m} ），这样的情况导致的问题就是，即使我们的拉格朗日函数的海塞矩阵性质很好，
\mu_k 很大的时候也无济于事，整个海塞矩阵的特征值会呈现一个两极分化的状态 。换句话说条件数很大 ，这个在数值优化中是一个大忌。总结一下就是说，对于所有依赖二阶信息的方法，都会呈现出很强的不稳定性。
要解决这个问题，有一种方法就是改变罚项的性质 ，这一点非常像岭回归往LASSO的转换，就是把我们的2-范数罚项修改为1-范数罚项，也就是修改我们的函数为
\phi_1(x;\mu) = f(x) + \mu \sum_{i \in \mathcal E}|c_i(x)| + \mu \sum_{i \in \mathcal I}[c_i(x)]^- 其中
[y]^- 的含义和之前相同。当然了，如果目标函数修改成这样之后，我们对应就会有下面的这个定理成立。
Theorem 3:
若
x^* 是非线性规划问题的严格局部极小值点，并且
\lambda_i^*, i \in \mathcal{E} \cup \mathcal I 为KKT条件对应的拉格朗日系数，那么对任意的
\mu > \|\lambda^* \|_\infty = \max_{i \in \mathcal E \cup \mathcal I} |\lambda_i^*| ，
x^* 都是
\phi_1(x, \mu) 的局部极小值。
这个也是对应原书的定理17.1。这个定理想说明的内容就是，我们的
\mu 不再需要让它充分的大，就可以找到函数的局部极小值点。
增广拉格朗日方法（ALM） 上面的方法有一个显著的好处就是在于不需要
\mu \to \infty ，但是很明显这个函数不是一个光滑函数 ，因此求极小值这个事情就会变得困难。为了避免掉这个事情，我们需要新的方法。
增广拉格朗日方法（Augmented Lagrangian Methods, ALM）也是一个比较常见的优化算法，和之前的罚项法不同的地方在于，它是针对函数对应的拉格朗日函数添加罚项，而不是针对目标函数本身 。比方说对于一个等式约束问题
\min_{x \in \mathbb{R}^n} f(x)
s.t. \quad c_i(x) = 0, i \in \mathcal E
那么它的对应的增强拉格朗日函数就是
\mathcal L_A(x, \lambda; \mu) = f(x) - \sum_{i \in \mathcal E} \lambda_i c_i(x) + \frac \mu 2 \sum_{i \in \mathcal E}c_i^2(x) 可以看出它就是一个拉格朗日函数加上罚项
\frac \mu 2 \sum_{i \in \mathcal E}c_i^2(x) 的结果。那么这个时候，可以得到的是
\nabla_x \mathcal L_A(x, \lambda; \mu) = \nabla f(x) - \sum_{i \in \mathcal E}(\lambda_i - \mu c_i(x))\nabla c_i(x) 注意到当
x^* 这个点满足KKT条件时，如果我们设它对应的拉格朗日乘数为
\lambda_i^*, i \in \mathcal E ，那么很明显无论
\mu 取多少，都有
\nabla_x \mathcal L_A(x^*, \lambda^*; \mu) = 0 ，来解
x^*, \lambda^* 。所以我们的想法就是考虑下面的一个迭代
\lambda_i^{k + 1} = \lambda_i^k - \mu c_i(x_k), i \in \mathcal E 这个设计的思路在于，一般情况下
x^* 时可以迭代且已知的，但是**
\lambda_i 都是不知道的**，所以我们每一次做这样的迭代，其实就是一个对于
\lambda_i^{k + 1} 的猜测。当然为什么这么猜测，就是一个挺深奥的问题了。
我们举一个例子来说明这样做的一个合理性
Example 1:
考虑问题
\min_x (x_1 -1)^2 + x_2 ^2 ，且
x_1 = 0 ，说明增广拉格朗日方法的正确性。
其实我们可以写出它的增广拉格朗日函数
\mathcal L_A(x, \lambda) = (x_1 - 1)^2 + x_2^2 - \lambda x_1 + \frac \mu 2 x_1^2 对它求梯度可以得到
\nabla_x \mathcal L_A(x ,\lambda) = (2(x_1 - 1) -\lambda + \mu x_1 , 2x_2)^T = (0, 0)^T 因此可以解出
x_1 = \frac{2 + \lambda}{2 + \mu}, x_2 = 0 ，这一点说明，假如说
\lambda > -2 ，那么我们每一次估计
\lambda 的迭代公式就是
\lambda' = \lambda - \mu x_1 < \lambda ，换句话说会把
\lambda 给缩小。反过来，如果
\lambda < -2 ，那么你会发现迭代公式会把
\lambda 扩大。一言以蔽之，
\lambda 会被“拉到”
-2 ，而如果验证一下原问题的KKT条件，会发现这个就是它的KKT条件对应的拉格朗日系数。也就是说这个迭代公式并不是空穴来风，它是可以帮助我们解决问题的。
关于增广拉格朗日方法自然也有它的相关性质。
Theorem 4:
设
x^* 是原问题的一个局部极小值点，且满足LICQ条件，并且在KKT条件的点满足二阶充要条件。那么存在一个
\bar \mu ，使得对于任意的
\mu \ge \bar \mu ，
x^* 都是
\mathcal L_A(x, \lambda^*; \mu) 的局部极小值点。
这个定理对应原书的17.5。简单来说，它说明了并不需要
\mu \to \infty 才能找到解，并且原问题的光滑性也得到了一定的保证。
可能这个时候有的人会跳出来说：你这个
\lambda^* 不是刚刚才说不知道吗 ？确实，不过这个问题并不是没有解决方法，事实上我们还有一个另外的定理。
Theorem 5:
设
x^*, \bar \mu 都和theorem 4中的含义相同，那么存在正常数
\delta, \epsilon, M 使得对任意满足
\|\lambda^k - \lambda^* \| \le \mu_k \delta, \mu_k \ge \bar \mu 的
\lambda^k, \mu_k
(1) 问题
\min_x \mathcal L_A(x, \lambda^k; \mu_k) \quad s.t. \|x - x^*\| \le \epsilon 都有唯一解
x_k ，并且我们有
\|x_k - x^* \| \le M \|\lambda^k - \lambda^* \| / \mu_k 。
(2)
\|\lambda^{k + 1} - \lambda^* \| \le M \|\lambda^k - \lambda^* \| / \mu_k
(3)
\nabla_{xx}^2 \mathcal{L}_A(x_k, \lambda^k ; \mu_k) 正定，且
\nabla c_i(x_k), i \in \mathcal{E} 梯度集合线性无关。
这个定理就说明了，只要我们的
\lambda^k 足够靠近
\lambda^* ，我们的
x_k 就会足够靠近
x^* ，并且每一步迭代都会使得
\lambda^k 与
\lambda^* 的差距以线性收敛速度缩小，并且迭代点附近也有LICQ一样的性质。换句话说，我们的增广拉格朗日方法在实操中是可行的 ，毕竟数值优化算法的误差是不可避免的。
当然了有一个隐患在于，实际的
\bar \mu 也是不知道的 ，所以我们在做迭代的时候，也要注意每一次增加
\mu 来观察最终收敛的结果是否有变。
交替方向乘子法（ADMM） 交替方向乘子法 （Alternating Direction Method of Multipliers）应该算是一个非常有名的一阶方法了。它的思路源于增广拉格朗日法。这里考虑的是一个这样的问题。
\min_{x \in \mathbb R^{n_1}, z \in \mathbb{R}^{n _2}} f_1(x) + f_2(z) \quad s.t. Ax + Bz = c 对于这个问题，如果要写出它的增广拉格朗日函数，就是
\mathcal L_A(x, z; s) = f_1(x) + f_2(z) + s^T (Ax + Bz - c) + \frac \mu 2 \|Ax + Bz - c \|^2 这个问题看似非常正常，但是在实际情况下，非常多出现两个子函数
f_1, f_2 单独优化都比较简单，合在一起优化却非常困难 的情况。在这样的情况下，我们的想法就是加上交替下降的思路，即每一次固定一个变量为常数，视作单变量的优化问题 。然后再使用增广拉格朗日方法。具体的步骤如下
x^{k + 1} = \arg\min_{x}[f_1(x) + (s^k)^T (Ax + Bz^k - c) + \frac \mu 2 \|Ax + Bz^k - c\|^2 z^{k + 1} = \arg\min_{z}[f_2(z) + (s^k)^T (Ax^{k + 1} + Bz - c) + \frac \mu 2 \|Ax^{k + 1} + Bz - c\|^2 s^{k + 1} = s^k + \mu (A x^{k + 1} + B z^{k + 1} - c) 当然了你需要给定初值
z^0, y^0 和
\mu > 0 。
这里的前两步就是交替下降法，也就是说每一步固定一个变量，只考虑与另外一个变量有关的项进行优化。第三步就是增广拉格朗日法，一直迭代到收敛为止即可。
ADMM方法的速度不算快（包括局部上的 ，这也算是一个缺点），如果
f_1, f_2 凸，那么它会有
O(\frac 1k) 的收敛速度。进一步的如果说
f_1, f_2 是强凸的，那么收敛速度就是线性的。但对于一阶方法而言，这已经够了。
那么关于这个方法，我们也给一个很有名的例子，来看我们如何来使用ADMM解决问题。
Example 2:
考虑问题
\min_{x \in \mathbb{R}^n}[\frac 12 \|Ax - b \|_2^2 + \lambda \|x\|_1] ，设计优化算法。
要使用ADMM方法，一个很重要的操作就是构造出两个相互不影响的函数 。因此我们的想法就是设
Ax - b= z ，所以这样的话问题就会变成
\min_{x \in \mathbb{R}^n, z \in \mathbb{R}^m} [\frac 12 \|z\|_2^2 + \lambda \|x \|_1] \quad s.t. ~ Ax - b= z 那么如果要使用ADMM，我们的迭代步骤就是
x^{k + 1} = \arg\min_{x}[\lambda \|x\|_1 + (s^k)^T (Ax - z^k - b) + \frac \mu 2 \|Ax - z^k - b\|^2
z^{k + 1} = \arg\min_{z}[\frac 12 \|z\|_2^2 + (s^k)^T (Ax^{k + 1} - z - b) + \frac \mu 2 \|Ax^{k + 1} - z - b\|^2
s^{k + 1} = s^k + \mu (A x^{k + 1} - z^{k + 1} - b)
这个计算的步骤也存在一些难点。对于第二个子问题，其实它是很容易找到问题的解的形式的（为了防止读者误解，这里多说几句，含义在英文里是closed-form，也就是说解可以写成一个等价好用的形式，后面我们也会继承这种写法），毕竟都是二次项，求个梯度然后设为0就好。但是对于第一个子问题，
\lambda \|x\|_1 的存在就使得问题的解没有一个固定的形式。不过这个问题也有解决的方案，这就是交替方向近端乘子法 （Alternating Direction Proximal Method of Multipliers, ADPMM）。
这个方法的思路来源于一阶方法中的近端梯度法 ，也就是加一个二阶项权重，使得问题的closed-form能够重现 。也就是说
x^{k + 1} = \arg\min_{x}[\lambda \|x\|_1 + (s^k)^T (Ax - z^k - b) + \frac \mu 2 \|Ax - z^k - b\|^2 + \frac 12 \|x - x^k\|_W^2
其中
W = \alpha I -\mu A^T A ，并且我们要求
\alpha 足够大，满足
\alpha \ge \mu \lambda_{\max}(A^T A) （这一点是因为要保正定，否则就不能说它是一个合理的范数了，注意
\|x\|_W^2 =x^T W x ）。这个方法的核心就是去掉我们的
x^T x 系数矩阵
A 的影响 。因为我们可以看到，
\frac \mu 2 \|Ax - z^k - b\|^2 这一项中，关于
x^T x 的这一项的格式为
\frac \mu 2 x^TA^T A x ，所以把
W 那一项代进去，我们可以把这一项消掉，这样的话关于
x^T x 其实它就没有额外矩阵的影响了。
这样操作之后，我们就可以通过配方，使得问题被转为下面这个格式
x^{k + 1} = \arg\min_{x} [\lambda \|x \|_1 + \mu x^T A^T (Ax^k - z^k - b + \frac 1 \mu s^k) + \frac \alpha 2 \|x - x^k \| _2^2] 为什么说这个东西的closed-form存在呢，这是因为我们有
\max(y - \lambda, 0) + \min (y + \lambda, 0) = \arg\min_{x} \frac 12 \|x - y \|_2^2 + \lambda \|x \| _ 1
而我们之前的那个式子其实是可以通过配方，把第二项和第三项放在一起，来组合成上面这样的形式的。那么closed-form存在，就说明这个优化的子问题并不需要通过数值方法来求解 ，这就会大大加快计算速度。
好的，那么到此为止，我们这一个系列就算是正式更新完毕了。
习题课 优化这个学科相比较其它课程而言，不会有太多独特的习题 ，这也是我们没有单独的一节习题课的原因。当然了，最重要的地方还是，读者要在习题中了解到算法设计的考虑，发现一些本质上的东西 。
那么我们开始吧。
Problem 1:
对矩阵
A = \begin{bmatrix}1 & 1 & -2 \\ 1 & 1 + \delta & 1 \\ -2 & 1 & 10\end{bmatrix}, \delta \ge 0 进行
A = LDL^{T} 的格式的Cholesky分解。问
\delta 在什么范围内的时候矩阵
A 为正定阵，并讨论
\delta \to 0 的时候，
D, L 的元素变化情况。
如何做Cholesky分解是数值分析要考虑的事情，我们这里直接给出答案
L = \begin{bmatrix}1 & 0 & 0 \\ 1 & 1 & 0 \\ -2 & \frac 3 \delta & 1\end{bmatrix} ，
D = \begin{bmatrix}1 & 0 & 0 \\ 0 & \delta & 0 \\ 0 & 0 & 6 - \frac 9 \delta\end{bmatrix} 要看矩阵是否正定，看
D 的性质就可以了。这里可以看出来，当
\delta > \frac 32 的时候矩阵就是正定的，那么
\delta \to 0 的时候我们会发现，
D 和
L 中都会出现趋于无穷的元素。这个现象其实说明矩阵不正定不代表它不能进行Cholesky分解 ，只是在非正定的情况下，矩阵的性质会受到很大的影响。因此我们在牛顿法的部分（链接：）提过说，修正的Cholesky分解会引入参数保证
D 中元素都是正的，且
L 中元素都有上界。
Problem 2:
设
f \in C^2 为
\mathbb R^n 中的凸函数，设
x_1, x_2 \in \mathbb R^n ，且
s = x_2 - x_1, y = \nabla f(x_2) - \nabla f(x_1) ，证明
s^T y \ge 0 。
如果
f 是凸的，那么设
x_1, x_2 \in \mathbb R^n ，一定有
f(\alpha x_1 + (1-\alpha) x_2) \le \alpha f(x_1) + (1-\alpha)f(x_2), \forall \alpha \in [0, 1] 稍微化简就可以得到
\frac{f(\alpha x_1 + (1-\alpha) x_2) - f(\alpha x_1)}{1 - \alpha} - \frac {f(x_1) - f(\alpha x_1)}{1 - \alpha} \le f(x_2) - f(x_1)
为了看着舒服些，设
t = 1-\alpha ，并且令
t \to 0 ，我们有
x_2^T \nabla f(x_1) - x_1^T \nabla f(x_1) \le f(x_2) - f(x_1)
（注意，这是我们一直在用的方向导数公式），因此我们会有
s^T \nabla f(x_1) \le f(x_2) - f(x_1) ，交换一下
x_1, x_2 的顺序（因为它们的地位相同）我们可以得到
-s^T \nabla f(x_2) \le f(x_1) - f(x_2) ，也就是说
s^T \nabla f(x_2) \ge f(x_2) - f(x_1) ，那么我们可以很容易发现
s^T \nabla f(x_2) \ge s^T \nabla f(x_1) ，这就说明了
s^T y \ge 0 。
Problem 3:
证明由
(x_1 - 1)^2 + (x_2 - 1)^2 \le 2
(x_1 - 1)^2 + (x_2 + 1)^2 \le 2
x_1 \ge 0
定义的可行域在点
x^* = (0, 0)^T 处有MFCQ成立，但是LICQ不成立。
要满足MFCQ，就是要说明
\exists w = (w_1, w_2) ，使得
\nabla c_i^T(x^*) w > 0, \forall i \in \mathcal A(x^*) \cap \mathcal I ，并且有
\nabla c_i^T(x^*) w = 0, \forall i \in \mathcal {E} 。而在点
x^* = (0, 0)^T 处，容易验证这三个约束条件都被激活了，所以它们都要满足上面的恒正条件。
那么我们注意到，如果我们按顺序标记这三个约束不等式为
c_1, c_2, c_3 ，那么我们会有
\nabla c_1(x_1, x_2) = (2(x_1 - 1), 2(x_2 - 1)) \nabla c_2(x_1, x_2) = (2(x_1 - 1), 2(x_2 + 1)) \nabla c_3(x_1, x_2) = (-1, 0) 代入
x^* = (0, 0)^T 我们就可以发现，取
w_1 = -1, w_2 = 0 即可。因此MFCQ条件是成立的。但是LICQ条件并不成立，因为要求激活集内包含的各个向量是线性无关的。但是约束有3个，每个向量的维数却只有2，因此这是不可能做到的。
Problem 4:
证明线性规划中内点算法系数矩阵
\begin{bmatrix}0 & A^T & I \\ A & 0 & 0 \\ S & 0 & X\end{bmatrix} 是满秩的当且仅当矩阵
A 是行满秩的。
要说明矩阵满秩，一个通用的思路就是对矩阵进行行列变换，将其化为上三角或下三角分块矩阵，然后观察对角元矩阵的性质 ，这是因为初等变换不改变矩阵的秩。那么对于这个矩阵我们可以怎么做呢？
假如说我们要保证矩阵是一个上三角矩阵，那么只需要消去左下角的
A, S 即可。那么我们第一步可以先把第三列乘一个
SX^{-1} ，加到第一列。这样会得到矩阵为
\begin{bmatrix}-SX^{-1} & A^T & I \\ A & 0 & 0 \\ 0 & 0 & X\end{bmatrix} 。也就是说左下角的
S 就被消去了。这个过程就相当于右乘一个初等变换矩阵。
第二步自然考虑消去
A ，那么自然考虑第一行做一个运算（因为列的操作很明显都不行了）。因此我们给第一行乘一个
AXS^{-1} ，加到第二行，就可以得到矩阵
\begin{bmatrix}-SX^{-1} & A^T & I \ 0 & AXS^{-1}A^T & AXS^{-1} \ 0 & 0 & X\end{bmatrix} 。那么在内点法那一节中我们说过，
S, X 都是对角元素为正的对角阵。所以问题的关键就落在了
AXS^{-1}A^T 上，然而只需要
A 是行满秩的，
AA^T 就是满秩的，中间乘一个数量矩阵
XS^{-1} 不会有任何影响。所以我们可以得到说，只要
A 行满秩，那么
AXS^{-1}A^T 就是满秩的，那么原始矩阵就是满秩的，这就完成了证明。
这个题虽然在高等代数中应该算是非常常见的题型，但是不能忽视的是，在运算的时候要注意矩阵的大小，在分块矩阵的运算中这个问题是容易被忽视的。
小结 这一节我们结束了对二次规划的讨论，介绍了一些常见的现代优化的方法，也补充了几道理论习题用于复习一些基本的数值优化知识点。当然了对于优化，其实还有相当多的主题可说，这一个系列也只是给大家搭建了一个基本的优化算法的框架，渗透了优化这个领域内所依赖的其它基本知识。另外再强调一遍，优化的所有内容都非常具备实操性，掌握编程的技能对于这个学科而言同样重要 。我们在每一节讲到具体的方法的时候都会贴上原始slides的算法步骤，也是鼓励大家自己用code去复现这些内容。
OK，完结撒花！
