7.8最优化

7.8-最优化基本概念

最优化问题形式

$$\begin{array}{r}maxf(x)\\ s.tx\in \Omega \end{array}$$

• $f(x)$为目标函数：objective function
• $x$为决策变量：decision variable
• $\Omega$为可行域：constrained set
• 最优解：若有$x^{\ast }\in \Omega$，使得$\forall x\in \Omega$，满足$f(x)\ge f(x^{\ast })$，则称$x^{\ast }$为该极小化问题的全局最优解，记作$x^{\ast }\in argmin\{f(x):x\in \Omega \}$；若有$x^{\ast }\in \Omega$，满足$\exists \epsilon >0$，与$x^{\ast }$的邻域$N_{\epsilon }(x^{\ast })=\{x:\Vert x-x^{\ast }\Vert <\epsilon \}$且$x\ne x^{\ast }$，使得$\forall x\in \Omega \cap N_{\epsilon }(x^{\ast })$，有$f(x)\ge f(x^{\ast })$，则$x^{\ast }$称为该极小化问题的一个局部最优解；若有$x^{\ast }\in \Omega$，满足$\exists \epsilon >0$，与$x^{\ast }$的邻域$N_{\epsilon }(x^{\ast })$，使得$\forall x\in \Omega \cap N_{\epsilon }(x^{\ast })$，且$x\ne x^{\ast }$有$f(x)>f(x^{\ast })$，则$x^{\ast }$称为该极小化问题的一个局部最优解；
• 最优值：若优化问题存在最优解，则该优化问题为最优值可达，在最优解处目标函数的取值称为最优值；若目标函数在可行域有下界，但无最优解，则称该优化问题为最优值不可达，此时最优值定义为$f^{\ast }=\underset{x\in \Omega }{\inf }f(x)$。

最优化问题的类型

• 向量优化
• 组合优化
• 半定优化
• 鲁棒优化
• 随即优化
• 稀疏优化
• 统计优化
• 张量与多项式优化
• 非光滑优化
• $...$ 具体的，稀疏性衡量：向量/矩阵的$l_0$范数$\Vert x{\Vert }_0$，取值为向量/矩阵中非零元素的个数

7.8-凸分析基础

范数

1. 向量范数

• 向量的$l_p$范数$(p\ge 1$)：$\Vert v{\Vert }_p=(\sum _{i=1}^n|v_i{|}^p{)}^{\frac{1}{p}}$
• 向量的$l_{\infty }$范数：$\Vert v{\Vert }_{\infty }=\underset{1\le j\le n}{\max }|v_{(j)}|$
• 由正定矩阵$A$诱导的向量范数：$\Vert v{\Vert }_A=\sqrt{v^{T}Av}$
• $$\begin{gathered} Cauchy-Schwarz不等式|a^{T}b|\le \Vert a{\Vert }_2\Vert b{\Vert }_2 \\ 等式成立的条件为a与b线性相关 \end{gathered}$$

2. 矩阵范数

• $如果函数\Vert \cdot \Vert :{\mathbb{R}}^{m\times n}\to {\mathbb{R}}^{+}满足:$
  • $1.正定性：\forall A\in {\mathbb{R}}^{m\times n}，有\Vert A\Vert \ge 0且\Vert A\Vert =0\iff A=0_{m\times n}$
  • $2.正齐次性：\forall A\in {\mathbb{R}}^{m\times n}，\alpha \in \mathbb{R}，有\Vert \alpha A\Vert =|\alpha |\Vert A\Vert$
  • $3.三角不等式：\forall A,B\in {\mathbb{R}}^{m\times n}，有\Vert A+B\Vert \le \Vert A\Vert +\Vert B\Vert$ $则称\Vert \cdot \Vert 为定义在向量空间{\mathbb{R}}^{m\times n}上的矩阵范数$
• $矩阵的内积:A,B\in {\mathbb{R}}^{m\times n},则⟨A,B⟩=Tr(A{B}^T)=\sum _{i=1}^m\sum _{j=1}^n{a}_{ij}{b}_{ij}$
• 矩阵的$l_1$范数：$\Vert A{\Vert }_1=\sum _{i=1}^m\sum _{j=1}^n|a_{ij}|$
• Frobenius范数：$\Vert A{\Vert }_F=\sqrt{Tr(A{A}^T)}=\sqrt{\sum _{i=1}^m\sum _{j=1}^n{a}_{ij}^2}$
• $Cauchy不等式|⟨A,B⟩|\le \Vert A{\Vert }_F\Vert B{\Vert }_F等式成立的条件为A与B线性相关$
• 矩阵的核范数： $\Vert A{\Vert }_{\ast }=\sum _{i=1}^r{\sigma }_i$，其中$r=rank(a),{\sigma }_i(i=1,2,...,r)$为$A$的所有非零奇异值（为矩阵范数）

3.矩阵的算子范数

• 由向量范数诱导的矩阵范数： 给定矩阵$A\in {\mathbb{R}}^{m\times n}$，${\mathbb{R}}^m$中的向量范数$\Vert \cdot {\Vert }_{(m)}$和${\mathbb{R}}^n$中的向量范数$\Vert \cdot {\Vert }_{(n)}$，其诱导的矩阵范数为:$\Vert A{\Vert }_{(m,n)}=\underset{x\in \mathbb{R},\Vert x{\Vert }_{(n)}=1}{\max }\Vert Ax{\Vert }_{(m)}$ 具体的，将 $\Vert \cdot {\Vert }_{(m)}$和$\Vert \cdot {\Vert }_{(n)}$取为向量的$l_p$范数，可诱导矩阵的$p$范数
  • 1-范数：$\Vert A{\Vert }_1=\underset{\Vert x{\Vert }_1=1}{\max }\Vert Ax{\Vert }_1=\underset{1\le j\le n}{\max }{\sum }_{i=1}^m|a_{ij}|$
  • 谱范数：$\Vert A{\Vert }_2=\underset{\Vert x{\Vert }_2=1}{\max }\Vert Ax{\Vert }_2=\sqrt{{\lambda }_{max}(A^{T}A)}$，其中${\lambda }_{max}(A^{T}A)$表示求矩阵$A^{T}A$的最大特征值
  • ∞范数：$\Vert A{\Vert }_{\infty }=\underset{\Vert x{\Vert }_{\infty }=1}{\max }\Vert Ax{\Vert }_{\infty }=\underset{1\le j\le m}{\max }{\sum }_{i=1}^n|a_{ij}|$
• $矩阵算子范数的相容性：\Vert Ax{\Vert }_{(m)}\le \Vert A{\Vert }_{(m,n)}\Vert x{\Vert }_{(n)}$
• $$\begin{gathered} 谱范数的性质：\Vert A{\Vert }_2^2=\Vert A^T{\Vert }_2^2=\Vert A^{T}A{\Vert }_2=\Vert A{A}^T{\Vert }_2， \\ 且对任意n阶正交矩阵C，D有\Vert CA{\Vert }_2=\Vert AD{\Vert }_2=\Vert CAD{\Vert }_2=\Vert A{\Vert }_2 \end{gathered}$$

凸集与凸函数

1. 凸集

• 仿射集：$x_1,x_2\in \mathcal{C}\Rightarrow \theta x_1+(1-\theta )x_2\in \mathcal{C},\forall \theta \in \mathbb{R}$
• 凸集：$x_1,x_2\in \mathcal{C}\Rightarrow \theta x_1+(1-\theta )x_2\in \mathcal{C},\forall 0\le \theta \le 1$
• $仿射集是凸集$
• $\mathcal{S},\mathcal{T}是凸集,k\in \mathbb{R}\Rightarrow \mathcal{S}+\mathcal{T},k\mathcal{S},\mathcal{S}\cap \mathcal{T},int\mathcal{S},cl(\mathcal{S})均为凸集$

2. 凸函数

2.1 光滑函数

• 梯度：函数$f:{\mathbb{R}}^n\to \mathbb{R}$，且$f$在$x$的一个邻域有意义，若存在向量$g\in {\mathbb{R}}^n$满足：$\underset{p\to 0}{\lim }\frac{f(x+p)-f(x)-g^{T}p}{\Vert p\Vert }=0$ 其中$\Vert \cdot \Vert$为任意向量范数，则称$f$在$x$处可微，$g$称为该函数在这一点的梯度，记作$▽f(x)$
• 特别的，若令$p=\epsilon e_i$，$e_i$是第$i$个分量为1的单位向量，则计算可得：$▽f(x)=[\frac{\partial f(x)}{x_1},\frac{\partial f(x)}{x_2},...,\frac{\partial f(x)}{x_n}{]}^T$