不断目标函数f的性质，我们便能更好的求解

1 优化谈话

优化问题是对现实世界问题的数学抽象。通常，我们有很多想做的事情，比如发表很多论文，赚很多钱。明确地说，我们想要完成一些事情。我们与世界互动，不断采取行动以尽可能接近我们的目标。但我们能采取的行动是有限的。例如，一天没有 25 个小时，我们不可能在一秒钟内输入 10,000 个单词。将要采取的动作抽象为决策变量 x ，将动作的约束条件抽象为约束 x\in X ，将要完成的目标抽象为目标函数 f ，得到优化问题：

\begin{align} \min&~~~f(x)\\ \text{st} &~~~x\in X \end{align}

我们如何获得更好的 x，甚至是最好的 x？它取决于目标函数f的性质和可行集X的形状。如果f的性质不好，我们在选择x时只能使用f本身，此时的优化方法称为零阶优化方法。零阶优化被广泛使用，包括网格搜索、模拟退火算法、遗传算法、粒子群优化等。如果我们可以很容易地解决 f \nabla f 的梯度，我们就可以继续朝着负的方向前进梯度，从而不断地找到一个更好的 x ，这称为一阶优化方法，如今热门的神经网络在训练中经常使用这种方法。当然，如果我们能找到更多关于 f 的信息，例如 f \nabla ^2f 的矩阵（由二阶偏导数组成的矩阵），可以更快地达到最优解。值得一提的是，如果我们知道 f 是二阶可微的，即使我们找不到 \nabla ^2f ，仍然可以通过一阶信息 \nabla f 估计出二阶信息 \nabla ^2f ，然后更快地解决它。简而言之，f的性质越好，我们可以获得的关于f的信息就越多，我们就能更好地解决它。当然，可行集X的作用也不容忽视。如果x被限制为离散值（例如整数、0-1变量），此时的问题称为组合优化问题。著名的组合优化问题，如旅行商问题、背包问题、并且路径问题被证明是NP完全的并且很难解决。组合优化也是一个很广阔的大陆，暂时不列出来。

在这篇笔记中，我们主要以具有“一些性质”的f和具有“更好的形状”的X为研究对象直线搜索方法,无约束优化方法,约束优化方法，并参考著名学者的著作《 》记录了一些优化方法及其性质。

2 无约束优化 2.1 最优解存在的充分条件

我们首先考虑没有约束的情况，即\min~f(x)。但在此之前，有一个非常关键的问题，我们什么时候才能找到 f(x) 的最小值？该定理给出了最优解存在的充分条件。

定理：设X为\{R}^n的非空子集，令f:X\\{R}在X的所有点上下半连续（函数值不大于函数极限）。如果 X 是紧的，或者 X 是闭的并且 f 是矫顽的，那么 f 在 X 上的最小值的集合是非空且紧的。

请注意，该定理不需要假设函数是连续的，只需要下半连续。这是因为下半连续性已经可以保证我们在任何可能的极限点处都能达到最小值，并且在趋于极限点时不会出现趋于最小值的邻域函数值，以及对应的函数限制点的值更大。案子。对X的要求保证了可以得到极限点，不会出现在设定的边界上或趋于无穷大。

2.2 最优条件

明确解的存在性后，就可以判断一个解是否为最优解，这是求解最优化问题的前提。如果 f 是可微的，则局部最优的一阶必要条件是 \nabla f(x)=0 ，如果 f 是二阶可微的，则局部最优的二阶必要条件是 \nabla^2f(x) 正半定。请注意，这不是充分条件，当 f 为凸时，一阶必要条件也是充分的。若f为凸函数但不可微，一阶充要条件为0\in\f(x)，即在点x处，水平面为次梯度，其他处的函数值点在水平面之上。

当优化问题有约束时，最优性条件不仅非常有意义，而且非常有趣，看下面的表达式。

2.3 强凸函数的良好性质

如果函数的性质很好，我们可以从当前解中得到最优解的信息。例如，当 f 满足 mI\le\nabla^2f\le MI 时，我们可以得到：

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

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

这意味着可以从当前梯度推断出当前函数值与最优函数值之间的距离，进而可以推断出当前解与最优解之间的距离。

证明：在点 x 处将 f 扩展为 x^*：

f(x^*)=f(x)+\nabla f(x)(x^*-x)+(x^*-x)\nabla^2f(\tilde x)(x^*-x)

根据 mI\le\nabla^2f\le MI ，所以：

\nabla f(x)(x^*-x)+m\|xx^*\|^2\le f(x^*)-f(x)\le \nabla f(x)(x^*- x)+M\|xx^*\|^2

根据二次函数的性质，我们知道：

\min_y \{\nabla^\top (yx)+\frac{\alpha}{2}\|yx\|^2\}=-\frac{1}{2\alpha}\|\nabla\|^ 2

这样就可以得到第一个公式。第二个公式在点 x^* 处将 f 扩展为 x：

f(x)=f(x^*)+(xx^*)\nabla^2f(\波浪号 x)(xx^*)

然后根据mI\le\nabla^2f\le MI得到。

2.3 最速下降法

很多情况下，我们无法直接求解\nabla f(x)=0，此时可以迭代求解。好消息是我们知道了梯度信息，当我们在负梯度方向走适当的距离时，函数的值会下降，我们可能会更接近最优解。梯度下降的最简单形式是：

x_{k+1}=x_k-\ \nabla f(x_k)

其中\是步长，步长的选择很有学问，可以选择一个常数步长、一个衰减步长等。步长也可以通过搜索来确定，比如精确搜索，或者可以减少计算量，可以使用众所周知的规则和规则搜索。一般来说，函数的性质越好，在相同的收敛和收敛速度下，需要的步长越小。

规则介绍到这里。搜索的目标是不断增加非负整数 m直线搜索方法,无约束优化方法,约束优化方法，并找到第一个 m 使得以下公式成立：

f(x_k+\beta^ms d_k)\le f(x_k) +\sigma \beta^ms\nabla f(x_k)^\top d_k

其中 \sigma 和 \beta 是设置参数，d_k 是搜索方向。当步长很小的时候，基本按照梯度的斜率下降。但是这个公式的含义是不需要这么苛刻，我们设置了\sigma\in(0,1)的“容差因子”。牺牲下坡的坡度，换来更大的步幅。通常，需要对两者进行权衡以实现更快的下降率。

2.4 牛顿法

在梯度下降法中，很难不问一个问题，沿着负梯度方向是不是下降最快的方向是真的吗？如果我们知道二阶信息 \nabla^2f ，我们可以更快地迭代吗？牛顿法通过\nabla^2f对负梯度方向-\nabla f进行修正，从而达到更快的收敛速度。它的迭代方法是：

x_{k+1}=x_k-\ (\nabla^2 f(x_k))^{-1}\nabla f(x_k)

当函数是二次的时，这个公式的作用是将负梯度方向修正为指向最优解的方向。因此，如果一个函数比较接近二次形式，例如二阶连续可微函数接近局部最优解时，收敛速度会大大加快。

牛顿法虽然收敛速度更快，但其计算成本却不容忽视。当决策变量的维数较高时，矩阵的计算和求逆需要大量的计算，甚至计算起来过于复杂。此时可以使用牛顿法的变体，例如：

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

x_{k+1}=x_k-\ (\nabla^2 f(x_0))^{-1}\nabla f(x_k)

或通过其他方式估计：

x_{k+1}=x_k-\ [\text{ of }(\nabla^2 f(x_0))^{-1}]\nabla f(x_k)

2.4 共轭梯度法

与最速下降法不同的是，共轭梯度法的思想不是每次都往“最快”的方向走，而是找到一系列共轭方向，依次沿着这些方向移动。共轭方向是经过精心选择的，因此对于二次函数，沿着这些方向依次精确搜索后可以获得最优解。也就是说，每一次优化的方向都被“优化”过了，并且在这个方向上达到了最优解。共轭梯度法虽然是从二次形式推导出来的，但在非二次函数上也能有很好的收敛性能。

共轭方向 d_i 需要满足以下“Q-共轭”性质：

d_i^\top Qd_j=0

从这个公式可以很容易地推导出共轭方向一定是线性无关的，所以\{R}^n有n个共轭方向。

如果对于二次形式 f(x)=x^\top Qx+b^\top x ，每一步搜索都是精确搜索：

\frac{\ (x_{k+1}+\alpha d_i)}{\ \alpha}=0

则有 x_{k+1}={\arg\min}_{x\in x_0 + \bm{\{span}}\{d_0,\cdots,d_k\}}f(x) ，即每一个都是沿着新的共轭方向优化的，不会影响已经优化的方向。

共轭方向 d_k 可以使用正交化从梯度 g_k 序列生成：

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+\ d_{k-1} , \=\frac{g_k^\top g_k}{g_{k-1}^\top g_{k-1}}

3 约束优化

通常我们遇到的优化问题都是有约束的，那么接下来，我们将在无约束优化的基础上，讨论如何在约束下进行优化。

3.1 梯度投影法

最简单的想法是仍然按照无约束优化的算法进行优化，一旦当前解决了可行集，就将其取回来。这种方法称为梯度投影法，即以下两步交替进行：

\波浪号 x_{k+1}=x_k-\d_k

x_{k+1}=\arg\min_{y\in C}\|xy\|

这要求 C 是一个凸集，在这种情况下，投影是存在的（根据定理）并且是唯一的（根据矛盾和凸集的定义）。

3.2 条件梯度法

与先考虑最优性迭代的梯度投影法不同，条件梯度法的思想首先考虑约束。条件梯度法的思想是找到可行方向，然后在可行方向上进行优化，在可行集中找到沿可行方向最远的点。以负梯度方向为可行方向（如果负梯度方向不可行，则已经是局部最优解），构造如下线性目标函数的子优化问题：

\begin{align} \min_x&~~~\nabla f(x_k)^\top(x-x_k)\\ \text{st} &~~~x\in C \end{align}

如果约束比较简单（比如线性约束），那么次优化问题就会很容易解决（线性规划），这也是条件梯度法的好处之一。

3.3 拉格朗日橙色定理

对于函数 f,h 连续可微且优化问题具有等式约束 h(x)=0 的情况，拉格朗日乘子定理给出了最优解的必要条件。

拉格朗日乘子定理：若x^*是h(x)=0条件下可微函数f的局部极小点，假设约束梯度\nabla h_1(x^*),\cdots,\nabla h_m( x^*) 是线性独立的（正则性），则有一个唯一的拉格朗日乘数 \^* 使得：

\nabla f(x^*)+\sum_{i=1}^m\^* \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\^* \nabla^2 h_i(x^*)\ge0

该定理可以用惩罚法证明，证明过程中可以得到\^*的显式表达式：

\^*=-\left(\nabla h(x^*)^\top \nabla h(x^*)\right)^{-1}\nabla h(x^*)^\top\nabla f( x^*)

反演部分解释了为什么需要规律性才能获得唯一的拉格朗日乘数。

3.4 KKT最优条件

KKT条件推广了拉格朗日方法，对于函数f、h、g连续可微且优化问题有等式约束h(x)=0和不等式约束g(x)\le0的情况，最优解为给定的。解的必要条件。

-Kuhn- 最优性的必要条件：如果x^*是函数f在h(x)=0,g(x)\le0条件下的局部极小点，假设约束的梯度\nabla h_1( x^* ),\cdots,\nabla h_m(x^*),\nabla g_i(x^*), i\in\{i|g_i(x^*)=0\} 线性独立（正则性），则有一个独特的拉格朗日乘数 \^*,\mu^* 使得：

\nabla f(x^*) +\sum_{i=1}^m\^* \nabla h_i(x^*) +\sum_{i=1}^r\mu_i^* \nabla g_i(x^* ) =0

其中\mu_i^*\ge0。对于 g_i(x^*) ，\mu_i^*=0 。

3.5 FJ最优条件

FJ条件推广了KKT条件，对于非常规情况，给出了最优解的必要条件。

Fritz John最优性的必要条件：如果x^*是函数f在h(x)=0,g(x)\le0条件下的局部极小点，则有标量\mu_0^*和乘数\^ *,\mu^* 使得：

\mu_0^*\nabla f(x^*) +\sum_{i=1}^m\^* \nabla h_i(x^*) +\sum_{i=1}^r\mu_i^* \nabla g_i (x^*) =0

其中\mu_i^*\ge0。对于 g_i(x^*) ，\mu_i^*=0 。\mu_0^*,\^*,\mu^* 并非全为零。

FJ条件更一般，我们可以通过函数的性质从FJ条件中推导出KKT条件，从而得到更强的必要条件。

3.6 从 FJ 条件到 KKT 条件

以下情况可以使FJ条件强化为KKT条件：

h是线性函数，g是凹函数。-条件：\nabla h_i(x^*)是线性无关的，存在一个向量d使得d^\top\nabla h_i(x^*)=0，对于g_i(x^*)=0有d ^\top\ nabla g_i(x^*) 。条件：h是线性函数，g是凸函数，存在x，g_i(x)，g_i(x^*)=0。