Distributed Computing for Huge-Scale Linear Programming
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916883533398016 |
|---|---|
| author | Tao, Luoyi |
| author_facet | Tao, Luoyi |
| contents | This study develops an algorithm for distributed computing of linear programming problems of huge-scales. Global consensus with single common variable, multiblocks, and augmented Lagrangian are adopted. The consensus is used to partition the constraints of equality and inequality into multi-consensus blocks, and the subblocks of each consensus block are employed to partition the primal variables into $M$ sets of disjoint subvectors. The global consensus constraints of equality and other constraints are replaced equivalently by the extended constraints of equality involving slack variables, since the slack variables help the feasibility and initialization of the algorithm. The block-coordinate Gauss-Seidel method, the proximal point method, and ADMM are used to update the primal variables, descent models used to update the dual. Convergence of the algorithm to optimal solutions is argued and the rate of convergence, $O(1/k^{1/2})$ is estimated, under feasibility of the algorithm and boundedness of the dual sequences supposed. Analysis is presented on how to ensure the feasibility and boundedness through initial and control parameter values and a dual descent model with built-in bound for the original constraints of inequality. Further exploration of dual descent models with built-in bound is needed. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_06204 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Distributed Computing for Huge-Scale Linear Programming Tao, Luoyi Optimization and Control 90C05 90C06 90C25 90C30 68W15 68W40 76F02 76F05 76F10 This study develops an algorithm for distributed computing of linear programming problems of huge-scales. Global consensus with single common variable, multiblocks, and augmented Lagrangian are adopted. The consensus is used to partition the constraints of equality and inequality into multi-consensus blocks, and the subblocks of each consensus block are employed to partition the primal variables into $M$ sets of disjoint subvectors. The global consensus constraints of equality and other constraints are replaced equivalently by the extended constraints of equality involving slack variables, since the slack variables help the feasibility and initialization of the algorithm. The block-coordinate Gauss-Seidel method, the proximal point method, and ADMM are used to update the primal variables, descent models used to update the dual. Convergence of the algorithm to optimal solutions is argued and the rate of convergence, $O(1/k^{1/2})$ is estimated, under feasibility of the algorithm and boundedness of the dual sequences supposed. Analysis is presented on how to ensure the feasibility and boundedness through initial and control parameter values and a dual descent model with built-in bound for the original constraints of inequality. Further exploration of dual descent models with built-in bound is needed. |
| title | Distributed Computing for Huge-Scale Linear Programming |
| topic | Optimization and Control 90C05 90C06 90C25 90C30 68W15 68W40 76F02 76F05 76F10 |
| url | https://arxiv.org/abs/2408.06204 |