凸优化理论

第一章凸集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是分别在{，，}和{，，}中取值的随机变量，并且表示概率()。那么条件概率()由下式给出:∑⁄，f可以通过一个线性分式映射从联合分布凸集p（维向量集合，每一个向量是一个联合分布）到条件概率分布凸集（维向量集合，每一个向量是一个条件分布）；----------------------------------------------------------------------------------------------------------------------------------6.分离与支撑超平面：重要的想法：用超平面或仿射函数（仿射集）将两个不相交的凸集分离开来！6.1、超平面分离定理：假设C和D是两个不相交的凸集，即,那么存在和b使得对于所有有,对于所有有；超平面{}称为集合C和D的分离超平面；*假设C和D的欧氏距离(){‖‖}即‖‖(，)，并且存在达到这个最小距离，这些条件是可以被满足的，如当C和D是闭的并且其中之一是有界的。定义：(‖‖‖‖)⁄,因此仿射函数()()[()⁄]分离了C和D，且与连接c和d之间的线段相垂直并且穿过其中点。1）仿射集与凸集的分离：仿射集等价于线性等式组，即多个超平面交集；凸集等价于线性等式组和线性不等式组的交集，即多个超平面、半空间交集构成的多面体；设C是凸集，而D是仿射的，即{}，其中。设C和D不相交，则存在使得和，对与所有均成立。2）超平面严格分离：如果对于任意有，并且对于任意，有；一般情况不相交的凸集并不一定能够被超平面严格分离，即使集合是闭集；3）点和闭凸集的严格分离：6.2、超平面分离逆定理：（分离超平面的存在表面C和D不相交）不成立任何两个凸集，如果其中至少有一个是开集，那么当且仅当存在分离超平面时，它们不相交；换句话说，如果它们都是闭集，逆定理可能是不成立的；***************************************************************************************严格线性不等式的择一定理：严格线性不等式,无解的充要条件是两个凸集{}{}不相交,即存在，使得，，，；这两个线性不等式仅有一个成立；***************************************************************************************6.3、支撑超平面定理设而是其边界上的一点，即，如果，并且对任意满足，那么称超平面{}为集合C在点处的支撑超平面；对于任意非空的凸集C和任意，在处存在C的支撑超平面；如果C的内部非空，即是上面所述；如果C内部是空集，那么C必处于小于n维的一个仿射集合中，并且任意包含这个仿射集合的超平面一定包含C和，这是一个平凡的支撑超平面，如{‖‖},支撑超平面为；6.4、支撑超平面逆定理如果一个集合是闭的，具有非空内部，并且其边界上每个点均存在支撑超平面，那么它是凸的；----------------------------------------------------------------------------------------------------------------------------------7.广义不等式：7.1、正常锥：锥,要求如下K是凸的（两点连线封闭）；K是闭的（集合是闭集）；-------------需要在距离空间中K是实的（具有非空内部）；----------需要在距离空间中K是尖的（不包含直线，）；正常锥可以用来定义广义不等式，即上的偏序关系。上偏序关系：;上严格偏序关系：;上的偏序关系、严格偏序关系就是7.2、一些例子非负象限是正常锥，向量间的偏序关系等价于所有分量间的偏序关系；半正定锥是中的正常锥，相应的广义不等式就是矩阵不等式，两个半正定矩阵间的偏序关系等价于矩阵差为半正定矩阵，两个半正定矩阵间的严格偏序关系等价于矩阵差为正定矩阵；半正定矩阵的内部有正定矩阵组成；[0,1]上非负的多项式锥：K定义如下{[]}，向量c;7.3、广义不等式性质：偏序性质：对加法保序；具有传递性；对非负乘数保序；自反；反对称；对极限运算保序；不具有全序性；7.4、最小元与极小元最小元：如果对于每个，都有，称是S的最小元;是最小元；表示可以与相比，并大于等于的所有元素；要求全部可比，在Rn上意味着其他元素的各个分量都大于等于该元素的分量，在半正定锥上意味着相减后差仍是半正定锥；极小元：如果，，那么，称x为S的极小元