下载文档原格式
凸优化理论第一章凸集1、仿射集1.1、定义：任意以及都有；直观上，如果两点在仿射集内，那么通过任意两点的直线位于其内；1.2、仿射集的关联子空间：如果是仿射集，且，则集合是一个子空间（关于加法和数乘封闭）,因此仿射集可以表示为一个子空间加上一个偏移，，可以是C中任意一点；定义C的维数为子空间V的维数（向量基的个数）;1.3、线性方程组的解集:等价于仿射集且其关联的子空间是就是的的零空间即;1.4、仿射组合：如果，称为的仿射组合；如果是仿射集，，且，那么；集合C是仿射集集合包含其中任意点的仿射组合；1.5、仿射包：集合C中的点的所有仿射组合组成的集合记为C的仿射包，；仿射包是包含的最小的仿射集合；1.6、仿射维数：集合仿射维数为其仿射包维数, 即仿射包相关联子空间的维数，即是其子空间最大线性无关基；如果集合的仿射维数小于n ，那么这个集合在仿射集合中;1.7、集合相对内部：定义为的内部，记为，即;集合内部：由其内点构成，内点为;1.8、集合的相对边界：集合C的相对边界定义为，为C的闭包；集合C的边界定义为;------------------------------------------------------------------------------------------------------------------------------ 2.凸集：如果，，，都有；直观上，如果两点在凸集内，则两点间的线段也在凸集内；仿射集是凸集；2.1、凸组合：如果，，，称为的凸组合；点的凸组合可以看做他们的混合或加权平均，代表混合时所占的份数。
如果点在凸集内，则它们的凸组合仍在凸集内；C是凸集集合包含其中所有点的凸组合；2.2、集合的凸包：集合C中所有点的凸组合，;C的凸包是包含C的最小凸集；2.3、无穷级数的凸组合：假设，，，并且，，、、，为凸集，那么若下面的级数收敛，那么2.4、积分的凸组合：假设对所有满足，并且,其中为凸集，那么如果下面积分存在，则： ;2.5、概率的凸组合：假设x是随机变量，为凸集，并且的概率为，那么；---------------------------------------------------------------------------------------------------------------------------------- 3锥：如果对于任意和，都有，称集合C为锥；直观上如果点在锥中，那么以原点为端点过该点的射线在锥中；3.1、凸锥：集合C是锥，并且是凸的，则称C为凸锥，即对于任意，和，，都有直观上，如果两点在凸锥中，那么以原点为端点，以过两点的两条射线为边界的扇形面在凸锥中；3.2、锥组合：具有，形式的点称为的锥组合（或非负线性组合）；如果均属于凸锥C，那么的每一个锥组合也在C中；集合C是凸锥它包含其元素的所有锥组合；3.3、锥包：集合C的锥包是C中所有元素的锥组合的集合；---------------------------------------------------------------------------------------------------------------------------------- 凸集的例子：空集、单点集、全集都是的仿射子集；线段是凸的，但不是仿射的；射线是凸的，不是仿射的，不是锥（除非端点是零点）；直线是仿射的，自然是凸的；如果通过零点，则是锥，并且是凸锥；子空间是仿射的、凸锥(满足对加法、数乘封闭、含零元)；超平面：，其中，且；，，在超平面上；闭的半空间：非平凡线性不等式的解空间，，半空间是凸的，但不是仿射的，也不是锥；半空间边界、内部：、；Euclid球：欧几里得球是凸集：；椭球：椭球是凸集：，对称正定矩阵，决定椭球从各个方向扩展的幅度；半轴长度有给出；正半定矩阵；若为奇异矩阵，椭球退化，即一些维度上半轴长为零，这时其仿射维数等于A的秩，退化的椭球也是凸的；范数球、范数锥：它们是凸集，范数锥：，；如二阶锥（二次锥）；---------------------------------------------------------------------------------------------------------------------------------- 4.多面体：有限个线性等式和不等式的解集：，，;因此多面体是有限个半空间和超平面的交集；仿射集合（如子空间、超平面、直线）、射线、线段、半空间都是多面体；多面体是凸集；有界多面体也称为多胞形<=>有限集合的凸包；多面体可以表示为，，b、d为向量；4.1、单纯形（一种多面体）：点描述法设k+1个点，，仿射独立，即，，，线性独立，那么这些点决定了一个单纯形：，，，，这个集合的仿射维数（它的仿射闭包的维数），即是，空间的维数，显然它的一个基就是，，，即集合的仿射维数为k；单纯形是凸集、并且是多面体，一般称k维单纯形（k+1个仿射独立点生成的凸包）；4.2、常见的单纯形:1维单纯形是一条空间线段（1个基向量，2个空间点）；2维单纯形是一个空间三角形（含其内部）（2个基向量，3个空间点）；3维单纯形是一个四面体（3个基向量，4个空间点）；4.3、单位单纯形：由零向量0和单位向量，，决定的n维单纯形，它可以表示为满足下列条件的向量的集合：;4.4、概率单纯形：由单位向量，，决定的n-1维单纯形，它是满足下列条件的向量集合：;概率单纯形中的每个向量对应于随机变量n个取值对应的一个概率分布，可理解为第i个元素的概率；4.5、单纯形的多面体描述法C是单纯形，充要条件是，对于某些，，有;，其中，，，，，，显然，B的秩为k；因此存在非奇异矩阵，使得，，,则: ，，，，，，，显然：且且且；这里A的选择与，，有关；4.6、多面体：凸包描述法有限集合，，的凸包是：，，，是一个有界多面体，但是无法用线性不等式和不等式的集合将其表示；凸包表达式的一个扩展：，，,其意义是，，的凸包加上，，的锥包，定义了一个多面体，反之每个多面体也都可以表示为此类形式；仿射集是凸集；多面体是凸集；仿射集是多面体；单纯形（特殊多面体）是凸集，可以给出线性等式和不等式表示；多面体（使用线性等式和不等式组定义）等价于凸包，无法给出线性等式和不等式表示；有限集的凸包是有界多面体，无法给出线性等式和不等式表示；5.保凸运算：用以从凸集构造出其他凸集；5.1、求交集：无穷多个凸集的交是凸集；5.2、仿射映射：,且,若S是凸的，那么是凸的；反之成立；伸缩、平移、投影是仿射映射；凸集的和、直积是凸的，凸集的投影是凸的，凸集的部分和是凸的；注意：，也是仿射函数；线性矩阵不等式的解：，是凸集；双曲锥：,是凸集；5.3、透视映射：，，定义域为，如果C是凸集，那么是凸集；反之成立；5.4、线性分式映射：是仿射的，其中并且,那么：，是线性分式（投射）函数, 定义域，P是透视函数；同样象与原象的凸性可以互推；线性分式映射的应用：条件概率，设u和v是分别在，，和，，中取值的随机变量，并且表示概率。
01凸优化理论与应用_凸集凸优化理论是数学中的一个重要分支，是一种求解优化问题的方法。
在实际应用中广泛存在的一类优化问题，可以用凸优化理论进行形式化的描述和求解。
凸优化理论主要研究凸集、凸函数和凸优化问题，并给出了一系列的优化方法和算法。
凸集是凸优化理论的基础概念之一，它是指一个集合中的任意两个点之间的连线上的所有点也属于该集合。
具体来说，一个凸集要满足以下两个条件：1. 对于任意两个点x1和x2属于凸集C，它们的连线上的任意一点都属于C，即对于任意的t(0<t<1)，都有tx1+(1-t)x2属于C。
2.对于凸集C中的任意一个点x，与该点相接的区域也属于C。
凸集在凸优化问题中起到了重要的作用，它可以用来描述问题的可行解空间，也可以用来描述问题的约束条件。
在凸优化问题中，通常将目标函数定义在凸集上，并要求在该凸集上寻找使目标函数取得最小值的一个点或一个解集。
凸函数是凸优化理论中的另一个重要概念，它是指定义在凸集上的实值函数，对于该函数上的任意两个点，连接它们的线段上的函数值都不大于线段的两个端点的函数值之间的凸函数。
具体来说，对于定义在凸集C上的函数f(x)，对于任意x1和x2属于C以及0<t<1，都有f(tx1+(1-t)x2)<=tf(x1)+(1-t)f(x2)。
凸函数在凸优化问题中起到了至关重要的作用，它具有很多好的性质，比如局部最小值就是全局最小值、唯一最小值等。
因此，在实际应用中，我们通常可以将问题转化为寻找凸函数的最小值。
凸优化问题是指在给定的凸集上求解凸函数的最小值的问题。
通常情况下，凸优化问题的目标函数是一个凸函数，约束条件也是一些凸集。
对于凸优化问题，存在一系列的优化算法和方法，如梯度下降法、内点法、对偶问题等。
凸优化理论与应用广泛涉及到各个领域，如机器学习、图像处理、信号处理、运筹学、控制理论等。
在机器学习中，凸优化理论可以用来描述和求解各种不同的学习问题，如线性回归、逻辑回归、支持向量机等。
