[cvp03] Recession Cone

上周回顾：上周主要研究了凸函数，给出了一些函数层面的性质和证明：

• 凸函数的定义、保持凸性、一阶条件、二阶条件
• 由上镜图研究凸函数；函数凸性与上镜图的凸性等价
• 函数的水平集为闭集、函数下半连续、函数上镜图为闭集。这三个条件互相等价；
• 凸函数一定是连续;

第三周：回收锥

• 2019-11-28 10:00-16:00, 创新岗 XJTU
• 参考教材 《Covex Optimization Theory》
• Teacher: Prof. Li Hui, School of Mathatics and Statistics，XJTU

回收锥

回收锥是凸优化解存在性和凸函数渐进特征分析的基础工具；

回收方向

对于非空凸集$C$, $\forall x \in C$ , 如果对于任意的$\alpha \ge 0$, 这样的一个方向始终满足 $x + \alpha d \in C$. 这样的$d$ 称作凸集$C$的一个回收方向； 所有的回收方向的集合成为集合$C$的回收锥，记做$R_C$

回收锥定理

若$C$为非空闭凸集，有以下结论成立

(a) 回收锥$R_C$ 是闭集和凸的；

(b) 要验证$d \in R_C$ 只需要存在一个向量$x\in C$ ,使得 $x + \alpha d \in C$对于所有$\alpha \ge 0 $成立；（也就是只要在集合中找到一点满足定义则其他点在这个方向上也满足）

Note!: 回收锥定义不要求凸集$C$闭，但回收锥定理一定要求凸集合为闭集；例如可以考虑如下的集合：

$C = {(x_1, x_2)

x_1 \gt 0,\ x_2 \gt 0}\ \cup\ {(0,0)}$

这个集合的回收锥就是他本身，然而他不是闭的；(0,1)是这个集合中除了(0,0)外所有元素的回收方向，不符合第二条；

回收锥性质

（a） $R_C$如果包含一个非零的方向，则$C$一定是无界的。反之亦然；（等价条件；我服了外国人的写作方式了。。。）

（b）$R_C = R_{ir(C)}$

（c） $C_1,\ C_2$是闭凸集， 且交集不是空集，则有$R_{C_1\cap C_2} = R_{C_1} \cap R_{C_2}$

关于（b）的记录下证明（其实是加强对相对内部的理解）

如果$d\in R_{ri(C)}$, 则有$x + \alpha d \in ri(C) \subset C$ 对任意$\alpha \ge 0$恒成立, 则根据回收锥定理自然有$d \in R_C$

如果$d\in R_C $ , 取$x \in ri(C)$, 则有$x + \alpha d \in C$, 根据第一周中的相对内部的线段定理，即一个元素若要在相对内部中，则他与已知相对内部一点的连线均在相对内部中， 则一定有$x+\alpha d \in ri(C)$, 所以$d \in R_{ri(C)}$

线性空间

$$L_C = R_C\ \cap \ -R_C$$

也就是把回收锥中$\alpha \ge 0$的限制去掉，变成$d$与$-d$都是$C$的回收方向；

线性空间有如下性质：若$C$是n维欧式空间$\mathbb{R^n}$的非空凸集；

(a) $L_C$是 $\mathbb{R^n}$的子空间

(b) $L_C = L_{ri(C)}$

凸集分解定理

对于每个包含在线性空间$L_C$中的子空间$S$， 都有 $C = S + (C \cap S^{\bot})$ 图示如下：

凸函数的回收方向

为什么要研究回收锥，是因为回收锥在如下两个方面可以与凸函数的最优性联系起来；回收锥是一个集合的概念，而《凸分析》部分貌似更加侧重从上镜图来分析凸函数，所以使用回收锥来研究凸函数的上镜图；

• $epi(f)$可以得到函数不单调增加的方向
• $epi(f)$的回收锥中的一些趋于水平的方向对应于函数无界的水平集的方向，沿着这些方向函数单调不增；

上镜图回收锥

$f$为闭的凸函数，考虑水平集 $V_{\gamma} = \{x | f(x) \le \gamma \}$ 则有

(a) 所有的水平集$V_{\gamma}$ 都有相同的回收锥，记做$R_f$， 且 $R_f = {d | (d,0) \in R_{epi(f)}}$ (b) 如果某个水平集$V_{\gamma}$是紧的，则f所有的水平集都是紧的；

$R_f$也称为函数$f$的回收锥， 其中的向量为$f$的回收方向

从几何上看，函数的回收锥就是上镜图回收锥在$R^n$ 上的投影。

• 函数沿着其回收方向是非增的； 反之，函数非增的方向一定是回收方向；
• 沿着函数的非回收方向始终是非递增的；

回收函数

$R_{epi(f)}$ 对应的函数称为$f$的回收函数，记做$r_f$ ,

他与函数的方向导数相关联，有如下的性质： $r_f(d)= \sup_{\alpha \gt 0} \frac{f(x + \alpha d) - f(x)}{\alpha} = \lim_{\alpha \rightarrow \infty } \frac{f(x + \alpha d) - f(x)}{\alpha}$

于是回收函数可以描述如下的函数变化性质：

解的存在性

凸优化的全局最优性

若$f$是凸函数，则$f$的所有局部最小值点都是全局最小值点；

Proof:

如果$x^{} $ 是局部最小值点，假设他不是全局最小值，则必然存在$x$使得 $f(x) \lt f(x^{})$

根据凸函数定义有： $f(\theta x^{*}+ (1-\theta) x) \le \theta f(x^{*}) + (1-\theta) f(x) \le f(x^{*})$ 也就是说 $x^$与 $x$连线上的点都比$x^$更优， 这与$x^*$是局部最优的假设矛盾，所以他不是全局最优的假设不成立。

最优解集合

设$X^*$ 为函数$f$上的最小值点集合，形式 $X^* = \bigcap_{k=0}^{\infty} V_{\gamma_k}$

其中标量序列 ${\gamma_k} \rightarrow \inf_{x\in X}f(x)$, 这里的${V_k}$为嵌套集合序列 （就是元素为集合的序列，且满足嵌套的性质：）

$$V_k \subseteq V_{k-1} ......\subseteq V_0$$

则有

$X^*$非空 $\Longrightarrow$ $f$ 存在最优解

Weierstrass 定理（连续函数在紧集上可以达到最小值） $\Longrightarrow$ $X^*$ 有界

最优解集的非空紧性

定理 ： 如果$f$ 的水平集是紧的，则$X^*$是 非空且紧的 (最优值存在且有界)

正常函数的Weierstrass定理:

函数的下列三个条件之一成立，则最优解集合$X^*$是 非空紧集

• $dom(f)$有界
• $f$存在非空有界水平集
• $f$是强制的

凸优化的Weierstrass定理

$X$是闭凸集， 且$X \cap dom(f) \neq \empty$, 则$f$ 在$X$上的最小值点集合$X^*$是非空紧集 $\iff$ $X$ 和$f$没有公共的非零回收方向；

Reference

• Convex Optimization Theory.
• 老师的课件
• Boyd的书主要侧重模型与算法，这周内容纯理论，所以无参考；