Notes: Nonlinear Programming

franciscochonge · 发表于 2022-2-21 16:55

1 优化漫谈

优化问题是现实问题的数学抽象。通常情况下，我们有很多想做的事情，比如发很多论文，挣很多钱。清晰一点说，我们是想要去完成一些目标。我们与这个世界进行交互，不断采取行动，尽可能接近目标。但是我们能够采取的行动是受限的，例如一天没有25小时，一秒钟不能打一万字。将采取的行动抽象为决策变量  ，将行动所受到的限制抽象为约束条件 $x\in X$ ，将想要完成的目标抽象为目标函数  ，便得到了优化问题：

$\begin{align} \min&~~~f(x)\\ \text{s.t.} &~~~x\in X \end{align}$
我们该怎么得到更好的  ，甚至最好的  呢？这要取决于目标函数  的性质，可行集  的形状。如果  性质比较糟糕，我们在选择  时只能用到  本身，此时的优化方法称为零阶优化方法。零阶优化使用非常广泛，网格搜索、模拟退火算法、遗传算法、粒子群算法等均属此类，暂且按下不表。如果我们能很方便地求解出  的梯度  ，我们就能沿着负梯度方向不断前进，从而不断求得更好的  ，这称为一阶优化方法，当今大火的神经网络在训练时往往采用这种方法。当然，如果我们能求得  的更多信息，比如  的Hessian矩阵  （由二阶偏导数构成的矩阵），便有可能更快地到达最优解。值得一提的是，如果我们已知  二阶可微，即使我们无法求得  ，依然有可能通过一阶信息  估计二阶信息  ，进而更快地求解。总之，  的性质越好，我们能够得到  的信息越多，我们便能更好的求解。当然，可行集  作用不容忽视。如果  被限定为离散值（如整数、0-1变量），此时的问题称为组合优化问题。著名的组合优化问题比如旅行商问题、背包问题、Hamiltonian路径问题，这些问题被证明是NP完全问题，相当难求解。组合优化也是非常广阔的一片大陆，暂且按下不表。
在这篇笔记中，主要以“具有一些性质”的  ，和“形状比较好”的  为研究对象，以著名学者Bertisekas著《Nonlinear Programming》为参考，记录一些优化方法及其性质。
2 无约束优化

2.1 最优解存在性的充分条件

我们先考虑没有约束条件的情况，即 $\min~f(x)$ 。但在此之前，有个很关键的问题，那就是什么时候我们能求得 $f(x)$ 的最小值？Weierstrass定理给出了最优解存在性的一个充分条件。
Weierstrass 定理：令  为  的非空子集，令 $f:X\mapsto \mathbb{R}$ 在  所有点上下半连续（函数值不大于函数极限）。若  是紧集，或  是闭集且  是强制的，则  在  上的最小值集是非空且紧的。
注意该定理并不需要假设函数连续，只需要下半连续。这是因为下半连续已经能够保证我们能在任何一个可能的极限点取得最小值，而不会出现邻域函数值在趋于极限点时趋于最小值，而极限点对应函数值反而更大的情况。而关于  的要求保证了极限点一定能取到，不会出现在集合边界或者趋于无穷的情况。
2.2 最优性条件

当我们明确解的存在性之后，能够判断一个解是否是最优解，是求解优化问题的前提。如果  可微，局部最优性的一阶必要条件为  ，如果  二阶可微，局部最优性的二阶必要条件为 $\nabla^2f(x)$ 半正定。注意这并不是充分条件，当  是凸函数时一阶必要条件同时也是充分条件。如果  是凸函数但不可微，一阶充要条件为 $0\in \partial f(x)$ ，即在  点处，水平面为一个次梯度，其余点处的函数值都在水平面上方。
当优化问题具有约束时，最优性条件不仅非常有意义，而且非常有意思，且看下文表述。
2.3 强凸函数的良好性质

如果函数的性质很好，我们就能从当前解中得到关于最优解的信息。例如当 $f$ 满足  时，我们可以得到：

$\frac{1}{2M}\|\nabla f(x)\|^2\le f(x)-f(x^*)\le\frac{1}{2m}\|\nabla f(x)\|^2$

$\frac{m}{2}\|x-x^*\|^2\le f(x)-f(x^*)\le \frac{M}{2}\|x-x^*\|^2$
这意味着从当前的梯度可以推知当前函数值与最优函数值之间的距离，进而推知当前解与最优解的距离。
证明：将  在  点处Taylor展开到  ：

$f(x^*)=f(x)+\nabla f(x)(x^*-x)+(x^*-x)\nabla^2f(\tilde x)(x^*-x)$
根据  ，所以：

$\nabla f(x)(x^*-x)+m\|x-x^*\|^2\le f(x^*)-f(x)\le \nabla f(x)(x^*-x)+M\|x-x^*\|^2$
根据二次函数的性质，我们知道：

$\min_y \{\nabla^\top (y-x)+\frac{\alpha}{2}\|y-x\|^2\}=-\frac{1}{2\alpha}\|\nabla\|^2$
从而可以得到第一个式子。第二个式子则将  在  点处Taylor展开到  ：

$f(x)=f(x^*)+(x-x^*)\nabla^2f(\tilde x)(x-x^*)$
进而根据  得到。
2.3 最速下降方法

很多情况下，我们并不能直接求解  ，这时候我们可以通过迭代的方式进行求解。令人欣慰的是，我们知道梯度信息，当我们沿着负梯度方向前进适当距离时，函数值会下降，我们或许更接近最优解了。最简单的梯度下降形式为：

$x_{k+1}=x_k-\alpha_k \nabla f(x_k)$
其中 $\alpha_k$ 是步长，步长的选取很有学问，可以选取常数步长，衰减步长等。也可以通过搜索的方式确定步长，如精确搜索，或者可以降低计算量，采用大名鼎鼎的Armijo规则、Goldstein规则搜索。一般来说，函数的性质越好，相同收敛性和收敛速度下，对步长的要求越少。
在此介绍Armijo规则，其搜索想要达到的目标是不断增大非负整数  ，寻找到第一个  使得如下式子成立：

$f(x_k+\beta^m s d_k)\le f(x_k) +\sigma \beta^ms\nabla f(x_k)^\top d_k$
其中 $\sigma$ 和 $\beta$ 是设定的参数，  是搜索方向。当步长选取非常小时，基本上按照梯度的斜率下降。但这个式子的含义是，没必要要求那么苛刻，我们设置一个 $\sigma\in(0,1)$ 的“宽容因子”。牺牲了下降的斜率，但是换来了更大的步子。通常情况下，需要权衡这两者，以取得较快的下降速度。
2.4 牛顿法

在梯度下降方法中，我们很难不去问这样一个问题，沿着负梯度方向是真的时下降最快的方向吗？如果我们知道二阶信息  ，能不能更快地迭代呢？牛顿法正是通过  来修正负梯度方向 $-\nabla f$ ，进而实现更快地收敛速度。其迭代方式为：

$x_{k+1}=x_k-\alpha_k (\nabla^2 f(x_k))^{-1}\nabla f(x_k)$
当函数为二次型时，该式起到的效果是将负梯度方向修正为指向最优解的方向。因此一个函数如果比较接近二次型，比如当二阶连续可微的函数在局部最优解附近时，将会大大加快收敛速度。
牛顿法虽然能更快收敛，但其计算量代价不容忽视。当决策变量维度较高时，Hessian矩阵的计算和求逆需要很大计算量，甚至复杂到没办法计算。这时候可以使用牛顿法的变种，比如：

$x_{k+1}=x_k-\alpha_k \begin{pmatrix} * & 0 & \cdots & 0\\ 0 & * & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \cdots &* \end{pmatrix} ^{-1}\nabla f(x_k)$

$x_{k+1}=x_k-\alpha_k (\nabla^2 f(x_0))^{-1}\nabla f(x_k)$
或者通过其他方式进行估计：

$x_{k+1}=x_k-\alpha_k [\text{approximation of }(\nabla^2 f(x_0))^{-1}]\nabla f(x_k)$
2.4 共轭梯度法

与最速下降方法不同，共轭梯度法的思路并不是每次沿着“最速”的方向前进，而是找到一系列共轭的方向，依次沿着这些方向前进。共轭方向是被精心挑选的，使得对于二次型函数，依次沿着这些方向精确搜索后，就能够得到最优解。也就是说，每次优化的方向都已经“优化完了”，在该方向上到达了最优解。虽说共轭梯度法从二次型推导而来，但它在非二次型函数上也可以有很好的收敛性能。
共轭方向 $d_i$ 需要满足如下“Q-共轭”性质：

$d_i^\top Qd_j=0$
从这个式子可以轻易推导出共轭方向一定是线性无关的，因此  具有n个共轭方向。
若对于二次型 $f(x)=x^\top Qx+b^\top x$ ，每次步长搜索都是精确搜索：

$\frac{\partial (x_{k+1}+\alpha d_i)}{\partial \alpha}=0$
那么有 $x_{k+1}={\arg\min}_{x\in x_0 + \bm{\mathrm{span}}\{d_0,\cdots,d_k\}}f(x)$ ，也就是说每次沿着新共轭方向优化，不会影响已经优化好的方向。
共轭方向  可以从一系列梯度 $g_k$ 中使用Schmidt正交化生成：

$d_k=-g_k+\sum_{j=0}^{k-1}\frac{g_k^\top Q d_j}{d_j^\top Q d_j}d_j$ ， $d_0=-g_0$
这个式子可以写成迭代的形式，方便求解：

$d_k=-g_k+\beta_k d_{k-1}$ ， $\beta_k=\frac{g_k^\top g_k}{g_{k-1}^\top g_{k-1}}$
3 约束优化

通常我们遇到的优化问题都是具有约束的，因此接下来在无约束优化的基础上，探讨如何在具有约束的情况下进行优化。
3.1 梯度投影法

最简单的思路是，仍然按照无约束优化的算法优化，一旦当前解出了可行集，就把它弄回去。这种方法称为梯度投影法，即下面两步交替进行：

$\tilde x_{k+1}=x_k-\alpha_k d_k$

$x_{k+1}=\arg\min_{y\in C}\|x-y\|$
这里要求 $C$ 是凸集，此时投影是存在（由Weiestrass定理）且唯一（由反证法和凸集定义）的。
3.2 条件梯度法

相比首先考虑最优性迭代的梯度投影法不同，条件梯度法的思路首先考虑约束。条件梯度法的思路是寻找可行方向，进而在可行方向上优化，找到可行集合中沿可行方向最远的点。将负梯度方向作为可行方向（如果负梯度方向不可行，此时已经是局部最优解），构建如下具有线性目标函数的子优化问题：

$\begin{align} \min_x&~~~\nabla f(x_k)^\top(x-x_k)\\ \text{s.t.} &~~~x\in C \end{align}$
如果约束条件比较简单（如线性约束），此时子优化问题将很容易求解（线性规划），这是条件梯度法的好处之一。
3.3 拉格朗日橘子定理

对于函数 $f,h$ 连续可微、优化问题具有等式约束  的情况，拉格朗日乘子定理给出了最优解的必要条件。
拉格朗日乘子定理：若  是可微函数  在  的条件下的局部最小值点，假设约束的梯度 $\nabla h_1(x^*),\cdots,\nabla h_m(x^*)$ 线性无关（正则性），则存在唯一的拉格朗日乘子  使得：

$\nabla f(x^*)+\sum_{i=1}^m\lambda_i^* \nabla h_i(x^*)=0$
并且如果函数二次可微，在 $\{y|\nabla h_i(x^*)^\top y=0,i=1,\cdots,m\}$ 上有：

$\nabla^2 f(x^*)+\sum_{i=1}^m\lambda_i^* \nabla^2 h_i(x^*)\ge0$
该定理可以通过惩罚方法证明，证明过程中可以得到  的显式表达式：

$\lambda^*=-\left(\nabla h(x^*)^\top \nabla h(x^*)\right)^{-1}\nabla h(x^*)^\top\nabla f(x^*)$
求逆的部分解释了为什么得到唯一拉格朗日乘子要求正则性。
3.4 KKT最优性条件

KKT条件推广了拉格朗日方法，对于函数 $f,h,g$ 连续可微、优化问题具有等式约束  和不等式约束 $g(x)\le0$ 的情况，给出了最优解的必要条件。
Karush-Kuhn-Tucker最优性必要条件：若  是函数  在  的条件下的局部最小值点，假设约束的梯度 $\nabla h_1(x^*),\cdots,\nabla h_m(x^*),\nabla g_i(x^*), i\in\{i|g_i(x^*)=0\}$ 线性无关（正则性），则存在唯一的拉格朗日乘子  使得：

$\nabla f(x^*) +\sum_{i=1}^m\lambda_i^* \nabla h_i(x^*) +\sum_{i=1}^r\mu_i^* \nabla g_i(x^*) =0$
其中  。对于  ，  。
3.5 FJ最优性条件

FJ条件推广了KKT条件，对于非正则的情况，给出了最优解的必要条件。
Fritz John最优性必要条件：若  是函数  在  的条件下的局部最小值点，则存在标量 $\mu_0^*$ 和乘子  使得：

$\mu_0^*\nabla f(x^*) +\sum_{i=1}^m\lambda_i^* \nabla h_i(x^*) +\sum_{i=1}^r\mu_i^* \nabla g_i(x^*) =0$
其中  。对于  ，  。 $\mu_0^*,\lambda^*,\mu^*$ 不全为零。
FJ条件较为通用，我们可以通过函数的性质，从FJ条件推出KKT条件，从而得到更强的必要条件。
3.6 从FJ条件到KKT条件

如下几种情况均能够使得FJ条件加强为KKT条件：

是线性函数，且是凹函数。
Mangasarian-Fromovitz条件： $\nabla h_i(x^*)$ 线性无关，且存在向量 $d$ ，使得 $d^\top\nabla h_i(x^*)=0$ ，对于有 $d^\top\nabla g_i(x^*)<0$ 。
Slater条件： 是线性函数，是凸函数，且存在对于有 $g_i(x)<0$ 。

xiangtingsl · 发表于 2022-2-21 17:04

拉格朗日橘子定理

zt3ff3n · 发表于 2022-2-21 17:09

反正不是橙子定理[飙泪笑]

		自动登录	找回密码
密码			立即注册