新闻资讯

服务热线400-123-4567

行业资讯

最优化方法1——最优化问题的解存在唯一性

作者：佚名发布时间：2024-06-10 05:23:08点击：

最优化问题的分类是多样的。按照是否存在约束条件，最优化问题可以分为无约束优化问题和约束优化问题两大类型。
无约束优化在生活中是一种比较常见的优化问题，也是我们接触的比较早的问题。一般的来说，无约束优化问题可以被看作求一个函数的极值问题，即

$\\min_{x}f(x),\\quad \ ext{s.t.}\\,x\\in\\mathcal{X},\\qquad\\qquad(1.1)\\\\$

其中， $x\\in\\mathcal{X}$ 被称为决策变量， $f(x)\\in \\mathbb{R}$ 被称为目标函数。使得 $f(x)$ 达到极小的 $x$ 被称为上述优化问题的解，记为 $x^*$ ，而 $f(x^*)$ 则是该优化问题的最优值。该问题有一种等价的写法：

$x\\in\\arg\\min f(x)$

而如果以上问题受到了某些条件的限制，那么该问题便成了一个约束优化问题，即

$\\begin{aligned}&\\min f(x)\\\\ &\ ext{s.t.}\\quad \\begin{aligned}&c_i(x)=0,\\quad i\\in\\mathcal{E},\\\\ &c_i(x)\\geq0,\\quad i\\in\\mathcal{I}. \\end{aligned}\\end{aligned}\\qquad\\qquad(1.2)\\\\$

这里， $\ ext{s.t.}$ 是"subject to"的缩写，意为“满足于”，一般的，在 $\ ext{s.t.}$ 之后的表达式被称为该约束优化问题的约束条件。 $c_i(x)\\in\\mathbb{R}(i\\in\\mathcal{E}\\cup\\mathcal{I})$ 被称为约束函数，其中 $c_i(x)=0(i\\in\\mathcal{E})$ 是等式约束， $c_i(x)\\geq0(i\\in\\mathcal{I})$ 是不等式约束， $\\mathcal{E}$ 和 $\\mathcal{I}$ 在一起被称为约束的指标集合。

以上的两种优化问题是最基本的两种问题，一般来说所有优化问题均可以被变换为这两种形式。特别的，如果是求极大值问题 $\\max f(x)$ ，我们可以取目标函数的相反数，使其变为求极小值问题，即 $\\min -f(x)$ 。

本节开始，我们首先讨论无约束优化问题。

一般的来说，对于无约束优化问题，它的最优解可以分为全局最优解与局部最优解。

Def 1.1： 在以下无约束优化问题中：
$\\min f(x),\\quad \ ext{s.t.}\\,x\\in\\mathcal{X},\\\\$
(1). 若对于任意的 $x\\in\\mathbb{R}^n$ ， $f(x)\\geq f(x^*)$ ，则称 $x^*$ 为该问题的全局最优解；如果 $f(x)>f(x^*)$ ，则称 $x^*$ 为该问题的严格全局最优解。
(2). 对于 $x^*\\in\\mathbb{R}^n$ ，若存在 $\\varepsilon>0$ ，使得对于任意 $x\\in\\mathbb{R}^n$ ，当 $\\|x-x^*\\|<\\varepsilon$ 时，有 $f(x)\\geq f(x^*)$ ，则称 $x^*$ 为该问题的局部最优解；同理，如果 $f(x)>f(x^*)$ ，则称 $x^*$ 为该问题的严格局部最优解。

如以上图中所示， $A$ 和 $B$ 两点为曲线的严格全局最优解，而 $C$ 和 $D$ 两点则为局部最优解。

在实际问题中，全局最优解往往不存在或者难以达到。因此往往局部最优解是我们所希望的，本专题中介绍的所有算法，如不特殊说明，则都是求局部最优解的算法。

首先一个问题是我们如何保证最优解的存在性呢？考虑一般的无约束优化问题，如果目标函数是连续的，且定义域是紧的，那么我们很容易得出最优解的存在性。但是如果以上两个条件中有其一不成立，都会导致目标函数在定义域上的不可微性质，这时候我们无法直接判断其解的存在性。

我们需要一个工具把以上的集中情况全部集中起来讨论。考虑到在数学分析中，我们学过Weierstrass定理，其保证了紧集上的连续函数的最值点的存在性。下面我们将这一定理进行推广。

我们需要一些工具来辅助说明。
Def 1.2： 令 $\\bar{\\mathbb{R}}:=\\mathbb{R}\\cup\\{\\pm\\infty\\}$ 为广义实数空间，则映射 $f:\\mathbb{R}^n\ o\\bar{\\mathbb{R}}$ 为广义实值函数。
Def 1.3： 给定广义实值函数 $f$ 和非空集合 $\\mathcal{X}$ 。如果存在 $x\\in\\mathcal{X}$ 使得 $f(x)<+\\infty$ ，且对于任意的 $x\\in\\mathbb{X}$ ，都有 $f(x)>-\\infty$ ，则称函数关于集合 $\\mathcal{X}$ 是适当的。
Def 1.4： 对于一个广义实值函数 $f:\\mathbb{R}^n\ o\\bar{\\mathbb{R}}$ ，对于任意的 $x\\in\\mathbb{R}^n$ ，有
$\\liminf_{y\ o x}f(y)\\geq f(x),\\\\$
则称 $f$ 为下半连续函数。
Def 1.5： 对于一个广义实值函数 $f:\\mathbb{R}^n\ o\\bar{\\mathbb{R}}$ ，
$C_\\alpha:=\\{x|f(x)\\leq \\alpha\\},\\\\$
是 $f$ 的一个 $\\alpha$ -下水平集。而
$\\mathbf{epi}:=\\{(x,t)\\in\\mathbb{R}^{n+1}|f(x)\\leq t\\},\\\\$
称为 $f$ 的上镜图。

实际上，下水平集就是 $f$ 的定义域中所有函数值不大于 $\\alpha$ 的点的集合。而上镜图则反映了函数 $f$ 和 $f$ 的上方区域。下面是一个函数的上镜图。

特别的，如果上镜图 $\\mathbf{epi}$ 是闭集，则称对应的 $f$ 为闭函数。

Lemma 1.6： 对于一个广义实值函数 $f$ ，以下命题等价：
(1). $f$ 是下半连续的；
(2). $f$ 的任意 $\\alpha$ -下水平集都是闭集；
(3). $f$ 是闭函数。

Proof： 设(1)成立，令 $(x_k,y_k)\\in\\mathbf{epi}f$ 且 $\\displaystyle\\lim_{k\ o\\infty}(x_k,y_k)=(\\bar{x},\\bar{y})$ ，根据下半连续性，有

$f(\\bar{x})\\leq \\liminf_{k\ o\\infty}f(x_k)\\leq \\lim_{k\ o\\infty}y_k=\\bar{y},\\\\$

这等价于 $(\\bar{x},\\bar{y})\\in\\mathbf{epi}f$ ，即上镜图是闭集。即(3)成立。

再设(3)成立。取 $\\alpha$ 下水平集中的元素 $x_k\ o\\bar{x}$ ，注意到 $(x_k,\\alpha)\\in\\mathbf{epi}f$ 且 $(x_k,\\alpha)\ o(\\bar{x},\\alpha)$ ，由 $\\mathbf{epi}f$ 为闭集可知 $(\\bar{x},\\alpha)\\in\\mathbf{epi}f$ ，即 $f(\\bar{x})\\leq \\alpha$ ，从而(2)成立。

最后设(2)成立，假设存在一个序列 $\\{x_k\\}\ o\\bar{x}$ 但 $\\displaystyle f(\\bar{x})>\\liminf_{k\ o\\infty}f(x_k)$ ，取 $t$ 使得

$f(\\bar{x})>t>\\liminf_{k\ o\\infty}f(x_k),\\\\$

根据下极限的定义， $\\{x_k|f(x_k)\\leq t\\}$ 中必定包含无穷个 $x_k$ ，假设 $\\{x_k\\}$ 中存在子列 $\\{x_{k_l}\\}$ 使得 $f(x_{k_l})\\leq t$ 且 $\\displaystyle\\lim_{l\ o\\infty}x_{k_l}=\\bar{x}$ ，这与 $t$ -下水平集为闭集矛盾，因此(1)成立。 $\\blacksquare$

根据以上一系列的工具，我们可以得到以下的推广版本的Weierstrass定理。

Thm 1.7：(Weierstrass定理) 考虑一个合适的闭的函数 $f:\\mathcal{X}\ o(-\\infty,+\\infty]$ ，如果函数满足以下三个条件中的任意一个，则问题 $(1.1)$ 的最小值点集 $\\left\\{x\\in\\mathcal{X}|f(x)\\leq f(y),\\forall y\\in\\mathcal{X}\\right\\}$ 是非空的紧集。
(1).定义域 $\\mathbf{dom}f:=\\left\\{x\\in\\mathcal{X}:f(x)<+\\infty\\right\\}$ 是有界的；
(2).存在一个常数 $\\bar{\\gamma}$ 使得下水平集：
$C_{\\bar{\\gamma}}:=\\left\\{x\\in\\mathcal{X}:f(x)\\leq \\bar{\\gamma}\\right\\},\\\\$
非空有界。
(3).对于任意满足范数趋于无穷的点列 $\\{x^k\\}\\subset\\mathcal{X}$ ，即 $\\|x^k\\|\ o+\\infty$ ，有
$\\lim_{k\ o\\infty}f(x^k)=+\\infty,\\\\$

Proof： 假设(1)成立，则 $\\mathrm{dom}f$ 是有界的。由于存在 $x_0\\in\\mathcal{X}$ 使得 $f(x_0)<+\\infty$ ，令 $\\bar{\\gamma}=f(x_0)$ ，则下水平集 $C_{\\bar{\\gamma}}$ 非空有界。
假设(3)成立，假设 $C_{\\bar{\\gamma}}$ 无界，则存在点列 $\\{x^k\\}\\subset C_{\\bar{\\gamma}}$ 满足 $\\displaystyle \\lim_{k\ o\\infty}\\|x^k\\|=+\\infty$ ，但根据(3)，有 $\\displaystyle \\lim_{k\ o\\infty}f(x^k)=+\\infty$ ，这与 $f(x)\\leq \\bar{\\gamma}$ 矛盾，因此 $C_{\\bar{\\gamma}}$ 非空有界。
这样，条件(1)和(3)都可以转化为条件(2)。下面证明条件(2)成立即可。
采用反证法，假设 $\\displaystyle t:=\\inf_{x\\in\\mathcal{X}}f(x)=-\\infty$ ，则存在点列 $\\{x^k\\}_{k=1}^\\infty\\subset C_{\\bar{\\gamma}}$ ，使得 $\\displaystyle\\lim_{k\ o\\infty}f(x^k)=t=-\\infty$ 。因为 $C_{\\bar{\\gamma}}$ 的有界性，点列必定存在聚点，记为 $x^*$ 。由于 $(x^*,t)\\in \\mathbf{epi}f$ ，且上镜图是闭的，这与函数的适当性矛盾，从而 $t>-\\infty$ 。
由于 $f(x^*)\\leq t$ ，且 $t$ 是下确界，故必定有 $f(x^*)=t$ ，即下确界可以取到，根据引理Lemma 1.6和 $C_{\\bar{\\gamma}}$ 的有界性，可知最小值点是紧的。 $\\blacksquare$

定理Thm 1.7中的三个条件本质上都是再保证 $f$ 的最小值无法再无穷远处取得，从而我们可以只在一个有界的下水平集中考虑 $f(x)$ 的最小值，且不要求函数 $f$ 的连续性。

我们可以举例说明以上定理的适用性。对于函数 $f(x)=x$ 和 $g(x)=e^x$ ，定义域均为 $x\\in\\mathcal{X}$ ，前者满足定理Thm 1.7中的条件(3)，因此存在最小值，而后者不满足以上三个条件中的任意一个，从而最小值不存在。

上述Weierstrass定理只保证了最优解的存在性，但无法确定是否是唯一的。最优化问题解的唯一性在理论分析和算法比较中扮演着重要角色．比如，假设问题(1.1)的解是唯一存在的，记为 $x^*$ ，那么不同的算法最终都会收敛到 $x^*$ 。此时，我们通过比较不同算法的收敛速度来判断算法好坏是非常合理的。但是如果问题(1.1)存在多个最优值点，不同的算法收敛到的最优值点可能不同，那么这些算法收敛速度的比较就失去了参考价值。

我们考虑函数是强拟凸的情况。

Def 1.8： 给定凸集 $\\mathcal{X}$ 和函数 $f:\\mathcal{X}\ o(-\\infty,+\\infty]$ ，如果对于任意的 $x\ eq y$ 和 $\\lambda\\in(0,1)$ ，有
$f(\\lambda x+(1-\\lambda)y)<\\max\\{f(x),f(y)\\},\\\\$
则称函数 $f$ 是强拟凸的。

强拟凸函数的几何意义是定义域内任何两点之间线段上的函数值不会大于两个端点处函数值的最大值，一般来说，强拟凸函数不一定是凸函数，但其任意一个下水平集都是凸集，并可以包含一部分性质较好的非凸函数。任意强凸函数均为强拟凸的，但凸函数并不一定是强拟凸的。

下面是一个强拟凸函数的示意图。

Thm 1.9： 对于问题(1.1)，设 $\\mathcal{X}$ 是 $\\mathbb{R}$ 的一个非空，紧凸集，如果 $f:\\mathcal{X}\ o(-\\infty,+\\infty]$ 是适当，闭且强拟凸的函数，则存在唯一的 $x^*$ 满足
$f(x^*)<f(x),\\quad \\forall x\\in\\mathcal{X}\\backslash\\{x^*\\}.\\\\$

Proof: 根据Weierstrass定理，问题(1.1)至少存在一个全局最优解，假设还存在另外一个全局最优解 $y^*$ ，则 $f(x^*)=f(y^*)$ 。由强拟凸函数的定义，对于任意的 $\\lambda$ ，

$f(\\lambda x^*+(1-\\lambda)y^*)<\\max\\{f(x^*),f(y^*)\\}=f(x^*),\\\\$

这与 $x^*$ 的全局最优性矛盾。 $\\blacksquare$

如果能将抽象的优化问题化为直观的图像，这是我们所期待的。一般的来说，对于一维问题，这是容易的。三维以上的问题可能无法实现，而对于二维问题，我们需要通过平面图的方式对其进行呈现。

由于二维问题的图像是立体的，我们需要借助等高线对其进行描述。所谓等高线，指的是，函数图像上函数值恒等于一个常数的所有点的集合，根据常数的不同，我们可以得到一簇等高线族。

例如，考虑以下函数：

$f(x_1,x_2)=100(x_2-x_1^2)^2+(1-x_1)^2,\\\\$

这个函数叫做Rosenbrock函数，是一个非常著名的检验函数，其极小值点为 $(1,1)$ 。
下图给出了这个函数的图像和等高线描述，其中黑点表示函数的极小点，等高线图中的颜色越浅表示函数值越小.该函数等高线的形状犹如一个香蕉，所以我们也称该函数为香蕉函数。

满足 $\ abla f(x)=0$ 的点称为稳定点.由最优性条件可知，函数的极小点一定是稳定点，反之则不一定.那么稳定点有几种类型呢?我们知道极小点和极大点均为稳定点. 以有极大点和有极小点的二维函数 $f(x_1,x_2)$ 为例，它们的共同之处在于函数在极小值与极大值处的切平面平行于 $Ox_1x_2$ 平面。既非极小点又非极大点的稳定点为鞍点。这几种情形的二维函数的图形与等高线见下图。