Lecture 3 凸函数

凸函数定义

1. 在凸集上定义的关系；
   • 几何意义：输入两点凸组合的值在两点函数值的凸组合下方
   • 凹凸关系：一般极大化凹函数问题转化成极小化凸问题；
2. 严格凸：取等，想象输入两点线段上的值，输出等于两点的凸组合，如线性函数，而不是想象函数值水平相等（极特殊情形）；

常见凸函数

1. 线性函数：既是凹函数也是凸函数，常作为非凸的近似
2. 二次函数：$x^{T}Qx+ax+bx^TQx+ax+b$，$QQ$半正定
3. 最小二乘$\mathrm{\mid }\mathrm{\mid }Ax-b\mathrm{\mid }{\mathrm{\mid }}_2^2||Ax-b||^2\_2$：有$A^{T}AA^TA$半正定
4. 范数：$p\ge 1p\backslash geq\; 1$，一般在优化问题中，考虑1-范数和2范数较多；

凸函数的性质

1. 凸函数表明其是连续函数；
2. 凸函数$f⟺\varphi (\alpha )=f(x+\alpha y)f\backslash iff\backslash phi(\backslash alpha)=f(x+\backslash alpha\; y)$是凸函数，其中$\varphi \backslash phi$是一元函数；
   • 经过$xx$沿$yy$方向上$\alpha \backslash alpha$倍的值
   • 降维的思想，参考boyd讲义；
3. 构成凸函数的一个充要条件：$f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^T(y-x)f(y)\backslash geq\; f(x)+\backslash nabla\; f(x)^T(y-x)$
   • 图像在切平面之上
   • 证明
     • 已知凸函数推不等式：泰勒展开，取$\lambda \to 0\backslash lambda\; \backslash rightarrow\; 0$的极限
     • 满足不等式推凸函数：凸组合
4. 构成凸函数的二阶充要条件
   • 非空开集
   • 二阶可微
   • 任意点处海森矩阵半正定
   • 关于梯度的不等关系关系：泰勒展开

保凸运算

1. 凸函数构成的透视函数
2. 凸函数的非负组合
3. 一组凸函数求最大

凸集与凸函数关联

1. 凸函数的下水平集$\{x\mathrm{\mid }f(x)\le a\}\backslash \{x|f(x)\backslash leq\; a\backslash \}$是凸集
   • 注意是对x，如果是二维，是下水平集投影在x轴上区间；
   • 如果是非凸函数，下水平集投影在x轴上的区间是断开的（因为$f(x)\ge af(x)\backslash geq\; a$）；
   • 反之不成立：下水平集是凸集的不一定是凸函数，想象鹰图；
2. 上图：包含边界$y=f(x)y=f(x)$的上部区域$y\ge f(x)y\backslash geq\; f(x)$构成的集合
   • 几何上看，从边界出发一系列的射线；
3. 对非空闭凸集，投影定理描述的距离函数$f(y)=min\{\mathrm{\mid }\mathrm{\mid }y-x\mathrm{\mid }{\mathrm{\mid }}_2,x\in C\}f(y)=min\backslash \{||y-x||\_2,x\backslash in\; C\backslash \}$是凸函数；
4. m个凸函数的前k大凸函数的和构成的函数是凸函数；

Note: The lecture from cxt.