Algoritmos de lagrangiano aumentado aplicados ao problema não linear contínuo de alocação de recursos

Abstract

Resumo: Propomos uma classe de algoritmos para resolver o problema não linear contínuo de alocação de recursos, o qual é bastante conhecido e pesquisado devido à sua diversificada gama de aplicações. Consideramos problemas em que a função objetivo é convexa e iniciamos analisando o caso de uma única restrição de igualdade e variáveis canalizadas. Este, por sua vez, é conhecido na literatura como problema não linear da mochila. A metodologia proposta consiste no desenvolvimento de algoritmos com uma abordagem híbrida, combinando o método de Lagrangiano aumentado, que penaliza as restrições mais complicadas do problema, com o método de Newton, para resolver os subproblemas gerados a cada passo do algoritmo. Em um segundo momento, estendemos os algoritmos para uma classe mais ampla de problemas incluindo mais de uma restrição, as quais podem ser não lineares. Neste caso, utilizamos uma abordagem semelhante ao método de Gauss-Newton em mínimos quadrados, para possibilitar o uso de informações somente de primeira ordem com respeito às restrições do problema. A maioria dos trabalhos desenvolvidos na literatura da área trata de problemas quadráticos separáveis. A abordagem que propomos é mais geral no sentido que os problemas podem ser não quadráticos e não separáveis. Apresentamos e discutimos propriedades de convergência dos algoritmos propostos e finalizamos a tese com experimentos numéricos, aplicando os algoritmos desenvolvidos através de implementações realizadas no software Matlab.

Abstract: We propose a class of algorithms for solving the continuous nonlinear resource allocation problem, which is well known and researched due to its diverse range of applications. We consider problems where the objective function is convex and we started by analyzing the case of a single equality constraint and simple bounds. This, in turn, is known in the literature as the nonlinear Knapsack problem. The proposed methodology consists of developing algorithms with a hybrid approach combining the augmented Lagrangian method, which penalizes the more complicated constraints of the problem, with Newton’s method, to solve the subproblems generated at each step of the algorithm. In a second moment, we extend the algorithms to a broader class of problems including more than one constraint, which can be nonlinear. In this case, we use an approach similar to the Gauss-Newton method for the least squares problem, to enable the use of only first-order information concerning the constraints of the problem. Most works developed in the literature deal with separable quadratic problems. The approach that we propose is more general in the sense that problems can be non-quadratic and non-separable. We present and discuss convergence properties of the proposed algorithms and we finish the thesis with numerical experiments, applying the algorithms developed through implementations carried out with the software Matlab.