Lagrangianos aumentados livres de fatorações de matrizes para otimização não linear (2025)
- Authors:
- 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:
- 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:
- Data da defesa: 12.03.2025
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
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://teses.usp.br/teses/disponiveis/45/45132/tde-09052025-143141/. Acesso em: 09 maio 2026. -
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://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 2026 maio 09 ] Available from: https://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 2026 maio 09 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-09052025-143141/ - Completamento de matrizes de distâncias Euclidianas
- Implementação de um método de Lagrangianos aumentados com informação de primeira ordem
- Accelerated derivative-free spectral residual method for nonlinear systems of equations
- On complexity and convergence of high-order coordinate descent algorithms for smooth nonconvex box-constrained minimization
- Optimization of slice configuration of steel coils
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
