Optimization-convex-func-pre

凸函数-pre

本章主要介绍凸函数相关的知识，由于课时的原因将会分为上下两节，本博客为上，主要介绍凸函数相关的基本概念，凸函数的基本性质与判定定理。

再次意识到自己写的有一点过于麻烦。，开始尝试简化一下，。

基本定义

由于本人好多东西也都忘了。。以及当时学的时候很多的形式与当前的形式也不尽相同。所以下面会列举不少相对比较基础的概念

数学分析相关定义

• 梯度

  给定函数$f :R^n\to R$，且$f$在点$x$的邻域内有意义，若存在向量$g\in R^n$满足

  $\lim_{p\to 0} \frac{f(x+p)-f(x)-g^Tp}{||p||} = 0$

  其中$||\cdot||$是任意方向的向量范数，则称$f$在$x$处可微$(Frechet)$可微，$g$为$f$在$x$处的梯度若对于区域的每个点都存在$\nabla f(x)$, 则$f$在区域上可微

  基本表示如下

  $\nabla f(x) = \left[ \frac{\partial f(x)}{\partial x_1},\frac{\partial f(x)}{\partial x_2},\cdots,\frac{\partial f(x)}{\partial x_n} \right]$

• $Hessian$ 矩阵

  若函数$f :R^n\to R$，在点$x$处的二阶偏导数$\frac{\partial^2 f(x)}{\partial x_i\partial x_j}$$i,j=1,2,...,n$都存在

  则 下图被称$f$在$x$处的$Hessian$矩阵

  

  若$\nabla^2 f(x)$在区域上的每一点$x$都存在，则称$f$在区域$D$上二阶可微，若$\nabla^2 f(x)$在区域上连续，称$f$在区域$D$上二阶连续可微，也可证明此时$Hessian$矩阵是对称矩阵

• 多元函数的$Taylor$展开

  当函数$f :R^n\to R$是连续可微的，对向量$p\in R^n$，有

  $f(x+p)=f(x)+\nabla f(x+tp)^Tp$

  其中，$0<t<1$, 若$f$在区域$D$上二阶连续可微，则

  $\nabla f(x+p)=\nabla f(x)+\int^1_0\nabla^2f(x+tp)p \ dt$

  $f(x+p)=f(x)+\nabla f(x)^Tp +\frac 12 p^T\nabla^2 f(x+tp)p$

  其中，$0<t<1$

• $Lipschitz$ 连续

  对可微函数$f$，若存在$L>0$,对任意$x,y\in dom \ f$有如下条件

  $||\nabla f(x)-\nabla f(y)||\le L||x-y||$

  则称$f$是梯度$Lipschitz$ 连续的，也称$L$光滑，

  个人觉得此条件相对而言是一个比较强的条件了，往往可以一系列好的性质。一阶常微分方程的解的存在唯一定义便用到了此结论

  引理 二次上界 若可微函数$f(x)$的定义域 $dom \ f=R^n$ 而且$f$是梯度$Lipschitz$ 连续的 ，则$f(x)$ 有二次上界

  $f(y)\le f(x)+\nabla f(x)^T(y-x)+\frac L2 ||y-x||^2, \forall x,y\in dom \ f$

  证明如下，比较好懂就不写了QAQ~~（懒得写）~~

  

  推论 可微函数$f(x)$$dom \ f = R^n$且仅有一个全局极小点$x^*$, 若$f$是梯度$Lipschitz$ 连续的, 则对任意$x$有

  $\frac 1{2L} ||\nabla f(x)||^2\le f(x)-f(x^*)$

  使用引理可直接证明。

  PS在凸集中提到矩阵的二范数为最大奇异值。因此也可直接联系到此

矩阵与自动求导

• 矩阵变量函数的导数，$G,X\in R^{m\times n}$,$G$为梯度

  $\lim_{V\to 0} \frac{f(X+V)-f(X)-}{||V||} = 0$

  则矩阵变量函数的梯度如下所示

  

  然而矩阵范数相对较繁琐，实际中往往使用另一种可微$Gateaux$可微

  $\lim_{t\to 0} \frac{f(X+tV)-f(X)-t}{t} = 0$

  满足上式子的$G$成为$Gateaux$梯度

• 矩阵变量函数的导数

  有线性函数$f(X) = tr(AX^TB)$ $A\in R^{p\times n},B\in R^{m\times p} ,X\in R^{m\times n}$

  则对任意方向的$V\in R^{m\times n}, t\in R$ 有

  $\lim_{t\to 0} \frac{f(X+tV)-f(X)}{t} \\= \lim_{t\to 0} \frac{tr(A(X+tV)^TB)-tr(AX^TB)}{t} = tr(AV^TB) =$

  也因此，$\nabla f(X) = BA$

  类似可证$f(X,Y) = \frac 12||XY-A||_F^2$ 其中$Xin R^{m\times p},Y\in R^{p\times n}$

  有$\frac{\partial f}{\partial Y} = X^T(XY-A)$, $\frac{\partial f}{\partial X} = (XY-A)Y^T$

  具体证明不懂可评论或联系作者

凸函数相关

一波基础定义来袭。。

• 广义实值函数

  $def \quad \bar R = R\cup\{\pm\infty\}$ 为广义实数空间，称映射$f\quad R^n\to\bar R$为广义实值函数

• 适当函数

  至少一处取值不是正无穷，且处处取值不是负无穷的函数

• 下水平集与上方图

  下水平集：对于广义实值函数$f:R^n\to\bar R$, 有$C_\alpha = \{ x|f(x)\le\alpha \}$

  上境图：对于广义实值函数$f:R^n\to\bar R$, 有 $epi \ f = \{ (x,t)\in R^{n+1}|f(x) \le t \}$

  一维函数与其上境图的基本关系如下：（上方图的名字大概也由此而来

  

  可以证明对于某函数的上方图是凸集的充要条件为该函数为凸函数

  个人证明如下，不太严谨。。

  必要性：

  ​ 显然，对上方图的两点$(x_1,y_1)(x_2,y_2)$，其中$x\in R^n,y\in R$

  ​ 则对于两点间的任意一点 ，显然$\theta x_1+(1-\theta )x_2\in R^n$

  ​ 并且$(x_1,y_1)(x_2,y_2)$也在上方图中，于是$y_1,y_2\le t$ ，

  ​ 从而$\theta y_1+(1-\theta) y_2\le max(y_1,y_2)\le t$ 得证

  充分性

  ​ 如果$x_1,x_2\in dom f$,有$(x_1,y_1)(x_2,y_2)\in epi\ f$ 则由于$epi \ f$是凸集，则

  ​ $$(\theta x_1+(1-\theta )x_2, \ \theta y_1+(1-\theta) y_2)\in epi\ f\
  f(\theta x_1+(1-\theta )x_2)\le \theta y_1+(1-\theta)y_2$$

  ​ 且$x_1,x_2$是任意选取的，则充分性得证

• 闭函数

  设广义实值函数$f:R^n\to\bar R$, 若$epi \ f$为闭集，则$f$为闭函数

• 下半连续函数

  设广义实值函数$f:R^n\to\bar R$, 若对任意的$x\in R^n$有$\lim_{y\to x}\inf f(y)\ge f(x)$ 则成$f(x)$为下半连续函数

  ---

  不过可以证明的是闭函数与下半连续函数是等价的，有如下等价命题

  1. 函数的任意$\alpha-$下水平集是闭集
  2. 函数是下半连续的
  3. 函数是闭函数

  下面简单 证明一下$2\to 3$吧，其余不介绍了

  假设$(x_k,y_k)\in epi\ f$,并且$(x_k,y_k)$ 的极限是$(\bar x,\bar y)$

  $f(\bar x)\le \lim_{k\to +\infty}\inf f(x_k)\le \lim_{k\to +\infty} f(y_k)\le \bar y$

  得证

参考资料

1. 最优化：建模、算法与理论 刘浩洋,户将,李勇锋,文再文著
2. 凸优化 Stephen Boyd 著
3. BUAA数学系崔老师的课堂课件