Rates of convergence for conditional gradient algorithms near singular and nonsingular extremals
Rates of convergence for conditional gradient algorithms near singular and nonsingular extremals
复制标题
条件梯度算法在奇异极值和非奇异极值附近的收敛速度
DOI：
--
复制
发表时间：
1979
期刊：
影响因子：
--
通讯作者：
J. Dunn
中科院分区：
文献类型：
--
作者：
J. Dunn
考虑了两种条件梯度算法的问题min¿F，具有Banach空间的有界凸子集。这两种方法都不需要行搜索；一种方法不需要Lipschitz常数。在这两种情况下，收敛速率估计是相似的，并且主要依赖于集合值算子T的连续性，其不动点是F的极值。T at¿的连续性由a（¿）= inf{¿= |y¿¿，||；Y -¿||>¿}随着增加而增长。结果表明，对于凸F和Lipschitz连续F'，算法收敛于o(1/n)，几何收敛，或在有限多步收敛，取决于a（¿）> = o（¿）>，还是a（¿）> a¿2 = a >，还是a（¿）> a¿= a >0。这三个抽象条件与一类重要的具有有限控制输入的最优控制问题的非奇异性概念密切相关。当meas {t|s(t)=0} =0时满足第一个条件（在L1中），其中s（¿）为与极值控制¿（¿）相关联的开关函数；第二个条件满足于s（¿）有有限多个零，且都是简单的（典型的砰砰极值）；当s（¿）离零有界时，满足第三个条件。强凸性或一致凸性假设在主要的收敛定理中不被调用。其中一个定理可以推广到拟凸泛函的一个大子类。
Two conditional gradient algorithms are considered for the problem min ¿F, with ¿ a bounded convex subset of a Banach space. Neither method requires line search; one method needs no Lipschitz constants. Convergence rate estimates are similar in the two cases, and depend critically on the continuity properties of a set valued operator T whose fixed points, ¿, are the extremals of F in ¿. The continuity properties of T at ¿ are determined by the way a(¿) = inf{¿= |y¿¿,||;y-¿||>¿} grows with increasing ¿. It is shown that for convex F and Lipschitz continuous F', the algorithms converge like o(1/n), geometrically, or in finitely many steps, according to whether a(¿)>0 for ¿>0, or a(¿)>A¿2 with A>0, or a(¿)>A¿ with A>0. These three abstract conditions are closely related to established notions of nonsingularity for an important class of optimal control problems with bounded control inputs. The first con-- dition is satisfied (in L1)when meas {t|s(t)=0} =0, where s(¿) is the switching function associated with the extremal control ¿(¿); the second condition is satisfied when s(¿) has finitely many zeros, all simple (typical of the bang-bang extremal); the third condition is satisfied when s(¿) is bounded away from zero. Strong or uniform convexity assumptions are not invoked in the main: convergence theorems. One of the theorems can be extended to a large subclass of quasiconvex functionals F.