凸优化学习笔记（二）：凸函数、函数共轭、拟凸函数

二、凸函数

基本概念

定义 1 — 基本

函数 $f:R^n\rightarrow R$ 是凸函数，当且仅当

• $f$ 的定义域是凸集

• $\forall x_1,x_2\in dom(f),\forall \theta\in [0,1],f(\theta x_1+(1-\theta)x_2)\leq \theta f(x_1)+(1-\theta)f(x_2)$

定义 2 — 任意直线限制（降维）

函数 $f:R^n\rightarrow R$ 是凸函数，当且仅当

• $\forall x\in dom(f),\forall v\in R^n,t\in R,g(t)=f(x+tv)$ 为凸， $dom(g)=\{t|x+tv\in dom(f)\}$

定义理解：在高维空间选择一个起点和任意一个方向来切这个高维函数，切出来的边缘就是一个一维函数，“所有切出来的一维函数是凸的” 等价于 “原来的高维函数是凸的”。

举例练习：

定义 3 — 一阶条件

设 $f:R^n\rightarrow R$ 可微，即梯度 $\bigtriangledown f$ 在 $dom(f)$ 上均存在，则 $f$ 为凸等价于：

• $dom(f)$ 为凸

• $f(y)\geq f(x)+\bigtriangledown f(x)^T(y-x),\forall x,y\in dom(f)$

进一步推导，若 $f$ 中存在一点 $x_0$ 使得 $\bigtriangledown f(x_0)=0$ ，则 $f(y)\geq f(x_0),\forall y\in dom(f)$ ，即 $x_0$ 为全局最小点。另外，若上述一阶条件中的 $\geq$ 改为 $>$ ，则为强凸的充要条件。

定义 4 — 二阶条件

若 $f:R^n\rightarrow R$ 二阶可微，则函数 $f$ 是凸函数，当且仅当

• $dom(f)$ 为凸

• $\forall x\in dom(f),\bigtriangledown^2f(x)\succeq 0$ ，即 $f$ 的 Hessian 矩阵半正定（特征值均 $\geq 0$ ）

性质：

• $\bigtriangledown^2 f(x)\succ 0\Rightarrow f(x)$ 严格凸，但 $f(x)$ 严格凸 $\not\Rightarrow \bigtriangledown^2 f(x)\succ 0$ ，例如 $f(x)=x^4$

• 特例： $f(x)=\displaystyle\frac{1}{2}x^TPx+q^Tx+r$ 严格凸 $\Leftrightarrow \bigtriangledown^2f(x)\succ 0$

• 凸函数不一定可微（ $y=|x|$ ）

• 范数是凸函数，但零范数（ $||x||_0=$ 非零元素数目，不满足范数定义）不是凸函数

• 极大值函数 $f(x)=\max{x_1,x_2,…,x_n},x\in R^n$ 不可导，但是凸的；由于其不可导，因此常用 $log-sum-up$ 函数 $f(x)=log(e^{x_1}+…+e^{x^n}),x\in R^n$ 解析近似，满足 $\max{x_1,…,x_n}\leq f(x)\leq \max{x_1,…,x_n}+log(n)$ ， $f(x)$ 光滑且凸

定义 5 — 一阶条件另一种形式

设 $f$ 为可微函数，则 $f$ 为凸函数当且仅当 $\operatorname{dom} f$ 为凸集且下式成立：

定义 6 — epigraph

函数 $f:\mathbb{R}^{n} \rightarrow \mathbb{R}$ 的 epigraph 定义如下：

易知 $\operatorname{epi} f\subseteq \mathbb{R}^{n+1}$ 。通过 epigraph，我们可以得到如下凸函数定义：

• 函数 $f$ 为凸函数当且仅当其对应 $\operatorname{epi} f$ 为凸集。

凸函数扩展

对数凸 / 凹

对数凸：

• $f:R^n\rightarrow R$ 为 log convex，若 $\forall x\in dom(f),f(x)>0$ 且 $log(f)$ 为凸函数。

对数凹：

• $f:R^n\rightarrow R$ 为 log concave，若 $\forall x\in dom(f),f(x)>0$ 且 $log(f)$ 为凹函数。

性质：

• log convex $\Rightarrow$ convex

• concave, $f(x)>0 \Rightarrow$ log concave

强凸函数

注意区分强凸和严格凸，强凸一定是严格凸的，但严格凸不一定强凸，比如 $f(x)=e^x$ 。

定义 1

若存在常数 $m>0$ ，使得

为凸函数，则称 $f(x)$ 为强凸函数（或 $m$ -强凸函数），其中 $m$ 为强凸参数。

定义 2

若存在常数 $m>0$ ，使得对 $\forall x,y\in\operatorname{dom} f$ 和 $\theta\in(0,1)$ ，有：

则称 $f(x)$ 为强凸函数，其中 $m$ 为强凸参数。

定义 3 — 一阶条件

设 $f:R^n\rightarrow R$ 可微，即梯度 $\bigtriangledown f$ 在 $dom(f)$ 上均存在，则 $f$ 为强凸等价于：

• $dom(f)$ 为凸

• $f(y)\geq f(x)+\bigtriangledown f(x)^T(y-x)+\displaystyle\frac{m}{2}|y-x|^2,\forall x,y\in dom(f)$

性质

• 若 $f$ 为强凸函数且存在最小值，则 $f$ 的最小值唯一。

保持函数凸性

非负加权和：

• $f_1,…,f_m$ 为凸，则 $f=\sum\limits_{i=1}^m w_if_i$ 为凸，其中 $w_i\geq 0$

非负加权和（扩展）：

• $f(x,y)$ 对任意 $y\in A,f(x,y)$ 均为凸，且 $w(y)\geq 0,\forall y\in A$ ，则 $g(x)=\int_{y\in A}w(y)f(x,y)dy$ 为凸

仿射映射：

• 若 $f:R^n\rightarrow R$ 为凸，则 $g(x)=f(Ax+b)$ 为凸，其中 $A\in R^{n\cdot m},b\in R^n,dom(g)=\{x|Ax+b\in dom(f)\}$

两个函数的极大值函数：

• $f_1,f_2$ 为凸，则 $f(x)=\max{f_1(x),f_2(x)}$ 为凸，其中 $dom(f)=dom(f_1)\cap dom(f_2)$

向量中 $r$ 个最大元素的和：

• 令 $x[i]$ 为 $x$ 中第 $i$ 大元素，则 $f(x)=\sum\limits_{i=1}^rx[i]$ 为凸函数

无限个凸函数的极大值：

• $\forall y\in A,f(x,y)$ 对于 $x$ 均为凸，则 $g=\sup_{y\in A}f(x,y)$ 为凸

• 例：实对称矩阵的最大特征值，该函数为凸

函数组合：

• $h:R^k\rightarrow R,g:R^n\rightarrow R^k,f=h\circ g,R^n\rightarrow R$ ，即 $f(x)=h(g(x))$ ，其中 $dom(f)=\{x\in dom(g)|g(x)\in dom(h)\}$

• $n,k\geq 1,dom(g),dom(h),dom(f)$ 不一定为 $R^n,R^k,R^n$ ，且 $h,g$ 均不一定二阶可微

• $\tilde h$ 为 $h$ 的扩展，即 $h$ 为凸，则定义域外为正无穷； $h$ 为凹，则定义域外为负无穷；当然也可以通过完善 $h$ 定义来避免进行扩展

函数的透视：

• $f:R^n\rightarrow R,g:R^n\cdot R_{++}\rightarrow R,g(x,t)=tf(\frac{x}{t}),dom(g)=\{(x,t)|t>0,\frac{x}{t}\in dom(f)\}$ ，则 $f$ 为凸， $g$ 为凸； $f$ 为凹， $g$ 为凹

函数的共轭 (Conjugate)

定义：

• $f:R^n\rightarrow R,f^*:R^n\rightarrow R,f^*(y)=\sup_{x\in dom(f)}(y^Tx-f(x))$

性质：

• $f(x)$ 若可微，则 $f^*(y)$ 对应的 $x$ 必是 $f’(x)=y$ 的一点

• 函数的共轭一定为凸（可以看成无限个仿射函数的极大值）

共轭的共轭：

• 若 $f$ 非凸， $f^{**}\not=f$

• 若 $f$ 为凸，且 $f$ 为闭函数，即 $\forall \alpha\in R,{x|x\in dom(f),f(x)\leq \alpha}$ 为闭集，则 $f^{**}=f$ ，即：

拟凸函数

凸集与凸函数的关系

定义：

• 若 $f:R^n\rightarrow R$ ，则定义其 $\alpha$ -Sublevel Set 为 $C_{\alpha}=\{x\in dom(f)|f(x)\leq \alpha\}$

性质：

• 凸函数的所有的 $\alpha$ -Sublevel Set 都是凸集；但就算函数的 $\alpha$ -Sublevel Set 都是凸集， $f$ 也不一定是凸函数（例如 $-e^x$ ）

拟凸 / 凹 / 线性函数定义 1

定义：

• Quasi Convex： $f:R^n\rightarrow R,\forall \alpha,S_{\alpha}=\{x\in dom(f)|f(x)\leq \alpha\}$ 为凸，即 $\alpha$ -Sublevel Set 为凸集

• Quasi Concave： $f:R^n\rightarrow R,\forall \alpha,S^{‘}_{\alpha}=\{x\in dom(f)|f(x)\geq \alpha\}$ 为凸

• Quasi Linear： $f:R^n\rightarrow R,\forall \alpha,S^{‘‘}_{\alpha}=\{x\in dom(f)|f(x)= \alpha\}$ 为凸

拟凸与凸的关系：

• 凸 $\Rightarrow$ 拟凸，但拟凸 $\not\Rightarrow$ 凸

单模态函数 (Unimodal Function)：

• 拟凸函数即为单模态函数

• 此类函数通常可以方便求解，但不好分析

定义 2

定义：

• $dom(f)$ 为凸，且 $\forall x,y\in dom(f),0\leq \theta\leq 1$ 满足 $\max\{f(x),f(y)\}\geq f(\theta x+(1-\theta)y)$

拟凸函数举例：

• 向量的长度 $X\in R^n$ ， $X$ 中最后一个非零元素的位置

• 线性分数函数 $f(x)=\displaystyle\frac{a^Tx+b}{c^Tx+d},dom(f)={x|c^Tx+d>0}$

定义 3 — 一阶条件

定义：

• 一阶可微

• $dom(f)$ 为凸

• $\forall x,y\in dom(f),f(y)\leq f(x)\Rightarrow \nabla^Tf(x)(y-x)\leq 0$

定义 4 — 二阶条件

定义：

• 二阶可微

• $dom(f)$ 为凸

• $\forall x,y\in dom(f),y^T\nabla f(x)= 0\Rightarrow y^T\nabla^2 f(x)y\geq 0$

性质：

• 在实数域上， $f^{‘}(x)=0,y\not=0\Rightarrow f^{‘’}(x)\geq 0$ ，即对比凸函数，拟凸函数在一些关键点上作出了限制

参考资料

• Convex Optimization

• 凸函数 - 文再文

• Previous
  凸优化学习笔记（一）：仿射集、凸集、锥
• Next
  凸优化学习笔记（三）：凸优化问题