On separable primal-dual algorithms for very large-scale optimization.
Date
2021-03
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: In this study, we develop two novel separable primal-dual algorithms, containing closed-form primal and dual variable expressions. The separability of the primal-dual expressions allow both algorithms to exploit massively parallel computational devices, which is desirable for very large-scale optimization. One of the algorithms is ideally suited for low-rank singular value decomposition (SVD), since the separable primal and dual updates become embarrassingly parallel for the SVD problem, allowing the algorithm to efficiently exploit general purpose graphical compute units (GPGPUs).In the first part of this study, we develop an iterative separable augmented Lagrangian algorithm (SALA), which has the salient feature of embarrassingly parallel primal and dual variable expressions, hence the algorithm is ideal for implementation on massively parallel computational devices, such as GPGPUs. SALAsolves a sequence of quadratic-like problems,able to capture reciprocal and exponential-like behavior; a desirable property in structural optimization. Since SALAresides in the class of alternating directions of multiplier method type algorithms, we demonstrate numerical results on structural problems requiring medium levels of accuracy.
In the second part of this study, we propose a separable Lagrangian algorithm (SLA) for very large-scale optimization. SLA, derived from the dual of Falk, solves a sequence of quadratic-like problems and, like SALA, is able to capture reciprocal and exponential-like behavior. SLA has embarrassingly parallel primal updates, while the dual variables require the solution of a positive-definite linear system. Indeed, both primal and dual variable updates can exploit massively parallel computational devices. We demonstrate numerical results for structural problems involving hundreds of millions of variables and constraints, solved for in a few minutes on a single quad-core machine.
Following the development of SLA, we address the low-rank SVD problem. Two separate algorithms are developed, using a variation of SLA that exploits the structure of the SVD problem, resulting in embarrassingly parallel primal and dual updates. Both algorithms use a GPGPU accelerated, constrained and convex sequential approximate optimization (SAO)approach to maximize the well-known Rayleigh quotient, while addressing the difficulties inherent to state-of-the-art Krylov subspace methods, such as resilience to slowly decaying singular values and constant memory requirements. The convex SAO subproblems are conditioned using a novel scaling strategy, allowing for generic solver settings to be used across a wide range of singular value distributions. We demonstrate outstanding numerical results compared to state-of-the-art Lanczos methods, in both CPU and GPGPU implementations,which significantly reduce the time-complexity required for large-scale problems.
Finally, we propose a multi-solver approach to soften the no-free-lunch (NFL) theorems for optimization on large-scale structural problems. State-of-the-art algorithms and SLA, each exploiting different solution strategies, compete simultaneously for a problem solution on a single multi-core system. Numerical results demonstrate the efficacy of using a multi-solver approach over a range of test problems, since said approach outperforms any stand alone solver tested in terms of mean solution time.
AFRIKAANSE OPSOMMING: In hierdie studie ontwikkel ons twee nuwe skeidbare primaal-duale algoritmes, wat analitieseprimale en duale veranderlike uitdrukkings bevat. Die skeibaarheid van die primaal enduale veranderlike uitdrukkings laat albei algoritmes toe om kragtige parallelle rekenaarstelsels te benut, wat belangrik is vir grootskaalse optimering. Een van die algoritmes is byuitstek geskik vir die ontbinding van enkelwaardes van lae rangorde (SVD), aangesien dieskeibare primale en duale opdaterings onafhanklik parallel word vir die SVD-probleem, watdie algoritme in staat stel om algemene grafiese rekenaareenhede (GPGPU’s) doeltreffend tebenut. In die eerste deel van hierdie studie ontwikkel ons ’n iteratiewe skeibare toegevoegde La-gransiese algoritme (SALA), wat die opvallendste kenmerk het van onafhanklike parallelleen duale veranderlike opdaterings, daarom is die algoritme ideaal vir implementering opkragtige parallelle rekenaar stelsels, soos GPGPU’s.SALAlos ’n reeks kwadratiese problemeop, wat resiproke en eksponensiële gedrag kan vasvang; ’n wenslike eienskap in struktureleoptimering. AangesienSALAin die klas van alternatiewe rigtings van vermenigvuldigingsme-tode (ADMM) algoritmes voorkom, toon ons numeriese resultate op strukturele problemewat medium akkuraatheidsvlakke benodig. In die tweede deel van hierdie studie stel ons ’n skeibare Lagransiese algoritme (SLA) voor virgrootskaalse optimering.SLA, afgelei van die duale stelling van Falk, los ’n reeks kwadratieseprobleme op en is, soosSALA, in staat om resiproke en eksponensiële gedrag vas te vang. InSLAword die duale veranderlikes verkry deur die oplossing van ’n positief-definiete lineêrestelsel. Beide die primale en duale veranderlike opdaterings kan groot parallelle rekenaarstelsels gebruik. Ons demonstreer numeriese resultate vir strukturele probleme met honderdemiljoene veranderlikes en beperkings wat binne ’n paar minute op ’n enkele verwerker opgelosis.Na die ontwikkeling vanSLAenSALA, spreek ons die lae rang SVD-probleem aan. Tweeafsonderlike algoritmes word ontwikkel vir onderskeidelik digte en yl matrikse, met behulpvan ’n variasie vanSLAwat die struktuur van die SVD-probleem benut, wat onafhanklikeparallelle primale en duale opdaterings tot gevolg het. Albei algoritmes gebruik ’n GPGPU-versnelde konvekse SAO-benadering om die bekende Rayleigh-kwosiënt te maksimeer, terwyldie probleme aangespreek word met moderne Krylov-subruimte-metodes. Die konvekse SAO-subprobleme word gekondisioneer deur gebruik te maak van ’n nuwe skaalings-strategie, watdit moontlik maak om generiese instellings oor ’n wye verskeidenheid enkele waardeverdelingste gebruik. Ons demonstreer uitstekende numeriese resultate in vergelyking met die nuutsteLanczos-metodes, in beide CPU- en GPGPU-implementasies van ons voorgestelde SVD-algoritmes, wat die tydkompleksiteit wat nodig is vir lae-rang SVD op grootskaalse datastelle,aansienlik verminder.Laastens stel ons ’n multi-oplosser-benadering voor om die NFL-stellings te versag vir opti-mering van grootskaalse strukturele probleme. Moderne algoritmes enSLA, wat verskillendebenaderings gebruik om die SAO-subprobleme op te los, ding gelyktydig mee om ’n prob-leemoplossing op ’n enkele meervoudige stelsel verwerkers. Numeriese resultate toon diedoeltreffendheid van die gebruik van ’n multi-oplosser-benadering oor ’n reeks toetsprob-leme aan, aangesien ons voorgestelde benadering beter as enige enkele oplosser is, alhoewelbeperkte berekeningsbronne beskikbaar is.
AFRIKAANSE OPSOMMING: In hierdie studie ontwikkel ons twee nuwe skeidbare primaal-duale algoritmes, wat analitieseprimale en duale veranderlike uitdrukkings bevat. Die skeibaarheid van die primaal enduale veranderlike uitdrukkings laat albei algoritmes toe om kragtige parallelle rekenaarstelsels te benut, wat belangrik is vir grootskaalse optimering. Een van die algoritmes is byuitstek geskik vir die ontbinding van enkelwaardes van lae rangorde (SVD), aangesien dieskeibare primale en duale opdaterings onafhanklik parallel word vir die SVD-probleem, watdie algoritme in staat stel om algemene grafiese rekenaareenhede (GPGPU’s) doeltreffend tebenut. In die eerste deel van hierdie studie ontwikkel ons ’n iteratiewe skeibare toegevoegde La-gransiese algoritme (SALA), wat die opvallendste kenmerk het van onafhanklike parallelleen duale veranderlike opdaterings, daarom is die algoritme ideaal vir implementering opkragtige parallelle rekenaar stelsels, soos GPGPU’s.SALAlos ’n reeks kwadratiese problemeop, wat resiproke en eksponensiële gedrag kan vasvang; ’n wenslike eienskap in struktureleoptimering. AangesienSALAin die klas van alternatiewe rigtings van vermenigvuldigingsme-tode (ADMM) algoritmes voorkom, toon ons numeriese resultate op strukturele problemewat medium akkuraatheidsvlakke benodig. In die tweede deel van hierdie studie stel ons ’n skeibare Lagransiese algoritme (SLA) voor virgrootskaalse optimering.SLA, afgelei van die duale stelling van Falk, los ’n reeks kwadratieseprobleme op en is, soosSALA, in staat om resiproke en eksponensiële gedrag vas te vang. InSLAword die duale veranderlikes verkry deur die oplossing van ’n positief-definiete lineêrestelsel. Beide die primale en duale veranderlike opdaterings kan groot parallelle rekenaarstelsels gebruik. Ons demonstreer numeriese resultate vir strukturele probleme met honderdemiljoene veranderlikes en beperkings wat binne ’n paar minute op ’n enkele verwerker opgelosis.Na die ontwikkeling vanSLAenSALA, spreek ons die lae rang SVD-probleem aan. Tweeafsonderlike algoritmes word ontwikkel vir onderskeidelik digte en yl matrikse, met behulpvan ’n variasie vanSLAwat die struktuur van die SVD-probleem benut, wat onafhanklikeparallelle primale en duale opdaterings tot gevolg het. Albei algoritmes gebruik ’n GPGPU-versnelde konvekse SAO-benadering om die bekende Rayleigh-kwosiënt te maksimeer, terwyldie probleme aangespreek word met moderne Krylov-subruimte-metodes. Die konvekse SAO-subprobleme word gekondisioneer deur gebruik te maak van ’n nuwe skaalings-strategie, watdit moontlik maak om generiese instellings oor ’n wye verskeidenheid enkele waardeverdelingste gebruik. Ons demonstreer uitstekende numeriese resultate in vergelyking met die nuutsteLanczos-metodes, in beide CPU- en GPGPU-implementasies van ons voorgestelde SVD-algoritmes, wat die tydkompleksiteit wat nodig is vir lae-rang SVD op grootskaalse datastelle,aansienlik verminder.Laastens stel ons ’n multi-oplosser-benadering voor om die NFL-stellings te versag vir opti-mering van grootskaalse strukturele probleme. Moderne algoritmes enSLA, wat verskillendebenaderings gebruik om die SAO-subprobleme op te los, ding gelyktydig mee om ’n prob-leemoplossing op ’n enkele meervoudige stelsel verwerkers. Numeriese resultate toon diedoeltreffendheid van die gebruik van ’n multi-oplosser-benadering oor ’n reeks toetsprob-leme aan, aangesien ons voorgestelde benadering beter as enige enkele oplosser is, alhoewelbeperkte berekeningsbronne beskikbaar is.
Description
Thesis (PhD)--Stellenbosch University, 2021.
Keywords
Mathematical optimization, Large scale systems, Singular value decomposition, Sequential approximate optimization, UCTD