First-order methods for problems with O(1) functional constraints can have almost the same convergence rate as for unconstrained problems

DOI10.1137/20M1371579zbMATH Open1509.65054arXiv2010.02282MaRDI QIDQ6350586FDOQ6350586

Authors: Yangyang Xu 

Publication date: 5 October 2020

Abstract: First-order methods (FOMs) have recently been applied and analyzed for solving problems with complicated functional constraints. Existing works show that FOMs for functional constrained problems have lower-order convergence rates than those for unconstrained problems. In particular, an FOM for a smooth strongly-convex problem can have linear convergence, while it can only converge sublinearly for a constrained problem if the projection onto the constraint set is prohibited. In this paper, we point out that the slower convergence is caused by the large number of functional constraints but not the constraints themselves. When there are only $m=O(1)$ functional constraints, we show that an FOM can have almost the same convergence rate as that for solving an unconstrained problem, even without the projection onto the feasible set. In addition, given an $varepsilon>0$, we show that a complexity result that is better than a lower bound can be obtained, if there are only $m=o(varepsilo{n}^{-frac12})$ functional constraints. Our result is surprising but does not contradict to the existing lower complexity bound, because we focus on a specific subclass of problems. Experimental results on quadratically-constrained quadratic programs demonstrate our theory.

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonlinear programming (90C30) Abstract computational complexity for mathematical programming problems (90C60)

This page was built for publication: First-order methods for problems with O(1) functional constraints can have almost the same convergence rate as for unconstrained problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6350586)