A Relaxation Method for Nonsmooth Nonlinear Optimization with Binary Constraints
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915710898274304 |
|---|---|
| author | Xiao, Lianghai Qian, Yitian Pan, Shaohua |
| author_facet | Xiao, Lianghai Qian, Yitian Pan, Shaohua |
| contents | We study binary optimization problems of the form \( \min_{x\in\{-1,1\}^n} f(Ax-b) \) with possibly nonsmooth loss \(f\). Following the lifted rank-one semidefinite programming (SDP) approach\cite{qian2023matrix}, we develop a majorization-minimization algorithm by using the difference-of-convexity (DC) reformuation for the rank-one constraint and the Moreau envelop for the nonsmooth loss. We provide global complexity guarantees for the proposed \textbf{D}ifference of \textbf{C}onvex \textbf{R}elaxation \textbf{A}lgorithm (DCRA) and show that it produces an approximately feasible binary solution with an explicit bound on the optimality gap. Numerical experiments on synthetic and real datasets confirm that our method achieves superior accuracy and scalability compared with existing approaches. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_03008 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Relaxation Method for Nonsmooth Nonlinear Optimization with Binary Constraints Xiao, Lianghai Qian, Yitian Pan, Shaohua Optimization and Control G.1.6 We study binary optimization problems of the form \( \min_{x\in\{-1,1\}^n} f(Ax-b) \) with possibly nonsmooth loss \(f\). Following the lifted rank-one semidefinite programming (SDP) approach\cite{qian2023matrix}, we develop a majorization-minimization algorithm by using the difference-of-convexity (DC) reformuation for the rank-one constraint and the Moreau envelop for the nonsmooth loss. We provide global complexity guarantees for the proposed \textbf{D}ifference of \textbf{C}onvex \textbf{R}elaxation \textbf{A}lgorithm (DCRA) and show that it produces an approximately feasible binary solution with an explicit bound on the optimality gap. Numerical experiments on synthetic and real datasets confirm that our method achieves superior accuracy and scalability compared with existing approaches. |
| title | A Relaxation Method for Nonsmooth Nonlinear Optimization with Binary Constraints |
| topic | Optimization and Control G.1.6 |
| url | https://arxiv.org/abs/2601.03008 |