最优化方法 - 导论、凸集、最佳逼近

最优化方法研究导论

基本概念

最优化方法通俗地来说就是研究如下类型优化问题的学科：

$$\begin{array}{rl}& \max f(x)\\ & s.t.x\in \mathcal{X}\end{array}$$

其中 $s.t.$ 表示 subject to，上式包含了我们研究最优化的三个对象：

• 决策变量：指决策者为实现规划目标的方案，措施，是问题中要确定的未知量.
• 目标函数：指问题要达到的目的要求，表示为决策变量的函数.
• 约束条件：指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式.

这里面 $\mathcal{X}$ 又叫可行域，一般而言可以表示成如下的形式：

$$\mathcal{X}=\left\{x:c_i(x)=0,i=1,2,\cdots ,m;c_i(x)⩽0,i=m+1,\cdots ,n\right\}$$

也就是说，约束条件可以表述为 $c_i(x)=0$ 或 $c_i(x)⩽0$ 的形式.

约束条件的更改

运筹学当中，我们曾学到线性规划的标准形式，其约束条件可以都表示为 $c_i(x)=b$ ，我们是否也能用增加松弛变量的方式来进行变换？

在最优化方法中，我们实际上遇到的不止会是运筹学当中遇到的线性规划问题，这些优化问题往往会需要函数的可微性，但是松弛变量会影响可微性.

为什么呢？我们不妨来看一种增加松弛变量的方法，考虑 $x_1$ 无约束，那么我们的增加松弛变量的方法就是：

$$x_1=x_1^{\prime }-x_1^{\prime \prime }=\frac{|x_1|+x_1}{2}-\frac{|x_1|-x_1}{2}$$

但是绝对值是不可微的，这就会出现问题. $\square$

优化问题类型

定义：无约束优化问题、有约束优化问题

如果优化问题当中没有约束条件，则称为无约束优化问题，否则称为有约束优化问题.

在之后我们将会逐个讨论.

可行解、最优解

定义：可行域、可行点

记

$$F=\left\{x\in {\mathbb{R}}^n\mid c_i(x)=0,i=1,\cdots ,m;c_i(x)⩾0,i=m+1,\cdots ,p\right\}$$

称 $F$ 为问题的可行域，$F$ 中任意一点称为可行点.

定义：整体最优解，严格整体最优解

一个点 $x^{\ast }\in F$ 称为问题的整体最优解，若

$$f(x^{\ast })⩽f(x),\forall x\in F\wedge x\ne x^{\ast }$$

若不等式严格成立，则称 $x^{\ast }$ 为严格整体最优解. 若对 $x^{\ast }$ 的一个邻域 $N(x^{\ast })=\left\{x\mid \Vert x-x^{\ast }\Vert ⩽\delta \right\}$ 有

$$f(x^{\ast })⩽f(x),\forall x\in F\cap N(x^{\ast })\wedge x\ne x^{\ast }$$

则称 $x^{\ast }$ 为问题的局部最优解.

最优解将会是我们之后求解的目标.

凸集及其性质

凸集和凸包

定义：凸集

称一个集合 $D\subset {\mathbb{R}}^n$ 为凸集，如果对于任意的 $\lambda \in (0,1)$ 以及 $x,y\in D$ ，都有

$$\lambda x+(1-\lambda )y\in D$$

这个概念在数学分析当中就已经阐述了，但是在最优化理论当中，凸集的性质是相当好的，我们之后的理论将会围绕凸集和凸函数进行.

定义：凸组合

设 $x^1,\cdots ,x^m$ 是 ${\mathbb{R}}^n$ 中的 $m$ 个点，称 $\sum _{i=1}^m{\lambda }_i{x}^i$ 为 $x^1,\cdots ,x^m$ 的凸组合，这里 ${\lambda }_i⩾0$ ，且 $\sum _{i=1}^m{\lambda }_i=1$ .

凸组合是线段的一个推广，给定 $m$ 个点，其凸组合的全体构成的集合就是这些点构成的凸包（见下文）.

定义：凸包

设 $D\subset {\mathbb{R}}^n$ ，称下列集合

$$H(D)=\left\{y\mid y=\sum _{i=1}^m{\lambda }_i{y}_i,\sum _{i=1}^m{\lambda }_i=1,y_i\in D,i=1,2,\cdots ,m\right\}$$

即 $D$ 中任意有限个点的凸组合全体为 $D$ 的凸包.

凸包可以理解为“凸化”，它将一个非凸的集合变为凸集，因此它有一些比较好的性质.

注意其中的一个问题，至少从定义看来，我们只能写成某 $k$ 个向量的凸组合，而不是可以写成任意长的凸组合.

定理

设 $D\subset {\mathbb{R}}^n$ 是凸集，则 $D$ 中任意 $m$ 个点的凸组合仍属于 $D$ .

证明： 考虑归纳法，当 $m=2$ 时，根据凸集的定义可知结论成立，假设 $m=k$ 时结论成立，那么当 $m=k+1$ 时：

$$\begin{array}{rl}x& =\sum _{i=1}^{k+1}{\lambda }_i{x}^i\\ & =(1-{\lambda }_{k+1})\sum _{i=1}^k\frac{{\lambda }_i}{1-{\lambda }_{k+1}}{x}^i+{\lambda }_{k+1}{x}^{k+1}\end{array}$$

其中 $\sum _{i=1}^{k+1}{\lambda }_i=1$，对 $\sum _{i=1}^k\frac{{\lambda }_i}{1-{\lambda }_{k+1}}{x}^i$ 根据归纳假设可知其为 $x^{\prime }\in D$ ，同时最终可得 $x=(1-{\lambda }_{k+1})x^{\prime }+{\lambda }_{k+1}{x}^{k+1}$ 为两点的凸组合. 因此结论成立. $\square$

定理

设 $D\subset {\mathbb{R}}^n$ ，则对 $H(D)$ 中任意点 $x$ ，它一定可以表示为 $D$ 中 $n+1$ 个点的凸组合.

证明： 对于 $x\in H(D)$ ，我们可以将其表示为 $k$ 个向量的凸组合：

$$x=\sum _{i=1}^k{\lambda }_i{x}^i$$

现在讨论 $k$ 和 $n+1$ 的关系. 注意 $D$ 并没有默认为凸集，首先讨论 $k⩽n+1$ ，这个情况得到结论是显然的，因为可以把系数分拆得到更多的向量，当 $k>n+1$ 时，我们考虑如下所示的向量组：

$$x^2-x^1,x^3-x^1,\cdots ,x^k-x^1$$

共 $>n$ 个向量，但 ${\mathbb{R}}^n$ 的维数只有 $n$ ，上述向量是线性相关的，因此我们可以取其极大无关组，从而将 $x^1$ 用更少的凸组合方式表示出来，进而将向量数减少到 $n+1$ 及以下. $\square$

构造性证明

另一个构造性证明请参考教材.

保凸运算

下列集合运算是保凸的：

1. 交集：两个凸集的交还是凸集.
2. 仿射函数：经过线性变换之后（伸缩、平移、旋转），凸集还是凸集.
3. 线性分式函数或透视函数.

定义：透视函数

透视函数的定义： $P:{\mathbb{R}}^{n+1}\to {\mathbb{R}}^n,P(z,t)=\frac{z}{t}$ 其中定义域为 $\mathrm{dom}(P)={\mathbb{R}}^n\times {\mathbb{R}}_{++}$ 其中 ${\mathbb{R}}_{++}$ 为正实数集.

我们下面证明其保凸性.

定理：透视函数保凸

如果 $C\subset \mathrm{dom}(P)$ 是凸集，则其透视函数图像 $P(C)=\left\{P(x)\mid x\in C\right\}$ 也是凸集.

凸集的分离和支撑

简单回顾

这里我们略去关于邻域、闭包、内部、边界的讨论，这些都在以前说明过. 只强调一下符号：

• $\mathrm{cl}(D)$ 为闭包；
• $\mathrm{int}(D)$ 为内部；
• $\partial D$ 为边界；
• ${\mathbb{R}}^n\setminus D$ 为补集.

分离超平面定理

定义：分离超平面

设 $D_1,D_2\subset {\mathbb{R}}^n$ 为两个非空凸集，若存在非零向量 $\alpha \in {\mathbb{R}}^n$ 和实数 $\beta$ ，使得

$$\begin{array}{rl}& D_1\subset H^{+}=\left\{x\in {\mathbb{R}}^n\mid {\alpha }^{\mathrm{T}}x⩾\beta \right\}\\ & D_2\subset H^{-}=\left\{x\in {\mathbb{R}}^n\mid {\alpha }^{\mathrm{T}}x⩽\beta \right\}\end{array}$$

则称超平面 $H=\left\{x\in {\mathbb{R}}^n\mid {\alpha }^{\mathrm{T}}x=\beta \right\}$ 分离了 $D_1$ 和 $D_2$ . 如果将上述的不等号改为严格不等号，则称 $H$ 严格分离了 $D_1$ 和 $D_2$ .

这里我们实际上要说明的是：这个超平面是否一定存在？这个结论是肯定的，换句话说：没有交集的两个凸集，可以被一个超平面完全分隔开.

最佳逼近定理

闭凸集的最佳逼近

定理：最佳逼近定理 （凸集）

设 $D\subset {\mathbb{R}}^n$ 是非空闭凸集，$y\in {\mathbb{R}}^n$ 但 $y\notin D$ ，则 (1) 存在唯一的点 $\overline{x}\in D$ 使得

$$\Vert \overline{x}-y{\Vert }_2=\inf \left\{\Vert x-y{\Vert }_2,x\in D\right\}$$

(2) $\overline{x}\in D$ 是 $D$ 中离 $y$ 最近的点的充要条件是：

$$(x-\overline{x}{)}^{\mathrm{T}}(\overline{x}-y)⩾0,\forall x\in D$$

证明：

(1) 存在性：由于 $D$ 有可能无界，那么对于连续函数

$$f(x)=\Vert x-y{\Vert }_2$$

无法使用最值定理，因此我们考虑以 $y$ 为球心，任取 $z\in D$ ，以 $r=\Vert y-z{\Vert }_2$ 为半径作闭球，设为 $B(y;r)$ ，此时 $B(y;r)\cap D$ 是闭凸集，因此在 $B(y;r)\cap D$ 上应用最值定理即可找到 $f(x)$ 的最小值.

而对于 $D\setminus B(y;r)$ 的部分，这部分的元素和 $y$ 的距离至少都有 $r$ ，因此无需在其中寻找最小值.

唯一性： 假设存在另外一个最佳逼近 $\tilde{x}$ ，那么考虑

$$\Vert \frac{\overline{x}+\tilde{x}}{2}-y\Vert ⩽\frac{1}{2}\Vert \overline{x}-y\Vert +\frac{1}{2}\Vert \tilde{x}-y\Vert$$

根据最佳逼近的定义，上述不等号只能取等，而三角不等式的取等条件就是 $\overline{x}-y$ 和 $\tilde{x}-y$ 线性相关，即

$$(\overline{x}-y)=\alpha (\tilde{x}-y)$$

两侧取范数即可得到 $\alpha =1$ 或 $-1$ ，但 $-1$ 时，$y=\frac{\tilde{x}+\overline{x}}{2}\in D$ ，出现矛盾. 因此只有 $\alpha =1$ ，即 $\overline{x}=\tilde{x}$ 成立. $\square$

(2) 充分性：考虑

$$\begin{array}{rl}\Vert x-y{\Vert }^2& =\Vert (x-\overline{x})+(\overline{x}-y){\Vert }^2\\ & =[(x-\overline{x}{)}^{\mathrm{T}}+(\overline{x}-y{)}^{\mathrm{T}}][(x-\overline{x})+(\overline{x}-y)]\\ & =\Vert x-\overline{x}{\Vert }^2+\Vert \overline{x}-y{\Vert }^2+2(x-\overline{x}{)}^{\mathrm{T}}(\overline{x}-y)\\ & ⩾\Vert \overline{x}-y{\Vert }^2\end{array}$$

这就说明了 $\overline{x}$ 是离 $y$ 最近的点.

必要性：对于任意给定的 $x\in D$ 以及 $\lambda \in (0,1)$ ，有

$$\overline{x}+\lambda (x-\overline{x})=(1-\lambda )\overline{x}+\lambda x\in D$$

所以由最佳逼近的性质有：

$$\begin{array}{rl}\Vert \overline{x}-y{\Vert }_2^2& ⩽\Vert \overline{x}+\lambda (x-\overline{x})-y{\Vert }_2^2\\ & =\Vert \overline{x}-y{\Vert }_2^2+2\lambda (\overline{x}-y{)}^{\mathrm{T}}(x-\overline{x})+{\lambda }^2\Vert x-\overline{x}{\Vert }_2^2\end{array}$$

那么有

$$2(\overline{x}-y{)}^{\mathrm{T}}(x-\overline{x})+\lambda \Vert x-\overline{x}{\Vert }_2^2⩾0$$

令 $\lambda \to 0^{+}$ 可得结论. $\square$