Conditional Gradient Methods for Convex Optimization with General Affine and Nonlinear Constraints
This work expands the applicability of projection-free methods to constrained convex optimization, offering potential benefits for large-scale problems in domains like healthcare, though it is incremental in extending existing conditional gradient frameworks.
The paper introduces new conditional gradient methods for convex optimization with general affine and nonlinear constraints, achieving O(1/ε²) iteration complexity for smooth and structured nonsmooth problems, and demonstrates their effectiveness in radiation therapy treatment planning.
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.