A condensing approach for linear-quadratic optimization with geometric constraints

Resumen Técnico: Un enfoque de condensación para optimización lineal-cuadrática con restricciones geométricas

Autor: Alberto De Marchi (Universidad de las Fuerzas Armadas de Múnich, Alemania).

1. El Problema

El trabajo aborda problemas de optimización de dimensión finita de la forma:
$$\min_{x} f(x) := \frac{1}{2}\langle x, Qx \rangle + \langle q, x \rangle$$
sujeto a:
$$Ax \in C$$
Donde:

• $f(x)$ es una función cuadrática convexa.
• $A$ es una matriz lineal.
• $C$ es un conjunto cerrado y no vacío en $\mathbb{R}^m$, que puede ser no convexo.

Importancia: Este marco generaliza los programas cuadráticos (QP) clásicos. Permite modelar condiciones lógicas, restricciones de cardinalidad y dinámicas no suaves (como en mecánica de contactos o sistemas con conmutación) que surgen en control óptimo, procesamiento de señales y toma de decisiones. El desafío principal es que las técnicas estándar de programación no lineal suelen fallar en puntos factibles interesantes debido a la violación de calificaciones de restricciones en conjuntos no convexos (disyuntivos).

2. Metodología

El enfoque propuesto combina el marco del Método del Lagrangiano Aumentado (AL) con una reformulación de subproblemas que explota la estructura lineal-cuadrática del problema.

• Formulación Lagrangiana Aumentada:
  Se introduce una variable auxiliar $z$ para separar la función objetivo de las restricciones geométricas ($Ax = z, z \in C$). Se define una función de Lagrangiano aumentado que penaliza la violación de la igualdad lineal y añade un término de regularización proximal (Tikhonov) para estabilidad numérica.
  $$\mathcal{L}_\sigma(x, z, \hat{x}, \hat{y}) = \mu f(x) + \frac{1}{2}\|Ax - z + \hat{y}\|^2 + \frac{\rho}{2}\|x - \hat{x}\|^2$$

• Algoritmo Principal (Esquema de Lagrangiano Aumentado):
  Se utiliza un esquema iterativo (Algoritmo 3.1) que resuelve una secuencia de subproblemas hasta alcanzar estacionariedad aproximada. El método incluye un mecanismo de "salvaguarda" (safeguarding) para proyectar los multiplicadores duales en un conjunto compacto, garantizando la convergencia global.

• La Innovación: Técnica de Condensación (Condensing):
  En lugar de resolver el subproblema aumentado en las variables $(x, z)$ simultáneamente (que tiene $n+m$ variables), el autor propone eliminar analíticamente la variable $x$.

  1. Para un $z$ fijo, el subproblema en $x$ es un problema cuadrático sin restricciones (o con restricciones de igualdad "seguras" como dinámicas lineales) que tiene una solución única y cerrada, denotada como $X_k(z)$.
  2. Se define una función marginal $M_k(z) = \min_x \mathcal{L}_\sigma(x, z, \dots)$.
  3. El subproblema se reduce a minimizar $M_k(z)$ sujeto a $z \in C$.

  Ventajas de la condensación:

  • Reduce la dimensión del problema de $n+m$ a $m$ (donde $m$ suele ser menor o igual a $n$, pero la estructura es más simple).
  • Mejora el acondicionamiento del problema.
  • La función marginal $M_k(z)$ es continuamente diferenciable con gradiente Lipschitz, lo que permite el uso eficiente de métodos de primer orden (como gradiente proyectado).
  • Se puede manejar explícitamente restricciones de igualdad "seguras" (ej. dinámicas de control) sin relajarlas, manteniendo la estructura dispersa.

3. Contribuciones Clave

1. Marco Híbrido: Integra las garantías teóricas rigurosas de los métodos de Lagrangiano Aumentado para restricciones no convexas (basados en trabajos previos como [8]) con la eficiencia computacional de la estructura lineal-cuadrática.
2. Técnica de Condensación: Propone una reformulación que reduce el tamaño del subproblema y su mal acondicionamiento, permitiendo resolver problemas más grandes y complejos.
3. Oráculo de Proyección Genérico: El método solo requiere un oráculo de proyección sobre el conjunto $C$ (que puede ser no convexo), sin necesidad de regularizaciones específicas o funciones de penalización diseñadas a mano para cada tipo de restricción.
4. Robustez y Flexibilidad: El esquema es robusto ante restricciones redundantes y maneja naturalmente condiciones lógicas (complementariedad, conmutación, "o bien-o bien") y restricciones de control conmutado.

4. Resultados Numéricos

El artículo evalúa el método en tres benchmarks de control óptimo:

1. Problema de Valor Inicial con Dinámica Discontinua: Un sistema con un solo cambio (switch) reformulado como un sistema de complementariedad lineal.
2. Problema del Obstáculo Discretizado: Un problema de control óptimo con restricciones de desigualdad y complementariedad.
3. Control de Seguimiento AFTI-16: Un modelo de avión con restricciones geométricas no convexas en los controles (condición "o bien-o bien" en los ángulos de elevación y alerones).

Hallazgos principales:

• Rendimiento Superior: La formulación condensada supera consistentemente a la formulación extendida (estándar) en términos de tiempo de ejecución y número de iteraciones.
• Tratamiento de Igualdades: El tratamiento "duro" (hard) de las restricciones de igualdad (dinámicas) dentro de la condensación ofrece los mejores tiempos de ejecución.
• Escalabilidad: El método logra resolver instancias con discretizaciones mucho más finas (ej. $N=256$ en el problema del obstáculo) con tiempos de ejecución razonables, donde métodos anteriores requerían millones de iteraciones internas.
• Comparación de Subsolutores: El uso de panoc+ (con extrapolación cuasi-Newton) generalmente supera a nmpg (gradiente proyectado con paso espectral), aunque la condensación mejora el rendimiento en ambos casos.
• Calidad de Solución: En simulaciones de control en bucle cerrado, el algoritmo encuentra secuencias de control suficientes para guiar el sistema y rechazar perturbaciones, a pesar de la no convexidad del conjunto admisible.

5. Significado e Impacto

Este trabajo es significativo porque cierra la brecha entre la teoría de optimización para restricciones no convexas y la práctica computacional eficiente en control.

• Eficiencia: La técnica de condensación permite aplicar métodos de Lagrangiano Aumentado a problemas de gran escala que antes eran computacionalmente prohibitivos debido al mal acondicionamiento y la alta dimensionalidad.
• Generalidad: Ofrece una herramienta unificada para manejar restricciones complejas (lógicas, de cardinalidad, de contacto) sin necesidad de adaptar el algoritmo a cada caso específico, dependiendo únicamente de la capacidad de proyectar sobre el conjunto $C$.
• Aplicabilidad en Control: Proporciona un método robusto para problemas de control óptimo con dinámicas no suaves y restricciones de conmutación, áreas críticas en robótica, aeronáutica y sistemas de energía.

En resumen, el artículo presenta un algoritmo numérico que combina la solidez teórica de los métodos de penalización con una ingeniería de subproblemas inteligente, logrando aceleraciones significativas y mayor robustez en la resolución de problemas de optimización lineal-cuadrática con restricciones geométricas complejas.