A Relaxação Lagrangiana pode aproximar um problema com muitas restrições através de um sistema mais mais simples. A solução do problema relaxado é solução aproximada do proble real, o que é uma nformação muito útil.
O método utiliza um multiplicador de Lagrange para penalizar violações de uma ou mais restrições. Essa penalidade substitui a obrigatoriedade dessas restrições, o que geralmente torna o problema mais fácil de ser solucionado.
A maximização das variáveis duais nessa função Lagrangiana(multiplicadores de Lagrange) é o problema dual Lagrangiano.
Formulação matemática Tome o sistema de um problema linear descrito abaixo, onde e : +maxs.a. Se dividir a matriz de restrições A em , , com , o sistema fica na seguinte forma: +maxs.a.(1)(2) Nós podemos transferir a restrição (2) para a função objetivo: +maxs.a. Se for um conjunto de elementos positivos, será aplicada uma penalidade ao violar a restrição (2), assim como uma bonificação ao seguir essa restrição à risca. Esse novo sistema é a relaxação Lagrangiana com respeito ao problema original.
A solução relaxada como um limitante Para um conjunto fixo de , o resultado ótimo do problema relaxado será sempre pior ou igual ao resultado do problema original. Para demonstrar essa propriedade, considere a solução ótima do problema original e do problema relaxado. podemos montar a série de inequações:
A primeira inequação é devida a plausibilidade de como solução de ambos os sistemas, a segunda inequação é devida a plausibilidade de como solução ótima do problema relaxado.
Andando em direção a solução do sistema original Baseado nas inequações acima, ao minimizar o valor da solução ótima do problema relaxado, obtemos um limitante inferior que se aproxima do resultado ótimo para o problema original. Sendo assim, podemos resolver o problema original explorando esse sistema semi dual: mins.a. Sendo descrito como: maxs.a.(1) O algoritmo da relaxação Lagrangiana consiste na exploração dos valores factíveis de buscando minimizar . Cada valor objetivo de é um possível limitante inferior para o problema origina(maximização), sendo o de maior valor salvo como melhor limitante. Depois podemos utilizar uma heurística, baseada ou não nos valores de advindos de , para encontrar soluções plausíveis, iterando até que o melhor limitante e a melhor solução conhecida alcancem a tolerancia desejada.
Métodos semelhantes O Lagrangiano progressivo foi desenvolvido em 1970. É muito similar a relaxação lagrangiana, adicionando um novo elemento, além de atualizar os valores de de forma mais conservadora.
O algoritmo de penalidades não cria nenhuma variável dual, apenas remove as restrições e penaliza os desvios. É um método bem intuitivo, porém tem problemas com ajuste dos seus parametros.
Referências
Livros
Bertsekas, Dimitri P. (1999). Nonlinear Programming: 2nd Edition. Athena Scientific. ISBN 1-886529-00-0.
Artigos
Bragin, Mikhail A.; Luh, Peter B.; Yan, Joseph H.; Yu, Nanpeng and Stern, Gary A. (2015). "Convergence of the Surrogate Lagrangian Relaxation Method," Journal of Optimization Theory and Applications. 164 (1): 173-201, Bragin, Mikhail A.; Tucker, Emily, L. (2022) "Surrogate "Level-Based" Lagrangian Relaxation for mixed-integer linear programming," Scientific Reports. 12: 22417, doi:10.1038/s41598-022-26264-1 Neal Young, Lagrangian Relaxation Example, in AlgNotes Blog. Neal Young, 2012, Toy Examples for Plotkin-Shmoys-Tardos and Arora-Kale solvers in CSTheory Stack Exchange. Categoria:Otimização Categoria:Otimização discreta