PreprintarXiv licencearXiv
Accelerated Prox-Level Methods for Unknown Piecewise-Smooth Optimization II: Function-constrained Optimization
Abstract
We introduce an anytime, almost parameter-free algorithm for convex function-constrained optimization, in which the objective and constraint functions are unknown piecewise-smooth. Our algorithm, Restarted Penalty APEX (Penalty Accelerated Prox-level method for Exploring Piecewise Smoothness), is an accelerated bundle-level method based on the penalty approach. For problems satisfying quadratic growth, the proposed method is the first to achieve optimal oracle complexity without knowing the growth modulus or the exact penalty coefficient. Furthermore, Restarted Penalty APEX generates a verifiable certificate that bounds both the optimality gap and the constraint violation. This certificate also appears to be new to the literature.
Related
- Variance-reduced First-order Methods for Finite-sum Function Constrained Convex Optimization
- Restarted Accelerated Primal-Dual Algorithms with Adaptive Stepsizes for Nonlinear Conic Constrained Convex Optimization
- Region-Preserving Accelerated Gradient Methods for Geodesically Convex Optimization
- First-Order Methods for Wasserstein Distributionally Robust Constrained Optimization
- Adaptive two-points zero-order accelerated methods for stochastic convex optimization problems
BibTeX
@misc{lin2026accelerated,
title = {{Accelerated Prox-Level Methods for Unknown Piecewise-Smooth Optimization II: Function-constrained Optimization}},
author = {Zhenwei Lin and Zhe Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.03251},
eprint = {2609.03251},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.03251},
}
RIS
TY - UNPB
TI - Accelerated Prox-Level Methods for Unknown Piecewise-Smooth Optimization II: Function-constrained Optimization
AU - Zhenwei Lin
AU - Zhe Zhang
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2609.03251
UR - https://arxiv.org/abs/2609.03251
AB - We introduce an anytime, almost parameter-free algorithm for convex function-constrained optimization, in which the objective and constraint functions are unknown piecewise-smooth. Our algorithm, Restarted Penalty APEX (Penalty Accelerated Prox-level method for Exploring Piecewise Smoothness), is an accelerated bundle-level method based on the penalty approach. For problems satisfying quadratic growth, the proposed method is the first to achieve optimal oracle complexity without knowing the growth modulus or the exact penalty coefficient. Furthermore, Restarted Penalty APEX generates a verifiable certificate that bounds both the optimality gap and the constraint violation. This certificate also appears to be new to the literature.
ER -