Utilize este identificador para referenciar este registo:
https://hdl.handle.net/10316/45237
Título: | On the optimal order of worst case complexity of direct search | Autor: | Dodangeh, Mahdi Vicente, Luís Nunes Zhang, Zaikun |
Data: | 2016 | Editora: | Springer Berlin Heidelberg | Projeto: | info:eu-repo/grantAgreement/FCT/COMPETE/132981/PT | Título da revista, periódico, livro ou evento: | Optimization Letters | Volume: | 10 | Número: | 4 | Resumo: | The worst case complexity of direct-search methods has been recently analyzed when they use positive spanning sets and impose a sufficient decrease condition to accept new iterates. For smooth unconstrained optimization, it is now known that such methods require at most \mathcal {O}(n^2\epsilon ^{-2}) function evaluations to compute a gradient of norm below \epsilon \in (0,1), where n is the dimension of the problem. Such a maximal effort is reduced to \mathcal {O}(n^2\epsilon ^{-1}) if the function is convex. The factor n^2 has been derived using the positive spanning set formed by the coordinate vectors and their negatives at all iterations. In this paper, we prove that such a factor of n^2 is optimal in these worst case complexity bounds, in the sense that no other positive spanning set will yield a better order of n. The proof is based on an observation that reveals the connection between cosine measure in positive spanning and sphere covering. | URI: | https://hdl.handle.net/10316/45237 | DOI: | 10.1007/s11590-015-0908-1 10.1007/s11590-015-0908-1 |
Direitos: | embargoedAccess |
Aparece nas coleções: | I&D CMUC - Artigos em Revistas Internacionais |
Mostrar registo em formato completo
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.