[凸优化]1-凸集和凸函数

第一章凸集和凸函数优化的重要意义最优化是工程技术、经济管理、科学研究中经常遇到的问题。例如：结构设计资源分配生产计划运输方案模式识别、数据挖掘、机器学习深度学习、强化学习、人工智能解决优化问题的手段经验积累主观判断做实验比优劣建立数学模型求解最优策略优化问题数学标准形式minx f0(x)s.t. fi(x)≤0 (i=1,2,⋯ ,m)hj(x)=0&nb

Mezzベ

1218人浏览 · 2021-06-04 22:35:39

Mezzベ · 2021-06-04 22:35:39 发布

第一章凸集和凸函数

优化的重要意义

最优化是工程技术、经济管理、科学研究中经常遇到的问题。例如：

结构设计
资源分配
生产计划
运输方案
模式识别、数据挖掘、机器学习
深度学习、强化学习、人工智能

解决优化问题的手段

经验积累主观判断
做实验比优劣
建立数学模型求解最优策略

优化问题数学标准形式

$\begin{aligned} \underset{x}{min}\ &f_0(x)\\ s.t.\ &f_i(x)\le0\ (i=1,2,\cdots,m)\\ &h_j(x)=0\ (j=1,2,\cdots,n) \end{aligned}$

可行解集 $X=\{x\in R^n:f_i(x)\le0,i=1,2,\cdots,m;h_j(x)=0,j=1,2,\cdots,n\}$
最优值 $p^*=inf\{f_0(x):x\in X\}$
最优解 $x^*\in X:f_0(x^*)=p^*$
最优解不唯一
局部极小解： $\exist \epsilon>0$ ，使得 $\forall x\in X,\lVert x-\hat{x}\rVert_2<\epsilon$ ，有 $f(\hat{x})\le f(x)$ ，称 $\hat{x}$ 为 $f$ 的局部极小解
全局极小解：如果 $\forall x\in X$ ，有 $f(\hat{x})\le f(x)$ 成立，称 $\hat{x}$ 为 $f$ 的全局极小解

例子

组合优化
- 变量：投资于不同财产的数目
- 限制条件：预算、各项财产最大/最小投资额、最小收益
- 目标：总投资风险最小或者总收益最大
数值拟合
- 变量：模型参数
- 限制条件：先验信息，参数取值范围
- 目标：最小化拟合误差或者预测误差

求解优化问题

一般优化问题

难于求解
计算复杂度高、需要时间长、不总能找到最优解

特定的优化问题能够有效、可靠的求解，例如

线性规划问题
二次规划问题（最小二乘问题）
图优化问题
凸优化问题

线性规划问题(Linear Programming)

目标函数和限制函数都为线性函数，即

$\begin{aligned} min\ &c_1x_1+c_2x_2+\cdots+c_nx_n\\ s.t.\ &a_{i1}x_1+a_{i2}x_2+\cdots+a_{in}x_n\le b_i(i=1,3,\cdots,m)\\ &x_j\ge0(j=1,2,\cdots,n) \end{aligned}$

矩阵形式

$\begin{aligned} min\ &c^Tx\\ s.t.\ & Ax\le b\\ &x\ge0 \end{aligned}$

这里， $A\in R^{m\times n},c,x\in R^n,b\in R^m$

求解线性规划

无分析解（闭式解）
有效的算法及成熟的软件
计算时间复杂度：如果 $m\le n$ ，则 $O(n^2m)$ ，这里 $x\in R^n$ .

使用线性规划

通过一些标准技巧，一些复杂问题能转化成线性规划问题。例如，含有 $l_1$ − 范数或 $l_\infin$ − 范数的优化问题、分段线性优化问题等

举例

球面 $S=\{(x,y,z)\in R^3:x^2+y^2+z^2=1\}$

椭球面 $E=\{(x,y,z)\in R^3:\frac{(x-p)^2}{a^2}+\frac{(y-q)^2}{b^2}+\frac{(z-r)^2}{c^2}=1\}$

求从球面到椭球面的最近欧氏距离 $d(S,E)=min\{d((x_1,y_1,z_1),(x_2,y_2,z_2))\}$ ，这里 $(x_1,y_1,z_1)\in S,(x_2,y_2,z_2)\in E$

该问题可转化为如下的优化问题：

$\begin{aligned} min\ &(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2\\ s.t.\ & x_1^2+y_1^2+z_1^2=1\\ &\frac{(x_2-p)^2}{a^2}+\frac{(y_2-q)^2}{b^2}+\frac{(z_2-r)^2}{c^2}=1 \end{aligned}$

二次规划问题(Quadratic Programming)

$\begin{aligned} \underset{x}{min}\ &\frac12x^TQx+c^Tx\\ s.t.\ &Ax=b\\ &x\ge0 \end{aligned}$

这里， $Q\in R^{n\times n}$ 为对称矩阵，矩阵 $A\in R^{m\times n},c,x\in R^n,b\in R^m$ .

最小二乘问题(Least Square Problem)

$min\lVert Ax-b\lVert_2^2$

求解最小二乘问题

分析解（闭式解）： $x^*=(A^TA)^{-1}A^Tb$
有效的算法及成熟的软件
计算时间复杂度 $O(n^2m)$ ， $A\in R^{m\times n}$ .

使用最小二乘

一些标准的技术提高了其适应性。例如，增加权重、增加调整项等

凸优化问题

$\begin{aligned} min\ &f_0(x)\\ s.t.\ &f_i(x)\le b_i,i=1,2,\cdots,m \end{aligned}$

求解凸优化问题

无分析解
有效、可靠的算法

使用凸优化

通过一些技巧，许多问题可以转化为凸优化问题
凸优化问题有一套理论较为完善的求解方法。

有关的数学知识

内积和范数

$n$ 维实向量集合 $R^n$ 上的标准内积： $\forall x=(x_1,x_2,\cdots,x_n)\in R^n,y=(y_1,y_2,\cdots,y_n)\in R^n$ ,

$\lt x,y\gt=x^Ty=\sum_{i=1}^{n}x_iy_i$
$E u c l i d$ 范数( $l_2$ -范数)： $\forall x=(x_1,x_2,\cdots,x_n)\in R^n$ ,

$\lVert x\rVert_2=(x^Tx)^\frac12=(\sum_{i=1}^{n}x_i^2)^\frac12$
两个非零向量 $x,y\in R^n$ 的夹角：

$\arg(x,y)=\arccos(\frac{x^Ty}{\lVert x\rVert_2\lVert y\rVert_2})\in[0,\pi]$
$C a u c h y - S c h w a r t z$ 不等式： $\forall x,y\in R^n,\lvert x^Ty\rvert\le\lVert x\rVert_2\lVert y\rVert_2$
$n\times n$ 对称矩阵集合 $S_n$ 上的标准内积为， $\forall X,Y\in S^n$ ,

$\lt X,Y\gt=tr(X^TY)=\sum_{i=1}^n\sum_{j=1}^nx_{ij}y_{ij}=\sum_{i=1}^nx_{ii}y_{ii}+2\sum_{i\lt j}x_{ij}y_{ij}$
矩阵 $X=[x_{ij}]\in R^{m\times n}$ 的 $F r o b e n i u s$ 范数定义为

$\lVert X\rVert_F=(tr(X^TY))^\frac12=(\sum_{i=1}^m\sum_{j=1}^nx_{ij}^2)^\frac12$

范数

范数定义：满足以下条件的函数 $f:R^n\mapsto R,domf=R^n$ 称为范数

$f$ 是非负的： $\forall x\in R^n$ ，有 $f(x)\ge0$
$f$ 是正定的：若 $f (x) = 0$ ，则 $x = 0$
$f$ 是齐次的： $\forall x\in R^n,t\in R$ ，有 $f(tx)=\lvert t\rvert f(x)$
$f$ 满足三角不等式： $\forall x,y\in R^n$ ，有 $f(x+y)\le f(x)+f(y)$

范数采用符号 $f(x)=\lVert x\rVert$ ，范数是对向量 $x\in R^n$ 的长度的度量

两个向量 $x,y\in R^n$ 之间用范数 $\lVert \cdot\rVert$ 表示的距离定义为

$dist(x,y)=\lVert x-y\rVert$

$l_p$ -范数

$l_p$ -范数( $p\ge 1$ )

$\lVert x\rVert_p=(\lvert x_1\rvert^p+\lvert x_2\rvert^p+\cdots+\lvert x_n\rvert^p)^\frac1p=(\sum_{i=1}^n\lvert x_i\rvert^p)^\frac1p$

$l 1$ -范数： $\lVert x\rVert_1=\sum_{i=1}^n\lvert x_i\rvert$
$l 2$ -范数( $E u c i l d$ 范数)： $\lVert x\lVert_2=(\sum_{i=1}^nx_i^2)^\frac12$
$C h e b y s h e v$ 或 $l_\infin$ 范数： $\lVert x\rVert_\infin=\max\{\lvert x_1\rvert,\lvert x_2\rvert,\cdots,\lvert x_n\rvert\}$

$l_0$ -范数： $\lVert x\rVert_0=$ 向量中非零元素的个数

二次范数

对 $P\in S_{++}^n$ ，定义 $P$ -二次范数如下：

$\lVert x\rVert_p=(x^TPx)^\frac12=\lVert p^\frac12x\rVert_2$

二次范数的单位球是椭圆
如果一个范数的单位球是椭圆，该范数是二次范数

矩阵范数

矩阵 $X=[x_{ij}]\in R^{m\times n}$ 的 $F r o b e n i u s$ 范数

$\lVert X\rVert_F=(tr(X^TY))^\frac12=(\sum_{i=1}^m\sum_{j=1}^nx_{ij}^2)^\frac12$
矩阵 $X=[x_{ij}]\in R^{m\times n}$ 的绝对值之和范数

$\lVert X\rVert_{sav}=\sum_{i=1}^m\sum_{j=1}^n\lvert x_{ij}\rvert$
矩阵 $X=[x_{ij}]\in R^{m\times n}$ 的最大绝对值范数

$\lVert X\rVert_{mav}=\max\{\lvert x_{ij}\rvert:i=1,2,\cdots,m;j=1,2,\cdots,n\}$

范数的等价性

令 $\lVert\cdot\rVert_a$ 和 $\lVert\cdot\rVert_b$ 是 $R^n$ 上的范数，则存在正常数 $\alpha,\beta$ 对所有的 $x\in R^n$ ，有

$\alpha\lVert x\rVert_a\le\lVert x\rVert_b\le\beta\lVert x\rVert_a$

任何有限维向量空间上的范数都是等价的
推论：任意范数可由 $E u c l i d$ 范数进行界定，即存在常数 $\gamma\in(0,1]$ ，使得

$\lVert x\rVert\ge\gamma\lVert x\rVert_2$

对偶范数

定义：令 $\lVert\cdot\rVert$ 是 $R^n$ 上的范数，其对偶范数 $\lVert\cdot\rVert_*$ 定义为

$\lVert z\rVert_*=\sup\{z^Tx:\lVert x\rVert\le1\}=\sup\{z^Tx:\lVert x\rVert=1\}$

范数的对偶

$l_2$ -范数： $\lVert z\rVert_*=\sup\{z^Tx:\lVert x\rVert_2=1\}=\lVert z\rVert_2$
$l_1$ -范数： $\lVert z\rVert_*=sup\{z^Tx:\lVert x\rVert_1=1\}=\max\{z_1,z_2\}=\lVert z\rVert_\infin$
$l_\infin$ -范数： $\lVert z\rVert_*=sup\{z^Tx:\lVert x\rVert_\infin=1\}=\lVert z\rVert_1$
$l_p$ -范数： $\lVert z\rVert_*=sup\{z^Tx:\lVert x\rVert_p=1\}=\lVert z\rVert_q$ 当且仅当 $\frac1p+\frac1q=1$

对偶范数的性质

性质 1： $z^Tx\le\lVert x\rVert\cdot\lVert z\rVert_*\ (\forall x)$
性质 2：对偶范数的对偶范数为原范数，即 $\lVert x\rVert_{**}=\lVert x\rVert$

导数

假定： $f:R^n\mapsto R^m,x\in int\ domf$ 。函数 $f$ 在 $x$ 处可微，则存在矩阵 $Df(x)\in R^{m\times n}$ 满足

$\underset{z\in domf,z\neq x,z\rightarrow x}{lim}\frac{\lVert f(z)-f(x)-Df(x)(z-x)\rVert_2}{\lVert z-x\rVert_2}=0$

$Df(x)\in R^{m\times n}$ 称为 $f$ 在 $x$ 处的导数（或 $J a c o b i a n$ 矩阵）
偏导数： $Df(x)_{ij}=\frac{\partial f_i(x)}{\partial x_i},i=1,2,\cdots,m;j=1,2,\cdots,n$

$f$ 在 $x$ 处以 $z$ 为变量的一次逼近为： $\overline{f}(z)=f(x)+Df(x)(z-x)$

梯度

实函数： $f:R^n\rightarrow R,x\in int\ domf$ 的导数为行向量 $Df(x)\in R^{1\times n}$ ，其转置称为函数的梯度，即

$\nabla f(x)=Df(x)^T\in R^n$

这里 $\nabla f(x)_i=\frac{\partial f(x)}{\partial x_i},i=1,2,\cdots,n$

$f$ 在 $x\in int\ domf$ 处以 $z$ 为变量的一次逼近： $\overline{f}(z)=f(x)+\nabla f(x)^T(z-x)$

凸集

定义

凸集的定义：集合 $C\in R^n$ 称为凸集，如果 $\forall x,y\in C$ 及 $\forall \theta\in[0,1]$ ，有

$z=\theta x+(1-\theta)y\in C$

凸集中任意两点的连线仍在该集合中

多个点 $x_1,x_2,\cdots,x_m\in C$ 的凸组合定义为：

$\{z:z=\sum_{i=1}^m\lambda_ix_i,\forall\lambda_i\ge0,\sum_{i=1}^m\lambda_i=1\}$

性质

凸集合的交运算：令 $\{C_i:i\in I\}$ 是凸集的集合，那么 $∩i∈ICi \cap_{i\in I}C_i$ 是凸集
凸集合的和运算：令 $C_1,C_2$ 为凸集合，则 $\{x_1+x_2:x_1\in C_1,x_2\in C_2\}$ 是凸集
仿射函数保凸集：仿射函数 $f (x) = A x + b$ ，这里 $A\in \mathbb R^{m\times n},b\in\mathbb R^m$ 有
- $S\subseteq\mathbb R^n$ 是凸集 $\Rightarrow f(S)=\{f(x):x\in S\}$ 是凸集
- $S\subseteq\R^m$ 是凸集 $\Rightarrow f^{-1}(S)=\{x\in \R^n:f(S)\in S\}$ 是凸集

凸函数

定义

凸函数（Convex Function）:

令集合 $C\subseteq\R^n$ 是一凸集。 $\forall x,y\in C,\forall\lambda\in[0,1]$ ，如果函数 $f:C\rightarrow\R$ 满足以下条件

$f(\lambda x+(1-\lambda)y)\le\lambda f(x)+(1-\lambda)f(y)$

则 $f$ 为凸函数。

凹函数（Concave Function）:

令集合 $C\subseteq\R^n$ 是一凸集。 $\forall x,y\in C,\forall\lambda\in[0,1]$ ，如果函数 $f:C\rightarrow\R$ 满足以下条件

$f(\lambda x+(1-\lambda)y)\ge\lambda f(x)+(1-\lambda)f(y)$

则 $f$ 为凹函数。

定理：函数 $f:C\rightarrow\R$ 是凹函数当且仅当函数 $- f$ 是凸函数

严格凸函数（Strictly Convex）:

严格凹函数（Strictly Concave）:

一阶判定

定理： $C\subseteq\R^n$ 为凸集且函数 $f:C\rightarrow\R$ 在集合 $C$ 上可微，那么

函数 $f$ 是凸函数当且仅当 $\forall x,y\in C$ ，有

$f(y)\ge f(x)+\nabla^Tf(x)(y-x)$
如果 $\forall x,y\in C$ 且 $x\neq y,f(y)\gt f(x)+\nabla^Tf(x)(y-x)$ ，那么函数 $f$ 是严格凸函数

二阶判定

定理： $C\subseteq\R^n$ 为凸集（开集）且函数 $f:C\rightarrow\R$ 在集合 $C$ 上二阶连续可微，那么

函数 $f$ 是凸函数当且仅当 $\forall x\in C,\nabla^2f(x)$ 为对称半正定矩阵
如果 $\forall x\in C,\nabla^2f(x)$ 为对称正定矩阵，那么函数 $f$ 是严格凸函数

这里， $\forall x=[x_1,x_2,\cdots,x_n]\in C$ ，函数 $f$ 的 Hessian 矩阵 $\nabla^2f(x)\in\R^{n\times n}$ 定义为

$(\nabla^2f(x))_{ij}=\frac{\partial^2f(x)}{\partial x_i\partial x_j}\ \ (i,j=1,2,\cdots,n)$

推论： $C\subseteq\R^n$ 为凸集且函数 $f:C\rightarrow\R$ 定义为 $f(X)=x^TQx+2p^Tx+r$ ，这里， $Q\in S^n$ 为对称矩阵，那么

函数 $f$ 是凸函数当且仅当 $Q$ 为对称半正定矩阵
函 $f$ 是凹函数当且仅当 $Q$ 为对称半负定矩阵
函数 $f$ 是严格凸（凹）函数当且仅当 $Q$ 为对称正（负）定矩阵
否则，函数 $f$ 为非凸非凹函数

性质

非负乘积保持凸性： $\forall\alpha\geq0$ ，如果函数 $f$ 是定义在 $C$ 上的凸函数，则函数 $g(x)=\alpha f(x)$ 是凸函数
和运算保持凸性：如果函数 $f_1,f_2$ 为凸函数，那么函数 $g(x) = f_1(x)+f_2(x)$ 为凸函数
$C\in R^n$ 为凸集且 $\{f_i:C\rightarrow\R|i\in I\}$ 是凸函数的集合，则其权重和 $f=\sum_{i\in I}w_if_i$ 是凸函数，这里权重 $w_i\geq0,\forall i\in I$
$f$ 是定义在凸集 $C\subseteq\R^n$ 上的凸函数，则 $g:B\rightarrow\R,g(x)=f(Ax+b),B=\{Ax+b:x\in C\}$ 是凸函数
函数 $f (x, y)$ 是定义在集合 $Z=\{(x^T,y^T)^T:x\in\R^m,y\in\R^n\}$ 上的凸函数。则对凸集合 $C$ ，有 $g(x)=\underset{y\in C}{\inf}f(x,y)$ 是凸函数
如何对于任意的 $y\in A,f(x,y)$ 是关于 $x$ 的凸函数，那么 $g(x)=\underset{y\in A}{\sup} f(x,y)$ 是凸函数。
共轭函数：函数 $f:\R^n\rightarrow\R$ 的共轭函数 $f^*:\R^n\rightarrow\R$ 定义为：仿射函数 $y^Tx$ 与 $f (x)$ 之间的最大差值，即 $f^*(x)=\underset{x\in domf}{\sup}(y^Tx-f(x))$
- 如果函数 $f$ 可微，在满足 $f^{'} (x) = y$ 的点 $x$ 处差值最大。
- 对于任意函数 $f$ ，其共轭函数 $f^*$ 为凸函数¹
$C\in R^n$ 为凸集且 $\{f_i:C\rightarrow R|i\in I\}$ 是凸函数的集合，那么函数 $h:C\rightarrow\R,h(x)=\underset{i\in I}{\sup}f_i(x)$ 是凸函数。当 $I$ 是有限指标集合时，
$h(x)=\underset{i\in I}{\sup}f_i(x)=\max\{f_1(x),f_2(x),\cdots,f_n(x)\}$

Jensen’s Inequality

$C\in\R^n$ 为凸集且 $f(x),x\in C$ 是凸函数。 $\forall x_1,x_2,\cdots,x_k\in C,\forall\lambda_1,\lambda_2,\cdots,\lambda_k\geq0$ 且 $\lambda_1+\lambda_2+\cdots+\lambda_k=1(k\geq2)$ ，有
$f(\sum_{i=1}^k\lambda_ix_i)\leq\sum_{i=1}^k\lambda_if(x_i)$