PaperlayerView exact revision on arXiv

Source-linked AI summary

Relative Primal--Dual Gap Certificates for Operator-Composite Trust-Region Methods

Harbir Antil

arXiv:2609.27348v1math.OCcs.NAmath.APmath.NA

TL;DR

The paper studies trust-region minimization with a smooth term and a convex regularizer composed through a linear map. It uses primal–dual gaps and an absolute stationarity test to control approximate steps, with finite termination and an O(epsilon^-2) outer-trial bound.

  • Problem

    The paper addresses trust-region minimization combining a smooth, potentially nonconvex term with a convex regularizer applied through a linear composition.

    Source: §1 · p. 1

  • Method

    A relative primal–dual gap controls approximate proximal-step error and linear-model decrease, while a separate absolute test certifies stationarity tolerance.

    Source: §1 · p. 2

  • Results

    O(epsilon^-2) outer trials suffice for finite termination with chi(w) <= epsilon, for every 0 < epsilon <= 1.

    Source: §4.3 · p. 11

  • Takeaways & Limitations

    The inner procedure need not attain a dual solution or compute an exact proximal point, provided its gaps are finite, evaluable, and tend to zero.

    Source: §3.1 · p. 7

    For indicator regularizers, a finite gap requires a feasible tested primal point; the stated regularity assumption excludes nontrivial indicator constraints on the operator image.

    Source: §1 · p. 2, §5 · p. 13

Abstract

from arXiv · show

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.

1. Introduction

The paper develops computable primal–dual gap certificates for inexact proximal steps in trust-region methods for smooth, possibly nonconvex objectives with convex linear compositions. These certificates support outer convergence guarantees without exact trust-region model minimization.

1. Introduction

  • Duality-based a posteriori error analysis motivates the certificate: the gap measures combined primal and dual errors for admissible approximations, regardless of how they were computed.The outer objective need not satisfy the convex duality relations used for the proximal subproblem.Source: §1 · p. 2
  • A relative primal–dual gap bounds the computed step relative to the exact step and guarantees decrease of the linear composite model.Both properties are needed for the trust-region analysis.Source: §1 · p. 2
  • Earlier work studies inexact proximal trust-region methods [20] [4] [17] and dual-gap error bounds or tests [21–23, 25, 10, 18].These works provide related approximation conditions and candidate-construction methods.Source: §1 · p. 2
  • The gap-based step bounds and a separate absolute stationarity test yield convergence of the stationarity measure and an O(epsilon^-2) bound on outer trials.The analysis allows bounded, possibly indefinite model operators and does not require exact trust-region model minimization.Source: §1 · p. 2
  • The outer theorem assumes computable inner gaps tending to zero; the analysis assumes exact smooth evaluations and linear operations.For extended-valued regularizers, the tested primal point must have finite objective value.Source: §1 · pp. 2–3

2. Problem setting

The problem setting combines a smooth function with a proper, convex, lower-semicontinuous regularizer composed with a linear map. The proximal-gradient step supplies a stationarity measure for this composite objective.

2. Problem setting

  • The operator acts between a Hilbert space and a Banach space, with its Banach adjoint mapping into the dual of the Hilbert space.The setup uses a Riesz map for the Hilbert space, without identifying the Banach space with its dual.Source: §2 · p. 3
  • The setting assumes a globally Lipschitz gradient, a proper convex lower-semicontinuous regularizer, a nonempty effective domain, and an objective bounded below.The smooth term need not be convex.Source: §2 · p. 3
  • The unique proximal-gradient step satisfies a subgradient optimality inclusion, and a zero step is equivalent to composite stationarity.The zero-step characterization holds for one, equivalently every, positive step parameter.Source: §2 · p. 3
  • The proximal-gradient step is defined by applying the proximal map of the composite regularizer to a gradient-shifted point.The convergence analysis uses the stationarity measure chi, but the algorithm does not evaluate it exactly.Source: §2 · p. 3
  • The stationarity measure chi is Lipschitz on the Hilbert space and vanishes exactly at points satisfying the composite first-order condition.A zero value also implies membership in the regularizer's effective domain.Source: §2 · p. 4

3. Primal–dual gap certificate

The section develops primal–dual gap certificates that bound proximal-solution error and control trust-region steps without requiring dual attainment. A separate absolute stationarity test complements the relative certificate to ensure finite termination, including at stationary points.

3. Primal–dual gap certificate

  • The computable gap splits into optimality defects and bounds proximal-solution error without requiring dual attainment.The gap is evaluated from the candidate pair; interpreting its exact error identity uses a zero-gap dual solution.Source: §3 · pp. 4–5
  • The relative certificate controls step error and norm, and under t||B||≤1−σ guarantees descent and model decrease.If the proximal stationarity step is zero, the approximate step and its gap are also zero.Source: §3 · p. 6
  • For certified recovered pairs, the step-error bound sharpens to (σ/2)||s||; the factor-two improvement is sharp even for R(x)=|x|.The sharper bounds require a finite gap and Ty in dom R; for an indicator regularizer, the tested point must be feasible.Source: §3 · pp. 5–6

3.1 A computable stationarity test

  • The absolute test handles stationary requests where the relative rule demands zero gap, while nonzero proximal steps pass the relative test finitely.Under the inner approximation property, the combined stationarity test terminates finitely and its absolute-test outcome certifies χ(w)≤ε.Source: §3.1 · pp. 7–8

4. Cauchy steps and trust-region convergence

The section constructs finite Cauchy searches with certified model decrease, then establishes convergence to stationarity and finite termination with an O(ε^-2) outer-trial bound.

4. Cauchy steps and trust-region convergence

  • The geometric Cauchy search terminates after finitely many inner iterations and parameter reductions, returning a step within the trust-region radius.At each reduced proximal parameter, the search uses a relative certificate and returns the first certified step satisfying the radius test.Source: §4 · p. 8

4.1 Model agreement and lower bounds for the radius

  • Whenever Δk ≤ cχk, every trial is very successful because the nonsmooth terms cancel from actual-minus-predicted reduction and the smooth Taylor error is bounded.The Taylor error is at most Lf||dk||²/2.Source: §4.1 · p. 10

4.2 Convergence to stationarity

  • For infinite sequences satisfying the algorithm rules, χ(wk) tends to zero; every strong accumulation point is stationary, and in finite dimensions every accumulation point is stationary.The convergence result does not require an inner procedure to certify exact stationarity in finitely many iterations.Source: §4.2 · p. 10
  • The stationarity conclusion is for strong accumulation points; weak subsequential compactness alone does not justify passage through the generally nonlinear proximal stationarity map.Additional assumptions are needed to conclude stationarity for arbitrary weak accumulation points.Source: §4.2 · p. 11

4.3 Finite termination and number of outer iterations

  • Algorithm 4.3 terminates at χ(w) ≤ ε after O(ε^-2) outer trials; this bound excludes inner proximal iterations and applications of T and T*.The estimate holds with the initial point, radii, algorithmic parameters, and uniform bound on ||Bk|| fixed independently of ε.Source: §4.3 · p. 11

5. A dual proximal-gradient inner solver

The dual proximal-gradient method supplies finite primal–dual gaps tending to zero under the stated Hilbert-space regularity and evaluation assumptions. Recovered and averaged candidates support inner stopping tests, while exact recovery also permits a less restrictive test.

5. A dual proximal-gradient inner solver

  • O(j^-1) gap bounds for recovered and averaged primal candidates improve on transferring an O(j^-1) dual objective estimate through primal distance.Finite gaps tending to zero yield finite termination of the stated inner tests.Source: §5 · pp. 13–15
  • The dual objective has a minimizer under Assumption 5.1, and its associated recovered point is the unique minimizer of the proximal objective.The minimizing dual point has norm at most L_R.Source: §5 · p. 13
  • The dual proximal-gradient iteration has finite gaps tending to zero when R is finite and globally Lipschitz and the required evaluations are available.The step size satisfies γt∥T∥^2 ≤ 1; the iteration bounds use a known Lipschitz constant, but the gap tests do not.Source: §5 · pp. 13–14

5.1 An optional averaged primal candidate

  • The averaged primal candidate has a vanishing full gap even though its residual need not vanish.Testing it requires the full gap, including both the residual and Fenchel-defect terms.Source: §5.1 · pp. 15–16

5.2 Sufficient inner iteration counts

  • ε_gap = σ^2∥p(w; t)∥^2_W/(8t) is sufficient for the corresponding candidate to pass the relative test.The stated iteration bounds give sufficient inner counts for either the recovered or averaged candidate.Source: §5.2 · p. 16

5.3 An optional test for recovered pairs

  • An exact recovered pair permits twice the gap allowed by the original test while retaining the same conclusions.The outer Cauchy search, convergence, and trial estimate retain their constants; averaged candidates continue to use the original tests.Source: §5.3 · p. 17

6. A semilinear control problem with total variation

The application is a semilinear elliptic control problem with total-variation regularization, analyzed and computed using the full H1 control metric. The paper establishes smoothness properties for the reduced objective and gives an H1 regularity result for minimizers on convex domains.

6. A semilinear control problem with total variation

  • The state solves -Δu + u^3 = z with zero boundary data, and the control problem uses total variation together with a quadratic L2 control cost.The control has no prescribed boundary trace.Source: §6 · p. 17

6.1 Smooth part and the algorithmic assumptions

  • The full H1 metric defines the gradient, proximal subproblems, and trust-region radii, while the quadratic control cost remains an L2 cost.The state map and reduced functional are twice continuously differentiable, and the reduced functional has a globally bounded Hessian.Source: §6 · p. 17, §6.1 · p. 18

6.2 H1 control

  • On a convex domain, every minimizer of the BV-extended problem belongs to H1, and the original problem attains its minimum in the control space.The BV-extended problem has a global minimizer on the stated bounded Lipschitz domains.Source: §6.2 · p. 19

7. Numerical experiments

The experiments implement the method on finite-element meshes using an H1 metric and unsmoothed total variation. Across the tested meshes, outer and state Newton counts remain constant, while interior-point totals vary.

7. Numerical experiments

  • The discrete objective uses continuous piecewise affine controls and states, with quadrature integrating the isotropic total-variation term exactly and without smoothing.The control space uses the full H1 inner product.Source: §7 · p. 19

7.1 Implementation

  • The implementation tests feasible projected multipliers using both terms of the gap certificate, and all reported proximal calls terminate before switching from accelerated to ordinary dual updates.The conic model candidate is scaled to the trust region and used only when its predicted reduction is at least that of the Cauchy step.Source: §7.1 · pp. 19–20

7.2 Mesh refinement

  • 28–52 interior-point iterations were used across meshes, while outer and state Newton counts remained constant.Both outer trials were accepted on every mesh; the reported stationarity measure is for the discrete problem.Source: Table 1 · p. 21, §7.2 · p. 21

A. PDE analysis for the semilinear control problem

The appendix sets the Sobolev space and norm used in its PDE estimates, with dimension bounded to ensure the required embedding into L4.

A. PDE analysis for the semilinear control problem

A.1 State map, derivatives, and a global Hessian bound

The elliptic state operator is shown to be a smooth bijection with a smooth inverse, yielding a differentiable state map. Its derivative equations support a global Hessian bound for the reduced objective.

A.1 State map, derivatives, and a global Hessian bound

  • The embedding V into L4 makes the cubic term continuous, so A(u) = −Δu + u^3 is smooth.Strong monotonicity and A(0) = 0 then imply coercivity, and the monotone-operator theorem gives bijectivity.Source: §A.1 · p. 22
  • The state map is smooth because each derivative Ju = −Δ + 3u^2 is coercive and invertible, yielding local inverses that agree globally.Strong monotonicity also gives a Lipschitz bound for state differences in terms of control differences.Source: §A.1 · p. 22
  • The first and second state derivatives satisfy J_u v_d = d and J_u w_{d,e} = −6u v_d v_e.These equations result from differentiating the state equation.Source: §A.1 · p. 22
  • The reduced objective is C2, and the control-independent estimate bounds its Hessian on W.The bound follows from testing the linearized equation, applying Young’s inequality, and using the Riesz identity.Source: §A.1 · pp. 22–23

A.2 Existence and regularity of optimal controls

A minimizing-sequence argument establishes existence of an optimal control, and a regularity result places relaxed minimizers in H1. With the multiplier fixed, the associated convex problem has a unique minimizer.

A.2 Existence and regularity of optimal controls

  • A minimizing sequence is bounded in L2 and BV; compactness and lower semicontinuity yield a minimizer of the relaxed problem.The tracking term converges using compactness of L2 into V* and strong monotonicity of the state operator.Source: §A.2 · p. 23
  • Minimality along segments and convexity of total variation show that the fixed-λ̄ convex problem has a unique minimizer.The uniqueness uses the positive quadratic control cost.Source: §A.2 · p. 23
  • For convex domains, the Neumann-case regularity result [11] gives an H1 minimizer, so every relaxed minimizer also solves the original problem.The argument applies the cited result with a = α/β and g = −λ̄/β.Source: §A.2 · p. 23
Loading 2609.27348v1…