在最优化理论中，凸集、凸函数、等值线（面）、梯度和海森矩阵等概念具有密切联系，它们提供了优化问题的几何特性、函数特性、局部特性和全局特性等方面的信息，可以帮助我们设计有效的优化算法，进而找到最优化问题的最优解．

1.1 凸集与凸函数

    凸集和凸函数是线性规划和非线性规划都要涉及的基本概念，关于凸集和凸函数的一些定理在最优化问题的理论及算法研究中具有重要作用．

1.1.1 凸集

定义1.1.1 设$\mathbf{\Omega }\subset {\mathbb{R}}^n$，若对所有的$\mathbf{x},\mathbf{y}\in \mathbf{\Omega }$及$\alpha \in [0,1]$都有$\alpha \mathbf{x}+(1-\alpha )\mathbf{y}\in \mathbf{\Omega }$，则称$\mathbf{\Omega }$为凸集（Convex set)．

从几何直观上，如果集合中的任意两点连线上的点仍在该集合中，则此集合为凸集．如图 1-1-1中（a）、（c）和（d）为凸集，而（b）为非凸集．

定义1.1.2 设${\mathbf{x}}^{(1)},{\mathbf{x}}^{(2)},\cdots ,{\mathbf{x}}^{(m)}\in {\mathbb{R}}^n$，${\alpha }_1,{\alpha }_2,...,{\alpha }_m$是一组非负实数，且$\sum _{i=1}^m{\alpha }_i=1$，则$\sum _{i=1}^m{\alpha }_i{\mathbf{x}}^{(i)}$称为一个凸组合．

    由凸集和凸组合的定义容易证明以下定理1.1.1和结论．

定理1.1.1 $\mathbf{\Omega }\subset {\mathbb{R}}^n$为凸集的充要条件是$\mathbf{\Omega }$中任意有限个点的凸组合仍在$\mathbf{\Omega }$中．

结论 设 ${\mathbf{\Omega }}_1$ 和${\mathbf{\Omega }}_2$为${\mathbb{R}}^n$中两个凸集，$\beta$是实数 ，则

（１）$\beta {\mathbf{\Omega }}_i=\{\beta \mathbf{x}|\mathbf{x}\in {\mathbf{\Omega }}_i,i=\mathrm{1,}2\}$为凸集 ；

（２）${\mathbf{\Omega }}_1\cap {\mathbf{\Omega }}_2$为凸集 ；

（３）${\mathbf{\Omega }}_1\pm {\mathbf{\Omega }}_2＝\{\mathbf{x}\pm \mathbf{y}|\mathbf{x}\in {\mathbf{\Omega }}_1,\mathbf{y}\in {\mathbf{\Omega }}_2\}$为凸集 ．

1.1.2 凸函数

定义1.1.3 对于定义在凸集$\mathbf{\Omega }\subset {\mathbb{R}}^n$上的函数$f:\mathbf{\Omega }\to \mathbb{R}$，$f$是凸函数（Convex function）当且仅当对于任意$\mathbf{x},\mathbf{y}\in \mathbf{\Omega }$和任意$\alpha \in \left(\mathrm{0,}1\right)$，都有

$f\left(\alpha \mathbf{x}+\left(1-\alpha \right)\mathbf{y}\right)\le \alpha f\left(\mathbf{x}\right)+\left(1-\alpha \right)f\left(\mathbf{y}\right).$

如果

$f\left(\alpha \mathbf{x}+\left(1-\alpha \right)\mathbf{y}\right)<\alpha f\left(\mathbf{x}\right)+\left(1-\alpha \right)f\left(\mathbf{y}\right)$

成立，则函数$f$是$\mathbf{\Omega }$上的严格凸函数．

    反之，对于定义在凸集$\mathbf{\Omega }\subset {\mathbb{R}}^n$的函数$f:\mathbf{\Omega }\to \mathbb{R}$，当$-f$是（严格）凸函数时，$f$是（严格）凹函数（Concave function）．

    如果函数$f:\mathbf{\Omega }\to \mathbb{R}$是定义在凸集$\mathbf{\Omega }$的凸函数，那么对于任意$\mathbf{x},\mathbf{y}\in \mathbf{\Omega }$，在空间${\mathbb{R}}^{n+1}$ 中连接两点$A:{\left({\mathbf{x}}^{\top },f\left(\mathbf{x}\right)\right)}^{\top }$和$B:{\left({\mathbf{y}}^{\top },f\left(\mathbf{y}\right)\right)}^{\top }$之间线段上的所有点，都位于函数$f$的图像上面，图 1-1-2‌为一元凸函数的直观显示．

    根据凸函数的定义，易得凸函数的以下性质：

性质1 设函数$f,f_1,f_2$都是凸函数，则对于任意$a⩾0$，函数$af$也是凸函数；$f_1+f_2$也是凸函数．

性质 2 已知凸集$\mathbf{\Omega }\in {\mathbb{R}}^n$，$f:\mathbf{\Omega }\to \mathbb{R}$是定义在$\mathbf{\Omega }$上的凸函数，那么$\mathbf{\Omega }$中某一点是$f$的全局极小点，当且仅当它是$f$的局部极小点．

例如，设$\mathbf{x}\in {\mathbb{R}}^n$，线性函数$f(\mathbf{x})={\mathbf{a}}^{\top }\mathbf{x},(\mathbf{a}\in {\mathbb{R}}^n且为常向量)$即是凸函数也是凹函数；正定二次函数$f(\mathbf{x})=\frac{1}{2}{\mathbf{x}}^{\top }\mathbf{Hx}+{\mathbf{b}}^{\top }\mathbf{x},(\mathbf{H}\in {\mathbb{R}}^{n\times n},\mathbf{b}\in {\mathbb{R}}^n为常向量)$为凸函数．

下一节将给出凸函数判定的一阶和二阶条件．

1.2 等值线（面）、梯度与海森矩阵

1.2.1 等值线（面）

定义1.2.1 当$\mathbf{x}\in {\mathbb{R}}^2$或${\mathbb{R}}^3$，使函数$f(\mathbf{x})$取值为同一常数的点集$\{\mathbf{x}|f(\mathbf{x})=c,c为常数\}$ 称为$f(\mathbf{x})$的等值线（面）（contour），其中函数$f(\mathbf{x})$是连续的单值函数，即定义域内每一个自变量所对应的函数值是唯一的．

    等值线有以下4个性质：

        （1）不同的等值线不相交；

        （2）除极点所在的等值线外，等值线不会中断；

        （3）等值线稠密的地方函数值变化较快，稀疏的地方变化较慢；

        （4）在极值点附近，等值线近似地为同心椭圆族．

    以上4个性质推广至高维的等值线仍成立．

    例如，当$\mathbf{x}\in {\mathbb{R}}^2$，凸函数$f(\mathbf{x})=x_1^2-x_1{x}_2+x_2^2+x_1+x_2$的图形及等值线图如图 1-2-1‌所示；而非凸函数$f(x_1,x_2)=\left(1-\frac{1}{2}{x}_1+x_1^5+x_2^3\right){\text{e}}^{-(x_1^2+x_2^2)}$图形及等值线如图 1-2-2‌所示．

图1-2-2非凸函数的图形（左）及等值线图（右）

1.2.2 梯度

定义1.2.2 设函数$f(\mathbf{x}),\mathbf{x}=(x_1,x_2,\cdots ,x_n{)}^{\top }$在平面区域$\mathbf{\Omega }$内具有一阶连续偏导数，则对于点$P\in \mathbf{\Omega }$，可以确定一个向量

$\mathbf{g}={\left(\frac{\partial f}{\partial x_1},\frac{\partial f}{\partial x_2},\cdots ,\frac{\partial f}{\partial x_n}\right)}^{\top }$，

称向量$\mathbf{g}$为函数$f(\mathbf{x})$在点$P$处的梯度，也记作$\nabla f(\mathbf{x})$．

梯度的每个分量分别描述了函数$f(\mathbf{x})$沿坐标系的每个坐标轴方向的变化率．它具有如下性质：

    性质1 梯度方向与等值线的切线方向垂直．

   证明 设等值线的方程为$f(\mathbf{x})=c$，若用参数方程表示曲面上的点$\mathbf{x}$，可设$\mathbf{x}=\mathbf{x}(t)$其中$t\in \mathbf{\Omega }$，而$f(\mathbf{x}(t))=c$是关于$t$的一元函数，上式两边对$t$求导有

    其中$\nabla f(\mathbf{x}(t){)}^{\top }$是梯度方向，${\mathbf{x}}^{\prime }(t)$是等值线的切线方向．证毕．

这一性质有时也简称为梯度垂直等值线．

    例如，图 1-2-3‌给出了非凸函数$f(x_1,x_2)=\left(1-\frac{1}{2}{x}_1+x_1^5+x_2^3\right){\text{e}}^{-(x_1^2+x_2^2)}$在点$(0,1.8)$，$(-0.9,-1)$和$(-2.05,0.2)$处的梯度与等值线垂直情况．

    性质2 函数在某点处沿着梯度方向变化最快且最大变化率等于梯度的模．

证明 设${\theta }_i,(i=1,2,\cdots ,n)$为方向$\mathbf{r}$的方向角，则 ${\left(\cos {\theta }_1,\cos {\theta }_2,\cdots ,\cos {\theta }_n\right)}^{\top }$为$\mathbf{r}$的单位向量，所以函数$f(\mathbf{x})$在点$P$处的沿方向$\mathbf{r}$的方向导数可表示为

$\begin{array}{rl}\frac{\partial f}{\partial \mathbf{r}}{|}_P& =\frac{\partial f}{\partial x_1}\cos {\theta }_1+\frac{\partial f}{\partial x_2}\cos {\theta }_2+\cdots +\frac{\partial f}{\partial x_n}\cos {\theta }_n\\ & =\nabla f\cdot \cos (\widehat{\nabla f,\mathbf{r}}),\end{array}$

所以，当$\nabla f$与$\mathbf{r}$夹角$(\widehat{\nabla f,\mathbf{r}})=0$时，

$\begin{array}{rl}{\left|\frac{\partial f}{\partial \mathbf{r}}\right|}_P& =\left|\nabla f\cdot \cos (\widehat{\nabla f,\mathbf{r}})\right|\\ & =\left|\nabla f\right|\\ & =\sqrt{{\left(\frac{\partial f}{\partial x_1}\right)}^2+{\left(\frac{\partial f}{\partial x_2}\right)}^2+\cdots +{\left(\frac{\partial f}{\partial x_n}\right)}^2},\end{array}$

取值最大，且最大值为$\Vert \nabla f\Vert$．证毕．

可以使用定义1.1.3判断一个函数是否为凸函数，也可以根据梯度判定，即下面的定理1.2.1．

定理1.2.1（一阶条件）若函数$f(\mathbf{x})$可微，即$f$的梯度$\nabla f$在定义域$D$中处处存在，函数$f$是凸函数当且仅当对于任意$\mathbf{x},\mathbf{y}\in D$，有下式成立：

$f(\mathbf{y})\ge f(\mathbf{x})+\nabla f(\mathbf{x}{)}^{\top }(\mathbf{y}-\mathbf{x})$.

称上述条件为凸函数判定的一阶条件．当$\mathbf{x}\in \mathbb{R}$（或${\mathbb{R}}^2$）时，一阶条件有清晰的几何意义，即对任意$\mathbf{x}$处的函数值始终位于其切线（或切面）的上方．如图 1-2-4‌所示．

1.2.3 海森矩阵

海森矩阵是一个由多元函数的二阶偏导数构成的方阵，它可以刻画函数的局部曲率．

定义1.2.3 如果$f(\mathbf{x}),\mathbf{x}\in {\mathbb{R}}^n$的所有二阶偏导数都存在，那么矩阵

$$\begin{array}{r}\mathbf{H}(\mathbf{x})=\left(\begin{array}{cccc}\frac{{\partial }^{2}f}{\partial x_1^2}& \frac{{\partial }^{2}f}{\partial x_1\partial x_2}& \cdots & \frac{{\partial }^{2}f}{\partial x_1\partial x_n}\\ \frac{{\partial }^{2}f}{\partial x_2\partial x_1}& \frac{{\partial }^{2}f}{\partial x_2^2}& \cdots & \frac{{\partial }^{2}f}{\partial x_2\partial x_n}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{{\partial }^{2}f}{\partial x_n\partial x_1}& \frac{{\partial }^{2}f}{\partial x_n\partial x_2}& \cdots & \frac{{\partial }^{2}f}{\partial x_n^2}\end{array}\right)\end{array}$$

为$f(\mathbf{x})$的海森（Hessian）矩阵，也记为${\nabla }^{2}f(\mathbf{x})$．

根据Hessian矩阵的正定性可以判定函数是否为凸函数．

定理1.2.2 （二阶条件）若函数$f(\mathbf{x})$二阶可微，即$f$的Hessian矩阵${\nabla }^{2}f$在定义域$D$中处处存在，函数$f$是凸函数当且仅当对任意$\mathbf{x}\in D$，该点处的Hessian矩阵是半正定的，即

${\nabla }^{2}f(\mathbf{x})⪰0$.

对于一元函数而言，Hessian矩阵半正定退化为$f^{\prime \prime }(x)\ge 0$，意味着函数$f$的导函数是非递减的．从几何上来说，Hessian矩阵处处半正定意味着函数$f$处处曲率非负．类似地，可以发现对于严格凸函数有${\nabla }^{2}f(\mathbf{x})\succ 0$，而对于凹函数有 ${\nabla }^{2}f(\mathbf{x})⪯0$．

例如，函数$f(\mathbf{x})=x_1^2-x_1{x}_2+x_2^2+x_1+x_2$在$\mathbf{x}\in {\mathbb{R}}^2$为凸函数．这是因为$\nabla f(\mathbf{x})=\left(\begin{array}{c}2x_1-x_2+1\\ 2x_2-x_1+1\end{array}\right)$，而 ${\nabla }^{2}f(\mathbf{x})=\left(\begin{array}{cc}2& -1\\ -1& 2\end{array}\right)\succ 0$．

而函数$f(x,y)=1-{\text{e}}^{-x^2}+0.01x^2+1-{\text{e}}^{-y^2}+0.01y^2$在$(x,y)\in {\mathbb{R}}^2$为非凸函数．这是因为${\nabla }^{2}f(\mathbf{x})=\left(\begin{array}{cc}2{\text{e}}^{-x^2}-4x^2{\text{e}}^{-x^2}& 0\\ 0& 2{\text{e}}^{-y^2}-4y^2{\text{e}}^{-y^2}\end{array}\right)$不是正定或半正定．

图 1-2-5‌画出了这两个函数的图形．

1.3 最优化问题及建立最优化模型

1.3.1 最优化模型

一般的最优化模型为

$$min(max)f(\mathbf{x})\text{\hspace{1em}(1.3.1)}$$

其中$f$为实值函数．若$\mathcal{F}\equiv {\mathbb{R}}^n$，则称（1.3.1）为无约束优化问题；若$\mathcal{F}$是由满足$g_i(\mathbf{x})\ge 0,(i=1,\cdots ,m)$和$h_j(\mathbf{x})=0,(j=1,\cdots ,l)$的点组成的集合，则称（1.3.1）为约束优化问题，且记为

$$\begin{array}{rl}& \min (\max )f(\mathbf{x})\\ & \text{s.t.}\{\begin{array}{l}{g}_i(\mathbf{x})\le 0,i=1,\cdots ,m\\ h_j(\mathbf{x})=0,j=1,\cdots ,l\end{array}\end{array}\text{\hspace{1em}(1.3.2)}$$

其中 $\min (\max )$ 表示目标函数求最小（或最大），“$\text{s.t.}$”表示受限于（subject to 或 such that）．称模型中的$f(\mathbf{x})$ 为目标函数（Objective），模型（1.3.2）中的式$\{\begin{array}{l}{g}_i(\mathbf{x})\le 0,i=1,\cdots ,m\\ h_j(\mathbf{x})=0,j=1,\cdots ,l\end{array}$为约束条件（Constraint），称集合$\mathcal{F}$为问题（1.1.2）的可行域（Feasible region），即

$\mathcal{F}=\{\mathbf{x}|g_i(\mathbf{x})\le 0,i=1,\cdots ,m;h_j(\mathbf{x})=0,j=1,\cdots ,l\}$，

并称$\mathbf{x}$为问题（1.3.2）的可行解．

在可行域$\mathcal{F}$中取得的使目标函数最小（或最大）的解${\mathbf{x}}^{\ast }$称为模型的 最优解，目标函数值$f({\mathbf{x}}^{\ast })$称为对应的最优值．

说明：后面如无特殊说明，本书中默认的最优化问题为最小化问题．

1.3.2 凸优化问题

若$f(\mathbf{x})$为凸函数，$\mathcal{F}$为凸集，则称问题（1.3.2）为凸规划（Convex programming）或凸优化问题，即求凸函数在凸集上的极小点．

若$f(\mathbf{x}),g_i(\mathbf{x}),h_j(\mathbf{x})$均为线性函数，则称问题（1.3.2）为线性规划（Linear Programming）；否则为非线性规划．特殊地，若模型（1.3.2）中的变量均取整数，即$\mathbf{x}\in \mathcal{F}\subseteq {\mathbb{Z}}_{+}^n$，则称其为整数规划（integer programming）；若$f(\mathbf{x})$为二次函数，$g_i(\mathbf{x}),h_j(\mathbf{x})$均为线性函数，则称问题（1.3.2）为二次规划（Quadratic Programming）．

例如，问题

$\begin{array}{rl}& \min f(\mathbf{x})=x_1^2+x_2^2-2x_1-2x_2+2\\ & \text{s.t.}\{\begin{array}{l}{g}_1(\mathbf{x})=5.5-3x_1-x_2\ge 0\\ g_2(\mathbf{x})=4.5-x_1-2x_2\ge 0\\ g_3(\mathbf{x})=0.2-x_1^{-3}+x_2\ge 0\end{array}\end{array}$

是为凸优化问题．图 1-3-1‌直观图显示了问题中目标函数的等值线和约束条件围成的可行域．

凸优化问题要求可行域$\mathcal{F}$是凸集且$f$是$\mathcal{F}$上的凸函数的最优化问题，这两个条件任一不满足则该问题即为非凸优化问题．

例如，$\underset{x\in [-1,2]}{\max }\{2+x\sin 10\pi x\}$是非凸优化问题．图 1-3-2‌画出了函数图形和最优点．虽然可行域$[-1,2]$是凸集，但目标函数在此区间上不是凸函数．

1.3.3 建立优化模型

    在科学研究和实际生产生活中有大量的问题需要通过建立优化模型解决，下面仅给出几个简单的建模示例．

例1 油井生产计划优化例2 反应器设计与操作

例3 网站用户行为优化

例4 结构设计优化

例5 电动汽车充电站网络布局与充电策略优化

例6 油气田开发的井位布置优化

在后面学习了各优化算法后，我们就可以对这些模型进行求解．

随堂练（客观题）随堂练（主观题）