Impacto de las restricciones en la optimización convexa

Question

Permítanme empezar diciendo que no sé casi nada de optimización, así que les ruego que me tengan paciencia. Básicamente, me pregunto si es posible resolver un problema con dos restricciones resolviendo el problema con cada restricción individualmente y combinando de alguna manera las soluciones. Sin embargo, estoy teniendo problemas para visualizar el escenario. Más concretamente:

Supongamos que $V$ es un espacio de Banach y $f:V \to \mathbb{R}$ es convexa y continua. Además, sea $K_1, K_2 \subset V$ sea convexa y consideremos las soluciones $x_i$ de los problemas de optimización $$\quad \min_{x \in K_i} f(x).$$

Para $K = K_1 \cap K_2$ deje $x$ resolver $$\min_{x \in K} f(x).$$

• Es $x$ la proyección de $x_1$ en $K_2$ ?
• Es $x$ una combinación lineal de $x_1$ y $x_2$ ?
• ¿Existen relaciones entre $x$ , $x_1$ y $x_2$ ¿en absoluto?
• ¿Cambia la situación si restringimos aún más $f$ ? ¿Por ejemplo ser cuadrático?

Muchas gracias de antemano.

Answer 1

Para los conjuntos convexos generales, el tipo de relaciones simples que sugieres no existen. A mí me resulta útil hacer dibujos bidimensionales para ver por qué. (Incluso si el espacio es de dimensión superior a 2, podríamos restringir los problemas al plano abarcado por $x_1,x_2,x$ y ninguna de las respuestas a tus preguntas cambiaría). He aquí un ejemplo de lo que puede ocurrir incluso en el caso sencillo de que $f$ es lineal:

La flecha roja es la dirección del gradiente negativo de $f$ . Minimizar $f$ significa avanzar todo lo posible en esa dirección. Para responder a sus preguntas concretas:

• No. En este caso, la proyección de $x_2$ en $K_1$ no está en $K_2$ por lo que no puede ser igual a $x$ . La proyección de $x_1$ en $K_2$ está en $K$ pero aún no es igual a $x$
• El origen no está representado en el diagrama, pero si $x_1$ y $x_2$ son colineales con el origen, entonces $x$ no es una combinación lineal de $x_1$ , $x_2$ .
• La única relación fácil y sencilla es que $f(x_1) \le f(x)$ y $f(x_2) \le f(x)$ .
• En este ejemplo, la función es lineal. Es lo más sencillo que se puede hacer sin que el problema sea trivial.

Dicho esto, hay métodos (como el ADMM) que pueden utilizar solucionadores de subproblemas para converger a la solución de un problema mayor.