傲世皇朝动态 NEWS真实、正向、传递价值

当前位置: 首页 > 傲世皇朝动态 > 行业新闻

[优化理论]无约束问题的最优性理论

日期:2024-07-01 13:18:46 / 人气:

这里开一个新坑,因为各种各样的原因我开始学习优化理论(毕竟是AI专业哈哈哈),这一系列的文章就当作一个我学习的笔记,也顺便分享给大家。因为之前对实分析之类的前置知识了解较少,也很多是自学的(我们专业没有开相关的课程),所以可能会有疏漏,欢迎提出。

这篇文章的话主要从最优化问题解的存在性,还有各种情况下的(比如可微的、不可微的、复合的、非光滑非凸的这些)问题的最优性条件进行讨论,主要是在无约束的条件下。阅读这篇文章之前建议有高等数学基础和一点点的实分析基础。

考虑一个优化的问题:

\緻set{x\\in R^n}{\\min}f(x)\\\\ \	ext{s.t.}\\quad x\\in \\chi \\\\ 其中 \\chi\\subseteq R^n 是可行集,就是 x 可以取的范围。

我们通过高等数学里面的Weierstrass定理可以知道定义在紧集上面的连续函数是一定存在最大(最小)值点的,但我们在机器学习里面要优化的函数不一定是连续的,而且定义域也可能不是紧的,所以我们要把这个定理推广一下来使得我们在机器学习里面遇到的优化问题都能运用这个定理。

我们考虑一个适当且闭的函数 f:\\chi\\rightarrow(-\\infty,\\infty] ,然后考虑三个条件:

(1): \	ext{dom}f\\overset{\	ext{def}}{=}\\{x\\in\\chi|f(x)<+\\infty\\} 是有界的。

(2):存在一个常数 \\bar{\\gamma} 使得下水平集

C_{\\bar{\\gamma}}\\overset{\	ext{def}}{=}\\{x\\in\\chi|f(x)\\leq\\bar{\\gamma}\\}\\\\ 是非空且有界的。

(3): f 是强制的,也就是说对 ||x^k||\\rightarrow+\\infty 的点列 \\{x^k\\}\\subset\\chi ,都有

\緻set{k\\rightarrow \\infty}{\\lim}f(x^k)=+\\infty\\\\ 如果三个条件中的任意一个满足了,那么上面说的那个优化问题里面的最小值点集 \\{x\\in\\chi|f(x)\\leq f(y),\\forall y\\in\\chi\\} 是非空并且是紧的。

根据一些直观感觉,我们可以知道这三个条件都是防止最小值点取在无穷远处,所以我们可以只在一个有界的下水平集中考虑这个最小值点(形象一点解释就是,假设一个开口向上的二次函数,考察她的一个下水平集,也就是上面那个定义的集。其中最小值点,也就是谷底,肯定在这个集里面包着,下水平集的那个常数 \\bar{\\gamma} 越低,那下水平集就越小)。并且注意到这里只要求 f(x) 是一个适当且闭的函数,并没有要求连续,所以适用范围更加广泛。

我们举几个例子来看看这个看起来很抽象的定理讲了啥。例如 f(x)=x^2x\\in\\chi=R ,这个函数是个强制函数,满足(3),所以这个全局最优解(也就是最小值)一定存在,这个也可以直观地看出。再例如 f(x)=e^{-x}x\\in\\chi=R ,她不满足任意一个条件,所以显然她不存在全局最优解。而通过函数图像来看,她是不断向下滑的图像,不存在不在无穷远处的最小值。这就是这个定理的意义所在。

这个Weierstrass定理的推广就给出了上面那种优化问题的最优解的存在性条件。

无约束的最优化问题一般可以表示为

\緻set{x\\in R^n}{\\min}f(x)\\\\ 这里没有任何的约束条件。

我们想应该怎么走才能找到一个局部最优点呢,形象地来说就是在函数图像上一直往下走,直到走到不能再往下为止。我们就来具体数学化地表达一下这个往下的概念。我们知道函数上一个点的梯度的方向就是这个点上变化率最大的方向(是向上的,假如能的话)。假设一个矢量 d ,其满足

\
abla f(x)^Td<0\\\\ 我们就把这个矢量 d 称之为下降方向。为什么呢?因为这个梯度是向上的(假如能的话),然后 d 和她的内积小于0的话,说明 d 在梯度方向的投影是相反的,也就是向下的。所以我们可以认为 d 是向下的,也就是下降方向。

我们知道,在局部最优点上,没办法在不往上先走一段的前提下继续往下走了,所以我们自然而然地通过下降这个定义得到一个必要条件,也就是:

假设 f 在全空间 R^n 可微,如果 x^* 是一个局部极小解,那么就有

\
abla f(x^*)=0\\\\ 这就是一阶的必要条件。

在高等数学里面学过,假如一个函数的一阶导数是0,我们还不能判断她是否是最小值点(有可能是最大值点),所以我们要求她的二阶导数,通过这个来具体判断。这里因为是一个 x\\in R^n 的函数,所以事情更不简单了,但本质还是判断二阶项。

我们对函数 f(x)x 附近进行泰勒展开,可以得到

f(x+d)=f(x)+\
abla f(x)^Td+\\frac{1}{2}d^T\
abla^2f(x)d+O(||d||^2)\\\\ 当一阶条件满足时,我们有

f(x+d)=f(x)+\\frac{1}{2}d^T\
abla^2f(x)d+O(||d||^2)\\\\假设 f 在点 x^* 的一个开邻域内是二阶连续可微的,则

我们有二阶必要条件:如果 x^*f 的一个局部极小点,则

\
abla f(x^*)=0,\\quad \
abla^2f(x^*)\\succeq0\\\\ 也有二阶充分条件:如果在点 x^* 处有

\
abla f(x^*)=0, \\quad \
abla^2 f(x^*)\\succ0\\\\ 成立,则 x^*f 的一个局部极小点。

注意一下这里的 \
abla^2f 和物理里面常用的拉普拉斯算子不同,这里表示的是黑塞矩阵(就是偏导组成的矩阵,还带交叉项的),而拉普拉斯算子只是对这个矩阵求迹得到的东西!要注意区分。

这里这个弯弯的符号代表的是这个矩阵的特征值是大于等于0( \\succeq )还是大于0 (\\succ ),就是半正定还是正定的意思啦。

假如那个矩阵(就是黑塞矩阵)的特征值有的大于0有的小于0,则认为这个点是鞍点。

无约束不可微问题的优化问题仍然是

\緻set{x\\in R^n}{\\min}f(x)\\\\ 只是这里 f 是不可微的。

这下麻烦就大了,我们不能老老实实地求梯度去用上面的方法来判断极小值点了。但聪明的数学家们引入了一个次梯度的概念,这样就可以在不可微的点进行操作。

我们先给一个次梯度的定义:

f 为适当的凸函数, x 为定义域 \	ext{dom}f 中的一点,若矢量 g\\in R^n 满足

f(y)\\geq f(x)+g^T(y-x),\\quad\\forall y\\in\	ext{dom}f\\\\ 时则称 gf 在点 x 处的一个次梯度。进一步地,我们称集合

\\partial f(x)=\\{g|g\\in R^n,f(y)\\geq f(x)+g^T(y-x),\\quad\\forall y\\in\	ext{dom}f\\}\\\\fx 上的次微分。

这里有个图能形象表示出次微分在不可微的点上到底长啥样:

次微分,其中红线就属于次微分里面的一个个次梯度

当这个不可微的点是函数 f 的全局极小值时,当且仅当

0\\in\\partial f(x^*)\\\\因为0也包含在里面而且是凸函数,所以整个函数都要在这条水平线以上,所以就是全局最小值了。

有一些奇奇怪怪的问题她的目标函数由两部分 fh 组成,其中 f 是光滑函数(可能非凸), h 为凸函数(可能非光滑),我们就要找她的局部最优解。

我们先把复合优化问题给写出来

\緻set{x\\in R^n}{\\min}\\psi(x)\\overset{\	ext{def}}{=}f(x)+h(x)\\\\ 这个复合优化问题的一阶必要条件就是

-\
abla f(x^*)\\in\\partial h(x^*)\\\\ 其中 \\partial h(x^*) 就是凸函数 h 在点 x^* 处的次梯度集合,也就是次微分。

假如非光滑和非凸一起来,那问题就更大了,因为我们处理非光滑的工具——次微分不能在非凸的函数上面定义,这个怎么办呢?还是老办法,推广一下就好。对于一些适当下半连续的函数仍然是可以定义次微分的,只不过对于普通次微分在凸函数上需要在全局成立的不等关系,在非凸函数中,只要在极限条件下(也就是一个点的足够近的附近)成立就可以了。

我们定义一种新的次微分:Frechet次微分。

f:R^n\\rightarrow(-\\infty,+\\infty] 是适当的下半连续函数。对给定的 x\\in\	ext{dom}f ,满足如下条件的所有矢量 u\\in R^n 的集合为 f 在点 x 处的Frechet次微分

\緻set{y\\rightarrow x}{\\lim}\緻set{y\
eq x}{\\inf}\\frac{f(y)-f(x)-\\langle u,y-x\\rangle }{||y-x||}\\geq0\\\\ 记为 \\hat\\partial f(x) 。当 x\
otin \	ext{dom}f 时,将 \\hat{\\partial}f(x) 定义为空集。

通过Frechet次微分的定义,我们可以对其取极限,得到一个更广泛些的东西,叫极限次微分(也可以简称次微分),定义为

\\partial f(x)=\\{u\\in R^n|\\exists x^k\\rightarrow x,f(x^k)\\rightarrow f(x),u^k\\in\\hat\\partial f(x^k)\\rightarrow u\\}\\\\可以证明,当 f 可微时,极限次微分和Frechet次微分都退化成梯度。

有了这两个东西,我们就可以写出非光滑非凸问题的最优性问题的一阶必要条件:

f 是适当下半连续函数,如果 x^*f(x) 的一个局部极小点,则有

0\\in\\partial f(x^*)\\\\我们还有着更强的条件

0\\in\\hat\\partial f(x^*)\\\\


谢谢阅读~


平台注册入口