最优化模型与算法-基于Python实现 课件 第1、2章 凸集合、凸函数

凸集合最优化模型与算法——基于Python实现第一章01仿射集、凸集和凸锥直线与线段是我们熟悉的几何对象。如何对其定义呢？我们沿用解析几何的思想，给出直线与线段的概念。设

为空间

中的两个点，那么具有下列形式的点

(1.1.1)

构成一条过

和

的直线。参数

对应

，

对应

。参数

的值在0和1之间变动，

的轨迹构成了

和

之间的(闭)线段。的表示形式给出了直线的另一种解释，如图1.1.1所示：是基点(对应)和方向(由指向)乘以参数的和。因此，给出了在由向方向上的位置。当由0增加到1时，点相应地由移动到。如果，点在为端点的射线上。图1.1.1直线的几何解释1.1.1直线与线段设集合，如果过中任意两个不同点的直线仍然在集合中，则称集合是仿射集。也就是说，是仿射的等价于：对于任意及，有即仿射集中任意两点的系数之和为1的线性组合仍包含在中。明显地，直线与平面都是仿射集。仿射集合的概念也可以扩展到多个点的情况。如果

我们称具有

形式的点为

的仿射组合。利用仿射集合的定义(即仿射集合包含其中任意两点的仿射组合)，我们可以归纳出以下结论：一个仿射集包含其中任意点的仿射组合，即如果是一个仿射集，并且那么仍然在中。1.1.2仿射集特别地，如果一个仿射集经过原点，那么称该集合为子空间，即如果是一个仿射集并且，则集合(1.1.3)是一个子空间。子空间的一个重要性质是关于加法和数乘是封闭的。为说明这一点，设，

，则有

。因为

是仿射的，且

，所以(1.1.4)。由，可知。因此仿射集合

可以表示为(1.1.5)即一个子空间加上一个偏移向量。与仿射集相关联的子空间与的选取无关，所以可以是中的任意一点。我们定义仿射集的维数为子空间的维数，其中是中的任意元素。1.1.2仿射集下面给出仿射集的一个例子。例

1.1.1线性方程组的解集。考虑线性方程组的解集，其中，，则是一个仿射集。为证明这点，设，，即则对于任意，有(1.1.6)这表明任意的仿射组合也在中，并且与仿射集相关联的子空间就是的零空间。既然线性方程组的解集是空间中的一个仿射集，那么空间中的任意仿射集是否都可以表示为某个线性方程组的解集？如果该命题成立，那么我们便得到了空间中仿射集的代数描述。该命题是成立的，证明可参见[2]定理1.3。设是两个不同的点，那么包含和的最小的仿射集是什么？答案是由和所确定的直线。这个问题蕴含着仿射包的概念。由集合中的点的所有仿射组合组成的集合称为的仿射包，记为(1.1.7)仿射包是包含的最小的仿射集合：如果是满足的仿射集合，那么。1.1.2仿射集如果集合的仿射维数小于n，那么这个集合的仿射集合。集合相对于的内部称为集合相对内部，记为，即(1.1.8)

其中，即半径为r，中心为x并由范数定义的球(这里的可以是任意范数，并且所有范数定义了相同的相对内部)。进一步可以定义集合的相对边界为，此处表示的闭包。集合的仿射包的维数称为集合的仿射维数。仿射维数在凸分析及凸优化中非常有用，然而它与经典维数的定义不一致。例如，上的单位圆环的仿射包是全空间，所以其仿射维数为2。但在其他大多数维数的定义下，上的单位圆环的维数为1。1.1.3仿射维数与相对内部例1.1.2考虑中位于平面的一个正方形：(1.1.9)其仿射包为-平面，即的内部为空，但其相对内部为(1.1.10)的边界是其自身，而相对边界是(1.1.11)1.1.3仿射维数与相对内部上一小节介绍的仿射集是一类特殊的凸集合。下面介绍一般的凸集合的概念。如果集合中任意两点间的线段仍然在中，则称集合为凸集合，即对任意和满足的都有

(1.1.12)直观地理解，如果集合中的每一点都可以被其他点沿着它们之间一条“无阻碍”的路径看见，那么这个集合就是凸集合。“无阻碍”是指整条路径都在集合中。由于仿射集包含穿过集合中任意不同两点的整条直线，任意不同两点间的线段自然也在集合中。因而仿射集是凸集合。1.1.4凸集合图1.1.2一些简单凸集和非凸集1.1.4凸集合图1.1.2

显示了

空间中一些简单的凸集合和非凸集合。其中，左边的菱形集合，包括它的边界是凸集合，中间的心形集合不是凸集合，因为集合中显示为点的两点之间的线段不包含在集合中，右边的正方形包含一些边界点而不包含其他边界点，不是凸集合。我们称点

为点

的一个凸组合，其中

并

。与仿射集合类似，一个集合是凸集合等价于集合包含其中所有点的凸组合。点的凸组合可以看做它们的加权平均，

代表

的权重。设

是两个不同的点，那么包含

和

的最小的凸集是什么？答案是以

和

为端点的线段。这个问题蕴含着凸包的概念。集合

的凸包，记为

，定义如下：(1.1.13)顾名思义，凸包是凸集合，它是包含集合的最小的凸集。也就是说，如果是包含的凸集，那么。图1.1.3展示了凸包的概念，其中左边的六边形(含内部)是十五个点的凸包，右边的肾形集合也是非凸集，其凸包是肾形集合(连同内部)和阴影部分共同构成的集合。1.1.4凸集合图1.1.3

中两个集合的凸包010203041.1.4凸集合凸集合的概念可以推广到包括无限级数、积分以及一般形式的概率分布。假设

，满足(1.1.14)并且，其中为凸集。那么，如果级数收敛，我们有(1.1.15)假设对所有满足，并且，其中是凸集。那么，如果下面的积分存在，我们就有(1.1.16)最一般的情况，设

是凸集，

是随机变量，并且

的概率为1，那么

。事实上，这一形式包含了前述的特殊情况。例如，假设随机变量

只在

和

中取值，其概率分别是

和

其中

。于是，

，

即退化为两个点的凸组合。1.1.5凸锥考虑从原点出发，经过某一定点x的射线。它具有一项重要的特性，即对任意

，

依然包含于该射线中。这一例子蕴含着锥的概念。如果对于任意

和

都有

，称集合

是锥。如果集合

是锥，并且是凸集合，则称

为凸锥，即对于任意

和

，都有(1.1.17)在几何上，具有此类形式的点构成了二维的扇形，如图1.1.4所示，这个扇形以0为顶点，边是过和的射线，包含所有具有形如的点，其中。图1.1.4二维扇形1.1.5凸锥具有

形式的点称为

的锥组合(或非负线性组合)。如果

均属于凸锥

，那么，

的每一个锥组合也在

中。实际上，集合

是凸锥的充要条件，是它包含其元素的所有锥组合。集合中元素的所有锥组合的集合称为集合的锥包，即

(1.1.18)集合的锥包是包含的最小的凸锥。图1.1.5展示了两个集合的锥包，左边的集合由若干离散的点构成，右边的集合是一个肾形区域。图1.1.5锥包02凸函数的示例1.2.1超平面和半空间超平面三维欧氏空间

中的一个平面可以表示为

，

其中

，

R。推广至维n维欧氏空间

便得到了超平面的概念。超平面是具有下面形式的集合(1.2.1)其中，且。超平面是关于x的非平凡线性方程的解空间，因此是一个仿射集。几何上，超平面可以解释为与给定向量a的内积为常数的点的集合，也可以看成法线方向为a的超平面。常数决定了平面从原点的偏移量。可以将超平面表示成下面的形式(1.2.2)其中是超平面上任意满足的点。进一步，可以表示为(1.2.3)这里表示的正交补，即与正交的向量的集合(1.2.4)从上式可知，超平面由偏移加上所有正交于法向量的向量构成。1.2.1超平面和半空间半空间一个超平面将

划分为两个半空间。闭的半空间是具有下列形式的集合，

(1.2.5)它是一个非平凡的线性不等式的解空间，其中

。半空间是凸的，但不是仿射的。半空间(1.2.5)也可表示为

(1.2.6)其中

是相应超平面上的任意一点，即

满足

，表达式(1.2.6)有明显的几何解释：半空间由

加上任意与(向外的)法向量

呈钝角(或直角)的向量组成。半空间(1.2.5)的边界是超平面

。集合

是半空间

的内部，称为开半空间。1.2.2欧氏球和椭球欧氏球

中的空间欧氏球(简称球)具有下面的形式(1.2.7)其中，表示欧几里得范数，即。向量是球心，标量为半径。由距离球心距离不超过的所有点组成。欧氏球的另一个常见的表达式为(1.2.8)欧氏球是凸集，即如果，并且，那么

(1.2.9)欧氏球对应于欧几里得范数。如果将欧几里得范数进行拓展，相应地可得到欧氏球的拓展—椭球。椭球椭球是凸集合，是欧氏球的拓展，具有如下形式(1.2.10)其中，即是对称正定矩阵。向量为椭球的中心。椭球的半轴长度为，这里为的特征值。球可以看成时的椭球。椭球另一个常用的表示形式是(1.2.11)其中是对称正定阵。取，则表达式等价于(1.2.10)式。当式(1.2.11)中的矩阵为对称半正定矩阵，且为奇异矩阵时，集合(1.2.11)称为退化的椭球，其仿射维数等于的秩。退化的椭球也是凸的。非退化的椭球联系于一个新的范数，那任意一个范数是否也对应一个几何对象“球”呢？答案是肯定的，这便是范数球。1.2.2欧氏球和椭球设

为

空间的某一范数，则以为半径，

为球心的

集合称为范数球。明显地，范数球是凸的。空间的每一个范数实际上还对应一个锥。集合(1.2.12)称为关于范数的范数锥。明显地，它是一个凸锥。1.2.3范数球和范数锥1.2.4多面体上面的小节介绍了多面体和超平面的概念，再由交运算便可以得到多面体。有限个线性等式和不等式的解集称为多面体，即

(1.2.13)可见，多面体是有限个半空间和超平面的交集。可以使用紧凑表达式(1.2.14)来表示(1.2.5)式。其中(1.2.15)此处的表示上的分量不等式，即表示。上面小节中介绍了若干空间中凸集合的例子。下面的例子给出了矩阵空间中的一个凸集合。用表示对称矩阵的集合，即(1.2.16)这是一个维数为的向量空间。我们用表示对称半正定矩阵的集合，即(1.2.17)用表示对称正定矩阵的集合，即(1.2.18)这些符号与相对应，即表示非负实数，而表示正实数。集合是一个凸锥：如果并且，那么。依据半正定矩阵的定义可以直接验证这个结论：对于任意，如果并且

，那么，我们有(1.2.19)1.2.5半正定锥03保持凸性的运算交集运算保持凸性：如果和是凸集，那么也是凸集。这个性质可以扩展到无穷个集合的交集：定理1.3.1如果对于任意，都是凸的，那么也是凸集。特别地，子空间、仿射集合和凸锥对于任意交运算也是封闭的。举一个简单的例子，多面体是半空间和超平面(它们都是凸集)的交集，因而是凸的。例1.3.1半正定锥可以表示为(1.3.1)对于任意是关于的(不恒等于零的)线性函数，因此集合(1.3.2)实际上就是中的半空间。由此可见，半正定锥是无穷个半空间的交集，因此是凸集合。1.3.1交集一个凸集合在何种变换之下可以依然保持凸性。这样的变换有多种，应用最广泛的是仿射变换。定理1.3.2如果是一个线性变换和常数的和，则称函数是仿射变换。即具有的形式，其中。假设是凸集合，并且函数是仿射变换，那么，在下的像集(1.3.3)也是凸集合。类似地，如果是仿射函数，那么在下的原像(1.3.4)也是凸集合。1.3.2仿射变换(4)部分和。下面的集合称为的部分和：(1.3.8)其中，。当m=0时，部分和退化为和的交集；当n=0时，部分和等于。可以验证，两个凸集合的部分和仍是凸集合。下面仅验证(3)中集合的和的凸性。的凸性可以直接通过凸集合的定义证明。此外，还可以通过下面的方法证明这个结论：如果和是凸集合，那么其直积(也称为Cartesian乘积)(1.3.9)也是凸集。例1.3.2此例给出若干凸集合在仿射变换下的像集(1)伸缩和平移。如果是凸集，并且那么集合和是凸集合，其中(1.3.5)(2)一个凸集合向它的某几个坐标的投影仍是凸集合，即如果是凸集合，那么(1.3.6)也是凸集合。(3)两个集合的和定义为(1.3.7)如果和是凸集，那么也是凸集合。1.3.2仿射变换这个集合在仿射变换下的像是。这种证明手法具有代表性，请读者自行构造恰当的仿射变换，证明其余的集合的凸性。实际上，许多重要的凸集合都可以使用上面的方法来验证其凸性。举例如下。例1.3.3多面体多面体是凸集合。因为它可以表示为非负象限和原点的Cartesian乘积在仿射函数下的原像，即(1.3.10)例1.3.4线性矩阵不等式的解。条件(1.3.11)称为关于x的线性矩阵不等式(LMI)，其中，。线性矩阵不等式的解是凸集合。事实上，它是半正定锥在仿射映射下的原像。例1.3.5双曲锥。集合(1.3.12)是凸集，其中。因为它是二阶锥(1.3.13)在仿射函数下的原像。1.3.2仿射变换04支撑超平面1.4支撑超平面前面介绍的凸集合的概念是借助凸集合内的点进行刻画的，另外，凸集合还可以从外部借助支撑超平面来刻画。同时，支撑超平面与下一章要介绍的凸函数的次微分联系紧密。设，是其边界上的一点，即(1.4.1)如果，并且对任意满足，那么称超平面为集合在点处的支撑超平面，即与集合被超平面分离。其几何解释如图1.4.1所示：超平面与相切于点，而且半空间包含。图1.4.1超平面

在

处支撑1.4支撑超平面一个基本的结论是支撑超平面定理：对于任意非空的凸集和任意，在处存在的支撑超平面。支撑超平面定理的证明本质上依赖于凸集合分离定理。有兴趣的读者可以参见文献[2]中推论11.6.2。一件引人注意的事情是支撑超平面定理的逆命题。当集合满足一定条件时，支撑超平面定理的逆命题也成立：如果一个集合是闭的，具有非空内部，并且其边界上每个点均存在支撑超平面，那么它是凸集合。该命题给出了凸集的另一种刻画方式。05对偶锥许多数学运算及几何形体都是成对出现的。例如，加法和减法互为逆运算，指数和对数互为反函数。前文介绍的凸锥也是成对出现的，这便是本节要介绍的对偶锥。令为一个锥。集合被称为的对偶锥。顾名思义，是一个锥，即使原来的锥不是凸的，也总是凸的。几何上，当且仅当是支撑原点的超平面的法线。如图1.5.1所示，左图中，法线向内的半空间包含锥，所以。右图中，法线向内的半空间不包含，所以。1.5对偶锥图1.5.1对偶锥1.5对偶锥下面给出几个常见的锥的对偶锥。例1.5.1子空间是一个锥。它的对偶锥是其正交补例1.5.2非负卦限。锥的对偶锥是它本身(1.5.1)我们称这种锥为自对偶锥。例1.5.3半正定锥。记对称矩阵的集合为，我们使用其标准内积半正定锥是自对偶的，即对于任意的，(1.5.2)下面，我们证明这一结论。假设，那么存在使(1.5.3)因此，正半定矩阵满足，由此可知。假设，我们可以利用特征值分解将分解为，其中特征值。于是，我们有(1.5.4)例1.5.4范数锥的对偶。令为定义在上的范数。与之相关的锥的对偶锥由其对偶范数定义，(1.5.5)这里的对偶范数。请读者依据对偶锥的定义尝试给出证明。上面给出了若干对偶锥的例子，我们指出对偶锥满足一些基本的性质：是闭凸锥。可导出是的凸包的闭包。因此，如果是闭凸锥，则。除了本小节介绍的对偶锥的定义之外，文献中有多种类似的“对偶锥”的定义，如文献[2]中第14节定义的极锥。1.5对偶锥谢谢观看凸函数最优化模型与算法——基于Python实现第二章01凸函数的定义和例子一些常见的初等函数，如一元函数

等，具有共同的形态，即函数曲线凸向下方，具有这种形态的函数称为凸函数。定义2.1.1函数

是凸的，如果

是凸集，且对于任意

和任意

，有

(2.1.1)

则称

为凸函数。图2.1.1凸函数示意图从几何上看，上述不等式意味着连接点

和

之间的线段，在函数

的图像上方(如图2.1.1所示)。如果(2.1.1)式中的不等式当

以及

时严格成立，那么称函数

是严格凸的。如果

是凸的，那么我们称函数

为凹的；如果

是严格凸的，那么称函数

为严格凹的。2.1.1凸函数的概念对于仿射函数，不等式(2.1.1)总成立，因此所有的仿射函数是既凸又凹的。反之，若某个函数是既凸又凹的，则它是仿射函数。函数是凸的，当且仅当该函数在与其定义域相交的任何直线上都是凸的。换言之，函数

是凸的，当且仅当对于任意

和任意向量

，函数

在其定义域

中是凸的。这个性质非常有用，因为它容许我们将函数限制在直线上来判断其是否是凸函数。2.1.1凸函数的概念通常可以定义凸函数在定义域外的值为

，从而将这个凸函数延拓至全空间

。如果

是凸函数，那么我们定义它的值拓展函数

如下：(2.1.2)值拓展函数是定义在全空间上的，取值集合为。我们也可以从值拓展函数的定义中确定原函数的定义域，即。这种拓展可以简化符号描述，我们不需要明确描述定义域或者每次提到时都限定“对所有的”。以基本不等式(2.1.1)为例，对值拓展函数可以描述为：对任意和，以及，有(2.1.3)(当或时不等式总成立)当然此时我们应当利用扩展运算来理解这个不等式。若和都在内，上述不等式即为不等式(2.1.1)，如果有任何一个在外，上述不等式的右端为，不等式仍然成立。值拓展函数2.1.1凸函数的概念再看一个例子，设

和

是

上的两个凸函数，逐点和函数

的定义域为

，对于任意

有

。利用值拓展函数我们可以简单地描述为，对于任意

，

，其中，函数

的定义域被自动定义为

，因为当

或者

时，

。在有些文献中，凸函数的值域被拓展为

。在这种情况下，如果一个凸函数取不到

，并且它能取有限值，那么称这样的凸函数为恰当凸函数。本书如果没有特别声明，所提到的凸函数均指恰当凸函数。在不造成歧义的情况下，本书将用同样的符号来表示一个凸函数及其值拓展函数，即假设所有的凸函数都隐含地被拓展了，也就是在定义域外都被定义为。“”2.1.1凸函数的概念例2.1.1凸集的示性函数。设是一个凸集，考虑凸函数其定义域为，对于所有的，。换言之，此函数在集合上取值为零，其延拓函数可以描述如下(2.1.4)凸函数被称作集合的示性函数。利用示性函数，可以更加方便地描述问题。例如，对于在集合上极小化函数(假设其定义在整个空间)的问题，可以给出等价地描述为：在上极小化函数。上面介绍了凸函数的概念及其值拓展函数。对于某一特定的函数，如何判断其是否是凸函数呢。下面我们分别假定函数是一阶可微和二阶可微的，对其进行分析，分别给出函数是凸函数的一阶条件和二阶条件。“”2.1.1凸函数的概念定理2.1.1(一阶凸性条件)假设

可微(即其梯度

在开集

内处处存在)，则函数

是凸函数的充要条件是

内是凸集且对于任意

内下式成立

(2.1.5)

如图2.1.2所示，上述不等式意味着凸函数的函数图像将位于定义域内任意一点切线的上方。由得出的仿射函数即为函数在点附近Taylor近似。不等式(2.1.5)表明，对于一个凸函数，其一阶Taylor近似实质上是原函数的一个全局下估计。反之，如果某个函数的一阶Taylor近似总是其全局下估计，那么这个函数是凸的。图2.1.2凸函数的一阶条件2.1.1凸函数的概念不等式(2.1.5)说明从一个凸函数的局部信息，即它在某点的函数值及梯度，我们可以得到一些全局信息(如它的全局下估计)。这也许是凸函数的最重要的信息，由此可以解释凸函数以及凸优化问题的一些非常重要的性质。下面是一个简单的例子，由不等式(2.1.5)可以知道，如果

那么对于所有的

，存在

，即

是函数

的全局极小点。另一个著名的例子是第6章中介绍的在线凸优化算法，其遗憾界的估计本质上依赖于不等式(2.1.5)。严格凸性同样可以由一阶条件刻画：函数

严格凸的充要条件是

是凸集且对任意

，有

(2.1.6)对于凹函数，亦存在与之对应的一阶条件：函数

是凹函数的充要条件是

是凸集且对于任意

，有下式成立

(2.1.7)2.1.1凸函数的概念下面考虑定理2.1.1的证明。证明思路充分利用凸函数的性质：函数

是凸函数当且仅当函数限定在定义域内任意一条直线上是凸的。因此，首先证明函数

是一元的情况时，命题成立，再将函数

为n元函数的情形化归为一元函数。证明：为了证明(2.1.5)，先考虑

的情况。我们证明可微函数

是凸函数的充要条件是对

内的任意

和

有

(2.1.8)首先假设

是凸函数，且

。因为

是凸集(某个区间)，对于任意

我们有

。由函数

的凸性可得

(2.1.9)

将上式两端同除t可得

(2.1.10)

令t→0，可以得到不等式(2.1.8)。为了证明充分性，假设对

(某个区间)内的任意

和

，函数满足不等式(2.1.8)。选择任意

且

。令

。两次应用不等式可得

(2.1.11)将第一个不等式乘以

，第二个不等式乘以

，并将二者相加可得

(2.1.12)从而说明了函数是凸的。2.1.1凸函数的概念现在来证明一般情况，即

。设

，考虑过这两点的直线上的函数

，即函数

，此函数对

求导可得

。首先假设函数

是凸的，则函数

是凸的，由前面的讨论可得

，即

(2.1.13)再假设此不等式对于任意和均成立。因此，若以及，我们得到(2.1.14)即，说明函数是凸的。证毕。现在假设函数二阶可微，不妨假设函数为一元函数，则对于开集内的任意一点，它的二阶导数存在，考虑函数的凸性是否可用二阶导数刻画。考虑简单的一元二次函数的情形：此时函数为凸函数当且仅当函数曲线开口向上，即。此外，若函数退化为一次函数，即时，则函数仍为凸函数。综上所述，对于一元二次函数，若允许二次项的系数退化，则为凸函数当且仅当对任意，。这一结论对于一般的二阶可微函数是否成立？下面的定理给出了肯定的回答。2.1.1凸函数的概念定理2.1.2假设函数

二阶可微，即对于开集

内的任意一点，它的Hessian矩阵或者二阶导数

存在，则函数

是凸函数的充要条件是其Hessian矩阵是半正定阵，即对于所有的

有

(2.1.15)

对于上的函数，上式可以简化为(是凸的，即一个区间)，此条件说明函数的导数是非减的。条件从几何上可以理解为函数图像在点x处具有正的曲率。关于二阶条件的证明作为习题留给读者完成。类似地，函数

是凹函数的充要条件是

是凸集且对于任意

，有

。严格凸的条件可以由二阶条件刻画。如果对于任意的

有

，则函数

严格凸。但逆命题不一定成立，例如，函数

，其表达式为

，它是严格凸的，但在

处，二阶导数为零。2.1.1凸函数的概念添加标题例2.1.2二次函数。考虑二次函数

，其定义域为

，其表达式为

(2.1.16)其中

。因为对于任意

，所以函数

是凸的，当且仅当

。对于二次函数，严格凸比较容易表达，函数

是严格凸的，当且仅当

(函数是严格凹的当且仅当

)。在判断函数的凸性和凹性时，不管是一阶条件还是二阶条件，

是凸集这个前提条件必须满足的。例如，考虑函数

，其定义域为

，对于所有

均满足

，但是函数

并不是凸函数。2.1.1凸函数的概念前文已经提到所有的线性函数和仿射函数均为凸函数(同时也是凹函数)，并描述了凸和凹的二次函数。下面给出更多的凸函数和凹函数的例子。首先考虑—元函数，其自变量记为x。例2.1.3一元凸函数指数函数。对任意

，函数

在

上是凸的。幂函数。当

或

时，

在

上是凸函数，当

，

在

上是凹函数。绝对值幂函数。当

时，函数

在

上是凸函数。对数函数。函数

在

上是凹函数。负熵函数。函数

在其定义域上是凸函数。定义域为

或者

，当

时定义函数值为0。我们可以通过基本不等式(2.1.1)或者二阶导数半正定或半负定来判断上述函数是凸的或是凹的。以函数

为例，其导数和二阶导数分别为

(2.1.17)因此对于

，有

。所以负熵函数是严格凸的。2.1.2凸函数的例子下面我们给出

上的一些凸函数的例子。例2.1.4n元凸函数。范数。

上的任意范数均为凸函数。最大值函数。函数

在

上是凸函数。二次一次线性分式函数。

，其定义域为

(2.1.18)

该函数是凸函数，函数图像如图2.1.3所示：图2.1.3

的图像2.1.2凸函数的例子指数和的对数。函数在是凸函数。这个函数可以看成最大值函数的解析近似函数，因为对任意x，下面的不等式成立(2.1.19)第二个不等式中当x的所有分量都相等时是紧的。图2.1.4描述了时函数的图像几何平均值。几何平均值函数在定义域上是凹函数。对数行列式。函数在定义域是凹函数。

判断上述函数的凸性(或者凹性)有多种途径，可以直接验证不等式是否成立，亦可以验证其Hessian矩阵是否半正定，或者可以将函数转换到与其定义域相交的任意直线上，通过得到的一元函数判断原函数的凸性。2.1.2凸函数的例子图2.1.4

的图像直观地说，如果一个函数比线性函数增长得快，那么它就是强凸函数。为了给出一个精确的定义，回想一下对于凸函数

，在任意点

，我们可以找到一个线性函数(切线)，它在

处等于

，在其他任何点不超过

。如果

严格位于切线的上方，且函数

与切线的差满足下述数量关系，则

是强凸的。强凸函数定义如下。定义2.1.2函数

关于范数

在

上是

-强凸的，如果任何

，有

(2.1.20)

强凸函数的示意图，如图2.1.5所示，其中函数

与其在

处切线的距离至少为

。图2.1.5强凸函数2.1.3强凸性强凸函数的一个重要性质如下。定理2.1.3设

为非空凸集，函数

关于范数

在

上是

-强凸的，

，则对所有

有

。证明：首先假设

是可微的，

是在

的内部，即

，根据强凸的定义，有

。

若

在

的边界上，仍然有对所有的

，

(否则

就不是最优的，我们可以向

方向移动以降低

的值)。因此，目标不等式依然成立。最后，给出

不可微条件下的证明。将

的定义域延拓到全空间，设

满足

如果

，否则

。因此，有

。由于

是一个恰当凸函数，所以有

。通过使用

的强凸性可推出目标不等式。证毕。如果函数

是二次可微的，则容易验证

强凸的条件是对所有

，

，其中

是

在

处的Hessian矩阵。2.1.3强凸性例2.1.5(欧式正则化项)函数关于范数是1-强凸的。要说明这一点，只需注意到在任意点处的Hessian矩阵是单位矩阵。以下定理给出了强凸函数其他有用的性质，其证明可以依据强凸的定义得到。定理2.1.4如果是上关于某个范数1-强凸的，那么是关于同一个范数是-强凸函数。此外，如果是的凸子集，则在上也是1-强凸的。2.1.3强凸性凸函数自然地诱导出若干凸集合。常用的有下水平集和上图。下水平集定义2.1.3函数的下水平集定义为。对于任意的，凸函数的下水平集仍然是凸集合。证明可以由凸集的定义直接得到：如果，则有，因此对任意，即。反之，逆命题未必成立：一个函数的所有下水平集都是凸集合，但函数本身未必是凸函数。例如，在上不是凸的(实际上，它严格是凹的)，但是其所有下水平集都是凸的。如果是凹函数，则由给出的上水平集是凸集。下水平集的性质可以用来判断集合的凸性，若某个集合可以描述为一个凸函数的下水平集，或者一个凹函数的上水平集，则它是凸集合。上图定义2.1.4函数的图像定义为(2.1.21)它是空间的一个子集。函数的上图定义为(2.1.22)它也是空间的一个子集。是“之上”的意思，所以上图的英文epigraph是“在函数图像之上＂的意思。图2.1.5的阴影部分是函数的上图，深颜色的下边界是函数的图像。2.1.4其他凸集合和凸不等式凸集和凸函数的联系可以通过上图来建立，如下面的定理所述：定理2.1.5—个函数是凸函数，当且仅当其上图是凸集；一个函数是凹函数，当且仅当其亚图(2.1.23)是凸集。该结论的证明可以参见文献[1]中的定理5.3。此结论虽然直观上较为自然，却具有重要的价值。它在凸集(几何对象)和凸函数(分析学研究对象)之间建立了一座桥梁。作为一个例子，考虑关于可微凸函数满足的不等式：(2.1.24)其中函数是凸的，。我们可以利用epi从几何角度理解上述基本不等式。如果epi，有(2.1.25)上式可以等价地描述为(2.1.26)如图2.1.7所示，向量定义了函数在点处上图epi的一个支撑超平面。图2.1.6函数的上图图2.1.7上图的支撑超平面2.1.4其他凸集合和凸不等式Jensen不等式及其扩展凸函数所满足的基本不等式：对于任意，有(2.1.27)有时也称作Jensen不等式。此不等式可以扩展至更多点的凸组合。如果函数是凸函数，且，则下式成立(2.1.28)此不等式可以扩展至无穷项和、积分以及期望。例如，如果在上且，则当相应的积分存在时，下式成立(2.1.29)扩展到更一般的情况，我们可以采用支撑集属于的任意概率测度。如果是随机变量，事件发生的概率为1，函数是凸函数，当相应的期望存在时，我们有(2.1.30)设随机变量的可能取值为，相应地取值概率为(2.1.31)则由一般不等式(2.1.31)可以得到基本不等式(2.1.1)。上述所有不等式均被称为Jensen不等式，而实际上最初由Jensen提出的不等式相当简单。对于任意有(2.1.32)请读者思考，上述不等式如果对于任意成立，是否与(2.1.28)式等价？2.1.4其他凸集合和凸不等式02保持凸性的运算01020304上一节，我们已经了解了若干具体的凸函数，为了研究或构造多种多样的凸函数，基本的方法是使用保持函数凸性的运算。非负加权求和显然，如果函数

是凸函数且

，则函数

也是凸函数。如果函数

和

都是凸函数，则它们的和

也是凸函数。将非负伸缩以及求和运算结合起来，可以看出，凸函数的集合本身是一个凸锥，凸函数的非负加权组和仍然是凸函数，即函数

(2.2.1)是凸函数。类似地，凹函数的非负加权求和仍然是凹函数。严格凸函数的非负，非零加权组和是严格凸函数。这个性质可以扩展至无限项的求和以及积分的情形。例如，如果固定任意

，函数

关于

是凸函数，且对任意

有

，若下式中的积分存在，则函数

(2.2.2)关于

是凸函数。我们可以很容易验证非负伸缩变换以及求和运算是保持凸性的运算，可以使用上图作具体结论。例如，如果

且

是凸函数，我们有

(2.2.3)因为凸集通过线性变换得到的像仍然是凸集，所以

是凸集。2.2保持凸性的运算复合仿射映射假设函数

，以及

，定义

为

(2.2.4)

其中

若函数

是凸函数，则函数

是凸函数；如果函数

是凹函数，那么函数

是凹函数。逐点最大和逐点上确界假设函数

，

均为凸函数，则

和

均为凸集合。因此，

也是凸集合，这个凸集合正是函数

和

的逐点最大值函数

的上图。因此，由定理2.1.5得到如下结论。定理2.2.1如果函数

和

均为凸函数，则二者的逐点最大值函数

有

(2.2.5)仍然是凸函数，其定义域为

。2.2保持凸性的运算下面依据凸函数的定义给出证明。证明：任取

以及

，有

从而说明了函数的凸性。证毕。(2.2.6)同样可以证明，如果函数为凸函数，则它们的逐点最大函数有(2.2.7)仍然是凸函数。特别地，(2.2.8)定义了一个分片线性(实际上是仿射)函数，它具有L个或者更少的子区域，因为它是一系列仿射函数的逐点最大值函数，所以它是凸函数。2.2保持凸性的运算如下例所示，基于定理2.2.1，可以验证一些重要的函数的凸性。例2.2.1最大个分量之和。对于任意，用表示中第大的分量，即将的分量按照降序进行排列得到下式(2.2.9)则对的最大的个分量进行求和所得到的函数(2.2.10)是凸函数。事实上，此函数可以表述为(2.2.11)即从的分量中选取个不同分量进行求和的所有可能组合的最大值。因为函数是个线性函数的逐点最大，所以是凸函数。“”2.2保持凸性的运算逐点最大的性质可以扩展至无限个凸函数的逐点上确界，如下面的定理所述。定理2.2.2如果对于任意，函数关于都是凸的，则函数(2.2.12)关于也是凸的。此时，函数的定义域为(2.2.13)从上图的角度理解，一系列函数的逐点上确界函数对应着这些函数上图的交集：对于函数，我们有(2.2.14)由定理1.3.1知，是凸集合，再由定理2.1.5知，函数是凸函数。例2.2.2集合的支撑函数。令集合，且，定义集合的支撑函数为(2.2.15)自然地，函数的定义域为

。对于任意是的线性函数，是一系列线性函数的逐点上确界函数，因此是凸函数。2.2保持凸性的运算复合运算除上面介绍的保持凸性的运算之外，实践中应用最广泛的函数运算可能是函数的复合运算。因此，我们特别关心复合运算在何种条件之下能保持函数的凸性。给定函数以及，定义复合函数为(2.2.16)我们考虑当函数是凸函数或凹函数时，函数和应满足的条件。首先考虑的情况，即。仅考虑的情况(事实上，将函数限定在与其定义域相交的任意直线上得到的函数决定了原函数的凸性)。为了找出复合规律，首先假设函数和是二次可微的，且。在上述假设下，函数是凸的等价于对所有的。复合函数的二阶导数为(2.2.17)假设函数是凸函数，函数是凸函数且非减(即且)，从式(2.2.17)可以得出，即函数是凸函数。2.2保持凸性的运算类似地，由式(2.2.17)可以得出如下结论。定理2.2.2给定函数以及，考虑复合函数则有(1)如果是凸函数且非减，是凸函数，则是凸函数，(2)如果是凸函数且非增，是凹函数，则是凸函数。请读者思考：如果是凹函数且是单调函数，则函数应具备怎样的条件，才能使函数是凹函数？作为本节的结束，我们指出函数之间的一些常见的运算未必保持凸性。例如，减法运算。设函数为凸函数，则未必是凸函数。称为DC(Differenceofconvexfunctions)函数，是一类重要的非凸函数。在第5章中将介绍极小化DC函数的最优化算法。2.2保持凸性的运算03共轭函数2.3.1共轭函数的概念定义2.3.1设函数

，则函数

(2.3.1)称为函数

的共轭函数。明显地，

是凸函数，这是因为它是一系列关于

的凸函数(实际上是仿射函数)的逐点上确界。无论

是否是凸函数，

都是凸函数。注意到当

是凸函数时，下标

可以去掉，这是因为根据之前关于函数延拓的定义，有

。我们从一些简单的例子开始探寻共轭函数的一些规律。在此基础上我们可以得到很多常见凸函数的共轭函数的解析形式。例2.3.1考虑上一些凸函数的共轭函数。(1)仿射函数。，作为的函数，当且仅当，即为常数时，有界。因此，共轭函数的定义域为单点集，且。(2)负对数函数。，定义域为。当时，函数无上界，当时，在处函数达到最大值。因此，定义域为，共轭函数为。(3)指数函数。，当时，函数无界。当时，函数在处达到最大值。因此，当时，。综合起来，(我们规定)。(4)负熵函数。，定义域为(同上面讨论，)。对所有，函数关于在上有上界，因此。在处，函数达到最大值。因此。2.3.1共轭函数的概念(5)严格凸的二次函数。考虑函数。对所有的，关于的函数都有上界并在处达到最大值，因此(2.3.2)例2.3.2对数-行列式。我们考虑上定义的函数。其共轭函数定义为(2.3.3)其中，是上的标准内积。首先我们说明只有当时，才有上界。如果，则有特征向量，且对应的特征值。令有(2.3.4)当时，上式无界。接下来考虑的情形。为了求最大值，令对的偏导为零，则(2.3.5)得(是正定的)。因此，其定义域为。例2.3.3示性函数。设是某个集合(不一定是凸集)的示性函数，即当，时，。示性函数的共轭函数为(2.3.6)它是集合的支撑函数。2.3.1共轭函数的概念共轭理论可理解为下面类型的“最佳”不等式。(2.3.7)其中和是从到的函数，令表示对此不等式有效的所有函数对的集合，“最佳”对是指中的不等式不能被收紧的函数对，即如果，并且