非线性规划凸优化——凸函数、凸规划（二）-526互联

凸规划是指若最优化问题的目标函数为凸函数，不等式约束函数也为凸函数，等式约束函数是仿射的。凸规划的可行域为凸集，因而凸规划的局部最优解就是它的全局最优解。当凸规划的目标函数为严格凸函数时，若存在最优解，则这个最优解一定是唯一的最优解。

一、凸集

凸集：设$C$为$n$维欧式空间的一个集合，若$C$内任意两点间的线段也均在$C$内，则称集合$C$为凸集。即

\[\forall x_1, x_2 \in C, \forall \theta \in [0,1]，则 x= \theta * x_1 + (1-\theta)*x_2 \in C \]

凸组合（convex combination）： $$λ_1x_1+⋯+λ_kx_k$$

其中，$λ_1,⋯,λ_k≥0,∑λ_i=1$，二元 $ k_1 * x_1 + (1-k_1)*x_2$就是一个凸组合。

凸集有良好的运算性质：(1) 交集为凸集。(2) 和集为凸集。(3) 直和为凸集。

超平面hyperplane：$H=\{x|a^Tx=b\}(a≠0)$;

半平面halfspace：$ H^+={ x|a^Tx \geq b}(a\neq 0) \\ H^-=\{ x|a^Tx \leq b\}(a\neq 0)$;

多面体polyhedra：多个线性不等式所刻画的集合：$$\{ x|a^T_ix\leq b_i,i=1,\cdots,m\}$$ 注：线性等式刻画的集合也是多面体！（可以将等式，转换为两个不等式）

椭球（Ellipsoid）：

\[\{x| (x-x_c)^T P^ {-1} (x-x_c)\leq 1 \}; 其中 P为正定矩阵; 椭球的轴长为\sqrtλ_i \]

二、凸函数

设$f$为定义在区间$I$上的函数，若对$I$上的任意两点$x_1, x_2$和任意$\lambda \in (0,1) $有

\[f(\lambda x_i + (1-\lambda)x_2)\leq \lambda f(x_i)+(1-\lambda)f(x_2) \]

将"$\leq$"换成"$<$"也成立则就是严格凸函数。

性质1：设 $f:R^n–>R^1$，$C$是凸集，若$f$是凸函数，则对于任意的$β$，水平集$D_\beta = \{x|f(x) \leq \beta, x \in C\}$是凸集。

性质2 : 凸优化问题的局部极小值是全局极小值。

性质3：若$f$一阶可微，则函数$f$为凸函数当且仅当$f$的定义域$domf$为凸集，且$ \forall x,y \in domf, f(y)\geq f(x) + \triangledown f(x)^T(y-x)$。

性质4：若$f$二阶可微，则函数$f$为凸函数当且仅当$f$的定义域$domf$为凸集，且$\triangledown ^2f(x)\succeq 0$。

正定：$f(x_1,x_2,...,x_n)=x^TAx$，(所有的二次齐次式都可以写成这个形式）如果对任意的$x \neq 0均有f(x)>0$，则称$(f(x)$为正定二次型，同时称$A$为正定矩阵。

[定理] 设$f(x):{R^n} \to R$是在凸集$X \subseteq {R^n}$上二阶可微。$f(x)$是凸函数的充分必要条件是$f(x)$的二阶海塞矩阵${\nabla ^2}f(x)$是半正定的；$f(x)$是凹函数的充分必要条件是$f(x)$的二阶海塞矩阵${\nabla ^2}f(x)$是半负定的。

例1：判断下述函数的凸凹性: (1)$f(x) = {e^x}$ (2)$f(x) = x^{\frac{1}{2}}$ (3)$f({x_1},{x_2}) = 2 + {x_1} + {x_2} - x_1^2 - x_2^2$ 解： (1) $f^{\prime \prime}(x)=e^x \geq 0$, 所以 $f(x)$ 函数是凸集 $R$ 上的的凸函数. (2) $f^{\prime \prime}(x)=-\frac{1}{4} x^{-3 / 2} \leq 0$, 所以 $f(x)$ 函数是凸集 $R$ 上的的凹函数. (3) $f\left(x_1, x_2\right)$ 的 Hessian 矩阵为:

\[\nabla^2 f(x)=\left[\begin{array}{cc} -2 & 0 \\ 0 & -2 \end{array}\right] \]

为了判断 $\nabla^2 f(x)$ 的半正 (负) 定性, 计算:

\[\begin{aligned} \operatorname{def}\left(\nabla^2 f(x)-\lambda I\right) & =\operatorname{def}\left[\begin{array}{cc} -2-\lambda & 0 \\ 0 & -2-\lambda \end{array}\right] \\ & =(-2-\lambda)^2=0 \end{aligned} \]

那么, $\lambda_1=\lambda_2=-2$, 所以矩阵 $\nabla^2 f(x)$ 为负定矩阵, $f(x)$ 为凸集 $R$ 上的凹函数.