Derivative-free low order-value optimization = : otimização de menor valor ordenado sem derivadas

Abstract

Resumo: O desenvolvimento dos métodos de otimização sem derivadas (DFO) foi impulsionado pela necessidade crescente de resolver problemas complexos e diversos, em especial, problemas para os quais as derivadas da função˜ao objetivo e das restrições não estão disponíveis. Este é o caso de diversas aplicações práticas encontradas na ciência, medicina e engenharia, entre outros. Por exemplo, em situações onde a função objetivo e do tipo caixa preta (black-box ), não possui expressão analítica, ou ainda, possui um alto custo computacional. Existem diversas abordagens distintas para DFO, dentre as quais podemos citar busca direta, busca padrão, baseada em modelos, laringianos aumentados, entre outros. Apesar da grande variedade de métodos encontrados na literatura, desconhecemos métodos dedicados a solução de problemas de otimização de menor valor ordenado (LOVO), nos quais buscamos minimizar o mínimo entre um número finito de valores de função em um conjunto viável. Neste trabalho estamos interessados no problema de otimização LOVO não linear restrito, cujo conjunto viável é convexo, fechado e não vazio, e cada função componente e do tipo black-box e continuamente diferenciavel. Também assumimos que é simples calcular a projeção ortogonal de um ponto arbitrário sobre o conjunto viável. Desenvolvemos um algoritmo de região de confiança sem derivadas para problemas LOVO restritos com convergência para pontos fracamente críticos. Sob condições adequadas, estabelecemos resultados de convergência global e de complexidade do pior caso. Discutimos a construção de modelos lineares e quadráticos adequados para otimização sem derivadas e estendemos o conceito para modelos quadráticos subdeterminados baseados em valores aproximados da função. Por fim, apresentamos uma implementação eficiente de nosso algoritmo, bem como resultados numéricos promissores.

Abstract: The development of derivative-free optimization (DFO) methods was driven by the growing need to solve complex and diverse problems, particularly, problems for which the derivatives of the objective function and constraints are not available. This is the case for many practical applications in science, medicine, and engineering, among others. For example, in situations where the objective function is of black-box type, it has no analytical expression or it has a high computational cost. There are several different approaches to DFO methods, among which we can mention direct and pattern search, model-based, augmented lagrangian, among others. Despite the wide variety of methods found in the literature, we are unaware of methods dedicated to solving low order-value optimization (LOVO) problems, in which we seek to minimize the minimum among a finite number of function values within a feasible set. In this work, we are interested in the constrained nonlinear optimization LOVO problem, whose feasible set is convex, closed, and nonempty, and each component function is black-box and continuously differentiable. We also assume that it is simple to compute the orthogonal projection of an arbitrary point onto the feasible set. We developed a derivative-free trust-region algorithm for constrained LOVO problems with convergence to weakly critical points. Under suitable conditions, we establish global convergence and worst case complexity results. We discuss the construction of linear and quadratic models suitable for derivative-free optimization and extend the concept to underdetermined quadratic models based on approximate values of the function. Finally, we present an efficient implementation of our algorithm, as well as numerical results.