Solución de problemas no lineales con restricciones usando DIRECT y una función lagrangeana aumentada

Abstract

En este trabajo se realiza un breve estudio sobre la optimización no lineal, en una pequeña clasificación de los diferentes tipos de funciones centrándonos en problemas con y sin restricciones; además de los métodos que se utilizan en la resolución de dichos problemas. Para la realización de nuestro trabajo llevamos a cabo el estudio y utilización del algoritmo DIRECT [5], que es un método determinista de optimización global. DIRECT comienza la búsqueda del mínimo global dividiendo su espacio (dominio) en partes rectangulares y lo repite continuamente en determinadas iteraciones hasta llegar al punto óptimo. El uso de la aplicación de DIRECT se desarrolla en primer lugar en problemas de optimización con restricciones del tipo de límites simples (problemas Dixon&Szego [3]), dentro de los cuales representaremos más detalladamente la función Camel. En segundo lugar utilizamos DIRECT para resolver problemas con restricciones del tipo igualdad y desigualdad (conjunto de problemas g), a través de la utilización de métodos basados en la función Langrangeana aumentada. La idea central es resolver el problema de optimización con restricciones a través de la resolución de una sucesión de sub-problemas más simples, esos problemas apenas con restricciones de límites en las variables. La utilización de la función Lagrangeana aumentada en un método de penalización tiene como objetivo superar el problema de mal condicionamiento de los sub-problemas sin restricciones. El éxito y la eficiencia de los métodos de penalización basados en la función Lagrangeana aumentada, teniendo como base los métodos de los multiplicadores [1]. Así, fue implementado el método de los multiplicadores basado en la función Lagrangeana aumentada para resolver problemas con restricciones. En cada iteración, es necesaria la resolución de un sub-problema, que fue realizado a través del método DIRECT. Por último, para evaluar el desempeño del método, este fue aplicado en una colección de problemas g [7] y comparamos con la resolución de los mismos problemas a través del método de los multiplicadores, más con el comando FMINCON (de Matlab [10]) en la resolución de los sub-problemas.

This paper provides a brief study on the area of nonlinear optimization, namely in the classification of different types of functions focusing on problems with and without constraints and, in addition, the methods used in solving these problems. To carry out our work we study and use the DIRECT method [5], that is a deterministic method of global optimization. DIERCT begins the search for global minimum by dividing the space (domain) into rectangular parts and continuously repeat it along the iterations to reach the optimal point. First using the DIRECT has been applied to solve bound constrained optimization problems (the Dixon&Szego problems [3]), where a more detailed explanation have been carried out to the Camel function. Second, to solve problems with equality constraints and inequality type (problems g), through the use of methods based on augmented Langrangian functions. The central idea is to solve the constrained optimization problem via solving a sequence of simpler sub-problems, called simple bound problems. The subproblems are based on an augmented Lagrangian function. The use of an augmented Lagrangian function in a penalty method aims to overcome the problem of illconditioning of the sub-problems without constraints. It has been shown through years the success and efficiency of penalty methods based on augmented Lagrangian functions, that are based on the multipliers method [1]. Hence, a multipliers method based on an augmented Lagrangian function has been implemented to solve constrained problems. In each iteration, is necessary to solve a subproblem that will be done by the DIRECT method. Finally, to evaluate the performance of the implemented method, we solve a subset of the collection of gs problems [7] and compared with the multipliers method but with the FMINCON command (from Matlab [10]) when solving the subproblems.