Preprint · 2022 · Open access

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

Zhe Zhang, Guanghui Lan

arXiv (Cornell University) · Published 11 October 2022 · DOI 10.48550/arxiv.2210.05807

Free PDFView at the publisherCite this paper

In brief

“Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization” is a 2022 preprint by Zhe Zhang and Guanghui Lan, published in arXiv (Cornell University). OpenAlex counts 18 citations as of 16 November 2026. It is open access under a CC BY licence: the full text is free to read at arXiv (Cornell University).

Citations
18
Most cited in
2026 (8)
References
1
Authors
2

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) \leq 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.

Cite this paper

Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.

APA 7

Zhang, Z., & Lan, G. (2022). Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization. arXiv (Cornell University). https://doi.org/10.48550/arxiv.2210.05807

MLA 9

Zhang, Zhe, and Guanghui Lan. “Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization.” arXiv (Cornell University), 2022. https://doi.org/10.48550/arxiv.2210.05807.

Chicago

Zhang, Zhe and Guanghui Lan. 2022. “Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization.” arXiv (Cornell University). https://doi.org/10.48550/arxiv.2210.05807.

Harvard

Zhang, Z. and Lan, G. (2022) ‘Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization’, arXiv (Cornell University). doi:10.48550/arxiv.2210.05807.

IEEE

Z. Zhang and G. Lan, “Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization,” arXiv (Cornell University), 2022, doi: 10.48550/arxiv.2210.05807.

BibTeX

@misc{zhang2022solving,
  title     = {{Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization}},
  author    = {Zhang, Zhe and Lan, Guanghui},
  howpublished = {arXiv (Cornell University)},
  year      = {2022},
  doi       = {10.48550/arxiv.2210.05807},
  url       = {https://doi.org/10.48550/arxiv.2210.05807}
}

Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)

Citations by year

YearCitationsShare of the best year
202311
202444
202555
202688

Topic and keywords

Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques

  • oracle complexity
  • Lagrangian
  • lower bounds
  • adaptive algorithms
  • strong convexity

Work with this paper

Most-cited papers in Computer Science

All highly cited Computer Science papers

Questions about this paper

How do I cite this paper in APA style?

Zhang, Z., & Lan, G. (2022). Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization. arXiv (Cornell University). https://doi.org/10.48550/arxiv.2210.05807

How many times has this paper been cited?

18 times, according to OpenAlex on 16 November 2026. Google Scholar and Scopus count different sets of sources, so their numbers differ.

Is this paper free to read?

Yes. It is open access: read the free full text at arXiv (Cornell University).

Who wrote this paper?

Zhe Zhang, Guanghui Lan.

What is the DOI of this paper?

10.48550/arxiv.2210.05807. The permanent link is https://doi.org/10.48550/arxiv.2210.05807.

Bibliographic data from OpenAlex (CC0), last checked 16 November 2026. ResearchGuru does not host this paper; the links go to the publisher or the repository that does.