Semidefinite Implementations of the Proximal Point Algorithm and Consequences for Progressive Decoupling in Optimization
Abstract
The proximal point algorithm for finding a zero of a maximal monotone mapping is the engine that drives augmented Lagrangian methods and various splitting schemes in convex optimization, where proximal terms that are merely positive semidefinite can be helpful in preconditioning. Here a semidefinite extension of that algorithm is developed with new features which guarantee convergence, typically even linear convergence, in broader territory than previously foreseen. Moreover, inexact minimization is allowed in the subproblems in a variable-metric implementation which might open up quasi-Newton-like approaches. The key to the extension is applying an advanced form of the positive definite proximal point algorithm to a projected monotone mapping derived from the given mapping, and combining that with a completion step. For this to work, the maximality of the projected mapping is essential, but maximality is not automatic. The circumstances that guarantee maximality are definitively analyzed and convenient criteria for maximality are thereby identified. Consequences of the extended algorithm are worked out for application to convex inf-projection, augmented Lagrangian steps, and bracketed progressive decoupling based on Spingarn's partial inverse as a scheme for problem decomposition.
Related
- Solving Quasi-Variational Inequalities Using the Progressive Decoupling of Linkages
- Low-Rank and Lifted Semidefinite Programming for Mixed-Integer Polynomial Power Grid Optimization
- TinySDP: Real Time Semidefinite Optimization for Certifiable and Agile Edge Robotics
- Optimization for One, Feasibility for Most: Decoupling Optimization from Feasibility in Chance-Constrained Programs
- Learning What to Evaluate: Correlation-Aware Decoupling for Multiobjective Bayesian Optimization
BibTeX
@misc{li2026semidefinite,
title = {{Semidefinite Implementations of the Proximal Point Algorithm and Consequences for Progressive Decoupling in Optimization}},
author = {Xudong Li and R. Tyrrell Rockafellar and Defeng Sun},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.23519},
eprint = {2609.23519},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23519},
}
RIS
TY - UNPB
TI - Semidefinite Implementations of the Proximal Point Algorithm and Consequences for Progressive Decoupling in Optimization
AU - Xudong Li
AU - R. Tyrrell Rockafellar
AU - Defeng Sun
PY - 2026
DA - 2026/09/20
PB - arXiv
DO - 10.48550/arxiv.2609.23519
UR - https://arxiv.org/abs/2609.23519
AB - The proximal point algorithm for finding a zero of a maximal monotone mapping is the engine that drives augmented Lagrangian methods and various splitting schemes in convex optimization, where proximal terms that are merely positive semidefinite can be helpful in preconditioning. Here a semidefinite extension of that algorithm is developed with new features which guarantee convergence, typically even linear convergence, in broader territory than previously foreseen. Moreover, inexact minimization is allowed in the subproblems in a variable-metric implementation which might open up quasi-Newton-like approaches. The key to the extension is applying an advanced form of the positive definite proximal point algorithm to a projected monotone mapping derived from the given mapping, and combining that with a completion step. For this to work, the maximality of the projected mapping is essential, but maximality is not automatic. The circumstances that guarantee maximality are definitively analyzed and convenient criteria for maximality are thereby identified. Consequences of the extended algorithm are worked out for application to convex inf-projection, augmented Lagrangian steps, and bracketed progressive decoupling based on Spingarn's partial inverse as a scheme for problem decomposition.
ER -