Worst case complexity of direct search under convexity

Abstract

In this thesis we prove that the broad class of direct-search methods of directional type, based on imposing sufficient decrease to accept new iterates, exhibits the same worst case complexity bound and global rate of the gradient method for the unconstrained minimization of a convex and smooth function without using derivatives. More precisely, it will be shown that the number of iterations needed to reduce the norm of the gradient of the objective function below a certain threshold is at most proportional to the inverse of the threshold. It will be also shown that the absolute error in the function values decay at a sub-linear rate proportional to the inverse of the iteration counter. In addition, we prove that the sequences of absolute errors of function values and iterates converge r-linearly in the uniformly/strongly convex case. A second open problem is solved in this thesis regarding the worst case complexity of direct search for smooth functions. It is proved that the factor consisting of the dimension of the problem squared that appears in the bounds for the worst number of function evaluations is optimal, in the sense that no better power of the problem dimension is attainable.

Nesta dissertação, provamos que a abrangente classe de métodos de procura directa do tipo direccional, que tem por base aceitar novas iteradas recorrendo a uma condição de decréscimo suficiente, exibe o mesmo limite superior de complexidade, no pior dos casos, que o método do gradiente para a minimização de uma função convexa e suave sem recurso a derivadas. Mais precisamente, será demonstrado que o número de iterações necessárias para reduzir a norma do gradiente da função objectivo abaixo de um determinado valor é, no máximo, proporcional ao inverso desse valor. Será também mostrado que o erro absoluto nos valores da função decresce a uma taxa sub-linear, proporcional ao inverso do contador das iterações. Demonstramos, igualmente, que as sucessões de erros absolutos, no valor da função e nas iteradas, convergem r-linearmente no caso uniformemente/fortemente convexo. É resolvido ainda um segundo problema em aberto na complexidade no pior dos casos da procura directa para funções suaves. É provado que o factor da dimensão do problema ao quadrado, presente nos limites superiores para o pior número de avaliações da função, é óptimo no sentido em que não é possível alcançar uma melhor potência na dimensão do problema.