Mathematical programs with cardinality constraints : a unified approach for weak stationaryconditions and a sequential optimality condition

Abstract

Resumo: Nesta tese, estudamos uma classe de problemas de otimização, chamada Mathematical Programs with Cardinality Constraints (MPCaC)). Este tipo de problema é geralmente difícil de lidar, porque envolve uma restrição que não é contínua e nem convexa, mas fornece soluções esparsas. Assim, reformulamos o problema de uma forma adequada, modelando-o como um problema inteiro misto e então consideramos a sua contraparte contínua, a qual será referida como problema relaxado. Investigamos o problema relaxado analisando as restrições gerais em dois casos: linear e não linear. No caso linear, propomos uma abordagem geral e apresentamos uma discussão das condições de qualificação de Abadie e Guignard, provando neste caso que todo minimizador do problema relaxado satisfaz as condições de Karush-Kuhn-Tucker (KKT). Por outro lado, no caso não linear, mostramos que as condições de qualificação clássicas podem ser violadas. Motivados por encontrar um minimizador para o problema MPCaC, definimos uma nova condição de estacionariedade, mais fraca do que KKT, propondo uma abordagem unificada que vai da estacionariedade mais fraca até a mais forte (dentro de um certo espectro de condições). Entretanto, estas condições não são condições de otimalidade. Deste modo, propomos também um conceito de estacionariedade fraca aproximada chamado AW-stationarity (do inglês, Approximate Weak stationarity), desenhado para lidar com problemas MPCaC. Provamos que é uma condição de otimalidade legítima independentemente de qualquer condição de qualificação. Muitas pesquisas em condições sequenciais de otimalidade têm sido feitas para otimização não linear com restrições nos últimos anos, sendo alguns trabalhos no contexto de problemas da classe Mathematical Programs with Complementarity Constraints (MPCC). No entanto, até onde sabemos, nenhuma condição sequencial de otimalidade foi proposta para problemas MPCaC. Estabelecemos algumas relações entre a nossa condição AW-stationarity e outras condições sequenciais de otimalidade usuais, tais como AKKT, CAKKT e PAKKT. Ressaltamos que, apesar do apelo computacional das condições sequenciais de otimalidade, nosso objetivo até este momento foi discutir os aspectos teóricos de tais condições para problemas MPCaC. Os aspectos algorítmicos por trás de nossa teoria são temas de pesquisa em andamento.

Abstract: In this thesis, we study a class of optimization problems, called Mathematical Programs with Cardinality Constraints (MPCaC). This kind of problem is generally difficult to deal with, because it involves a constraint that is not continuous neither convex, but provides sparse solutions. Thereby we reformulate MPCaC in a suitable way, by modeling it as mixed-integer problem and then addressing its continuous counterpart, which will be referred to as relaxed problem. We investigate the relaxed problem by analyzing the general constraints in two cases: linear and nonlinear. In the linear case, we propose a general approach and present a discussion of the Guignard and Abadie constraint qualifications, proving in this case that every minimizer of the relaxed problem satisfies the Karush-Kuhn-Tucker (KKT) conditions. On the other hand, in the nonlinear case, we show that some standard constraint qualifications may be violated. Motivated to find a minimizer for the MPCaC problem, we define new stationarity conditions, weaker than KKT, by proposing a unified approach that goes from the weakest to the strongest stationarity (within a certain range of conditions). However, these conditions are not optimality conditions. Thereby, we also propose an Approximate Weak stationarity (AW-stationarity) concept designed to deal with MPCaC problems. We proved that it is a legitimate optimality condition independently of any constraint qualification. Many research on sequential optimality conditions has been addressed for nonlinear constrained optimization in the last few years, some works in the context of Mathematical Programs with Complementarity Constraints (MPCC). However, as far as we know, no sequential optimality condition has been proposed for MPCaC problems. We also establish some relationships between our AW-stationarity and other usual sequential optimality conditions, such as AKKT, CAKKT and PAKKT. We point out that, despite the computational appeal of the sequential optimality conditions, our aim until this moment was to discuss the theoretical aspects of such conditions for MPCaC problems. The algorithmic aspects behind our theory are subject of ongoing research.