Frank-Wolf最优化方法5页.docx

1 Frank-Wolf方法一、问题形式 （1.1） 其中为矩阵，。记并设一阶连续可微。二、算法基本思想 是一个凸多面体，任取，将在处线性展开 用 或 （1.2） 逼近原问题，这是一个线性规划问题，设是其最优解。1） 若，则也是线性规划问题（1.2）的最优解，此时可证为原问题的K-T点。2） 若，则由是（1.2）的最优解，故必有从而 即为在处的下降方向，沿此方向作有约束的一维搜索设最佳步长因子为，令当充分小时 用取代，重复以上计算过程。三、算法迭代步骤1）给定初始点