Uma abordagem de gradiente projetado para otimização multiobjetivo com restrição de cardinalidade

Abstract

Resumo: Neste trabalho, propomos um algoritmo baseado no Método do Lagrangeano Aumentado para resolver problemas de otimizão multiobjetivo com restrição de cardinalidade. Especificamente, como são problemas difíceis de serem resolvidos diretamente, aproveitamos uma reformulação contínua que flexibiliza a restriçao de cardinalidade e propomos essa abordagem que utiliza, em conjunto, o m'etodo do gradiente projetado com busca linear não monótona, adequado para conjuntos viáveis convexos e fechados. Incorporamos tamb'em duas estratégias distintas de penalização externa vetorial, a penalização quadrática e a exponencial. Para relatar justificativas do uso de tal abordagem, realizamos um estudo, exibindo interpretação geométrica e perspectiva analítica dos métodos para resolver problemas de otimização multiobjetivo nos casos: linear, irrestrito e restrito. Na análise da convergência, mostramos a viabilidade do ponto limite e sua otimalidade sob hipóteses fortes, como eficiência fraca. Também utilizamos a teoria de dualidade Lagrangiana, que notamos facilitar os c'alculos. Entretanto, uma hipôtese mais forte, denominada eficiência pr'opria, foi necess'aria. Realizamos uma análise téorica sobre as propriedades de viabilidade e otimalidade das soluçôes obtidas, com base em condiçôes de estacionariedade e argumentos geométricos. Além disso, o algoritmo foi implementado em linguagem Python e aplicado a problemas reais de seleção de portfólio. Os experimentos demonstraram tempos de execução adequados ao contexto multiobjetivo, e os resultados foram avaliados por meio de indicadores como o Hipervolume. A comparação com métodos da literatura evidenciou a eficiência, robustez e competitividade na construção da fronteira de Pareto da abordagem proposta.

Abstract: In this work, we propose an algorithm based on the Augmented La grangian Method to solve multi-objective optimization problems with cardinality constraints. Specifically, since these problems are difficult to solve directly, we leverage a continuous reformulation that relaxes the car dinality constraint and propose this approach that uses, in conjunction with the projected gradient method with non-monotonic linear search, suitable for convex and closed feasible sets. We also incorporate two distinct vectorial external penalty strategies: quadratic and exponential. To provide justifications for using this approach, we conduct a study, presenting a geometric interpretation and an analytical perspective of the methods for solving multi-objective optimization problems in the fol lowing cases: linear, unconstrained, and constrained. In the convergence analysis, we demonstrate the feasibility of the limit point and its opti mality under strong assumptions, such as weak efficiency. We also utilize Lagrangian duality theory, which we note facilitates calculations. How ever, a stronger assumption, called eigenefficiency, was necessary. We performed a theoretical analysis of the feasibility and optimality prop erties of the obtained solutions, based on stationarity conditions and geometric arguments. Furthermore, the algorithm was implemented in Python and applied to real portfolio selection problems. The experi ments demonstrated runtimes suitable for the multi-objective context, and the results were evaluated using indicators such as Hypervolume. Comparison with methods in the literature demonstrated the efficiency, robustness, and competitiveness of the proposed approach in construct ing the Pareto frontier