最优化理论与算法(第十一章).docVIP

第十一章 约束最优化问题的可行方向法 §1 Frank-Wolf方法 一、问题形式 （11.1） 其中为矩阵，，。记并设一阶连续可微。 二、算法基本思想 是一个凸多面体，任取，将在处线性展开 用 或 （11.2） 逼近原问题，这是一个线性规划问题，设是其最优解。 若，则也是线性规划问题（11.2）的最优解，此时可证为原问题的K-T点。 若，则由是（11.2）的最优解，故必有 从而 即为在处的下降方向，沿此方向作有约束的一维有哪些信誉好的足球投注网站 　　　　　　　　　　　 设最佳步长因子为，令 当充分小时 　　　　 　　　　　　 用取代，重复以上计算过程。 　 三、算法迭代步骤 1）给定初始点，允许误差，。 2）求解线性规划问题，得最优解。 3）若，Stop,；否则go to 4)。 4）进行一维有哪些信誉好的足球投注网站，得最优步长因子； 令，，go to 2) 四、算法收敛性定理 定理11.1设非线性规划问题（11.1）的最优解存在，且对算法产生的点列，线性规划问题 （11.3） 的最优解总存在。则 若迭代到某步，有，则为问题（11.1）的K-T点； 若情形1）总不发生，则算法产生一有界无穷点列，其任意极限点都是原问题（11.1）的K-T点。 证明：若情形1）出现，则也是问题（11.3）的最优解，故满足（11.3）的K-T条件： （11.4） 而(11.1)的K-T条件： （11.5） （11.4）表明，，一起满足K-T条件（11.5），故是原问题的K-T点。 2）由点列包含在的极点的凸组合中，而均为的极点，故、均为有界点列。设为的任一极限点，即存在子列，使得： 注意到点列满足： 考虑点列、、，不失一般性，设 ， ， 否则，可以通过反复抽取子序列，使上式对某个子序列成立。由 是的最优解，故，有 且 再由 及 取极限，有 （11.6） 不等式组（11.6）等价于： （11.7） 若能证明 即为问题 的最优解，由本定理的第一部分可知，为原问题K-T点。下证：，若不然，由（11.7）即知必有 故为处的下降方向，因而当充分小时，有 进而有： （11.8） 但为单调下降的有界序列，故存在 而且 即 与（11.8）矛盾，故必有。 §2 Rosen的梯度投影法 一、问题形式 （11.9） 二、算法基本思想 该算法的基本思想是将无约束的最速下降算法推广到有约束情形。 若当前迭代点位于约束域内部，此时负梯度方向为可行下降方向； 若位于约束域边界上，情况就不同了，此时应将负梯度方向向可行域内部投影，以保证方向是可行下降方向。 设是当前迭代点（可行点），显然是下降方向，但为了使其为可行方向，应对其实施改造（投影）。记为的紧约束集合，改造后的向量应满足 或 即 这里，由与紧约束对应的系数向量（为列向量）构成的矩阵。以上分析表明需将向上投影，投影算子为： 投影算子一般满足： ， 由此 若，则为处的一个可行下降方向。 设为当前迭代点，列满秩，为相应的投影矩阵，且，令 将分块为