凸优化函数的定义、凸优化问题的概念及分类

首页摘要：

凸优化系列文章旨在对记录自己这方面的学习心得，本篇文章主要介绍凸优化函数的定义、凸优化问题的概念及分类。

凸优化函数的定义

从凸函数的名字也可以看出来，函数表示的区域形状是凸出来的，再具体点就是函数表示的区域任意两点连成的直线上的任意一点都落在该函数表示的区域内部，图中（A）曲线就是一个典型的凸函数，而（B）曲线由于有一部分凹进去而不满足定义。

现在开始用数理化定义凸函数。设函数$f: R_{n} \rightarrow R $ 是凸的，如果 $f$ 的定义域是凸集（即定义域的形状是凸出来的），且对于$\theta \in [0,1] $ ，$f$ 上任意两点$ x$ 、$y$ 均满足：

$$f(y)\geq \theta f(x)+(1-\theta)f(y)$$

那么我们称函数$f$ 是凸的，其充要条件是：$f(y) \geq f(x)+\nabla f(x)(x-y)$ ，这个条件很好理解，这里的微分项表示斜率，这个公式说明的就是函数两点之间任意一点大于两点连成直线上任意一点。

凸优化问题

凸优化问题指的是在定义域内具有全局最优解的问题，其数理化定义为：

$$\begin{matrix} minimize & f(x) \hfill \\ subject to & h_{i}(x)=0,i=1,2,...m\\ & g_{j}(x)\leq 0,j=1,2,...p\\ \end{matrix}$$

如果目标函数$f(x)$、不等式约束$g_{j}(x)<=0$全为凸函数以及等式约束$h_{i}(x)$是仿射的（即为线性函数），那么这个优化模型就是凸的。其最优解是$x$ 的充要条件是满足：$\nabla f(x)(x-y)\geq 0 ,\forall y \in X$ ，其中$X$ 是所有可行解。从$f$ 是凸函数的充要条件$f(y) \geq f(x)+\nabla f(x)(x-y)\geq 0$ 可以看出，只要满足$\nabla f(x)(x-y)\geq 0 ,\forall y \in X$ ，$f(x)$ 在定义域内就是最小的。

凸优化模型的主要分类

在处理优化问题时，我们总是尝试将面对的问题模型转化或者松弛成凸优化模型，常见的凸优化模型如下（但不限于）：

• 线性规划问题

线性规划问题的数理化定义为：

$$\begin{matrix} minimize & c^{T}x+d \hfill\\ subject to & Gx\leq e \\ & Ax=b\\ \end{matrix}$$

• 二次优化问题

二次优化问题的数理化定义为：

$$\begin{matrix} minimize & \frac{1}{2}x^{T}Px+q^{T}x+r \hfill\\ subject to & Gx\leq e \\ & Ax=b\\ \end{matrix}$$

其中，$P$ 为正定阵。

• 二阶锥模型

二阶锥问题的数理化定义为：

$$\begin{matrix} minimize & q^{T}x \hfill\\ subject to & \begin{Vmatrix} A_{i}x+b_{i} \end{Vmatrix}\leq c^{T}x+d,i=1,2,...,m \\ & Bx=l\hfill\\ \end{matrix}$$

结语

至此，凸优化问题的基本概念已经介绍完了，虽然看起来内容不多，在Boyd的凸优化书中却花了100多页来介绍，这篇文章提取其中的精华并省却了大量证明过程，这将为之后的介绍打下坚实的基础。