ERROR BOUNDS E DESIGUALDADE DE KURDYKA- LOJASIEWICZ EM COMPLEXIDADE DE MÉTODOS DE DESCIDA PARA FUNÇÕES CONVEXAS

Abstract

RESUMO: Neste trabalho mostramos como o conceito de error bounds pode ser usado como uma ferramenta efetiva para se obter resultados de complexidade de métodos de descida de primeira ordem em programação convexa. Para isso, estudamos a relação entre os conceitos de error bounds e desigualdade de Kurdyka- Lojasiewicz. Usando esses conceitos, obtemos a complexidade do método via um algoritmo de ponto proximal unidimensional. Como aplicação, analisamos um método para resolver um problema de viabilidade convexa. ABSTRACT: In this work, we show how the concept of error bounds can be used as an effective tool to obtain complexity results of a first order descent method in convex programming. To this end, we study the relationship between the concepts of error bounds and Kurdyka- Lojasiewicz inequality. Using these concepts, we obtain the complexity of the method by means of an unidimensional proximal point algorithm. As an application, we analyze a method for solving a convex feasibility problem.