第3讲凸集凸函数凸规划

凸函数和凸的凸函数和凸集是数学中的两个重要概念，在数学和工程应用中非常常见。

本文将着重介绍这两个概念的定义、性质和应用。

一、凸函数1. 定义对于实数集合X上的函数f，如果对于任意的x1,x2∈X及实数α(0≤α≤1)，都有f(αx1+(1−α)x2)≤αf(x1)+(1−α)f(x2)则称f是X上的凸函数。

简单来说，就是图像上任意两点连线在函数图像下方时，该函数为凸函数。

如下图：2. 性质（1）凸函数的一阶导数单调增加。

（2）如果f(x)在[a,b]内是凸函数，则∀x∈(a,b)，有f(x)≤f(a)+f'(a)(x−a)或f(x)≤f(b)+f'(b)(x−b)（即解析式可以被类比为斜率大于等于零的直线），同时也可以得出：f(a)+f(b)2≥f(a+b2)即弦比切的定理。

（3）如果f(x)在[a,b]上是二次凸函数，则额外满足：f(a+x+b−a−2x2b−a)≤f(a)+f(b)2−f'(a)(b−a)4根据其定义可知，凸函数有一个很好的性质，即对于任意一个凸函数f(x)，其局部最小值也是全局最小值。

这个性质在优化问题中非常有用。

3. 应用凸函数在优化问题中很常见，比如线性规划、非线性规划、半正定规划以及凸优化等。

此外，凸函数在机器学习中也有非常广泛的应用，比如核方法、支持向量机等。

二、凸集1. 定义凸集是指对于一个实数集合X，如果对于其中的任意两个点x1,x2∈X及实数α(0≤α≤1)，有αx1+(1−α)x2∈X则称X是凸集。

也就是说，凸集内的任意两点连线上的任意一点也在凸集内。

如下图：2. 性质（1）凸集的交仍为凸集。

（2）凸集的凸组合一定在该凸集内。

（3）凸集的闭包也是凸集。

（4）如果X是凸集，则对于x∈X，X是以x为球心的超球体内的凸集。

3. 应用凸集和凸函数在很多方面都是密切相关的，比如凸优化和半正定规划等都涉及到凸集的概念。

凸集也被广泛应用于统计学和经济学中，例如一些概率模型的凸包上界（convex hull upper bound）和有效边界（efficient set）等等。

第一章：凸集及凸函数凸集——1、仿射集2、凸集3、锥（尖锥、凸锥、多面锥）4、凸集的闭包、内部和相对内部：线段定理；相对内部一定非空；相对内点判定5、集合的凸包：集合凸包的表示方法（卡拉太奥多里定理、克莱因-米尔曼定理）6、回收锥定理7、凸集的序列交、线性化、分解凸函数——1、定义、上境图、恰当函数2、下半连续3、函数的闭性4、凸性与极大极小值的关系5、函数的连续性6、函数凸性的一阶条件和二阶条件7、多元函数逐点取下确界，凸性不变/复合函数凸集的分离——1、超平面，闭半空间，强分离、支撑超平面2、投影定理3、二次规划（作业）4、两个凸集的联系/强分离定理第二章：凸包络、非凸优化和凸规划凸包络——1、定义及性质2、各种凸包络：多胞形/单纯形上凸函数/闭区间上单变量凹函数/平面矩形双线性函数的凸包络（作业）3、凸函数、上境图和凸包络的关系D.C.函数——1、定义及举例2、D.C.集，D.C.不等式3、D.C.集是一个闭集D.C.规划——1、定义2、典范D.C.规划（转化为凸规划）3、双层规划最优解的存在性刻画——1、强制函数2、weierstrass定理3、凸函数的回收方向4、函数的回收锥5、紧的最优解集的存在性定理第三章：凸规划解的描述择一定理与极锥定理——1、Fakas引理的两种表示2、点与闭凸锥分离3、极锥、有限生成锥、多面锥及其关系4、Fakas引理的正规表示5、Minkowski-weyl定理6、极点与多面体集合的关系7、多面体表示定理8、极点的性质9、凸集、极点、超平面LP问题——1、线性规划的定义、标准型及性质2、凹函数极点最优性整数规划——1、formulation定义2、有理多面体、weyl定理3、有理多面体与整数规划可行域的关系4、LP与IP之间的关系5、Benders分解算法（作业）第四章：带有约束的最优化1、LP与对偶2、KKT，强互补松弛3、FD、SFD、LFD4、一阶最优性条件（几何特征+代数特征）5、对偶理论及强对偶定理6、最小公共点与最大交叉点7、拉格朗日对偶、几何乘子、拉格朗日乘子8、弱对偶定理、slater约束规格与强对偶9、最优解-几何乘子对10、安点定理。

凸集的例子在数学和几何学中，凸集是一个重要而有趣的概念。

它不仅在纯数学领域有广泛的应用，而且在实际问题的建模和解决中也起着至关重要的作用。

本文将为您介绍几个关于凸集的例子，帮助您更好地理解这一概念的实际意义。

例子一：凸多边形凸多边形是最简单的凸集之一。

它是由若干条线段连接而成的多边形，并且任意两点之间的连线都位于多边形内部。

简而言之，凸多边形没有凹陷的部分，任意两点之间的线段都在多边形内部，不会穿过多边形的边界。

著名的例子是正方形和正五边形，它们都是凸多边形的典型代表。

例子二：凸函数在数学中，凸函数是一个非常重要的概念，它在优化问题、经济学、物理学等多个领域中都有广泛的应用。

凸函数的定义是：对于定义在实数集上的函数f(x)，如果对于任意的实数x1和x2，以及0<=t<=1，都有以下关系成立：f(tx1+(1-t)x2)<=tf(x1)+(1-t)f(x2)那么函数f(x)就是一个凸函数。

直观地理解，凸函数的图像在任意两点之间的部分都位于连接这两点的线段的上方。

典型的例子包括二次函数f(x)=ax^2+bx+c（其中a>=0）以及指数函数f(x)=e^x等。

例子三：凸规划凸规划是数学规划中的一个重要分支，其目标是在满足一组约束条件的前提下，优化一个凸函数。

凸规划在工程、经济学、金融学等领域中都有广泛的应用。

考虑一个典型的凸规划问题：最小化f(x)，其中x是一个n维向量，f(x)是一个凸函数，同时满足约束条件g_i(x)<=0，h_j(x)=0，其中g_i(x)和h_j(x)分别是凸函数和仿射函数。

凸规划之所以重要，是因为它有着良好的性质和高效的求解算法，能够在实际问题中得到可行且高效的解决方案。

总结凸集是数学和几何学中一个重要且有趣的概念，它广泛应用于纯数学领域和实际问题的建模与解决中。

本文介绍了几个关于凸集的例子，包括凸多边形、凸函数和凸规划。

通过这些例子，我们希望读者能够更好地理解凸集的实际意义和应用价值。