Otimização sem derivadas com funções de base radial em regiões convexas : otimização de menor valor ordenado sem derivadas

Abstract

Esta tese aborda o desenvolvimento e análise teórica de algoritmos de otimização sem derivadas (Derivative-Free Optimization - DFO) para problemas com restrições convexas, com foco na extensão do método ORBIT (Optimization by Radial Basis Function Interpolation in Trust-Regions). O ORBIT original é um algoritmo de região de confiança que utiliza modelos interpoladores baseados em funções de base radial (RBF) para resolver problemas irrestritos. No entanto, a maioria dos problemas práticos envolve restrições, e a garantia de convergência com o uso exclusivo de pontos de interpolação viáveis era um desafio em aberto. O objetivo principal deste trabalho é propor e analisar algoritmos que preservem a robustez e as garantias de convergência do ORBIT para problemas com restrições, utilizando apenas pontos de interpolação viáveis. A dificuldade central reside em manter adequadas propriedades geométricas do conjunto de pontos interpoladores (como a independência afim) dentro da região viável, o que é essencial para a construção de modelos locais precisos e para a convergência global. A primeira contribuição é assegurar a convergência global do algoritmo ORBIT para problemas com restrições convexas fechadas e de interior não vazio. A segunda foi o algoritmo BoxORBIT, desenvolvido para problemas com restrições de caixa, um caso particular das restrições convexas, que adapta a estratégia de gestão geométrica, para um parâmetro menor, a construção de modelos totalmente lineares usando apenas pontos viáveis. Por fim, é desenvolvida uma extensão para lidar com restrições lineares gerais de desigualdade, inclusive em cenários degenerados. Para isso, é proposta uma metodologia que combina a identificação de restrições ativas, a construção de um conjunto gerador de direções viáveis baseado na matriz de restrições e, quando necessário, o uso do Método de Dupla Descrição (Double Description Method) para tratar do caso degenerado. 4 Os resultados teóricos demonstram a convergência global dos algoritmos propostos para pontos estacionários, sob hipóteses padrão de suavidade da função objetivo. A análise estabelece que é possível manter a condição de totalmente linear para os modelos RBF mesmo quando os pontos de interpolação são confinados ao conjunto viável. Adicionalmente, são apresentados resultados numéricos preliminares que validam a abordagem.

This thesis addresses the development and theoretical analysis of derivative-free optimization (DFO) algorithms for problems with convex constraints, focusing on extending the ORBIT method (Optimization by Radial Basis Function Interpolation in Trust-Regions). The original ORBIT is a trust-region algorithm that uses interpolation models based on radial basis functions (RBF) to solve unconstrained problems. However, most practical problems involve constraints, and guaranteeing convergence using exclusively feasible interpolation points was an open challenge. The main objective of this work is to propose and analyze algorithms that preserve the robustness and convergence guarantees of ORBIT for constrained problems, using only feasible interpolation points. The central difficulty lies in maintaining adequate geometric properties of the interpolation point set (such as affine independence)within the feasible region, which is essential for constructing accurate local models and ensuring global convergence. The first contribution is ensuring the global convergence of the ORBIT algorithm for problems with closed convex constraints with nonempty interior. The second contribution is the BoxORBIT algorithm, developed for problems with box constraints - a particular case of convex constraints - which adapts the geometric management strategy with a tighter parameter to build fully linear models using only feasible points. Finally, an extension is developed to handle general linear inequality constraints, including degenerate scenarios. For this, a methodology is proposed that combines the identification of active constraints, the construction of a set of feasible search directions based on the constraintmatrix, and, when necessary, the use of the Double Description Method to handle the degenerate case. Theoretical results demonstrate the global convergence of the proposed algorithms to stationary points, under standard smoothness assumptions of the objective function. 2 The analysis establishes that it is possible to maintain the "fully linearty" condition for the RBF models even when the interpolation points are confined to the feasible set. Additionally, preliminary numerical results validating the approach are presented.