Frank-Wolf最优化方法.docx

§1Frank-Wolf方法一、问题形式()其中为矩阵,,。记并设一阶连续可微。二、算法基本思想是一个凸多面体,任取,将在处线性展开用或()逼近原问题,这是一个线性规划问题,设是其最优解。若,则也是线性规划问题()的最优解,此时可证为原问题的K-T点。若,则由是()的最优解,故必有 从而即为在处的下降方向,沿此方向作有约束的一维搜索设最佳步长因子为,令当充分小时用取代,重复以上计算过程。三、算法迭代步骤1)给定初始点,允许误差,。2)求解线性规划问题,得最优解。3)若,Stop,;否则goto4)。4)进行一维搜索,得最优步长因子;令,,goto2)四、()的最优解存在,且对算法产生的点列,线性规划问题()的最优解总存在。则若迭代到某步,有,则为问题()的K-T点;若情形1)总不发生,则算法产生一有界无穷点列,其任意极限点都是原问题()的K-T点。证明:若情形1)出现,则也是问题()的最优解,故满足()的K-T条件:()而()的K-T条件:()()表明,,一起满足K-T条件(),故是原问题的K-T点。2)由点列包含在的极点的凸组合中,而均为的极点,故、均为有界点列。设为的任一极限点,即存在子列,使得:注意到点列满足:考虑点列、、,不失一般性,设,,否则,可以通过反复抽取子序列,使上式对某个子序列成立。由是的最优解,故,有且再由及取极限,有()不等式组()等价于:()若能证明即为问题的最优解,由本定理的第一部分可知,为原问题K-T点。下证:,若不然,由()即知必有故为处的下降方向,因而当充分小时,有进而有:()但为单调下降的有界序列,故存在而且即