Certificate-Coupled DCA for the Trust-Region Subproblem: Early Structural Escape and Progressive Global Certification

Abstract

We study the nonconvex trust-region subproblem by a certificate-coupled difference-of-convex algorithm that incorporates spectral information before exact first-order stationarity is attained. The method maintains a persistent randomized Krylov subspace together with the DCA iterates. Near stationarity, a sufficiently negative shifted Rayleigh quotient yields an explicit feasible correction with a quantitative decrease in the objective value; otherwise, completion of a prescribed Lanczos depth provides, with high probability, an approximate positive-semidefiniteness certificate. The same Krylov subspace also provides a certified upper bound on the largest eigenvalue for selecting the DC curvature parameter at subsequent accuracy stages. We prove a uniform negative-curvature correction result over the trust region, covering the near-orthogonal hard-case regime, together with finite-termination and work bounds at fixed tolerances and a quantitative objective-gap certificate. Under a progressive accuracy schedule, the certified objective values converge to the global optimum and the iterates converge in distance to the global solution set, while the Krylov subspace is retained across corrections and accuracy stages. Numerical experiments illustrate the phenomena established by the analysis: negative-curvature corrections can occur before the corresponding post-convergence spectral corrections, the quantitative decrease bound is satisfied in all tested near-orthogonal instances, and retaining the Krylov subspace reduces the median number of spectral matrix-vector products by approximately a factor of $2.6$ relative to restarting the spectral process in the controlled comparison.