Resumen Técnico: Optimización Funcional Con Restricciones sin Proyección para Aversión al Riesgo y Control de Esparsidad

1. Formulación del Problema

El artículo aborda el problema de optimización funcional con restricciones:
$$\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}$$
donde $X \subseteq \mathbb{R}^n$ es un conjunto no vacío, compacto y convexo. Las funciones $h_i$ son propias, semicontinuas inferiormente y convexas. El objetivo $f$ se estudia en dos regímenes:

1. Entorno Convexo: $f$ es convexa (posiblemente no suave).
2. Entorno No Convexo: $f$ es diferenciable con gradientes Lipschitz continuos.

Este marco modela aplicaciones donde los criterios conscientes del riesgo y las restricciones de esparsidad aparecen simultáneamente, como en la optimización de carteras (minimización del riesgo de bajo rendimiento con límites de activos) y la planificación de radioterapia de intensidad modulada (IMRT) (minimización de sobredosis/subdosis con selección de haces dispersa).

Desafío: Los métodos estándar basados en proyección (por ejemplo, penalización, Lagrangiano aumentado, primal-dual) requieren proyecciones repetidas sobre $X$, lo cual puede ser computacionalmente costoso y destruir las estructuras de esparsidad inherentes a la solución. Los métodos existentes sin proyección solo manejan restricciones simples o tienen cotas de complejidad dependientes de la magnitud de los multiplicadores de Lagrange duales óptimos, los cuales pueden ser arbitrariamente grandes.

2. Metodología

Los autores proponen algoritmos sin proyección que reemplazan las proyecciones con llamadas a un Oráculo de Minimización Lineal (LMO) sobre $X$. La innovación central es un Bucle Externo de Nivel combinado con un Oráculo de Gradiente Condicional (CGO) para subproblemas de punto de silla.

2.1 Entorno Convexo: Gradiente Condicional de Nivel (LCG)

Para el caso convexo, el problema se reduce a encontrar la raíz de una función de valor $\phi(l) = \min_{x \in X} \max \{ f(x) - l, h_1(x), \dots, h_m(x) \}$.

• Bucle Externo: Un método de Newton aproximado actualiza la estimación de nivel $l_k$. En lugar de gradientes exactos, utiliza una cota inferior $L_k$ y un subgradiente aproximado derivado del oráculo interno.
• Bucle Interno (CGO): Un Oráculo de Gradiente Condicional especializado resuelve el subproblema de punto de silla $\min_{x \in X} \max_{z \in Z} [f(x) - l_k] + \langle h(x), z \rangle$.
  • El oráculo devuelve una iterada primal $x_k$ y un intervalo de certificado $[L_k, U_k]$.
  • Crucialmente, el conjunto dual $Z$ es el simplex estándar, asegurando que el método no dependa de la magnitud de los multiplicadores de Lagrange óptimos.
  • La brecha $U_k - L_k$ impulsa la regla de parada y las actualizaciones de nivel.
• Extensión No Suave: Para funciones no suaves estructuradas (estructura max), el método emplea suavizado de Nesterov dentro del marco CGO, manteniendo el mismo orden de complejidad.

2.2 Entorno No Convexo: LCG de Punto Proximal Inexacto (IPP-LCG)

Para $f$ no convexa, el método reduce el problema a una secuencia de subproblemas convexos mediante regularización de punto proximal:
$$\min_{x \in X} f(x) + L_f \|x - x_{j-1}\|^2 \quad \text{s.t.} \quad h_i(x) \le 0.$$

• Mecanismo: El método LCG del entorno convexo se utiliza como solucionador inexacto para cada subproblema proximal.
• Salida: El algoritmo selecciona la iterada que minimiza la disminución del objetivo a lo largo de la secuencia.
• Garantía: Bajo la condición de Slater y supuestos de suavidad, el método computa un punto $(\epsilon, \epsilon)$-cercano a KKT.

3. Contribuciones Clave

1. LCG para Restricciones Funcionales Convexas:

   • Propone el método de Gradiente Condicional de Nivel (LCG).
   • Logra una complejidad de iteración de $O(\epsilon^{-2} \log(\epsilon^{-1}))$ para obtener una solución $\epsilon$-óptima y $\epsilon$-factible.
   • Significado: La cota de complejidad es independiente de la magnitud del multiplicador de Lagrange dual óptimo, una limitación presente en trabajos previos sin proyección (por ejemplo, Lan et al., 2021).

2. IPP-LCG para Objetivos No Convexos Suaves:

   • Desarrolla el método de Punto Proximal Inexacto LCG (IPP-LCG).
   • Resuelve una secuencia de subproblemas convexos usando LCG, manteniendo todas las soluciones internas libres de proyección.
   • Logra una complejidad de iteración de $O(\epsilon^{-3} \log(\epsilon^{-1}))$ para computar un punto $(\epsilon, \epsilon)$-cercano a KKT.

3. Mecanismo de Certificados:

   • El CGO devuelve certificados explícitos inferior y superior ($L_k, U_k$) que impulsan las actualizaciones del conjunto de nivel y las reglas de parada, evitando la necesidad de soluciones exactas de punto de silla.

4. Resultados Numéricos

Los autores evalúan los métodos en dos dominios de aplicación:

4.1 Selección de Carteras

• Configuración: Optimización de cartera aversa al riesgo con objetivos de riesgo escalonado (convexificados mediante CVaR o sustitutos no convexos suavizados) y restricciones de esparsidad (limitando el número de activos).
• Líneas Base: Comparación frente a CoexDurCG (sin proyección), FISTA, PGD y varios heurísticos orientados a la esparsidad (Greedy+Refit, IRL1, etc.) bajo un presupuesto fijo de tiempo de reloj de 5 segundos.
• Hallazgos:
  • Modelo Convexo: LCG logró el mejor riesgo escalonado fuera de muestra factible en 5 de 6 conjuntos de datos mientras cumplía estrictamente los objetivos de esparsidad.
  • Modelo No Convexo: IPP-LCG logró el mejor riesgo escalonado factible en 4 de 6 conjuntos de datos.
  • Compensación: Los métodos navegaron con éxito la compensación entre precisión y esparsidad, superando a menudo a las líneas base basadas en proyección en la reducción de riesgo factible dentro del mismo presupuesto de tiempo.

4.2 Radioterapia de Intensidad Modulada (IMRT)

• Configuración: Planificación de tratamiento con restricciones de esparsidad grupal (limitando el número de ángulos de haz) y restricciones clínicas de dosis-volumen.
• Hallazgos:
  • Convexo: LCG mejoró la satisfacción de restricciones en comparación con CoexDurCG con tiempos de ejecución similares.
  • No Convexo: Se probó una estrategia de "inicio en caliente" donde un plan convexo disperso de LCG inicializaba el refinamiento no convexo de IPP-LCG.
  • Resultado: El IPP-LCG iniciado en caliente redujo significativamente la violación máxima de restricciones (de 0.8438 a 0.1675) en comparación con un IPP-LCG iniciado en frío, preservando al mismo tiempo una estructura de tratamiento clínicamente dispersa (7 ángulos, 20 aperturas). La optimización no convexa iniciada en frío no logró encontrar planes clínicamente viables debido a una subdosis severa en el objetivo.

5. Significado y Afirmaciones

El artículo afirma que su contribución principal radica en extender los métodos sin proyección a restricciones funcionales generales sin depender de la magnitud de los multiplicadores duales para las garantías de complejidad. Al combinar un bucle externo de conjunto de nivel con un oráculo compacto de punto de silla, los autores retienen los beneficios de representación dispersa de los métodos de gradiente condicional (iteradas como combinaciones convexas de puntos extremos) mientras manejan restricciones no lineales complejas.

Los resultados numéricos sugieren que:

1. LCG es efectivo para problemas de riesgo-esparsidad convexos, ofreciendo un rendimiento competitivo o superior a los métodos existentes sin proyección y basados en proyección.
2. IPP-LCG es más efectivo no como solucionador autónomo desde un inicio aleatorio, sino como mecanismo de refinamiento cuando se inicializa con una solución convexa dispersa de alta calidad.

Los autores concluyen que estos métodos son particularmente adecuados para aplicaciones a gran escala donde las proyecciones son costosas y las representaciones estructurales dispersas son deseables. Las direcciones de trabajo futuro identificadas incluyen el desarrollo de esquemas no convexos más ligeros, el relajamiento de supuestos tipo Slater y el diseño de LMOs específicos para aplicaciones para conjuntos factibles implícitos.