Projection-Free Functional Constrained Optimization for Risk Aversion and Sparsity Control

arXiv:2210.05108v2 Announce Type: replace-cross Abstract: We study projection-free methods for functional constrained optimization with convex or smooth nonconvex objectives. Such problems arise in applications such as portfolio optimization and radiation therapy planning, where risk-aware criteria and sparsity frequently appear together. For the convex setting, we propose a Level Conditional Gradient (LCG) method that combines a level-set outer loop with a conditional gradient oracle for saddle-point subproblems, and we show an iteration complexity of $\mathcal{O}\big(\epsilon^{-2}\log(\epsilon^{-1})\big)$ for smooth and nonsmooth cases without dependence on the magnitude of an optimal dual Lagrange multiplier. For the nonconvex setting, we propose the Inexact Proximal Point LCG (IPP-LCG) method, which solves a sequence of convex subproblems by LCG and attains $\mathcal{O}\big(\epsilon^{-3}\log(\epsilon^{-1})\big)$ complexity for computing an \((\epsilon,\epsilon)\)-near-KKT point. Numerical results on portfolio selection and IMRT illustrate the practical sparsity/risk trade-offs of the proposed methods.