Resumo Técnico: Algoritmos O(n) para Projeção no Conjunto de Nível Subsuperior do Top-k-sum

1. O Problema

O artigo aborda o problema de projeção euclidiana no conjunto de nível subsuperior do operador top-k-sum. Dado um vetor de entrada $x_0 \in \mathbb{R}^n$, um índice $k \in \{1, \dots, n\}$ e um orçamento escalar $r \in \mathbb{R}$, o objetivo é resolver o seguinte problema de otimização fortemente convexa:

$$\begin{aligned} \text{minimizar} \quad & \frac{1}{2}\|x - x_0\|_2^2 \\ \text{sujeito a} \quad & x \in B_r^{(k)} := \left\{ x \in \mathbb{R}^n : T^{(k)}(x) := \sum_{i=1}^k \vec{x}_i \leq r \right\} \end{aligned}$$

Onde $\vec{x}$ denota o vetor $x$ ordenado em ordem não crescente ($\vec{x}_1 \geq \vec{x}_2 \geq \dots \geq \vec{x}_n$) e $T^{(k)}(x)$ é a soma dos $k$ maiores componentes de $x$.

Contexto e Importância:

• O operador top-k-sum está intimamente relacionado à Superquantil (também conhecida como CVaR - Conditional Value-at-Risk), amplamente utilizada em otimização robusta, aprendizado de máquina (para lidar com dados desbalanceados, fairness e robustez) e finanças.
• A projeção é uma sub-rotina crítica em métodos iterativos (como o Método de Lagrangiano Aumentado) para resolver problemas compostos de otimização de superquantil.
• Soluções existentes (como solvers de Programação Quadrática genéricos, ex: Gurobi, ou métodos de busca em grade) são computacionalmente proibitivas para grandes dimensões ($n$ na ordem de milhões), especialmente quando $k$ é uma fração linear de $n$.

2. Metodologia Proposta

Os autores propõem dois algoritmos de terminação finita que operam com complexidade $O(n)$ quando o vetor de entrada já está ordenado. A constante absorvida na complexidade é independente de $k$.

Abordagem Geral

O problema é reformulado assumindo que a entrada está ordenada (o que permite transformar as restrições em um sistema de desigualdades isotônicas e uma restrição de orçamento). O conjunto viável é visto como a interseção de um cone isotônico e um semiespaço.

Algoritmo 1: Abordagem PLCP (Parametric Linear Complementarity Problem)

• Base Teórica: Baseia-se na estrutura de matrizes Z (matrizes simétricas positivas definidas com elementos fora da diagonal não positivos) das condições KKT do problema ordenado.
• Mecanismo: Utiliza um método de pivoteamento paramétrico. O problema é penalizado com um parâmetro $\lambda \geq 0$ na função objetivo. O algoritmo varia $\lambda$ de 0 a $+\infty$, resolvendo uma sequência de subproblemas LCP (Problema de Complementaridade Linear).
• Eficiência: Devido à estrutura tridiagonal da matriz do sistema e às propriedades de monotonicidade da solução em relação a $\lambda$, o algoritmo realiza no máximo $n$ pivotações. Cada passo é executado em tempo constante $O(1)$, resultando em complexidade total $O(n)$.
• Implementação: O algoritmo não mantém explicitamente o vetor dual completo para economizar memória, utilizando uma atualização implícita via complemento de Schur.

Algoritmo 2: ESGS (Early-Stopping Grid-Search)

• Base Teórica: Uma melhoria refinada do método de busca em grade descrito em trabalhos anteriores (ex: [38]).
• Mecanismo: Em vez de realizar uma busca exaustiva sobre todos os pares de índices $(k_0, k_1)$ que definem os pontos de ruptura da solução (onde $k_0$ é o índice do último elemento estritamente maior que a média e $k_1$ o primeiro estritamente menor), o algoritmo explora propriedades de monotonicidade das condições KKT.
• Estratégia: O algoritmo inicia em $(k-1, k)$ e percorre um caminho no espaço de busca, decrementando $k_0$ ou incrementando $k_1$ com base em indicadores de satisfação das condições KKT.
• Vantagem: A monotonicidade permite "pular" regiões inteiras do espaço de busca que não podem conter a solução ótima, garantindo que o algoritmo termine em no máximo $n$ passos, também com complexidade $O(n)$.

Ordenação Parcial e Reutilização

Para vetores de entrada não ordenados, os autores derivam uma propriedade (Proposição 3) que permite o uso de ordenamento parcial ou aproximações de ordenação (ex: de iterações anteriores em um método iterativo).

• Em vez de ordenar completamente o vetor ($O(n \log n)$), o algoritmo pode extrair apenas os elementos necessários dinamicamente (usando um heap), resultando em complexidade $O(\bar{k}_1 \log n)$, onde $\bar{k}_1$ é o índice de corte ótimo (desconhecido a priori, mas determinado dinamicamente).

3. Contribuições Principais

1. Complexidade O(n): Desenvolvimento de dois algoritmos que resolvem o problema de projeção exata em tempo linear para entradas ordenadas, superando métodos anteriores que tinham complexidade $O(k(n-k))$ (quadrática no pior caso) ou dependiam de ordenação completa.
2. Terminação Finita e Exata: Diferente de métodos numéricos aproximados ou heurísticos, os algoritmos garantem a solução exata do problema de otimização convexa em um número finito de passos.
3. Eficiência em Grandes Escalas: Demonstração de que é possível resolver problemas com $n = 10^7$ em frações de segundo, algo inviável com solvers comerciais ou métodos de busca em grade tradicionais.
4. Extensibilidade: As técnicas são adaptáveis para a projeção na bola da norma-k vetorial (Ky-Fan norm), um problema relacionado mas mais complexo.

4. Resultados Numéricos

Os autores realizaram experimentos extensivos comparando seus métodos (ESGS e PLCP) com:

• GRID: Implementação do método de busca em grade de [38].
• SSN: Método de Newton semissuave de [24].
• Gurobi: Solver QP comercial (versões ordenada e não ordenada).

Principais Achados:

• Velocidade: Para $n = 10^7$ e $k = 10^4$, os métodos propostos resolvem o problema em < 0,05 segundos.
  • O método SSN (o concorrente mais rápido) leva cerca de 1 segundo.
  • O método GRID e o Gurobi levam de minutos a horas (ou falham por tempo limite).
• Escalabilidade: Os métodos propostos exibem um comportamento de escala linear, enquanto o método GRID exibe escala quadrática.
• Comparação ESGS vs. PLCP: O ESGS é geralmente 1,5 a 2 vezes mais rápido que o PLCP em instâncias difíceis (que exigem muitos pivotações), mantendo uma leve vantagem em instâncias fáceis.
• Ordenação: O tempo gasto na ordenação completa do vetor de entrada é frequentemente maior que o tempo de resolução do algoritmo de projeção para entradas já ordenadas, reforçando a utilidade da ordenação parcial proposta.

5. Significado e Conclusão

Este trabalho fornece uma "oráculo" de projeção altamente eficiente e exata, essencial para a viabilidade prática de métodos de otimização de segunda ordem e de Lagrangiano Aumentado aplicados a problemas de risco (CVaR/Superquantil) em larga escala.

A capacidade de resolver projeções em vetores de dimensão de milhões em tempo quase instantâneo remove um gargalo computacional significativo em aplicações de aprendizado de máquina robusto, design de sistemas críticos e otimização financeira. A implementação em Julia está disponível publicamente, facilitando a adoção por pesquisadores e engenheiros.