凸优化问题的说明

在说明什么是凸优化问题前，我们先来看下面的曲线图：

左右两条曲线哪一个只有唯一的极小值点？很明显是左图。

那下面的两个二维曲面图呢？

同样也是左图。

为什么要举上面的例子？就是要引出凸优化的本质：只有唯一的极值点。

凸优化的凸一般说的是下凸。

这有什么好处呢？现在的优化算法都是在找极值点，如果极值点唯一，那么这个问题通过梯度下降法就一定能够找到最优点。

接下来要介绍的是，优化问题的定义以及怎么判定一个优化问题是凸优化问题。

优化问题的定义

优化问题的数学表达式如下：
min ⁡ x f ( x ) s . t . h i ( x ) = 0 ,   i = 1 , 2 , ⋯   , N g j ( x ) ≤ 0 ,   j = 1 , 2 , ⋯   , M \begin{aligned} & \min_{\mathbf{x}} f(\mathbf{x}) \\ s.t. \quad h_i(\mathbf{x}) &= 0, \space i=1,2,\cdots,N \\ g_j(\mathbf{x}) &\le 0, \space j=1,2,\cdots,M \\ \end{aligned} s.t.hi​(x)gj​(x)​xmin​f(x)=0, i=1,2,⋯,N≤0, j=1,2,⋯,M​
其中， f ( x ) f(\mathbf{x}) f(x)是目标函数， h i ( x ) , i = 1 , 2 , ⋯   , N h_i(\mathbf{x}), i=1,2,\cdots,N hi​(x),i=1,2,⋯,N是等式约束函数， g j ( x ) , j = 1 , 2 , ⋯   , M g_j(\mathbf{x}), j=1, 2, \cdots, M gj​(x),j=1,2,⋯,M是不等式约束函数。

在说明凸优化问题的判别方法前，需要先了解一下凸集和凸函数的概念。

基本概念

凸集

几何上的直观解释：在欧式空间中，对于一个集合中的任意两点，它们连线上的任意一点都还在这个集合中，那么这个集合就是凸集。

例子：下面都是二维坐标下的集合，集合的边缘如果有加粗就表示集合包括边界点，没有加粗就是不包括边界点。

根据定义，第一个是凸集，第二个不是凸集，因为集合中的两个点（黑点）连线的一部分不在集合内，第三个也不是凸集，因为边界上的两个点连线的一部分不在集合内。

凸函数

一维情况下，凸函数几何上的一个直观例子就是：

具体的特点是：凸函数的任意两点之间的函数值都在这两点连线之下。

凸优化问题的判别方法

满足凸优化问题需要两个条件：目标函数是凸函数，它的可行域（约束条件规定的定义域）是凸集。

更具体来说，对于优化问题
min ⁡ x f ( x ) s . t . h i ( x ) = 0 ,   i = 1 , 2 , ⋯   , N g j ( x ) ≤ 0 ,   j = 1 , 2 , ⋯   , M \begin{aligned}& \min_{\mathbf{x}} f(\mathbf{x}) \\s.t. \quad h_i(\mathbf{x}) &= 0, \space i=1,2,\cdots,N \\g_j(\mathbf{x}) &\le 0, \space j=1,2,\cdots,M \\\end{aligned} s.t.hi​(x)gj​(x)​xmin​f(x)=0, i=1,2,⋯,N≤0, j=1,2,⋯,M​
如果目标函数 f ( x ) f(\mathbf{x}) f(x)是凸函数，约束条件 { h i ( x ) = 0 g j ( x ) ≤ 0 , i = 1 , 2 , ⋯   , N \left\{ \begin{aligned} h_i(\mathbf{x})=0 \\ g_j(\mathbf{x}) \le 0 \end{aligned}, i=1,2,\cdots,N\right. {hi​(x)=0gj​(x)≤0​,i=1,2,⋯,N决定的可行集是凸集，则该优化问题就是凸优化问题。

为什么要符合这两个条件呢？我们举一些反例来说明。

情况1：可行域是凸集，函数不是凸函数。

这个比较好理解，一个简单的例子如下图：

上图中可行域是整个实数集，显然是凸集，但目标函数不是凸函数，有两个局部最小值，无法保证极值点唯一。

情况2：可行域不是凸集，函数是凸函数。

上图中目标函数是凸函数，但可行域不是凸集，中间有断裂，从曲线的左边出发和从曲线的右边出发（梯度下降法需要选择初始点），会得到不一样的最小值，因此不能保证最小值的唯一性。

讨论至此，我们面对的问题是：

如何判定目标函数 f ( x ) f(\mathbf{x}) f(x)是凸函数，约束条件 { h i ( x ) = 0 g j ( x ) ≤ 0 , i = 1 , 2 , ⋯   , N \left\{ \begin{aligned} h_i(\mathbf{x})=0 \\ g_j(\mathbf{x}) \le 0 \end{aligned}, i=1,2,\cdots,N\right. {hi​(x)=0gj​(x)≤0​,i=1,2,⋯,N决定的可行集是凸集？

下面先来了解凸集和凸函数的数学判别方法。

凸集的数学判别方法

凸集的数学定义

先来看凸集的数学定义：

对于任意 x 1 , x 2 ∈ C \mathbf{x}_1,\mathbf{x}_2 \in C x1​,x2​∈C和任意 θ ∈ [ 0 , 1 ] \theta \in [0,1] θ∈[0,1]，如果有
θ x 1 + ( 1 − θ ) x 2 ∈ C \theta \mathbf{x}_1 + (1 - \theta) \mathbf{x}_2 \in C θx1​+(1−θ)x2​∈C
那么，集合 C C C是凸集。

x 1 , x 2 \mathbf{x}_1,\mathbf{x}_2 x1​,x2​都使用粗体，表示它们是多维向量，文档后面如果出现同样情况也是一样的意思。

对于凸集的判别直接使用上面的定义，下面举例说明。

凸集证明例子

例1：直线是凸集吗？

根据凸集在几何上的直观解释：集合中的任意两点，它们连线上的任意一点都在这个集合中。感觉直线是凸集，但我们需要数学的严谨证明。

w 1 x + w 2 y + b = 0 w_1 x + w_2 y + b = 0 w1​x+w2​y+b=0是二维坐标系 ( x , y ) (x,y) (x,y)中的一条直线，其中 w 1 , w 2 w_1,w_2 w1​,w2​是系数， b b b是截距，在 w 1 x + w 2 y + b = 0 w_1 x + w_2 y + b = 0 w1​x+w2​y+b=0上的点 ( x , y ) (x,y) (x,y)的集合是不是凸集？

是凸集。证明过程如下：

设定集合 C = { ( x , y ) ∣ w 1 x + w 2 y + b = 0 } C = \{ (x,y)|w_1 x + w_2 y + b = 0 \} C={(x,y)∣w1​x+w2​y+b=0}，对属于 C C C的任意两点 ( x 1 , y 1 ) , ( x 2 , y 2 ) (x_1,y_1),(x_2,y_2) (x1​,y1​),(x2​,y2​)，有
{ w 1 x 1 + w 2 y 1 + b = 0 w 1 x 2 + w 2 y 2 + b = 0 \left\{ \begin{aligned} w_1 x_1 + w_2 y_1 + b = 0 \\ w_1 x_2 + w_2 y_2 + b = 0 \end{aligned} \right. {w1​x1​+w2​y1​+b=0w1​x2​+w2​y2​+b=0​
对任意 θ ∈ [ 0 , 1 ] \theta \in [0,1] θ∈[0,1]，有
{ θ ( w 1 x 1 + w 2 y 1 + b ) = 0 ( 1 − θ ) ( w 1 x 2 + w 2 y 2 + b ) = 0 ⟹ 两 式 相 加   w 1 [ θ x 1 + ( 1 − θ ) x 2 ] + w 2 [ θ y 1 + ( 1 − θ ) y 2 ] + b = 0 \begin{aligned} &\left\{ \begin{aligned} \theta (w_1 x_1 + w_2 y_1 + b) &= 0 \\ (1-\theta) (w_1 x_2 + w_2 y_2 + b) &= 0 \end{aligned} \right. \\ \stackrel{两式相加}{\Longrightarrow}& \space w_1 [ \theta x_1 + (1-\theta) x_2 ] + w_2 [ \theta y_1 + (1-\theta) y_2 ] + b = 0 \end{aligned} ⟹两式相加​​{θ(w1​x1​+w2​y1​+b)(1−θ)(w1​x2​+w2​y2​+b)​=0=0​ w1​[θx1​+(1−θ)x2​]+w2​[θy1​+(1−θ)y2​]+b=0​
所以 ( θ x 1 + ( 1 − θ ) x 2 , θ y 1 + ( 1 − θ ) y 2 ) (\theta x_1 + (1-\theta) x_2, \theta y_1 + (1-\theta) y_2) (θx1​+(1−θ)x2​,θy1​+(1−θ)y2​)也在直线 w 1 x + w 2 y + b = 0 w_1 x + w_2 y + b = 0 w1​x+w2​y+b=0上，属于集合 C C C。

因此，集合 C = { ( x , y ) ∣ w 1 x + w 2 y + b = 0 } C = \{ (x,y)|w_1 x + w_2 y + b = 0 \} C={(x,y)∣w1​x+w2​y+b=0}是凸集，即直线是凸集。

超平面是凸集吗？答案是肯定的，具体证明如下。

假定 w , x \mathbf{w},\mathbf{x} w,x是n维向量， b b b是标量，那么 w T x + b = 0 \mathbf{w}^T \mathbf{x} + b = 0 wTx+b=0是n维空间中的超平面，证明在 w T x + b = 0 \mathbf{w}^T \mathbf{x} + b = 0 wTx+b=0上的点 x \mathbf{x} x的集合是凸集。

证明：设定集合 C = { x ∣ w T x + b = 0 } C = \{\mathbf{x}|\mathbf{w}^T \mathbf{x} + b = 0 \} C={x∣wTx+b=0}，对属于 C C C的任意两点 x 1 , x 2 \mathbf{x}_1, \mathbf{x}_2 x1​,x2​，有

{ w T x 1 + b = 0 w T x 2 + b = 0 \left\{ \begin{aligned} \mathbf{w}^T \mathbf{x}_1 + b = 0 \\ \mathbf{w}^T \mathbf{x}_2 + b = 0 \end{aligned} \right. {wTx1​+b=0wTx2​+b=0​
对任意 θ ∈ [ 0 , 1 ] \theta \in [0,1] θ∈[0,1]，有
{ θ ( w T x 1 + b ) = 0 ( 1 − θ ) ( w T x 2 + b ) = 0 ⟹ 两 式 相 加   w T [ θ x 1 + ( 1 − θ ) x 2 ] + b = 0 \begin{aligned} &\left\{ \begin{aligned} \theta (\mathbf{w}^T \mathbf{x}_1 + b) &= 0 \\ (1-\theta) (\mathbf{w}^T \mathbf{x}_2 + b) &= 0 \end{aligned} \right. \\ \stackrel{两式相加}{\Longrightarrow}& \space \mathbf{w}^T [ \theta \mathbf{x}_1 + (1-\theta) \mathbf{x}_2 ] + b = 0 \end{aligned} ⟹两式相加​​{θ(wTx1​+b)(1−θ)(wTx2​+b)​=0=0​ wT[θx1​+(1−θ)x2​]+b=0​
所以 θ x 1 + ( 1 − θ ) x 2 \theta \mathbf{x}_1 + (1-\theta) \mathbf{x}_2 θx1​+(1−θ)x2​也在直线 w T x + b = 0 \mathbf{w}^T \mathbf{x} + b = 0 wTx+b=0上，属于集合 C C C。

因此，集合 C = { x ∣ w T x + b = 0 } C = \{\mathbf{x}|\mathbf{w}^T \mathbf{x} + b = 0 \} C={x∣wTx+b=0}是凸集，即超平面是凸集。

以上例子得到的结论是：

对于函数 f ( x ) = w T x + b f(\mathbf{x}) = \mathbf{w}^T\mathbf{x} + b f(x)=wTx+b（这个一般叫作仿射函数），满足 f ( x ) = 0 f(\mathbf{x})=0 f(x)=0的点 x \mathbf{x} x的集合是凸集。

这个结论很重要，它告诉我们等式约束函数是仿射函数，即满足 h i ( x ) = w i T x + b i ,   i = 1 , 2 , ⋯   , N h_i(\mathbf{x}) = \mathbf{w}_i^T\mathbf{x} + b_i, \space i=1,2,\cdots,N hi​(x)=wiT​x+bi​, i=1,2,⋯,N，

优化问题的等式约束 h i ( x ) = 0 ,   i = 1 , 2 , ⋯   , N h_i(\mathbf{x}) = 0, \space i=1,2,\cdots,N hi​(x)=0, i=1,2,⋯,N规定的可行集是凸集。

我们得到第一个重要结论：等式约束函数是仿射函数，他规定的可行集是凸集。

你可能会问，等式约束函数是个曲线函数行不行？下面来看个例子。

例2：圆 x 2 + y 2 − 1 = 0 x^2 + y^2 - 1 = 0 x2+y2−1=0上的点的集合是不是凸集？

直观上感觉不是凸集，下面用数学定义来证明：

设定集合 C = { ( x , y ) ∣ x 2 + y 2 − 1 = 0 } C = \{(x,y)|x^2 + y^2 - 1 = 0\} C={(x,y)∣x2+y2−1=0}，对属于 C C C的任意两点 ( x 1 , y 1 ) , ( x 2 , y 2 ) (x_1,y_1),(x_2,y_2) (x1​,y1​),(x2​,y2​)，以及任意 θ ∈ [ 0 , 1 ] \theta \in [0,1] θ∈[0,1]，有
θ ( x 1 , y 1 ) + ( 1 − θ ) ( x 2 , y 2 ) ＝ ( θ x 1 + ( 1 − θ ) x 2 , θ y 1 + ( 1 − θ ) y 2 ) \theta (x_1,y_1) + (1 - \theta) (x_2,y_2) ＝ (\theta x_1+ (1 - \theta) x_2, \theta y_1+ (1 - \theta) y_2) θ(x1​,y1​)+(1−θ)(x2​,y2​)＝(θx1​+(1−θ)x2​,θy1​+(1−θ)y2​)
接着，计算：
[ θ x 1 + ( 1 − θ ) x 2 ] 2 + [ θ y 1 + ( 1 − θ ) y 2 ] 2 =   [ θ 2 x 1 2 + ( 1 − θ ) 2 x 2 2 + 2 θ ( 1 − θ ) x 1 x 2 ] + [ θ 2 y 1 2 + ( 1 − θ ) 2 y 2 2 + 2 θ ( 1 − θ ) y 1 y 2 ] =   θ 2 ( x 1 2 + y 1 2 ) + ( 1 − θ ) 2 ( x 2 2 + y 2 2 ) + 2 θ ( 1 − θ ) ( x 1 x 2 + y 1 y 2 ) \begin{aligned} &[\theta x_1+ (1 - \theta) x_2]^2 + [ \theta y_1+ (1 - \theta) y_2]^2 \\ = \space &[\theta^2 x_1^2 + (1 - \theta)^2 x_2^2 + 2\theta(1 - \theta) x_1 x_2] + [ \theta^2 y_1^2 + (1 - \theta)^2 y_2^2 + 2\theta(1 - \theta) y_1 y_2 ] \\ = \space &\theta^2 (x_1^2 + y_1^2) + (1 - \theta)^2 (x_2^2 + y_2^2) + 2\theta(1 - \theta) (x_1 x_2 + y_1 y_2) \end{aligned} = = ​[θx1​+(1−θ)x2​]2+[θy1​+(1−θ)y2​]2[θ2x12​+(1−θ)2x22​+2θ(1−θ)x1​x2​]+[θ2y12​+(1−θ)2y22​+2θ(1−θ)y1​y2​]θ2(x12​+y12​)+(1−θ)2(x22​+y22​)+2θ(1−θ)(x1​x2​+y1​y2​)​
根据已知条件
x 1 2 + y 1 2 = 1 x 2 2 + y 2 2 = 1 x_1^2 + y_1^2 = 1 \\ x_2^2 + y_2^2 = 1 x12​+y12​=1x22​+y22​=1
有
θ 2 ( x 1 2 + y 1 2 ) + ( 1 − θ ) 2 ( x 2 2 + y 2 2 ) + 2 θ ( 1 − θ ) ( x 1 x 2 + y 1 y 2 ) =   θ 2 + ( 1 − θ ) 2 + 2 θ ( 1 − θ ) ( x 1 x 2 + y 1 y 2 ) \begin{aligned} &\theta^2 (x_1^2 + y_1^2) + (1 - \theta)^2 (x_2^2 + y_2^2) + 2\theta(1 - \theta) (x_1 x_2 + y_1 y_2) \\ = \space &\theta^2 + (1 - \theta)^2 + 2\theta(1 - \theta) (x_1 x_2 + y_1 y_2) \end{aligned} = ​θ2(x12​+y12​)+(1−θ)2(x22​+y22​)+2θ(1−θ)(x1​x2​+y1​y2​)θ2+(1−θ)2+2θ(1−θ)(x1​x2​+y1​y2​)​
另外， x 1 x 2 + y 1 y 2 x_1 x_2 + y_1 y_2 x1​x2​+y1​y2​等效于向量 ( x 1 , x 2 ) (x_1, x_2) (x1​,x2​)和向量 ( y 1 , y 2 ) (y_1, y_2) (y1​,y2​)的数量积。

数量积的内容参考同济版高等数学的向量代数与空间解析几何，它的定义是：

对于两个向量 a , b \mathbf{a},\mathbf{b} a,b，它们的数量积是 a ⋅ b = ∣ a ∣ ∣ b ∣ cos ⁡ α \mathbf{a} \cdot \mathbf{b} = |\mathbf{a}||\mathbf{b}|\cos\alpha a⋅b=∣a∣∣b∣cosα。 α \alpha α是向量 a \mathbf{a} a和向量 b \mathbf{b} b之间的夹角。

所以
x 1 x 2 + y 1 y 2 = x 1 2 + y 1 2 ⋅ x 2 2 + y 2 2 cos ⁡ α ≤ cos ⁡ α ≤ 1 x_1 x_2 + y_1 y_2 = \sqrt{x_1^2+y_1^2} \cdot \sqrt{x_2^2+y_2^2} \cos\alpha \le \cos\alpha \le 1 x1​x2​+y1​y2​=x12​+y12​ ​⋅x22​+y22​ ​cosα≤cosα≤1
其中， α \alpha α是向量 ( x 1 , x 2 ) (x_1, x_2) (x1​,x2​)和向量 ( y 1 , y 2 ) (y_1, y_2) (y1​,y2​)之间的夹角，当前仅当 α \alpha α为0时取等号，即 ( x 1 , x 2 ) (x_1, x_2) (x1​,x2​)和 ( y 1 , y 2 ) (y_1, y_2) (y1​,y2​)两点重合时取等号。
θ 2 + ( 1 − θ ) 2 + 2 θ ( 1 − θ ) ( x 1 x 2 + y 1 y 2 ) ≤   θ 2 + ( 1 − θ ) 2 + 2 θ ( 1 − θ ) =   [ θ + ( 1 − θ ) ] 2 = 1 \begin{aligned} &\theta^2 + (1 - \theta)^2 + 2\theta(1 - \theta) (x_1 x_2 + y_1 y_2) \\ \le \space & \theta^2 + (1 - \theta)^2 + 2\theta(1 - \theta) \\ = \space & [\theta + (1 - \theta)]^2 = 1 \end{aligned} ≤ = ​θ2+(1−θ)2+2θ(1−θ)(x1​x2​+y1​y2​)θ2+(1−θ)2+2θ(1−θ)[θ+(1−θ)]2=1​
综上
[ θ x 1 + ( 1 − θ ) x 2 ] 2 + [ θ y 1 + ( 1 − θ ) y 2 ] 2 ≤ 1 [\theta x_1+ (1 - \theta) x_2]^2 + [ \theta y_1+ (1 - \theta) y_2]^2 \le 1 [θx1​+(1−θ)x2​]2+[θy1​+(1−θ)y2​]2≤1
由于 ( x 1 , x 2 ) (x_1, x_2) (x1​,x2​)和 ( y 1 , y 2 ) (y_1, y_2) (y1​,y2​)两点不重合，无法取到等号，所以 ( θ x 1 + ( 1 − θ ) x 2 , θ y 1 + ( 1 − θ ) y 2 ) (\theta x_1+ (1 - \theta) x_2, \theta y_1+ (1 - \theta) y_2) (θx1​+(1−θ)x2​,θy1​+(1−θ)y2​)不满足 x 2 + y 2 = 1 x^2 + y^2 = 1 x2+y2=1圆内，集合 C = { ( x , y ) ∣ x 2 + y 2 − 1 = 0 } C = \{(x,y)|x^2 + y^2 - 1 = 0 \} C={(x,y)∣x2+y2−1=0}不是凸集。

所以，曲线函数决定的可行集不是凸集。

凸集的交集还是凸集

上于的任意两个元素为，由于是所有凸集的交集，那么也必定属于那N个凸集的任意一个，即，根据凸集的定义，对任意有

现有N个凸集 S i ,   i = 1 , 2 , ⋯   , N S_i, \space i=1,2,\cdots,N Si​, i=1,2,⋯,N，它们的交集是 ⋂ i = 1 N S i \bigcap_{i=1}^N S_i ⋂i=1N​Si​。

假定属于 ⋂ i = 1 N S i \bigcap_{i=1}^N S_i ⋂i=1N​Si​的任意两个元素为 x 1 , x 2 \mathbf{x}_1, \mathbf{x}_2 x1​,x2​，由于 ⋂ i = 1 N S i \bigcap_{i=1}^N S_i ⋂i=1N​Si​是所有凸集的交集，那么 x 1 , x 2 \mathbf{x}_1, \mathbf{x}_2 x1​,x2​也必定属于那N个凸集的任意一个，即 x 1 , x 2 ∈ S i ,   i = 1 , 2 , ⋯   , N \mathbf{x}_1, \mathbf{x}_2 \in S_i, \space i=1,2,\cdots,N x1​,x2​∈Si​, i=1,2,⋯,N，根据凸集的定义，对任意 θ ∈ [ 0 , 1 ] \theta \in [0,1] θ∈[0,1]有
θ x 1 + ( 1 − θ ) x 2 ∈ S i ,   i = 1 , 2 , ⋯   , N \theta \mathbf{x}_1 + (1 - \theta) \mathbf{x}_2 \in S_i, \space i=1,2,\cdots,N θx1​+(1−θ)x2​∈Si​, i=1,2,⋯,N
也就是说 θ x 1 + ( 1 − θ ) x 2 \theta \mathbf{x}_1 + (1 - \theta) \mathbf{x}_2 θx1​+(1−θ)x2​属于每个凸集 S i ,   i = 1 , 2 , ⋯   , N S_i, \space i=1,2,\cdots,N Si​, i=1,2,⋯,N，所以它也属于交集 ⋂ i = 1 N S i \bigcap_{i=1}^N S_i ⋂i=1N​Si​，即
θ x 1 + ( 1 − θ ) x 2 ∈ ⋂ i = 1 N S i \theta \mathbf{x}_1 + (1 - \theta) \mathbf{x}_2 \in \bigcap_{i=1}^N S_i θx1​+(1−θ)x2​∈i=1⋂N​Si​
根据凸集的定义可以知道，交集 ⋂ i = 1 N S i \bigcap_{i=1}^N S_i ⋂i=1N​Si​是凸集。

这个结论非常有用，因为优化问题的约束条件往往有很多个：
{ h i ( x ) = 0 g j ( x ) ≤ 0 , i = 1 , 2 , ⋯   , N \left\{ \begin{aligned} h_i(\mathbf{x})=0 \\ g_j(\mathbf{x}) \le 0 \end{aligned}, i=1,2,\cdots,N\right. {hi​(x)=0gj​(x)≤0​,i=1,2,⋯,N
只要证明每个约束条件规定的可行集是凸集，那么所有约束条件共同决定的可行集就一定是凸集，这是第二个重要结论。

凸函数的数学判别方法

判别凸函数有3种方法：定义法、一阶条件法和二阶条件法，其中最好用的是二阶条件法。

下面对这3种方法一一介绍。

定义法

从定义来说，凸函数就是满足任意两点之间的函数值都在这两点连线之下的函数。

我们可以按照这个定义去证明凸函数：

假定函数 f f f的定义域记为 d o m f \mathbf{dom}f domf，如果 d o m f \mathbf{dom}f domf是凸集，且对任意 x , y ∈ d o m f \mathbf{x},\mathbf{y} \in \mathbf{dom}f x,y∈domf和任意 θ ∈ [ 0 , 1 ] \theta \in [0,1] θ∈[0,1]，都有 f ( θ x + ( 1 − θ ) y ) ≤ θ f ( x ) + ( 1 − θ ) f ( y ) f( \theta \mathbf{x} + (1-\theta) \mathbf{y} ) \le \theta f(\mathbf{x}) + (1-\theta) f(\mathbf{y}) f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)， f f f就是凸函数。

但是，如果函数非常复杂（特别是多维情况），这个不等式非常不好证明，所以一般不用定义法判别凸函数。

一阶条件法

一阶条件法原理的一个直观例子：

图中 f ( y ) f(y) f(y)是凸函数， ( x , f ( x ) ) (x,f(x)) (x,f(x))是函数的一个切点， F ( y ) = f ( x ) + f ′ ( x ) ( y − x ) F(y) = f(x) + f'(x) (y-x) F(y)=f(x)+f′(x)(y−x)是过切点的切线。

我们发现，凸函数上任意一点的切线都在凸函数曲线之下，这就是一阶条件法的原理，用数学来表达就是： f ( y ) ≥ f ( x ) + f ′ ( x ) ( y − x ) f(y) \ge f(x) + f'(x) (y-x) f(y)≥f(x)+f′(x)(y−x)。

扩展到多维情况，

f f f是凸函数的充要条件是：如果定义域 d o m f \mathbf{dom}f domf是凸集，对任意 x , y ∈ d o m f \mathbf{x},\mathbf{y} \in \mathbf{dom}f x,y∈domf，有
f ( y ) ≥ f ( x ) + ∇ f ( x ) T ( y − x ) f(\mathbf{y}) \ge f(\mathbf{x}) + \nabla f(\mathbf{x})^T (\mathbf{y}-\mathbf{x}) f(y)≥f(x)+∇f(x)T(y−x)
其中 ∇ = ∂ ∂ x \nabla = \frac{\partial }{\partial \mathbf{x}} ∇=∂x∂​。

只要看是否符合上面的充要条件，就能判断是不是凸函数，这就是一阶条件法。

使用一阶条件需要保证函数 f f f在开集定义域内可微。

一阶条件法和定义法是等效的，也就是互为充要条件，具体证明请看Stephen Boyd的Convex Optimization中的3.1.3节First-order conditions。

二阶条件法

定义

二阶条件法原理的一个直观例子：

函数 f ( x ) = x 2 + 5 x + 2 f(x) = x^2 + 5 x + 2 f(x)=x2+5x+2是凸函数（用一阶条件法来证明很简单，具体过程感兴趣的学员可以自己尝试完成），它的一阶导数和二阶导数如下：

可以发现，凸函数 f ( x ) f(x) f(x)的二阶导数 f ′ ′ ( x ) ≥ 0 f''(x) \ge 0 f′′(x)≥0。

这可以从一阶条件法来理解：

如果对任意 x x x和 y y y，要满足一阶条件 f ( y ) ≥ f ( x ) + f ′ ( x ) ( y − x ) f(y) \ge f(x) + f'(x) (y-x) f(y)≥f(x)+f′(x)(y−x)，根据 f ( y ) f(y) f(y)的泰勒展开二阶形式 f ( y ) = f ( x ) + f ′ ( x ) ( y − x ) + 1 2 f ′ ′ ( x ) ( y − x ) 2 f(y) = f(x) + f'(x) (y-x) + \frac{1}{2} f''(x) (y-x)^2 f(y)=f(x)+f′(x)(y−x)+21​f′′(x)(y−x)2，可以知道，必须要有 f ′ ′ ( x ) ( y − x ) 2 ≥ 0 f''(x) (y-x)^2 \ge 0 f′′(x)(y−x)2≥0，所以 f ′ ′ ( x ) ≥ 0 f''(x) \ge 0 f′′(x)≥0。

扩展到多维情况：

泰勒展开二阶形式 f ( y ) = f ( x ) + ∇ f ( x ) ( y − x ) + 1 2 ( y − x ) T ∇ 2 f ( x ) ( y − x ) f(\mathbf{y}) = f(\mathbf{x}) + \nabla f(\mathbf{x}) (\mathbf{y}-\mathbf{x}) + \frac{1}{2} (\mathbf{y}-\mathbf{x})^T \nabla^2 f(\mathbf{x}) (\mathbf{y}-\mathbf{x}) f(y)=f(x)+∇f(x)(y−x)+21​(y−x)T∇2f(x)(y−x)，对任意 x \mathbf{x} x和 y \mathbf{y} y，要满足一阶条件 f ( y ) ≥ f ( x ) + ∇ f ( x ) ( y − x ) f(\mathbf{y}) \ge f(\mathbf{x}) + \nabla f(\mathbf{x}) (\mathbf{y}-\mathbf{x}) f(y)≥f(x)+∇f(x)(y−x)，必须要有 ( y − x ) T ∇ 2 f ( x ) ( y − x ) ≥ 0 (\mathbf{y}-\mathbf{x})^T \nabla^2 f(\mathbf{x}) (\mathbf{y}-\mathbf{x}) \ge 0 (y−x)T∇2f(x)(y−x)≥0，即 ∇ 2 f ( x ) \nabla^2 f(\mathbf{x}) ∇2f(x)是半正定矩阵。

正定矩阵的定义可以参考同济版线性代数第五章相似矩阵及二次型：

一个常用的判定矩阵正定的方法是：

半正定矩阵就是把正定矩阵定义里的 f ( x ) > 0 f(\mathbf{x}) \gt 0 f(x)>0改成 f ( x ) ≥ 0 f(\mathbf{x}) \ge 0 f(x)≥0。

相应地，判定半正定的方法是：矩阵特征值都是非负的。

综上， f f f是凸函数的充要条件：如果定义域 d o m f \mathbf{dom}f domf是凸集，对任意 x ∈ d o m f \mathbf{x} \in \mathbf{dom}f x∈domf，有 ∇ 2 f ( x ) \nabla^2 f(\mathbf{x}) ∇2f(x)是半正定矩阵。

矩阵 ∇ 2 f ( x ) \nabla^2 f(\mathbf{x}) ∇2f(x)一般被称作Hessian矩阵。

只要看是否符合上面的充要条件，就能判断是否为凸函数，这就是二阶条件法。

使用二阶条件法需要保证函数 f f f在开集定义域内二阶可微。

例子

给两个二阶条件法的简单例子：

• f ( x , y ) = x 2 + y 2 f(x,y) = x^2 + y^2 f(x,y)=x2+y2是不是凸函数？

  f ( x , y ) f(x,y) f(x,y)的定义域 d o m f \mathbf{dom}f domf是二维空间 R 2 \mathbf{R}^2 R2，是凸集。

  直接计算它的Hessian矩阵
  ∇ 2 f ( x , y ) = [ ∂ 2 f ( x , y ) ∂ x 2 ∂ 2 f ( x , y ) ∂ x ∂ y ∂ 2 f ( x , y ) ∂ x ∂ y ∂ 2 f ( x , y ) ∂ y 2 ] = [ 2 0 0 2 ] \nabla^2 f(x,y) = \left[ \begin{array}{cc} \frac{\partial^2 f(x,y)}{\partial x^2} & \frac{\partial^2 f(x,y)}{\partial x \partial y} \\ \frac{\partial^2 f(x,y)}{\partial x \partial y} & \frac{\partial^2 f(x,y)}{\partial y^2} \end{array} \right] = \left[ \begin{array}{cc} 2 & 0 \\ 0 & 2 \end{array} \right] ∇2f(x,y)=[∂x2∂2f(x,y)​∂x∂y∂2f(x,y)​​∂x∂y∂2f(x,y)​∂y2∂2f(x,y)​​]=[20​02​]
  Hessian矩阵的特征值都是非负的， f ( x , y ) f(x,y) f(x,y)是凸函数。

  下面给出 f ( x , y ) f(x,y) f(x,y)的函数图：

  

• f ( x , y ) = x 2 − y 2 f(x,y) = x^2 - y^2 f(x,y)=x2−y2是不是凸函数？

  直接计算它的Hessian矩阵
  ∇ 2 f ( x , y ) = [ ∂ 2 f ( x , y ) ∂ x 2 ∂ 2 f ( x , y ) ∂ x ∂ y ∂ 2 f ( x , y ) ∂ x ∂ y ∂ 2 f ( x , y ) ∂ y 2 ] = [ 2 0 0 − 2 ] \nabla^2 f(x,y) = \left[ \begin{array}{cc} \frac{\partial^2 f(x,y)}{\partial x^2} & \frac{\partial^2 f(x,y)}{\partial x \partial y} \\ \frac{\partial^2 f(x,y)}{\partial x \partial y} & \frac{\partial^2 f(x,y)}{\partial y^2} \end{array} \right] = \left[ \begin{array}{cc} 2 & 0 \\ 0 & -2 \end{array} \right] ∇2f(x,y)=[∂x2∂2f(x,y)​∂x∂y∂2f(x,y)​​∂x∂y∂2f(x,y)​∂y2∂2f(x,y)​​]=[20​0−2​]
  Hessian矩阵的特征值有负数， f ( x , y ) f(x,y) f(x,y)不是凸函数。

  下面给出 f ( x , y ) f(x,y) f(x,y)的函数图：

  
  上图是一个马鞍图，其特点是在一个维度上只有极大值没有极小值，而在另一个维度上有极小值没有极大值。

下水平集（Sublevel Sets）

前面关于凸集的重要结论：

• 等式约束的可行集是凸集，必须满足：等式约束函数是仿射函数。
• 根据凸集的交集还是凸集，只要证明每个约束条件规定的可行集是凸集，那么所有约束条件共同决定的可行集就一定是凸集。

聪明的你可能发现了，还没有说明不等式约束的可行集是凸集需要满足什么条件，不着急，在此之前先来了解一个概念——下水平集。

什么是下水平集？先来看一个直观的例子：

在 f ( x ) f(x) f(x)曲线上，画一条横线 f ( x ) = α f(x) = \alpha f(x)=α，那么横线以下部分的 f ( x ) f(x) f(x)曲线所对应的定义域就是 f ( x ) f(x) f(x)的 α \alpha α下水平集；要是画一条横线 f ( x ) = β f(x) = \beta f(x)=β，横线以下曲线所对应的定义域就是 f ( x ) f(x) f(x)的 β \beta β下水平集。

可见，下水平集与所设的阈值有关，函数 f ( x ) f(\mathbf{x}) f(x)的 α \alpha α下水平集一般用下面的数学式表示
C α = { x ∈ d o m f ∣ f ( x ) ≤ α } C_\alpha = \{\mathbf{x} \in \mathbf{dom} f|f(\mathbf{x}) \le \alpha \} Cα​={x∈domf∣f(x)≤α}
α \alpha α下水平集合有一个非常重要的性质：对任意 α \alpha α，凸函数的 α \alpha α下水平集是凸集。

性质的证明：

假定凸函数 f ( x ) f(\mathbf{x}) f(x)的 α \alpha α下水平集是 C α C_\alpha Cα​。

对于任意 x , y ∈ C α \mathbf{x}, \mathbf{y} \in C_\alpha x,y∈Cα​，有 f ( x ) ≤ α , f ( y ) ≤ α f(\mathbf{x}) \le \alpha, f(\mathbf{y}) \le \alpha f(x)≤α,f(y)≤α。

因为 f ( x ) f(\mathbf{x}) f(x)是凸函数，对任意 θ ∈ [ 0 , 1 ] \theta \in [0,1] θ∈[0,1]，有
f ( θ x + ( 1 − θ ) y ) ≤ θ f ( x ) + ( 1 − θ ) f ( y ) ≤ θ α + ( 1 − θ ) α = α \begin{aligned} f(\theta \mathbf{x} + (1-\theta) \mathbf{y}) &\le \theta f(\mathbf{x}) + (1-\theta) f(\mathbf{y}) \\ & \le \theta \alpha + (1-\theta) \alpha = \alpha \end{aligned} f(θx+(1−θ)y)​≤θf(x)+(1−θ)f(y)≤θα+(1−θ)α=α​
所以， θ x + ( 1 − θ ) y ∈ C α \theta \mathbf{x} + (1-\theta) \mathbf{y} \in C_\alpha θx+(1−θ)y∈Cα​。根据定义， C α C_\alpha Cα​是凸集。

根据这条性质，我们有以下推论
{ g j ( x ) ≤ 0 的 可 行 域 是 g j ( x ) 的 0 下 水 平 集 g j ( x ) 是 凸 函 数 ⟹ 下 水 平 集 的 性 质 g j ( x ) ≤ 0 的 可 行 域 是 凸 集 \begin{aligned} &\left\{ \begin{aligned} &g_j(\mathbf{x}) \le 0 的可行域是 g_j(\mathbf{x}) 的0下水平集 \\ &g_j(\mathbf{x})是凸函数 \end{aligned} \right. \\ \stackrel{下水平集的性质}{\Longrightarrow} \quad &g_j(\mathbf{x}) \le 0的可行域是凸集 \end{aligned} ⟹下水平集的性质​​{​gj​(x)≤0的可行域是gj​(x)的0下水平集gj​(x)是凸函数​gj​(x)≤0的可行域是凸集​
得到的结论是：如果不等式约束函数是凸函数，那么不等式约束的可行集是凸集。

所以，不等式约束的可行集是凸集需要满足的条件是：不等式约束函数是凸函数。这是第三个重要结论。

总结

综上，凸优化这部分内容可以总结为下面这张图：

由此得到我们的结论，判定一个优化问题是凸优化问题的条件是：目标函数和不等式约束函数是凸函数，等式约束函数是仿射函数。

凸优化问题的例子

来看一个例子，已知N维列向量 x i = [ x i 1 x i 2 ⋮ x i N ] \mathbf{x}_i = \left[ \begin{array}{c} x_{i1} \\ x_{i2} \\ \vdots \\ x_{iN} \end{array} \right] xi​=⎣⎢⎢⎢⎡​xi1​xi2​⋮xiN​​⎦⎥⎥⎥⎤​，标量 y i y_i yi​和标量 b b b（都是常数）， w = [ w 1 w 2 ⋮ w N ] \mathbf{w} = \left[ \begin{array}{c} w_1 \\ w_2 \\ \vdots \\ w_N \end{array} \right] w=⎣⎢⎢⎢⎡​w1​w2​⋮wN​​⎦⎥⎥⎥⎤​是未知参数，它也是一个N维列向量。

要通过下面的优化问题求未知参数 w \mathbf{w} w：
min ⁡ w f ( w ) = 1 2 w T w = 1 2 ∑ i = 1 N w i 2 s . t . y i ( w T x i + b ) ≥ 1 ,   i = 1 , 2 , ⋯   , M \begin{aligned} & \min_{\mathbf{w}} f(\mathbf{w}) = \frac{1}{2} \mathbf{w}^T \mathbf{w} = \frac{1}{2} \sum_{i=1}^N w_i^2 \\ s.&t. \quad y_i(\mathbf{w}^T\mathbf{x}_i+b) \ge 1, \space i = 1,2,\cdots,M \end{aligned} s.​wmin​f(w)=21​wTw=21​i=1∑N​wi2​t.yi​(wTxi​+b)≥1, i=1,2,⋯,M​
现在想知道，这个优化问题是凸优化问题吗？

解：先把优化问题化成标准形式
min ⁡ w f ( w ) = 1 2 w T w = 1 2 ∑ i = 1 N w i 2 s . t . − y i w T x i − y i b + 1 ≤ 0 ,   i = 1 , 2 , ⋯   , M \begin{aligned} & \min_{\mathbf{w}} f(\mathbf{w}) = \frac{1}{2} \mathbf{w}^T \mathbf{w} = \frac{1}{2} \sum_{i=1}^N w_i^2 \\ s.t. &\quad - y_i \mathbf{w}^T \mathbf{x}_i - y_i b + 1 \le 0, \space i = 1,2,\cdots,M \end{aligned} s.t.​wmin​f(w)=21​wTw=21​i=1∑N​wi2​−yi​wTxi​−yi​b+1≤0, i=1,2,⋯,M​

下面计算目标函数 f ( w ) f(\mathbf{w}) f(w)的Hessian矩阵，首先算一次求导：
J = ∂ f ∂ w = [ ∂ f ∂ w 1 ∂ f ∂ w 2 ⋯ ∂ f ∂ w N ] J = \frac{\partial f}{\partial \mathbf{w}} = \left[ \begin{array}{ccc} \frac{\partial f}{\partial w_1} & \frac{\partial f}{\partial w_2} & \cdots & \frac{\partial f}{\partial w_N} \end{array} \right] J=∂w∂f​=[∂w1​∂f​​∂w2​∂f​​⋯​∂wN​∂f​​]
根据之前矩阵求导的规则：向量对向量求导，一般规定：求导矩阵的第一个维度以分子为准，第二个维度以分母为准。所以二次求导为：
∇ 2 f = ∂ J ∂ w = [ ∂ 2 f ∂ w 1 2 ∂ 2 f ∂ w 1 ∂ w 2 ⋯ ∂ 2 f ∂ w 1 ∂ w N ∂ 2 f ∂ w 2 ∂ w 1 ∂ 2 f ∂ w 2 2 ⋯ ∂ 2 f ∂ w 2 ∂ w N ⋮ ⋮ ⋱ ⋮ ∂ 2 f ∂ w N ∂ w 1 ∂ 2 f ∂ w N ∂ w 2 ⋯ ∂ 2 f ∂ w N 2 ] = [ 1 0 ⋯ 0 0 1 ⋯ 0 ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ 1 ] \begin{aligned} \nabla^2 f &= \frac{\partial J}{\partial \mathbf{w}} = \left[ \begin{array}{ccc} \frac{\partial^2 f}{\partial w_1^2} & \frac{\partial^2 f}{\partial w_1 \partial w_2} & \cdots & \frac{\partial^2 f}{\partial w_1 \partial w_N} \\ \frac{\partial^2 f}{\partial w_2 \partial w_1} & \frac{\partial^2 f}{\partial w_2^2} & \cdots & \frac{\partial^2 f}{\partial w_2 \partial w_N} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^2 f}{\partial w_N \partial w_1} & \frac{\partial^2 f}{\partial w_N \partial w_2} & \cdots & \frac{\partial^2 f}{\partial w_N^2} \end{array} \right] \\ &= \left[ \begin{array}{ccc} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{array} \right] \\ \end{aligned} ∇2f​=∂w∂J​=⎣⎢⎢⎢⎢⎢⎡​∂w12​∂2f​∂w2​∂w1​∂2f​⋮∂wN​∂w1​∂2f​​∂w1​∂w2​∂2f​∂w22​∂2f​⋮∂wN​∂w2​∂2f​​⋯⋯⋱⋯​∂w1​∂wN​∂2f​∂w2​∂wN​∂2f​⋮∂wN2​∂2f​​⎦⎥⎥⎥⎥⎥⎤​=⎣⎢⎢⎢⎡​10⋮0​01⋮0​⋯⋯⋱⋯​00⋮1​⎦⎥⎥⎥⎤​​
由于
∂ 2 f ∂ w k 2 = ∂ ( 1 2 ∑ i = 1 N w i 2 ) / ∂ w k 2 = ∂ ( 1 2 w k 2 ) / ∂ w k 2 = 1 , k = 1 , 2 , ⋯   , N ∂ 2 f ∂ w k ∂ w q = ∂ ( 1 2 ∑ i = 1 N w i 2 ) / ∂ w k ∂ w q = ∂ ( 1 2 w k 2 ) / ∂ w k ∂ w q = ∂ w k / ∂ w q = 0 , k , q = 1 , 2 , ⋯   , N 且 k ≠ q \frac{\partial^2 f}{\partial w_k^2} = \partial(\frac{1}{2} \sum_{i=1}^N w_i^2)/\partial w_k^2 = \partial(\frac{1}{2} w_k^2)/\partial w_k^2 = 1, \quad k=1,2,\cdots,N \\ \frac{\partial^2 f}{\partial w_k \partial w_q} = \partial(\frac{1}{2} \sum_{i=1}^N w_i^2)/\partial w_k \partial w_q = \partial(\frac{1}{2} w_k^2)/\partial w_k \partial w_q = \partial w_k/\partial w_q = 0, \quad k,q=1,2,\cdots,N且k \ne q \\ ∂wk2​∂2f​=∂(21​i=1∑N​wi2​)/∂wk2​=∂(21​wk2​)/∂wk2​=1,k=1,2,⋯,N∂wk​∂wq​∂2f​=∂(21​i=1∑N​wi2​)/∂wk​∂wq​=∂(21​wk2​)/∂wk​∂wq​=∂wk​/∂wq​=0,k,q=1,2,⋯,N且k​=q
所以
∇ 2 f = [ 1 0 ⋯ 0 0 1 ⋯ 0 ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ 1 ] \begin{aligned} \nabla^2 f = \left[ \begin{array}{ccc} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{array} \right] \\ \end{aligned} ∇2f=⎣⎢⎢⎢⎡​10⋮0​01⋮0​⋯⋯⋱⋯​00⋮1​⎦⎥⎥⎥⎤​​
Hessian矩阵 ∇ 2 f \nabla^2 f ∇2f的特征值非负，是半正定矩阵，所以目标函数 f ( w ) f(\mathbf{w}) f(w)是凸函数。

这里没有等式约束，只有M个不等式约束函数：
g i ( w ) = − y i w T x i − y i b + 1 = − y i ∑ k = 1 N w k x i k − y i b + 1 , i = 1 , 2 , ⋯   , M \begin{aligned} g_i(\mathbf{w}) &= - y_i \mathbf{w}^T \mathbf{x}_i - y_i b + 1 \\ &= - y_i \sum_{k=1}^N w_k x_{ik} - y_i b + 1, \quad i = 1,2,\cdots,M \end{aligned} gi​(w)​=−yi​wTxi​−yi​b+1=−yi​k=1∑N​wk​xik​−yi​b+1,i=1,2,⋯,M​
根据之前的矩阵求导知识，显然有，Hessian矩阵 ∇ 2 g i ( w ) = 0 \nabla^2 g_i(\mathbf{w}) = 0 ∇2gi​(w)=0，也就是特征值非负，是半正定矩阵，所以M个不等式约束函数是凸函数。

根据凸优化问题的判定条件，题中的优化问题是一个凸优化问题。

实际上，这个问题就是线性可分支持向量机的优化问题。