Relative Primal--Dual Gap Certificates for Operator-Composite Trust-Region Methods
Abstract
We study trust-region minimization of a smooth, possibly nonconvex functional plus a convex functional composed with a bounded linear operator. A relative primal--dual gap condition controls both the error in an approximate proximal-gradient step and its linear-model decrease. Together with a computable absolute stationarity test, it yields a finite Cauchy search, convergence of the proximal stationarity measure to zero, and an O(ε−2) bound on outer trials. The outer analysis allows the linear operator to take values in a Banach space and does not require dual attainment. When the operator takes values in a Hilbert space and the regularizer is finite and Lipschitz, the dual proximal-gradient method produces finite gaps tending to zero, provided the required proximal maps and functional values can be evaluated. We prove O(j−1) gap bounds for both recovered and averaged primal candidates and give a sharper bound on the primal error for exactly recovered points. A semilinear elliptic control problem with unsmoothed total-variation regularization and an L2 control cost illustrates the method in the full H1 metric. Across five meshes, outer and state Newton counts remain constant, while interior-point iteration counts vary mildly.
Related
- Primal-Dual Error Bounds and KKT Metric Subregularity in Convex Composite Optimization
- SafeRestore: Detector-Relative Risk Certificates for Selective Industrial Image Restoration
- Unifying Variational View of Accelerated Primal-Dual Methods
- Primal-Dual Adaptive Subgradient Methods
- Inertial Primal-Dual Dynamics Methods Featuring Implicit Hessian-Driven Damping for Convex Optimization Problems in Continuous and Discrete Time
BibTeX
@misc{antil2026relative,
title = {{Relative Primal--Dual Gap Certificates for Operator-Composite Trust-Region Methods}},
author = {Harbir Antil},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.27348},
eprint = {2609.27348},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.27348},
}
RIS
TY - UNPB
TI - Relative Primal--Dual Gap Certificates for Operator-Composite Trust-Region Methods
AU - Harbir Antil
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.27348
UR - https://arxiv.org/abs/2609.27348
AB - We study trust-region minimization of a smooth, possibly nonconvex functional plus a convex functional composed with a bounded linear operator. A relative primal--dual gap condition controls both the error in an approximate proximal-gradient step and its linear-model decrease. Together with a computable absolute stationarity test, it yields a finite Cauchy search, convergence of the proximal stationarity measure to zero, and an O(ε^−2) bound on outer trials. The outer analysis allows the linear operator to take values in a Banach space and does not require dual attainment. When the operator takes values in a Hilbert space and the regularizer is finite and Lipschitz, the dual proximal-gradient method produces finite gaps tending to zero, provided the required proximal maps and functional values can be evaluated. We prove O(j^−1) gap bounds for both recovered and averaged primal candidates and give a sharper bound on the primal error for exactly recovered points. A semilinear elliptic control problem with unsmoothed total-variation regularization and an L^2 control cost illustrates the method in the full H^1 metric. Across five meshes, outer and state Newton counts remain constant, while interior-point iteration counts vary mildly.
ER -