Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2509.00895 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917489617666048 |
|---|---|
| author | Zhou, Shenglong Li, Shuai Zhang, Hui Luo, Ziyan |
| author_facet | Zhou, Shenglong Li, Shuai Zhang, Hui Luo, Ziyan |
| contents | Unconstrained binary integer programming (UBIP) is a challenging optimization problem due to the presence of binary variables. To address the challenge, we introduce a novel class of functions named sharp-peak functions (SPFs), which equivalently reformulate the binary constraints as equality constraints, giving rise to an SPF-constrained optimization. Rather than solving this constrained reformulation directly, we focus on its associated penalty model. The established exact penalty theory shows that the global minimizers of UBIP and the penalty model coincide when the penalty parameter exceeds a threshold, a constant independent of the solution set of UBIP. To analyze the penalty model, we introduce Karush-Kuhn-Tucker (KKT) points and a new type of stationarity, referred to as P-stationarity, and provide a comprehensive characterization of its optimality conditions. We then develop an efficient algorithm called Sha-Peak based on the inexact alternating direction method of multipliers. It converges toa P-stationary point at a linear rate or terminates at such a point within finitely many steps. These results are established under appropriate parameter choices and a single mild assumption, namely, the local Lipschitz continuity of the gradient over a bounded box. Finally, numerical experiments demonstrate its nice performance in comparison to several established solvers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_00895 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sharp-Peak Functions for Exactly Penalizing Binary Integer Programming Zhou, Shenglong Li, Shuai Zhang, Hui Luo, Ziyan Optimization and Control Unconstrained binary integer programming (UBIP) is a challenging optimization problem due to the presence of binary variables. To address the challenge, we introduce a novel class of functions named sharp-peak functions (SPFs), which equivalently reformulate the binary constraints as equality constraints, giving rise to an SPF-constrained optimization. Rather than solving this constrained reformulation directly, we focus on its associated penalty model. The established exact penalty theory shows that the global minimizers of UBIP and the penalty model coincide when the penalty parameter exceeds a threshold, a constant independent of the solution set of UBIP. To analyze the penalty model, we introduce Karush-Kuhn-Tucker (KKT) points and a new type of stationarity, referred to as P-stationarity, and provide a comprehensive characterization of its optimality conditions. We then develop an efficient algorithm called Sha-Peak based on the inexact alternating direction method of multipliers. It converges toa P-stationary point at a linear rate or terminates at such a point within finitely many steps. These results are established under appropriate parameter choices and a single mild assumption, namely, the local Lipschitz continuity of the gradient over a bounded box. Finally, numerical experiments demonstrate its nice performance in comparison to several established solvers. |
| title | Sharp-Peak Functions for Exactly Penalizing Binary Integer Programming |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2509.00895 |