Distributed Optimization Methods for Large Scale Unconstrained Optimization Problems

Abstract

Many modern applications require networks of computational agents to solve optimization problems in a cooperative manner, while the growing interest in Big Data and machine learning calls for method that are able to solve problems of increasingly large dimension. This poses many challenges in the field of optimization as most classical methods are not suitable for the distributed framework: new algorithms need to be developed, that are able to deal with the practical limitations deriving from the distributed setting. This thesis focuses on distributed methods for large scale optimization. The contributions of this thesis to the area of distributed optimization are the following. First of all, we extend the convergence analysis of a class of existing first-order distributed methods to the case of time-varying networks and uncoordinated time-varying stepsizes. This extension is particularly relevant as changes in the communication network are common in practical applications due to possible technical failures in the communication and the increasing relevance of mobile sensor networks. One of the main issues for distributed optimization is the selection of the stepsize: classical globalization such as line search are not feasible in the multi-agent framework, while employing a fixed stepsize is known to often cause the method to be slow and usually requires the knowledge of the regularity constants of the problem, which can be hard to estimate distributedly. To overcome these issues we propose a distributed Inexact Newton method that relies on an adaptive choice of the stepsize, which can be computed distributedly and, under suitable regularity assumptions, ensures both global convergence and local fast convergence as in the centralized case. Systems of linear equations and large dimensions are a problem of interest by itself and as a part of second-order optimization methods. In general, in each iteration of the second-order method, like Inexact Newton method mentioned above, one has to solve a system of linear equations, either approximately or exactly, to get the search direction. Again, distributed environment represents a challenge. Fixed point methods are a known to be very effective in the centralized framework for linear system of large dimensions. We propose here a class of distributed fixed point methods that works in the distributed setting. We show that such methods converge for both static and time-varying network, achieving convergence results analogous to those that can be proved for the centralized case. Finally, in the last part of the thesis we consider the least square problems of very large dimension motivated by digitalization of cadastral maps. The dimension of the problem represent the main difficulty for classical method while the sparse structure presents an opportunity to be exploited in parallel computational framework. We present an Inexact Levenberg-Marquardt method for sparse least squares problem. The method exploits the underlying structure of the problem to define a fixed-point strategy for the computation of the search direction that is suitable for parallelization. Theoretical analysis is presented and we show both global and fast local convergence under the classical assumptions for least squares problems. All presented methods are implemented, and tested on relevant examples. The numerical results reveal that the theoretical results are confirmed by empirical evidence. Furthermore, the proposed methods are compared with the corresponding state-of-the-art methods and their competitiveness is demonstrated.

Многи савремени математички модели захтевају решавање проблема оптимизације на мрежи рачунарских чворова у кооперативном режиму, док растући интерес за велике скупове података и машинско учење захтева методе којима је могуће решити проблеме све већих димензија. Већина класичних оптимизационих метода није погодна за примену у дистрибуираном окружењу, те је потребно развити нове методе који могу да одговоре на изазове који потичу из дистрибуираног окружења. Ова теза је фокусирана на дистрибуиране методе за оптимизационе проблеме великих димензија. Резултати предављени у овој тези су допринос области дистрибуиране оптимизације у следећим аспектима. Прво је проширена анализа конвергенције за класу постојећих дистрибуираних метода првог реда, за случај комуникационих мрежа које се мењају у времену и за дужине корака које се мењају по времену без координације између комјутерских чворова. Ово проширење је од посебног значаја у практичним применама где су промене у комуникационим мрежама узроковане техничким проблемима укомуникацији или у случају све значајнијих покретних сензорских мрежа. Једно од главних питања у методама дистрибуиране оптимизације је одређивање дужине корака. Наиме, класичне технике глобализације попут линијског претраживања нису применљиве у овом оквиру, а примена фиксне дужине корака често доводи до спорог метода. Сем тога, примена фиксног корака захтева познавање глобалних константи које се не могу једноставно оценити у дистрибуираном окружењу. Стога је у тези предложен дистрибуирани приближан Њутнов метод са адаптивном дужином корака која се може срачунати у диструбираном окружењу, а помоћу тако одрђене дужине корака, уз уобичајене претпоставке о регуларности проблема, метод је глобално конвергентан и задржава локални ред конвергенције карактеристичан за централизовану оптимизацију. Системи линеарних једначина великих димензија су изазов и као независни проблеми и као део оптимизационих поступака другог реда. У општем случају, у свакој итерацији метода другог реда, попут приближног Њутновог метода који је већ поменут, потребно је решити, приближно или тачно, систем линеарних једначина да би се одредио правац претраживања. Дистрибуирано окружење и овде представља изазов. Методе непокретне тачке су познате као ефикасан начин решавања система линеарних једначина у централизованом окружењу. Овде је представљена класа дистрибуираних метода типа непокретне тачке која је прилагођена дистрибуираном окружењу. Показано је да поступци предложеног типа конвергирају за статичне и променљиве комуникационе мреже, а резултати о конвергенцији су аналогни резултатима у централизованом случају. У последњем делу тезе је размтран проблем најмањих квадрата веома велике димензије мотивисан проблемом дигитализације катастарских мапа. Веома велика димензија проблема представља главни проблем за примену класичних метода, док је ретка структура проблема природна могућност за примену паралелних метода. У тези је представљен приближни Левенберг-Маркардов метод за решавање ретких проблема најмањих квадрата. Ретка структура је искоришћена као основ за дефинисање стратегије типа непокретне тачке којом се одређује правац претраживања на начин који је погодан за паралелизацију. Представљена је теоријска анализа и показана глобална и локална конвергенција под класичним претпоставкама за овај тип проблема. Сви предложени методи су имплементирани и тестирани на релевантним тест примерима. Нумерички резултати су емпиријски потврдили теоријска тврђења. Поред тога, предложени методи су упоређени са најзначајнијим постојећим методама за одговарајуће класе проблема и показана је њихова компетитивност.

Mnogi savremeni matematički modeli zahtevaju rešavanje problema optimizacije na mreži računarskih čvorova u kooperativnom režimu, dok rastući interes za velike skupove podataka i mašinsko učenje zahteva metode kojima je moguće rešiti probleme sve većih dimenzija. Većina klasičnih optimizacionih metoda nije pogodna za primenu u distribuiranom okruženju, te je potrebno razviti nove metode koji mogu da odgovore na izazove koji potiču iz distribuiranog okruženja. Ova teza je fokusirana na distribuirane metode za optimizacione probleme velikih dimenzija. Rezultati predavljeni u ovoj tezi su doprinos oblasti distribuirane optimizacije u sledećim aspektima. Prvo je proširena analiza konvergencije za klasu postojećih distribuiranih metoda prvog reda, za slučaj komunikacionih mreža koje se menjaju u vremenu i za dužine koraka koje se menjaju po vremenu bez koordinacije između komjuterskih čvorova. Ovo proširenje je od posebnog značaja u praktičnim primenama gde su promene u komunikacionim mrežama uzrokovane tehničkim problemima ukomunikaciji ili u slučaju sve značajnijih pokretnih senzorskih mreža. Jedno od glavnih pitanja u metodama distribuirane optimizacije je određivanje dužine koraka. Naime, klasične tehnike globalizacije poput linijskog pretraživanja nisu primenljive u ovom okviru, a primena fiksne dužine koraka često dovodi do sporog metoda. Sem toga, primena fiksnog koraka zahteva poznavanje globalnih konstanti koje se ne mogu jednostavno oceniti u distribuiranom okruženju. Stoga je u tezi predložen distribuirani približan NJutnov metod sa adaptivnom dužinom koraka koja se može sračunati u distrubiranom okruženju, a pomoću tako odrđene dužine koraka, uz uobičajene pretpostavke o regularnosti problema, metod je globalno konvergentan i zadržava lokalni red konvergencije karakterističan za centralizovanu optimizaciju. Sistemi linearnih jednačina velikih dimenzija su izazov i kao nezavisni problemi i kao deo optimizacionih postupaka drugog reda. U opštem slučaju, u svakoj iteraciji metoda drugog reda, poput približnog NJutnovog metoda koji je već pomenut, potrebno je rešiti, približno ili tačno, sistem linearnih jednačina da bi se odredio pravac pretraživanja. Distribuirano okruženje i ovde predstavlja izazov. Metode nepokretne tačke su poznate kao efikasan način rešavanja sistema linearnih jednačina u centralizovanom okruženju. Ovde je predstavljena klasa distribuiranih metoda tipa nepokretne tačke koja je prilagođena distribuiranom okruženju. Pokazano je da postupci predloženog tipa konvergiraju za statične i promenljive komunikacione mreže, a rezultati o konvergenciji su analogni rezultatima u centralizovanom slučaju. U poslednjem delu teze je razmtran problem najmanjih kvadrata veoma velike dimenzije motivisan problemom digitalizacije katastarskih mapa. Veoma velika dimenzija problema predstavlja glavni problem za primenu klasičnih metoda, dok je retka struktura problema prirodna mogućnost za primenu paralelnih metoda. U tezi je predstavljen približni Levenberg-Markardov metod za rešavanje retkih problema najmanjih kvadrata. Retka struktura je iskorišćena kao osnov za definisanje strategije tipa nepokretne tačke kojom se određuje pravac pretraživanja na način koji je pogodan za paralelizaciju. Predstavljena je teorijska analiza i pokazana globalna i lokalna konvergencija pod klasičnim pretpostavkama za ovaj tip problema. Svi predloženi metodi su implementirani i testirani na relevantnim test primerima. Numerički rezultati su empirijski potvrdili teorijska tvrđenja. Pored toga, predloženi metodi su upoređeni sa najznačajnijim postojećim metodama za odgovarajuće klase problema i pokazana je njihova kompetitivnost.