Um estudo sobre o método de região de confiança para problemas de otimização irrestrita

Abstract

The trust region method is a method for solving nonlinear programming problems, applied in particular to unconstrained optimization problems. Its development began around the 1980s, although the first concepts emerged in the 1940s. Unlike the already established methods of unconstrained optimization (gradient, Newton, etc.), at each iteration of its algorithm a set called trust region is delimited in which an appropriate modeling of the function is made, which generates a subproblem that must be minimized, and if the relationship between the reduction of the model and the function is acceptable, the minimum point of this model becomes the point of the next iteration. This work studies the theory about the trust region method, also exploring the concept of the Cauchy step, which is a method for solving the subproblem. It is demonstrated that its application in the trust region algorithm from a quadratic model generates a sequence of points convergent to a 1st order critical point of the objective function, under some hypotheses related to the function and its model. Results regarding the convergence of the algorithm to 2nd order critical points are also proven, assuming that the objective function is convex. For this purpose, two cases are addressed, the first in which the model is convex in all points generated by the algorithm, and the second, admitting points in which the model is not convex. At the end, a computational implementation of the method is shown, where the algorithm was implemented in script language. Tests are performed with two objective functions, to verify the convex and non-convex cases, where their outputs are shown in text format, and with images indicating the graphical evolution of the algorithm until a minimum point in each function.