Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization

Abstract

While Nesterov's Accelerated Gradient Descent (AGD) efficiently solves constrained problems when the constraint set $X \subseteq \bbr^n$ is simple and easy to project onto, it remains an open question whether function-constrained problems ${\min }_{x\in X}\{F(x):g(x)\le 0\}$ can be solved as efficiently as unconstrained problems in terms of oracle complexity. We provide an affirmative answer by proposing the Accelerated Constrained Gradient Descent (ACGD) method, a single-loop algorithm that modifies AGD by replacing the descent step with a constrained descent step, adding only a few linear constraints to the prox mapping. ACGD achieves nearly the same oracle complexity as minimizing the optimal Lagrangian function (with the multiplier fixed at its optimal value). We establish matching lower bounds, demonstrating these complexity results are unimprovable. For large-scale problems with many constraints, we introduce ACGD-S, which replaces the computationally demanding constrained descent step with basic matrix-vector multiplications, maintaining optimal oracle and computation complexities. Together, these methods provide a nearly complete characterization of the hardness of smooth function-constrained optimization. Under the additional assumption that $X$ is bounded, we also propose adaptive versions that achieve an order-optimal oracle complexity without requiring knowledge of either the aggregate smoothness constant or the diameter of $X$; only the strong convexity modulus is required in the strongly convex case. We present encouraging numerical results demonstrating their efficiency.