Inexact variants of the alternating direction method of multipliers and their iteration-complexity analyses

Página do item simplificado
dc.contributor.advisor-co1Gonçalves, Max Leandro Nobre
dc.contributor.advisor-co1Latteshttp://lattes.cnpq.br/7841103869154032eng
dc.contributor.advisor1Melo, Jefferson Divino Gonçalves de
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/8296171010616435eng
dc.contributor.referee1Melo, Jefferson Divino Gonçalves de
dc.contributor.referee2Gonçalves, Max Leandro Nobre
dc.contributor.referee3Prudente, Leandro da Fonseca
dc.contributor.referee4Pérez, Luis Roman Lucambio
dc.contributor.referee5Andreani, Roberto
dc.creatorAdona, Vando Antônio
dc.creator.Latteshttp://lattes.cnpq.br/5115225898624770eng
dc.date.accessioned2019-04-23T11:43:52Z
dc.date.issued2019-03-27
dc.description.abstractThis thesis proposes and analyzes some variants of the alternating direction method of multipliers (ADMM) for solving separable linearly constrained convex optimization problems. This thesis is divided into three parts. First, we establish the iteration-complexity of a proximal generalized ADMM. This ADMM variant, proposed by Bertsekas and Eckstein, introduces a relaxation parameter into the second ADMM subproblem in order to improve its computational performance. We show that, for a given tolerance ρ>0, the proximal generalized ADMM with α in (0, 2) provides, in at most O(1/ρ^2) iterations, an approximate solution of the Lagrangian system associated to the optimization problem under consideration. It is further demonstrated that, in at most O(1/ρ) iterations, an approximate solution of the Lagrangian system can be obtained by means of an ergodic sequence associated to a sequence generated by the proximal generalized ADMM with α in (0, 2]. Second, we propose and analyze an inexact variant of the aforementioned proximal generalized ADMM. In this variant, the rst subproblem is approximately solved using a relative error condition whereas the second one is assumed to be easy to solve. It is important to mention that in many ADMM applications one of the subproblems has a closed-form solution; for instance, l_1-regularized convex composite optimization problems. We show that the proposed method possesses iteration-complexity bounds similar to its exact version. Third, we develop an inexact proximal ADMM whose rst subproblem is inexactly solved using an approximate relative error criterion similar to the aforementioned inexact proximal generalized ADMM. Pointwise and ergodic iteration-complexity bounds for the proposed method are established. Our approach consists of interpreting these ADMM variants as an instance of a hybrid proximal extragradient framework with some special properties. Finally, in order to show the applicability and advantage of the inexact ADMM variants proposed here, we present some numerical experiments performed on a setting of problems derived from real-life applications.eng
dc.description.provenanceSubmitted by Ana Caroline Costa (ana_caroline212@hotmail.com) on 2019-04-22T19:44:18Z No. of bitstreams: 2 Tese - Vando Antônio Adona - 2019.pdf: 5160326 bytes, checksum: 351610e1652d929b881b6d5d0ac9c40f (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)eng
dc.description.provenanceApproved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2019-04-23T11:43:52Z (GMT) No. of bitstreams: 2 Tese - Vando Antônio Adona - 2019.pdf: 5160326 bytes, checksum: 351610e1652d929b881b6d5d0ac9c40f (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)eng
dc.description.provenanceMade available in DSpace on 2019-04-23T11:43:52Z (GMT). No. of bitstreams: 2 Tese - Vando Antônio Adona - 2019.pdf: 5160326 bytes, checksum: 351610e1652d929b881b6d5d0ac9c40f (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2019-03-27eng
dc.description.resumoEsta tese propõe e analisa algumas variantes do método dos multiplicadores das direções alternadas (ADMM) para resolver problemas de otimização convexa com restrição linear. Esta tese e dividida em três partes. Primeiro, estabelecemos iteração complexidade de um ADMM generalizado proximal. Essa variante ADMM, proposta por Bertsekas e Eckstein, introduz um parâmetro de relaxação no segundo subproblema do ADMM para melhorar seu desempenho computacional. Mostramos que, para uma determinada tolerância ρ>0, o ADMM generalizado proximal com α em (0, 2) fornece, em no máximo O(1/ρ^2) iterações, uma solução aproximada do sistema Lagrangiano associado ao problema de otimização considerado. E ainda demonstrado que, em no máximo O(1/ρ) iterações, uma solução aproximada do sistema Lagrangiano pode ser obtida por meio de uma sequência ergódica associada a sequência gerada pelo ADMM generalizado proximal com α em (0, 2]. Em segundo lugar, propomos e analisamos uma variante inexata do ADMM generalizado proximal acima mencionado. Nesta variante, o primeiro subproblema e aproximadamente resolvido usando uma condição de erro relativo, enquanto o segundo e considerado fácil de resolver. É importante mencionar que, em muitas aplicações do ADMM, um dos subproblemas tem uma solução em forma fechada; por exemplo, problemas de otimização convexos compostos l_1-regularizados. Mostramos que o método proposto possui iteração complexidade semelhantes à sua versão exata. Terceiro, desenvolvemos um ADMM proximal inexato cujo primeiro subproblema é resolvido inexatamente usando um critério de erro relativo aproximado semelhante ao ADMM inexato generalizado proximal acima mencionado. Os limites de iteração complexidade pontual e ergódico para o método proposto são estabelecidos. Nossa abordagem consiste em interpretar essas variantes do ADMM como uma instância de um estrutura híbrida proximal extragradiente com algumas propriedades especiais. Finalmente, a fim de mostrar a aplicabilidade e vantagem das variantes inexatas do ADMM propostas aqui, apresentamos alguns experimentos numéricos realizados em um cenário de de problemas derivados de aplicações da vida real.eng
dc.description.sponsorshipCoordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPESeng
dc.formatapplication/pdf*
dc.identifier.citationADONA, V. A. Inexact variants of the alternating direction method of multipliers and their iteration-complexity analyses. 2019. 92 f. Tese (Doutorado em Matemática) - Universidade Federal de Goiás, Goiânia, 2019.eng
dc.identifier.urihttp://repositorio.bc.ufg.br/tede/handle/tede/9522
dc.languageengeng
dc.publisherUniversidade Federal de Goiáseng
dc.publisher.countryBrasileng
dc.publisher.departmentInstituto de Matemática e Estatística - IME (RG)eng
dc.publisher.initialsUFGeng
dc.publisher.programPrograma de Pós-graduação em Matemática (IME)eng
dc.rightsAcesso Aberto
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subjectMétodo dos multiplicadores das direções alternadaspor
dc.subjectPrograma convexopor
dc.subjectMétodo extragradiente híbridopor
dc.subjectCritério de erro relativopor
dc.subjectIteração complexidade pontualpor
dc.subjectIteração complexidade ergódicapor
dc.subjectAlternating direction method of multiplierseng
dc.subjectConvex programeng
dc.subjectHybrid extragradient methodeng
dc.subjectRelative error criterioneng
dc.subjectPointwise iteration-complexityeng
dc.subjectErgodic iteration-complexityeng
dc.subject.cnpqCIENCIAS EXATAS E DA TERRA::MATEMATICAeng
dc.titleInexact variants of the alternating direction method of multipliers and their iteration-complexity analyseseng
dc.title.alternativeVariantes inexatas do método dos multiplicadores das direções alternadas e sua analise de iteração complexidadepor
dc.typeTeseeng

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
Tese - Vando Antônio Adona - 2019.pdf
Tamanho:
4.92 MB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
2.11 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Baixar

Coleções

Doutorado em Matemática (IME)