论文标题
有条件的梯度方法用于凸优化，并具有一般仿射和非线性约束
Conditional Gradient Methods for Convex Optimization with General Affine and Nonlinear Constraints
论文作者
论文摘要
有条件的梯度方法最近在机器学习和优化社区中引起了很多关注。这些简单的方法可以保证生成稀疏的解决方案。此外，如果没有完整梯度的计算，他们有时也可以处理大规模的问题，即使决策变量数量成倍增加。本文旨在通过提出新的条件梯度方法来显着扩大这些方法的应用领域，以解决一般仿射和非线性约束的凸优化问题。更具体地说，我们首先提出了一种新的约束外推条件梯度（COEXCG）方法，该方法可以实现$ {\ cal o}（1/ε^2）$迭代复杂性，用于平滑和结构化的非式非函数约束凸优化。我们进一步开发了COEXCG的新型变体，即推断和双重正则条件梯度（COEXDURCG）方法，这些方法可以达到与COEXCG相似的迭代复杂性，但允许对算法参数进行适应性选择。我们说明了这些方法在解决医疗保健行业引起的一系列重要的放射治疗治疗计划问题方面的有效性。据我们所知，所有算法方案及其复杂性结果在无投射方法领域都是新的。
Conditional gradient methods have attracted much attention in both machine learning and optimization communities recently. These simple methods can guarantee the generation of sparse solutions. In addition, without the computation of full gradients, they can handle huge-scale problems sometimes even with an exponentially increasing number of decision variables. This paper aims to significantly expand the application areas of these methods by presenting new conditional gradient methods for solving convex optimization problems with general affine and nonlinear constraints. More specifically, we first present a new constraint extrapolated condition gradient (CoexCG) method that can achieve an ${\cal O}(1/ε^2)$ iteration complexity for both smooth and structured nonsmooth function constrained convex optimization. We further develop novel variants of CoexCG, namely constraint extrapolated and dual regularized conditional gradient (CoexDurCG) methods, that can achieve similar iteration complexity to CoexCG but allow adaptive selection for algorithmic parameters. We illustrate the effectiveness of these methods for solving an important class of radiation therapy treatment planning problems arising from healthcare industry. To the best of our knowledge, all the algorithmic schemes and their complexity results are new in the area of projection-free methods.
