第三周读书笔记 1. 牛顿法 Pure Newton's Method 在上一章中具体讨论了梯度方法,该类方法只应用了一阶最优条件的信息,即梯度。此外,在讨论标度梯度法时还简单地讨论到Newton方法,该类方法进一步地应用到二阶最优条件地信息,即Hessian矩阵。该章重点介绍牛顿法,与梯度方法利用梯度进行新点迭代的方法不同,牛顿法的点更新方法如下:若假设函数在处的Hessian矩阵是正定矩阵,即。那上面的最小化问题有唯一的稳定点,也是全局最小点: 其中,向量也被称作牛顿方向,利用以上更新公式进行迭代的方法也被称作纯粹牛顿方法。算法流程图如下: 牛顿法要求在每次更新处的Hessian矩阵为正定矩阵。或者我们可以放宽一点条件——即在定义域内的任意点处的Hessian矩阵均为正定,这说明了存在一个唯一的最优解。但是,这并不能保证算法的收敛性。 事实上,牛顿法在某些假设下具备很好的收敛性能(称局部二次收敛)——令在上二阶连续可导,假设: 存在,对任意有 存在,对任意,有 令是牛顿方法得到的序列,是在上唯一最小值。那么对任意,以下不等式成立: 此外,如果,那么
证明如下: 事实上,对于某些不满足上述条件(正定、李普希兹连续)的优化问题,牛顿方法也能表现出收敛性。但是,总的来说,当缺少这些严格假设时收敛性无法得到保障。为了解决即使在Hessian矩阵正定也无法保障牛顿法的收敛性问题下,进一步地提出一种步长解决方案,即阻尼牛顿法。 阻尼牛顿法 在纯粹牛顿法的基础上,我们在进行迭代更新时,重新加入步长选择机制,如利用回溯法进行步长选择的阻尼牛顿法,算法流程如下:
cholesky分解 这一小节是针对前部分的补充知识——在利用牛顿法解决相关优化问题的时候,我们会遇到判断Hessian矩阵是否正定,以及求解线性系统的问题,这两个问题都可以通过cholesky分解来解决。 给定一个的正定矩阵,cholesky分解的形式为,其中是一个的下三角矩阵且其对角元素为正数。一般利用cholesky分解去解决线性系统分为以下两步: 1. 找到的解 2. 找到的解 可以通过一个简单的递推公式计算cholesky因子。如下:
(1) 如果中任意两点之间的线段任在中,那么集合被称为凸集。即对任意和满足的都有 (2) 函数是凸函数,则是凸集,且对于任意在任 下有
的问题,其中为凸函数。也就是说,凸优化问题是指需要最小化的函数(代价函数)是凸函数,而且定义域为凸集的问题。 3.凸优化问题的一般求解方法 有些凸优化问题比较简单,是可以直接求解的,譬如二次规划,这里不做说明。求解凸优化问题,就要利用该问题的“凸”性——只要我一直朝着代价函数减小的方向去,那么我一定不会走错!这就是下降方法的基本思想。 《convex optimization》这本书中,将凸优化问题分为无约束优化、等式约束优化和不等式约束优化分别介绍了其算法,然其本质并无区别。下降方法即产生一优化点列其中 并且。此处表示迭代的步长(比例因子),表示的是搜索方向(搜索步径)。下降方法指只要不是最优点,成立。以下内容均来自Stephen Boyd 的《convex optimization》及其中文译本。 搜索步径 一旦确定了搜索方向,那么我们可以通过求解得到搜索步径,当求解该问题成本较低时,可以采用该方法。该方法称为精确直线搜索。 然而实践中一般采用非精确直线搜索方法,譬如回溯直线搜索。算法如下图:
下降方向 在各个领域都广为应用的LMS算法也称为随机梯度算法(LMS算法和这里算法的区别和联系应该会另写一篇)。用负梯度作为下降的方向是一种和自然的选择,此外还有Newton方法。而最速下降方法是定义出的在某一特定范数下的方法。梯度下降和Netwon方法分别是二次范数和Hessian 范数下的最速下降方法。算法的收敛性和Hessian矩阵有关,此处不详细说明。 等式约束 对于标准的凸优化问题,等式约束是仿射的,这也就意味着该优化问题的定义域是一个向量子空间。一个自然的想法是在这个空间内进行下降,这种想法被证明是可行的。根据初始迭代点的兴致,可以分为两类。 (1)初始点可行:在可行域内迭代 (2)初始点不可行:迭代过程中逐步靠近可行域 不等式约束 如果我们不能解决一个问题,那么就消除这个问题。 采用示性函数可以将不等式约束隐含在代价函数中,这里带来的问题是——代价函数非凸。障碍方法被引入以解决这个问题。(内点法)这样,不等式约束就变成了等式约束或是无约束的情况了。 如果,我不知道该怎么选择搜索方向?
“凸优化”教学大纲 ?基本目的: 近年来,随着科学与工程的进步,凸优化理论与方法的研究迅猛发展,在科学与工程计算,数据科学,信号和图像处理,管理科学等诸多领域中得到了广泛应用。通过本课程的学习,掌握凸优化的基本概念,对偶理论,典型的几类凸优化问题的判别及其计算方法,熟悉相关计算软件 ?课程对象: 高年级本科生和研究生。 ?教材: (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学时