Tese

Lagrangianos aumentados livres de fatorações de matrizes para otimização não linear (2025)

• Authors:
  • Marcondes, Diaulas Murize Santana Vieira
  • Birgin, Ernesto Julian Goldberg (Orientador)
• Autor USP: MARCONDES, DIAULAS MURIZE SANTANA VIEIRA - IME
• Unidade: IME
• Sigla do Departamento: MAP
• DOI: 10.11606/T.45.2025.tde-09052025-143141
• Subjects: PROGRAMAÇÃO NÃO LINEAR; SISTEMAS LAGRANGIANOS; OTIMIZAÇÃO NÃO LINEAR
• Keywords: Augmented lagrangian methods; Experimentos numéricos; Gradientes conjugados não lineares; Lagrangianos aumentados; MINRES; Nonlinear conjugate gradient; Nonlinear optimization; Numerical experiments
• Agências de fomento:
  • Financiamento CAPES
• Language: Português
• Abstract: Este trabalho aborda o problema de otimização contínua em que alguma das funções que definem o problema é não linear. O objetivo principal é desenvolver métodos que não precisem de fatorações de matrizes e que, portanto, possam ser aplicados a problemas de grande porte. Numa primeira parte do trabalho focamos em problemas com restrições de caixa da forma minimizar f(x) sujeita a \ell \leq x \leq u. Para este problema, propomos novos métodos baseados no consagrado método Gencan. Gencan é um método de restrições ativas que, dentro das faces, utiliza Newton truncado. Os novos métodos utilizam MINRES (do inglês, \textit{Minimum Residual Method}) na resolução dos sistemas lineares Newtonianos no lugar de gradientes conjugados com produtos de Hessiana-vetor. Para estes métodos, apresentamos resultados de complexidade para encontrar um iterando x^k que satisfaça uma condição de otimalidade com precisão \epsilon>0. Um deles, com complexidade O(\epsilon^), utiliza uma tolerância dinâmica na resolução dos sistemas lineares e modifica a direção calculada com MINRES para garantir um decréscimo da ordem de \epsilon^. Este método utiliza o método do Gradiente Espectral Projetado (SPG, do inglês \textit{Spectral Projected Gradient}) para sair das faces. O segundo método, com complexidade O(\epsilon^{-3/2}), resolve os sistemas lineares com MINRES de forma tal que, sobre certas hipóteses, a direção calculada garanta um decréscimo da ordem de \epsilon^{-3/2}.Este método sai das faces minimizando um modelo quadrático com regularização cúbica sujeito às restrições de caixa. Os dois métodos mencionados, utilizam a Hessiana na forma produto Hessiana-vetor, na resolução dos sistemas lineares Newtonianos. Propomos ainda um terceiro método que, dentro das faces, utiliza o método de gradientes conjugados não lineares LCGD (do inglês, \textit{Limited memory CG-Descent}). Este método utiliza apenas informação de primeira ordem. Para este método, apresentamos resultados de convergência assintótica a pontos estacionários. O método ASA-CG é também um método de restrições ativas que utiliza LCGD dentro das faces e uma variação do SPG para sair das faces. Experimentos numéricos mostram que, quando comparado ao ASA-CG e à versão atual do Gencan, o método proposto apresenta melhor desempenho em termos de eficiência e robustez. Na segunda parte do trabalho, consideramos o melhor dos métodos para minimização em caixas no contexto de um método de Lagrangianos aumentados para programação não linear. Algencan é um método de Lagrangianos aumentados que resolve uma sequência de subproblemas com restrições de caixa. Logo, a proposta consiste em resolver os subproblemas de Algencan com o novo método proposto para minimização em caixas. Experimentos numéricos mostram que a nova versão é mais robusta e eficiente, especialmente em problemas que não são de programação quadrática
• Imprenta:
  • Publisher place: São Paulo
  • Date published: 2025
• Data da defesa: 12.03.2025

Informações sobre o DOI: 10.11606/T.45.2025.tde-09052025-143141 (Fonte: oaDOI API)
• Este periódico é de acesso aberto
• Este artigo é de acesso aberto
• URL de acesso aberto
• Cor do Acesso Aberto: gold
• Licença: cc-by-nc-sa

---

How to cite

A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

• ABNT

  MARCONDES, Diaulas Murize Santana Vieira. Lagrangianos aumentados livres de fatorações de matrizes para otimização não linear. 2025. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2025. Disponível em: https://www.teses.usp.br/teses/disponiveis/45/45132/tde-09052025-143141/. Acesso em: 23 jun. 2025.

• APA

  Marcondes, D. M. S. V. (2025). Lagrangianos aumentados livres de fatorações de matrizes para otimização não linear (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de https://www.teses.usp.br/teses/disponiveis/45/45132/tde-09052025-143141/

• NLM

  Marcondes DMSV. Lagrangianos aumentados livres de fatorações de matrizes para otimização não linear [Internet]. 2025 ;[citado 2025 jun. 23 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45132/tde-09052025-143141/

• Vancouver

  Marcondes DMSV. Lagrangianos aumentados livres de fatorações de matrizes para otimização não linear [Internet]. 2025 ;[citado 2025 jun. 23 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45132/tde-09052025-143141/

Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

• Completamento de matrizes de distâncias Euclidianas
• Implementação de um método de Lagrangianos aumentados com informação de primeira ordem
• On complexity and convergence of high-order coordinate descent algorithms for smooth nonconvex box-constrained minimization
• Accelerated derivative-free spectral residual method for nonlinear systems of equations
• Optimization of slice configuration of steel coils