半小时梳理凸优化.pptVIP

保持函数凸性的算子 凸函数的非负加权和 凸函数与仿射函数的复合 凸函数的逐点最大值、逐点上确界 * 第三十张，课件共四十七张，编辑于2022年5月 凸函数的逐点最大值 f1,f2均为凸函数，定义函数f： 则函数f为凸函数。 * 第三十一张，课件共四十七张，编辑于2022年5月 思考 逐点上确界和上境图的关系 一系列函数逐点上确界函数对应着这些函数上境图的交集。 直观例子 Oxy平面上随意画N条直线(直线是凸的——虽然直线也是凹的)，在每个x处取这些直线的最大的点，则构成的新函数是凸函数； 同时：N条直线逐点求下界，是凹函数； 在Lagrange对偶函数中会用到该结论。 * 第三十二张，课件共四十七张，编辑于2022年5月 凸优化 优化问题的基本形式 * 第三十三张，课件共四十七张，编辑于2022年5月 第一张，课件共四十七张，编辑于2022年5月 主要内容 凸集基本概念 凸集保凸运算 分割超平面 支撑超平面 凸函数基本概念 上境图 Jensen不等式 凸函数保凸运算 凸优化一般提法 对偶函数 鞍点解释 用对偶求解最小二乘问题 强对偶KKT条件 * 第二张，课件共四十七张，编辑于2022年5月 思考凸集和凸函数 y=x2是凸函数，函数图像上位于y=x2上方的区域构成凸集。 凸函数图像的上方区域，一定是凸集； 一个函数图像的上方区域为凸集，则该函数是凸函数。 稍后给出上述表述的形式化定义。 因此，学习凸优化，考察凸函数，先从凸集及其性质开始。 * 第三张，课件共四十七张，编辑于2022年5月 凸集 集合C内任意两点间的线段均在集合C内，则称集合C为凸集。 * 第四张，课件共四十七张，编辑于2022年5月 凸集 * 第五张，课件共四十七张，编辑于2022年5月 超平面和半空间 超平面hyperplane 半空间halfspace * 第六张，课件共四十七张，编辑于2022年5月 超平面和半空间 * 第七张，课件共四十七张，编辑于2022年5月 多面体 多面体有限个半空间和超平面的交集。 仿射集(如超平面、直线)、射线、线段、半空间都是多面体。 多面体是凸集。 此外：有界的多面体有时称作多胞形(polytope)。 注：该定义略混乱，不同文献的含义不同。 * 第八张，课件共四十七张，编辑于2022年5月 多面体 * 第九张，课件共四十七张，编辑于2022年5月 保持凸性的运算 集合交运算 思考：如何证明？(提示：根据定义) 仿射变换 函数f=Ax+b的形式，称函数是仿射的：即线性函数加常数的形式 透视变换 投射变换(线性分式变换) * 第十张，课件共四十七张，编辑于2022年5月 集合交运算：半空间的交 * 第十一张，课件共四十七张，编辑于2022年5月 仿射变换 仿射变换 伸缩、平移、投影 若f是仿射变换， 若S为凸集，则f(S)为凸集； 若f(S)为凸集，则S为凸集。 * 第十二张，课件共四十七张，编辑于2022年5月 透视变换 透视函数对向量进行伸缩(规范化)，使得最后一维的分量为1并舍弃之。 透视的直观意义 小孔成像 * 第十三张，课件共四十七张，编辑于2022年5月 透视变换的保凸性 凸集的透视变换仍然是凸集。 思考：反过来，若某集合的透视变换是凸集，这个集合一定是凸集吗？ * 第十四张，课件共四十七张，编辑于2022年5月 投射函数(线性分式函数) 投射函数是透视函数和仿射函数的复合。 g为仿射函数： 定义f为线性分式函数 若c=0,d0，则f即为普通的仿射函数。 * 第十五张，课件共四十七张，编辑于2022年5月 分割超平面 设C和D为两不相交的凸集，则存在超平面P，P可以将C和D分离。 注意上式中可以取等号： 所以：逆命题：“若两个凸集C和D的分割超平面存在，C和D不相交”为假命题。 加强条件：若两个凸集至少有一个是开集，那么当且仅当存在分割超平面，它们不相交。 * 第十六张，课件共四十七张，编辑于2022年5月 分割超平面 * 第十七张，课件共四十七张，编辑于2022年5月 分割超平面的构造 两个集合的距离，定义为两个集合间元素的最短距离。 做集合C和集合D最短线段的垂直平分线。 * 第十八张，课件共四十七张，编辑于2022年5月 支撑超平面 设集合C，x0为C边界上的点。若存在a≠0，满足对任意x∈C，都有 成立，则称超平面 为集合C在点x0处的支撑超平面。 凸集边界上任意一点，均存在支撑超平面。 反之，若一个闭的非中空（内部点不为空）集合，在边界上的任意一点存在支撑超平面，则该集合为凸集。 * 第十九张，课件共四十七张，编辑于2022年5月 思考 如何定义两个集合的“最优”分割超平面？ 找到集合“边界”