最优化问题

Posted on

最优化问题

最优化问题值得四在一定约束条件下，求一个函数最大(小)值的过程；

由于极大极小问题可以互相转换$\min_x f(x)=-\max_x [-f(x)]$,不失一般性，因此我们统一形式化描述如下：
$$
\begin{aligned}
&\min_{x\in \mathcal X}f(x)\
s.t. \quad &c_i(x)=0,1\le i\le m_e\
&c_i(x)\le 0,m_e+1\le i\le m
\end{aligned}
$$
一般而言，我们的目标是找到全局最小值。但是， 有些复杂的目标函数有多个局部最小值点。需要比较这些点处的目标函数值。

梯度下降

驻点的精确求解往往是困难的，在实践中我们往往通过迭代算法找到近似解：从一个初始点$x_0$开始，基于某种规则，从$x_k$移动到下一个点$x_{k+1}$,构造这样一个数列，直到找到使得梯度为0的点为止。
$$
\exists h:\mathbb R\to\mathbb R, x_{k+1}=h(x_k),\lim_{k\to +\infty}\nabla f(x_k)=0
$$
注意Taloy展开如下：
$$
f(x)=f(a)+\frac{f^{\prime}(a)}{1!}(x-a)+\frac{f^{(2)}(a)}{2!}(x-a)^2+\cdots+\frac{f^{(n)}(a)}{n!}(x-a)^n+\frac{f^{(n+1)}(\theta)}{(n+1)!}(x-a)^{(n+1)}
$$
设计$$f(x+\Delta x)-f(x)\approx(\nabla f(x))^\top\Delta x$$

希望做到$f(x+\Delta x)<f(x)$,取$\Delta x=-t\nabla f(x)$可以做到；

其中$t>0$为预先设置的步长，它尽量小；

Steepest Descent

我们希望在第$k$次迭代时，选取合适的步长$t^*$来最优化目标函数$f(x)$;

形式化地说，考虑以下优化问题：
$$
t^*={\arg\min}_{t} f(x_k-t\cdot \nabla f(x_k))
$$
但是这仍然面临着一元函数求驻点的问题；

Stochastic Gradient Decent，SGD

随机梯度下降法考虑对每个样本都进行更新：
$$
\theta_{t+1}=\theta_{t}-\alpha\frac{\partial\mathcal{L}\big(\theta_{t};x^{(t)},y^{(t)}\big)}{\partial\theta}
$$
其中步长$\alpha$也被称为学习率（Learning Rate）,损失函数和学习率的关系如下：

image-20240614071347779

随机梯度下降的伪代码如下：

image-20240614071428586

Mini-batch SGD

小批量随机梯度下降法
$$
\begin{aligned}\theta_{t+1}&=\theta_{t}-\alpha\frac{\partial\mathcal{R}(\theta)}{\partial\theta_{t}}\&=\theta_t-\alpha\frac1N\sum_{i=1}^N\frac{\partial\mathcal{L}\big(\theta_t;x^{(i)},y^{(i)}\big)}{\partial\theta}\end{aligned}
$$

Stopping Criteria

使用一个验证集（Validation Dataset）来测试每一次迭代的参数在验证集上是否最优。如果在验证集上的错误率不再下降，就停止迭代；

这是为了避免算法陷入了局部最优或者鞍点，但我们要找的是全局最小值；

image-20240614071517964

凸优化

凸集：对于$n$维空间中点的集合$C$，若对集合中的任意两点$x$和$y$，以及$0≤θ≤1$，都有$θx+(1-θ)y∈C$，则称该集合为凸集;

image-20240614072716490

凸函数的判定：

  1. 对于$n$维空间中点的集合$C$，如果对集合中的任意两点$x$和$y$，以及实数$0≤θ≤1$，都有$f(θx+(1-θ)y)≤θf(x)+(1-θ)f(y)$;

  2. Hessian矩阵为半正定矩阵
    $$
    \mathbf{H}=\begin{bmatrix}\dfrac{\partial^2f}{\partial x_1^2}&\dfrac{\partial^2f}{\partial x_1\partial x_2}&\cdots&\dfrac{\partial^2f}{\partial x_1:\partial x_n}\\\dfrac{\partial^2f}{\partial x_2:\partial x_1}&\dfrac{\partial^2f}{\partial x_2^2}&\cdots&\dfrac{\partial^2f}{\partial x_2:\partial x_n}\\\vdots&\vdots&\ddots&\vdots\\\dfrac{\partial^2f}{\partial x_n:\partial x_1}&\dfrac{\partial^2f}{\partial x_n:\partial x_2}&\cdots&\dfrac{\partial^2f}{\partial x_n^2}\end{bmatrix}
    $$

简单来说，凸优化问题就是同时满足凸函数+凸集的最优化问题，全局最优解的寻找直接被简化成局部最优解；

常见的约束条件有：

  1. 线性约束：$ {x∈R^n:Ax=b}$
  2. 多面体约束：$ {x∈R^n:Ax≤b}$

注意到，多个凸集的交集还是凸集，因此，优化问题中可能有多个等式和不等式约束，只要每个约束条件定义的可行域是凸集，则同时满足这些约束条件的可行域还是凸集；

严谨地说，如果一个最优化问题的可行域是凸集，并且目标函数是凸函数，则该问题为凸优化问题；

形式化描述如下：
$$
\min f(x), \
s.t. h_i(x)=0,i=1,…,k\
g_i(x)\leq0,i=1,…,l\
其中仿射函数h_i(x)为等式约束，\
凸函数g_i(x)为不等式约束
$$
目前，不少问题都是凸优化问题，比如线性回归，岭回归，支持向量机，Logistic回归；

损失函数

image-20240614073926119

image-20240614073909378