Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.04613 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915624773484544 |
|---|---|
| author | Khoo, Yuehaw Tang, Tianyun Toh, Kim-Chuan |
| author_facet | Khoo, Yuehaw Tang, Tianyun Toh, Kim-Chuan |
| contents | In this work, we propose a novel Bregman ADMM with nonlinear dual update to solve the Bethe variational problem (BVP), a key optimization formulation in graphical models and statistical physics. Our algorithm provides rigorous convergence guarantees, even if the objective function of BVP is non-convex and non-Lipschitz continuous on the boundary. A central result of our analysis is proving that the entries in local minima of BVP are strictly positive, effectively resolving non-smoothness issues caused by zero entries. Beyond theoretical guarantees, the algorithm possesses high level of separability and parallelizability to achieve highly efficient subproblem computation. Our Bregman ADMM can be easily extended to solve the quantum Bethe variational problem. Numerical experiments are conducted to validate the effectiveness and robustness of the proposed method. Based on this research, we have released an open-source package of the proposed method at https://github.com/TTYmath/BADMM-BVP. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_04613 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Bregman ADMM for Bethe variational problem Khoo, Yuehaw Tang, Tianyun Toh, Kim-Chuan Optimization and Control 65K10, 90C30, 90C35 In this work, we propose a novel Bregman ADMM with nonlinear dual update to solve the Bethe variational problem (BVP), a key optimization formulation in graphical models and statistical physics. Our algorithm provides rigorous convergence guarantees, even if the objective function of BVP is non-convex and non-Lipschitz continuous on the boundary. A central result of our analysis is proving that the entries in local minima of BVP are strictly positive, effectively resolving non-smoothness issues caused by zero entries. Beyond theoretical guarantees, the algorithm possesses high level of separability and parallelizability to achieve highly efficient subproblem computation. Our Bregman ADMM can be easily extended to solve the quantum Bethe variational problem. Numerical experiments are conducted to validate the effectiveness and robustness of the proposed method. Based on this research, we have released an open-source package of the proposed method at https://github.com/TTYmath/BADMM-BVP. |
| title | A Bregman ADMM for Bethe variational problem |
| topic | Optimization and Control 65K10, 90C30, 90C35 |
| url | https://arxiv.org/abs/2502.04613 |