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.
Related
- Regulating All Induced Equilibria: Counterexample-Coupled Incentive–Certificate Synthesis for Financial Stability
- Multivariate Cryptography-Based Anonymous Certificate Scheme
- Certificate-Carrying Distributed Model Predictive Control on Product Manifolds with SO(3)
- Constant Steps Are s-Composable: An Exact Interpolation Certificate for Gradient Descent
- Nonexistence of a Strongly Regular Graph with Parameters (266,45,0,9): A Certificate-Free Lean Proof
BibTeX
@misc{nguyen2026certificatecoupled,
title = {{Certificate-Coupled DCA for the Trust-Region Subproblem: Early Structural Escape and Progressive Global Certification}},
author = {Binh T. Nguyen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.00172},
eprint = {2610.00172},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.00172},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Certificate-Coupled DCA for the Trust-Region Subproblem: Early Structural Escape and Progressive Global Certification
AU - Binh T. Nguyen
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.00172
UR - https://arxiv.org/abs/2610.00172
AB - 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.
ER -