Convergência de algorítmos para programação nao linear

Abstract

Resumo: O objetivo deste trabalho é reunir os resultados, já provados, sobre convergência dos principais algoritmos para programação não linear. Para tanto, fazemos, inicialmente, uma discussão sobre diferentes definições de taxas de convergência, comparando-as entre si. Estabelecemos algumas implicações entre estas definições e exibimos alguns exemplos, elaborados especificamente para este fim, para mostrar que outras implicações não são válidas. Em seguida, discutimos métodos para resolver um problema irrestrito, ou seja, métodos para resolver o problema de minimizar uma função diferenciável sem restrições. Uma grande classe desses algoritmos inicia com um ponto dado e determina uma direção ao longo da qual é possível diminuir o valor da função, e nesta direção calcula um comprimento do passo que permite uma redução razoável do valor da função. Um método clássico de minimização irrestrita é o método de Cauchy, que corresponde a escolher a direção oposta ao gradiente da função no ponto corrente. Para o caso em que a função é quadrática, convexa e o cálculo do comprimento do pa gerada pelo algoritmo de Cauchy converge com velocidade g-linear, na norma euclidiana é feito por busca linear exata, mostramos um resultado original: a sequência diana, para o único minimizador da função e exibimos a taxa de convergência que depende do número de condicionamento da matriz hessiana da quadrática. O que temos na literatura é a convergência g-linear na norma induzida pela hessiana, mas apesar das normas em R" serem equivalentes, a velocidade de convergência g-linear depende da norma. Outro método para minimização irrestrita é o método de região de confiança. Apresentamos neste trabalho uma demonstração da convergência global deste método. O problema geral de programação não linear consiste em minimizar uma função sujeita a restrições, lineares ou não, de igualdade ou desigualdade. Aqui apresentamos métodos para resolver o problema com restrições de igualdade. Mostramos que, sob certas condições, o método de programação quadrática sequencial tem convergência local quadrática. Apresentamos também um algoritmo de filtro globalmente convergente.

Abstract: The purpose of this work is to summarize some results about convergence of the main algorithms used for nonlinear programming. We start by discussing different definitions of the convergence rate. We establish some implications and show that others are not valid, using for this aim examples purposely devised. We then discuss some methods to solve an unconstrained problem, i.e, methods to minimize a differentiable function without constraints. A large class of algorithms developed to solve these problems usually initiates with a given point and determines a direction and a step lenght in this direction in order to provide a reasonable reduction of the value of the objective function. A classical method of unconstrained minimization is the Cauchy method, in which the direction opposite to the gradient of the function at the current point is chosen. For the case where the function is quadratic, convex and the calculation of the lenght of the step is made by accurate linear search, we show an original result: the sequence generated by the Cauchy algorithm converges g-linearly, in the Euclidean norm, to the unique minimizer of the function. We show, in that case, that the convergence rate depends on the condition number of the Hessian matrix of the quadratic function. In the literature we have the g-linear convergence for the hessian-induced norm. Despite the fact that two norms in R" are equivalent, the g-linear convergence is a norm-dependent property. Another method for unconstrained minimization is the trust-region method, for which we present a proof of global convergence. The general problem of nonlinear programming consists in minimizing an objective function subject to equality and inequality constraints. In this work we present some methods to solve problems with equality constraints. We show that, under certain conditions, the method of sequential quadratic programming has local quadratic convergence. We also present a globally convergent filter algorithm.