Resumo Técnico: Otimização Funcional sem Projeção com Restrições para Aversão ao Risco e Controle de Esparsidade

1. Formulação do Problema

O artigo aborda o problema de otimização funcional com restrições:
$$\begin{aligned} f^* := \min_{x} \quad & f(x) \\ \text{s.t.} \quad & h_i(x) \le 0, \quad i = 1, \dots, m, \\ & x \in X, \end{aligned} \tag{1.1}$$
onde $X \subseteq \mathbb{R}^n$ é um conjunto não vazio, compacto e convexo. As funções $h_i$ são próprias, semicontínuas inferiormente e convexas. O objetivo $f$ é estudado em dois regimes:

1. Regime Convexo: $f$ é convexa (possivelmente não suave).
2. Regime Não Convexo: $f$ é diferenciável com gradientes Lipschitz contínuos.

Esta estrutura modela aplicações onde critérios conscientes de risco e restrições de esparsidade aparecem simultaneamente, como em otimização de carteiras (minimização do risco de desempenho abaixo do esperado com limites de ativos) e planejamento de radioterapia modulada por intensidade (IMRT) (minimização de superdosagem/subdosagem com seleção esparsa de feixes).

Desafio: Métodos baseados em projeção padrão (por exemplo, penalidade, Lagrangiano aumentado, primal-dual) exigem projeções repetidas sobre $X$, o que pode ser computacionalmente caro e destruir estruturas esparsas inerentes à solução. Métodos sem projeção existentes lidam apenas com restrições simples ou possuem limites de complexidade dependentes da magnitude dos multiplicadores de Lagrange duais ótimos, que podem ser arbitrariamente grandes.

2. Metodologia

Os autores propõem algoritmos sem projeção que substituem projeções por chamadas a um Oráculo de Minimização Linear (LMO) sobre $X$. A inovação central é um Loop Externo de Nível combinado com um Oráculo de Gradiente Condicional (CGO) para subproblemas de ponto de sela.

2.1 Regime Convexo: Gradiente Condicional de Nível (LCG)

Para o caso convexo, o problema é reduzido à busca da raiz de uma função de valor $\phi(l) = \min_{x \in X} \max \{ f(x) - l, h_1(x), \dots, h_m(x) \}$.

• Loop Externo: Um método de Newton aproximado atualiza a estimativa de nível $l_k$. Em vez de gradientes exatos, utiliza um limite inferior $L_k$ e um subgradiente aproximado derivado do oráculo interno.
• Loop Interno (CGO): Um Oráculo de Gradiente Condicional especializado resolve o subproblema de ponto de sela $\min_{x \in X} \max_{z \in Z} [f(x) - l_k] + \langle h(x), z \rangle$.
  • O oráculo retorna uma iteração primal $x_k$ e um intervalo de certificado $[L_k, U_k]$.
  • Crucialmente, o conjunto dual $Z$ é o simplex padrão, garantindo que o método não dependa da magnitude dos multiplicadores de Lagrange ótimos.
  • A lacuna $U_k - L_k$ impulsiona a regra de parada e as atualizações de nível.
• Extensão Não Suave: Para funções estruturadas não suaves (estrutura de máximo), o método emprega suavização de Nesterov dentro do framework CGO, mantendo a mesma ordem de complexidade.

2.2 Regime Não Convexo: LCG de Ponto Próximo Inexato (IPP-LCG)

Para $f$ não convexa, o método reduz o problema a uma sequência de subproblemas convexos via regularização de ponto próximo:
$$\min_{x \in X} f(x) + L_f \|x - x_{j-1}\|^2 \quad \text{s.t.} \quad h_i(x) \le 0.$$

• Mecanismo: O método LCG do regime convexo é usado como um solver inexato para cada subproblema próximo.
• Saída: O algoritmo seleciona a iteração que minimiza a redução do objetivo ao longo da sequência.
• Garantia: Sob a condição de Slater e suposições de suavidade, o método computa um ponto $(\epsilon, \epsilon)$-próximo de KKT.

3. Contribuições Principais

1. LCG para Restrições Funcionais Convexas:

   • Propõe o método Gradiente Condicional de Nível (LCG).
   • Alcança uma complexidade de iteração de $O(\epsilon^{-2} \log(\epsilon^{-1}))$ para obter uma solução $\epsilon$-ótima e $\epsilon$-viável.
   • Significado: O limite de complexidade é independente da magnitude do multiplicador de Lagrange dual ótimo, uma limitação presente em trabalhos anteriores sem projeção (por exemplo, Lan et al., 2021).

2. IPP-LCG para Objetivos Não Convexos Suaves:

   • Desenvolve o método Ponto Próximo Inexato LCG (IPP-LCG).
   • Resolve uma sequência de subproblemas convexos usando LCG, mantendo todas as soluções internas livres de projeção.
   • Alcança uma complexidade de iteração de $O(\epsilon^{-3} \log(\epsilon^{-1}))$ para computar um ponto $(\epsilon, \epsilon)$-próximo de KKT.

3. Mecanismo de Certificado:

   • O CGO retorna certificados explícitos inferior e superior ($L_k, U_k$) que impulsionam as atualizações do conjunto de nível e as regras de parada, evitando a necessidade de soluções exatas de ponto de sela.

4. Resultados Numéricos

Os autores avaliam os métodos em dois domínios de aplicação:

4.1 Seleção de Carteiras

• Configuração: Otimização de carteira avessa ao risco com objetivos de risco em etapas (convexificados via CVaR ou substitutos não convexos suavizados) e restrições de esparsidade (limitando o número de ativos).
• Baselines: Comparado contra CoexDurCG (sem projeção), FISTA, PGD e vários heurísticos orientados à esparsidade (Greedy+Refit, IRL1, etc.) sob um orçamento fixo de 5 segundos de tempo de relógio.
• Descobertas:
  • Modelo Convexo: O LCG alcançou o melhor risco em etapas fora da amostra viável em 5 de 6 conjuntos de dados, atendendo estritamente às metas de esparsidade.
  • Modelo Não Convexo: O IPP-LCG alcançou o melhor risco em etapas viável em 4 de 6 conjuntos de dados.
  • Compromisso: Os métodos navegaram com sucesso no compromisso precisão-esparsidade, frequentemente superando as baselines baseadas em projeção na redução viável de risco dentro do mesmo orçamento de tempo.

4.2 Radioterapia Modulada por Intensidade (IMRT)

• Configuração: Planejamento de tratamento com restrições de esparsidade de grupo (limitando o número de ângulos de feixe) e restrições clínicas de dose-volume.
• Descobertas:
  • Convexo: O LCG melhorou a satisfação das restrições em comparação com o CoexDurCG em tempos de execução similares.
  • Não Convexo: Uma estratégia de "inicialização quente" foi testada, onde um plano convexo esparsos LCG inicializou o refinamento não convexo IPP-LCG.
  • Resultado: O IPP-LCG com inicialização quente reduziu significativamente a violação máxima de restrição (de 0,8438 para 0,1675) em comparação com um IPP-LCG com inicialização fria, preservando uma estrutura de tratamento clinicamente esparsa (7 ângulos, 20 aberturas). A otimização não convexa com inicialização fria falhou em encontrar planos clinicamente viáveis devido a subdosagem severa no alvo.

5. Significado e Alegações

O artigo afirma que sua contribuição principal reside na extensão dos métodos sem projeção para restrições funcionais gerais, sem depender da magnitude dos multiplicadores duais para garantias de complexidade. Ao combinar um loop externo de conjunto de nível com um oráculo compacto de ponto de sela, os autores retêm os benefícios de representação esparsa dos métodos de gradiente condicional (iterações como combinações convexas de pontos extremos) enquanto lidam com restrições não lineares complexas.

Os resultados numéricos sugerem que:

1. LCG é eficaz para problemas de risco-esparsidade convexos, oferecendo desempenho competitivo ou superior aos métodos existentes sem projeção e baseados em projeção.
2. IPP-LCG é mais eficaz não como um solver autônomo a partir de uma inicialização aleatória, mas como um mecanismo de refinamento quando inicializado com uma solução convexa esparsa de alta qualidade.

Os autores concluem que esses métodos são particularmente adequados para aplicações em grande escala onde projeções são caras e representações estruturadas esparsas são desejáveis. Direções de trabalho futuro identificadas incluem o desenvolvimento de esquemas não convexos mais leves, o relaxamento de suposições do tipo Slater e o projeto de LMOs específicos para aplicações para conjuntos viáveis implícitos.