Relative Primal--Dual Gap Certificates for Operator-Composite Trust-Region Methods
TL;DR
This work proves $O(j^{-1})$ gap bounds for both recovered and averaged primal candidates and gives a sharper bound on the primal error for exactly recovered points, and proves the dual proximal-gradient method produces finite gaps tending to zero.
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(\varepsilon^{-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.