¿Son equivalentes estos problemas de optimización convexa?

Question

Consideremos el problema de optimización $$ \mathcal{P}_1: \qquad \min_{x \in \mathbb{R}^n} c^\top x \quad \text{sub. to } \ g(x,y_i) \leq 0 \ \ \forall i = 1,2,...,M$$

donde $c \in \mathbb{R}^n$ y $g:\mathbb{R}^n \times \mathbb{R}^m \rightarrow \mathbb{R}$ (de valor escalar) es tal que para todo $y \in \mathbb{R}^m$ el mapa $g(\cdot,y)$ es convexo, y para todo $x \in \mathbb{R}^n$ el mapa $g(x,\cdot)$ también es convexo.

Denota por $x^*$ un optimizador de $\mathcal{P}_1$ .

Dados los vectores $\{y_1,...,y_M\}$ de $\mathcal{P}_1$ definan el conjunto $$\mathcal{F} := \{ (F,f) \in \mathbb{R}^{1 \times m} \times \mathbb{R} \mid F y_i \leq f \ \ \forall i = 1,...,M \} = \{ (F,f) \in \mathbb{R}^{1 \times m} \times \mathbb{R} \mid \max_{i \in [1,M]} F y_i \leq f \}.$$

Para un determinado $(\bar{F},\bar{f}) \in \mathcal{F}$ Consideremos el problema de optimización $$ \mathcal{P}_2(\bar{F},\bar{f}): \qquad \min_{x\in \mathbb{R}^n } c^\top x \quad \text{sub. to } \ g(x,y) \leq 0 \ \ \forall y \in \{ z \in \mathbb{R}^m \mid \bar{F} z\leq \bar{f} \}.$$

Denota por $X_{(\bar{F},\bar{f})}^*$ el conjunto de optimizadores de $\mathcal{P}_2(\bar{F},\bar{f})$ .

Digamos que si se da un optimizador $x^*$ siempre existe una pareja $({F}^*,{f}^*)$ tal que $x^* \in X_{({F}^*,{f}^*)}^*$ .

Comentario. La idea es aprovechar la convexidad de $g(x,\cdot)$ para afirmar que siempre podemos considerar un medio plano en el peor de los casos $\{y \in \mathbb{R}^m \mid F^* y \leq f^*\}$ .

El caso lineal es aquí .

Answer 1

No creo que los problemas sean equivalentes. Sé que $$g(x,y_i)\leq 0, ~i=1,2,\dots,M \quad\Longrightarrow\quad g(x,y)\leq 0 ~ \forall y\in\mathcal{Y}$$ donde $\mathcal{Y}$ es el casco convexo de los puntos $y_i$ . Esto se deduce de la convexidad de $g$ en $y$ y no requiere convexidad conjunta. Por lo tanto, si se sustituye el semiplano por $\mathcal{Y}$ , tendrías una equivalencia.

Pero cualquiera de los semiplanos descritos por $\mathcal{F}$ contiene $\mathcal{Y}$ y es mayor que $\mathcal{Y}$ . Por lo tanto, hay puntos en el semiplano que podrían obtener $g(x,y)>0$ en el primer modelo, pero no en el segundo. Por lo tanto, el segundo modelo tiene un conjunto de restricciones más restrictivo y arrojaría un valor objetivo más alto.

EDIT: Sin una comprensión más completa de la propósito detrás de sus esfuerzos, es difícil saber cuál es el enfoque correcto. Supongo que hay una razón por la que no quieres resolver el problema en la forma originalmente planteada: es decir, con $M$ restricciones, una para cada punto $y_i$ .

Pero supongamos que se puede describir eficientemente el casco convexo $\mathcal{Y}$ en términos de un conjunto de desigualdades $Fy\leq f$ , donde $F$ es una matriz y $f$ es un vector. Entonces podrías reescribir tus restricciones: $$g(x,y) \leq 0 \quad \forall F y \leq y\quad\Longrightarrow\quad \sup_{y:~Fy\leq y} g(x,y) \leq 0$$ Para los fijos $y$ El $\sup$ es un problema de optimización convexo en $y$ . Una cosa que puedes considerar es encontrar el doble de este subproblema convexo. Este dual será una minimización en algunas variables $z$ . El resultado preciso depende de la naturaleza exacta de $g$ pero es muy posible que pueda reescribir su problema original como una minimización conjunta en $x$ y $z$ .