凸集、凸函数与凸规划

本文主要是介绍凸集、凸函数与凸规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

1 凸集

设集合$S\subset {\mathbb{R}}^n$，若$S$中任意两点连线仍属于$S$，则$S$称为凸集，即
$${\mathbf{x}}_1+\lambda ({\mathbf{x}}_2-{\mathbf{x}}_1)\in S$$

图1 凸集（左）与非凸集（右）

2 凸函数

设$S$为${\mathbb{R}}^n$上的非空凸集，$f$是定义在$S$上的实函数，若对任意${\mathbf{x}}_1,{\mathbf{x}}_2\in S$，及$\lambda \in (0,1)$，都有
$$f({\mathbf{x}}_1+\lambda ({\mathbf{x}}_2-{\mathbf{x}}_1))\le f({\mathbf{x}}_1)+\lambda [f({\mathbf{x}}_2)-f({\mathbf{x}}_1)]$$

则称$f$为$S$上的凸函数。
对于一元函数$f$，凸函数的几何解释可简单理解为曲线$f$上任意两点的弦不在曲线下方，如下图所示。

图2 凸函数

一元凸函数的几何证明

---

若$(x_1,f(x_1)),(x_2,f(x_2))$为曲线$f$上的两点，且满足$x_1<x<x_2$，由直线的两点式公式
$$\frac{y-y_1}{y_2-y_1}=\frac{x-x_1}{x_2-x_1}$$
知，该两点构成的弦所在直线的方程为
$$\frac{y-f(x_1)}{f(x_2)-f(x_1)}=\frac{x-x_1}{x_2-x_1}$$

由于弦上的点不小于对应曲线上的点，令$0<\lambda <1$，$x=x_1+\lambda (x_2-x_1)$，得
$$y\ge f(x)⟹\frac{f(x_1+\lambda (x_2-x_1))-f(x_1)}{f(x_2)-f(x_1)}\le \frac{x_1+\lambda (x_2-x_1)-x_1}{x_2-x_1}$$

因此$f(x_1+\lambda (x_2-x_1))\le f(x_1)+\lambda (f(x_2)-f(x_1))$，不等式得证。

2.1 凸函数性质

凸函数的局部极小点是全局极小点。

证明： 若${\mathbf{x}}^{\ast }$是凸函数$f(\mathbf{x})$的局部极小点，假设$\exists \hat{\mathbf{x}}\in S$，使得$f({\mathbf{x}}^{\ast })>f(\hat{\mathbf{x}})$，则对任意$\lambda \in (0,1)$，由凸集性质有
$${\mathbf{x}}^{\ast }+\lambda (\hat{\mathbf{x}}-{\mathbf{x}}^{\ast })\in S$$

因此
$$f({\mathbf{x}}^{\ast }+\lambda (\hat{\mathbf{x}}-{\mathbf{x}}^{\ast }))\le f({\mathbf{x}}^{\ast })+\lambda [f(\hat{\mathbf{x}})-f({\mathbf{x}}^{\ast })]<f({\mathbf{x}}^{\ast })$$
上述不等式表明，对任意$\lambda \in (0,1)$都存在$f({\mathbf{x}}^{\ast }+\lambda (\hat{\mathbf{x}}-{\mathbf{x}}^{\ast }))<f({\mathbf{x}}^{\ast })$，显然与$f({\mathbf{x}}^{\ast })$是极小值矛盾。

2.2 一阶判别公式

设$f$是定义在凸集$S$上的可微函数，则$f$为凸函数的充要条件是，对任意${\mathbf{x}}_1,{\mathbf{x}}_2\in S$，有
$$f({\mathbf{x}}_2)\ge f({\mathbf{x}}_1)+\nabla f({\mathbf{x}}_1{)}^T({\mathbf{x}}_2-{\mathbf{x}}_1)$$

一阶判别公式证明

---

必要性
由$f(x_1+\lambda (x_2-x_1))\le f(x_1)+\lambda (f(x_2)-f(x_1))$，得
$$f(x_2)\ge f(x_1)+\frac{f(x_1+\lambda (x_2-x_1))-f(x_1)}{\lambda (x_2-x_1)}(x_2-x_1)$$

显然当$\lambda \to 0$时，$f(x_2)\ge f(x_1)+f^{\prime }(x_1)(x_2-x_1)$，必要性得证。

充分性
由$f(x)\ge f(y)+f^{\prime }(y)(x-y)$，因此
$$f(x_1)\ge f(y)+f^{\prime }(y)(x_1-y),f(x_2)\ge f(y)+f^{\prime }(y)(x_2-y)$$

因此令$y=x_1+\lambda (x_2-x_1)$，上面左侧不等式两侧乘$(1-\lambda )$、右侧不等式两侧乘$\lambda$，合并两个不等式得
$$(1-\lambda )f(x_1)+\lambda f(x_2)\ge f(y)+f^{\prime }(y)[x_1+\lambda (x_2-x_1)-y]=f(y)$$

显然$f(x_1+\lambda (x_2-x_1))\le f(x_1)+\lambda (f(x_2)-f(x_1))$，充分性得证。

几何解释：$(x,f(x))$为曲线$f$上一点，$y$为该点处的切线，则自变量$x$增加$\Delta x$，对曲线$f$和切线$y$带来的变化分别为$\Delta f$和$\Delta y$，则
$$\Delta f>\Delta y$$

图 一元凸函数判别公式的几何意义

2.3 二阶判别公式

设$f$是定义在凸集$S$上的二阶可微函数，则$f$为凸函数的充要条件是在任意$\mathbf{x}\in S$处，Hesse矩阵半正定。

二阶判别公式证明

---

必要性
对任一点${\mathbf{x}}^{\ast }\in S$，存在$\lambda \in [-\delta ,\delta ]$，有${\mathbf{x}}^{\ast }+\lambda \mathbf{x}\in S$，因此
$$f({\mathbf{x}}^{\ast }+\lambda \mathbf{x})\ge f({\mathbf{x}}^{\ast })+\lambda \nabla f({\mathbf{x}}^{\ast }{)}^T\mathbf{x}$$

由$f(\mathbf{x})$在点${\mathbf{x}}^{\ast }$处二次可微，则
$$f({\mathbf{x}}^{\ast }+\lambda \mathbf{x})=f({\mathbf{x}}^{\ast })+\lambda \nabla f({\mathbf{x}}^{\ast }{)}^T\mathbf{x}+\frac{1}{2}{\lambda }^2{\mathbf{x}}^T{\nabla }^{2}f({\mathbf{x}}^{\ast })\mathbf{x}+o(||\lambda \mathbf{x}|{|}^2)$$

故$\frac{1}{2}{\lambda }^2{\mathbf{x}}^T{\nabla }^{2}f({\mathbf{x}}^{\ast })\mathbf{x}+o(||\lambda \mathbf{x}|{|}^2)\ge 0$，因此
$${\mathbf{x}}^T{\nabla }^{2}f({\mathbf{x}}^{\ast })\mathbf{x}\ge 0$$

即${\nabla }^{2}f({\mathbf{x}}^{\ast })$半正定，必要性得证。

充分性
设Hesse矩阵${\nabla }^{2}f(\mathbf{x})$在每一点$\mathbf{x}\in S$处半正定，对任意${\mathbf{x}}^{\ast },\mathbf{x}\in$ 凸集$S$，由中值定理得
$$f(\mathbf{x})=f({\mathbf{x}}^{\ast })+\nabla f({\mathbf{x}}^{\ast }{)}^T(\mathbf{x}-{\mathbf{x}}^{\ast })+\frac{1}{2}(\mathbf{x}-{\mathbf{x}}^{\ast }{)}^2{\nabla }^{2}f(\hat{\mathbf{x}})(\mathbf{x}-{\mathbf{x}}^{\ast })$$

其中$\hat{\mathbf{x}}=\mathbf{x}+\lambda ({\mathbf{x}}^{\ast }-\mathbf{x})$，因此当${\nabla }^{2}f(\hat{\mathbf{x}})$半正定时，必有
$$(x-\overline{x}{)}^T{\nabla }^{2}f(\hat{x})(x-\overline{x})\ge 0$$

故$f(\mathbf{x})\ge f({\mathbf{x}}^{\ast })+\nabla f({\mathbf{x}}^{\ast }{)}^T(\mathbf{x}-{\mathbf{x}}^{\ast })$，充分性得证。

3 凸规划

考虑非线性规划问题
$$\begin{array}{rl}\min & f(\mathbf{x})\mathbf{x}\in {\mathbb{R}}^n\\ \text{s.t.}& g_i(\mathbf{x})\le 0,i=1,\cdots ,m\\ & h_j(\mathbf{x})=0,j=1,\cdots ,l\end{array}$$

设$f(\mathbf{x})$为凸函数，$g_i(\mathbf{x})$为凸函数，$h_j(\mathbf{x})$是线性函数，则问题的可行域为
S = { x ∣ g i ( x ) ≥ 0 , i = 1 , ⋯ &ThinSpace; , m ; h j ( x ) = 0 , j = 1 , ⋯ &ThinSpace; , l } S = \{ \bm x\ |\ g_i(\bm x)\geq 0, i= 1,\cdots, m;\ h_j(\bm x)=0, j = 1,\cdots,l\} S={x ∣ gi​(x)≥0,i=1,⋯,m; hj​(x)=0,j=1,⋯,l}

上述问题是求凸函数在凸集上的极小点，这类问题成为凸规划。

重要性质：凸规划的局部极小点就是全局极小点，证明见2.1。

这篇关于凸集、凸函数与凸规划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---