“凸优化理论与应用”暑期学校学习总结 一、专家介绍 Stephen Boyd：斯坦福大学教授，曾多次来哈尔滨工业大学控制理论与制导技术研究中心开展学术讲座和交流活动。讲课全部是英文，很开朗。 段广仁：哈尔滨工业大学教授，曾于外国留学，讲了一口流利的英语，和Stephen Boyd教授交流时全部是英语。 谭峰：段广仁的学生，曾去Stephen Boyd教授那里做一年博后，然后回国，现在就职于哈尔滨工业大学，讲师。所以此次由她给大家做辅导。 二、课程安排 7.13上午8:15-9:15 开幕。段广仁老师对于本次暑期学校开展、Stephen Boyd、 谭峰以及幕后的工作人员做了简单的介绍，谈了课程的变 动的原因以及可能给我们加课等事宜。 9:30-11:00讲座1(Lecture 1) Stephen Boyd 教授。 7.14上午8:15-9:15 谭峰博士对于前一天Stephen Boyd 教授讲的知识的一个 回顾。 9:30-11:00讲座2(Lecture 2) Stephen Boyd 教授。 下午14:00-15:00讲座3(Lecture 3)Stephen Boyd 教授。 7.15上午8:15-9:15 谭峰博士。 9:30-11:00讲座4(Lecture 4) Stephen Boyd 教授。 7.16上午8:15-9:15 谭峰博士。 9:15-9:30 所有人一起拍一张照片。 9:30-11:00讲座5(Lecture 5) Stephen Boyd 教授。 三、主要知识 1.凸优化相应理论. 本部分一共有8章，老师只用了两节课共3个小时就讲完了。这部分的内容虽然我很认真的听了，也只能知道一点概况，说实话想学明白还需要以后投入大量的时间精力。 1.1 绪论 此部分介绍了在现实生活中存在的凸优化问题，最小二乘，线性规划，凸优化问题等。 1.2. 凸集 在此部分介绍了凸集里包含的集合的形式，如仿射集、凸集、凸锥、超平面
第一章凸集 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、无穷级数的凸组合： 假设，，，并且，，、、，为凸集，
内点法基本原理 摘要：内点法是求解含不等式约束最优化问题的一种十分有效的算法。内点法通过构造障碍函数，求解一系列只含等式约束最优化问题，逐步得到原问题的最优解，具有找初始点容易、线性收敛、迭代次数少等特点。本文主要介绍了内点法的基本原理，障碍方法的一般步骤并分析了该方法的优缺点，进行了算例实践。 关键词：内点法；障碍方法；Newton法 The Theory of Interior Point Method Abstract: Interior point method is a very effective algorithm for solving optimization problems with inequality constrained. Interior point method is constructed to solve a series of optimization problems with equality constraints, and the optimal solution of the original problem is obtained, which has the characteristics of finding the initial point easier, linear convergence, less iteration number and so on. This paper mainly introduces the theory of interior point method, the general steps of barrier method and analyzing the advantages and disadvantages of the method. Key words: interior point method; barrier method;Newton method
“凸优化”教学大纲 ?基本目的： 近年来，随着科学与工程的进步，凸优化理论与方法的研究迅猛发展，在科学与工程计算，数据科学，信号和图像处理，管理科学等诸多领域中得到了广泛应用。通过本课程的学习，掌握凸优化的基本概念，对偶理论，典型的几类凸优化问题的判别及其计算方法，熟悉相关计算软件 ?课程对象： 高年级本科生和研究生。 ?教材： (1)Stephen Boyd and Lieven Vandenberghe, Convex optimization, Cambridge University Press, 2004 参考书 (2)Jorge Nocedal and Stephen Wright, Numerical Optimization, Springer, 2006 (3)袁亚湘，孙文瑜，最优化理论与方法，科学出版社，2003 ?内容提要和学时分配： 1. 凸优化简介， 3学时 课程简介，凸优化问题介绍 2. 凸集，凸函数， 3学时 凸集和凸函数的定义和判别 3. 数值代数基础， 3学时 向量，矩阵，范数，子空间，Cholesky分解，QR分解，特征值分解，奇异值分解 4. 凸优化问题， 6学时 典型的凸优化问题，线性规划和半定规划问题 5. 凸优化模型语言和算法软件，3学时 模型语言：AMPL, CVX, YALMIP; 典型算法软件： SDPT3, Mosek, CPLEX, Gruobi 6. 对偶理论， 3学时 对偶问题的转换和对偶理论 7. 梯度法和线搜索算法，3学时 最速下降法及其复杂度分析，线搜索算法，Barzilar-Borwein 方法 8. 近似点梯度法， 3学时
凸优化总结 1基本概念 1.1） 凸集合：n S R ?是凸集，如果其满足：x; y S + = 1 x + y S λμλμ∈?∈ 几何解释：x; y S ∈，则线段[x,y]上的任何点都S ∈ 1.2） 仿 射 集 ： n S R ?是仿射集，如果其满足：x; y S , R ,+ = 1 x + y S λμλμλμ∈∈?∈ 几何解释：x; y S ∈，则穿过x, y 的直线上的任何点都S ∈ 1.3） 子空间：n S R ?是子空间，如果其满足：x; y S , R , x + y S λμλμ∈∈?∈ 几何解释：x; y S ∈，则穿过x, y ，0的平面上的任何点都S ∈ 1.4） 凸锥：n S R ?是凸锥，如果其满足：x; y S ,0 x + y S λμλμ∈≥?∈ 几何解释：x; y S ∈，则x, y 之间的扇形面的任何点都S ? 集合C 是凸锥的充分必要条件是集合C 中的元素的非负线性组合仍在C 中，作为一般化结 果，其中非负线性组合的数目可以推广到无穷 1.5） 超平面：满足{ } T x a x = b (a 0)≠的仿射集，如果b=0则变为子空间
1.6） 半空间：满足{ } T x a x b (a 0)≤≠的凸集，如果b=0则变为凸锥 1.7） 椭球体：{ } T -1 c c =x (x-x )A (x-x ) 1 ξ≤T n c A = A 0; x R ∈ 球心 1.8） 范数：f ：R n —R 是一种范数，如果对所有的n x; y R , t R ∈∈满足 1. f(x) 0; f(x) = 0 x = 0 2. f(tx) = tf(x) 3. f(x + y) f(x) + f(y) ≥?≤ 范数分类 ● 1范数 2 x = ● 2范数 1i x x x =∑ ● 3无穷范数 max i i x x ∞ = 1.9） 有效域：集合(){()}dom f x X f x =∈<∞ 1.10） 水平集：{()}{()}x X f x and x X f x αα∈<∈≤，其中α为一标量 1.11） 上镜图：函数:(,f x ∈-∞∞的上镜图由下面的集合给定 {}()(,),,()epi f x w x X w R f x w =∈∈<给出的1n R +给出的子集。 1.12） 多面体：有限数目半空间集合的交集{ }{ } T i i x a x b ,1,...=x Ax b P i k =≤= 1.13） 共轭函数：f ：R n —R 上的共轭函数定义为：*()sup (())T x domf f y y x f x ∈=-，* f 是凸 函数即使f 不是 1.14） Jensen 不等式： f ：R n —R 上的凸函数 ● 两点12112211221,0()()()i f x x f x f x θθθθθθθ+=≥?+≤+ ● 多点 11,0()()i i i i i i i i f x f x θ θθθ=≥?≤∑∑∑ ● 连续()0,()1(())()()p x p x dx f xp x dx f x p x dx ≥=?≤ ???