Minimización parcial alternante para resolver la optimización de consenso generalizada

Question

Estoy tratando de resolver el siguiente problema de optimización de consenso generalizado, que es un tipo particular de problema no lineal no convexo:

$$\begin{equation} \tag{P} X^*=\underset{x_i \in \mathcal{X}_i,~ \forall i \in \{0,1,\dots,N\} \\ y \in \mathbb{R}^m}{\text{argmin}}\mkern+05mu \sum_{i=0}^N f_i(x_i) \end{equation}$$ $$\begin{alignat}{2} \text{st. } & \mathcal{X}_i = \left\{x_i \in \mathbb{R}^n \mid \psi(x_i) = 0, ~ \phi(x_i) \leq 0\right\}, \forall i \in \{0,1,\dots,N\}\\ & X - H(y) = 0 \end{alignat}$$ donde $f:\mathbb{R}^n\mapsto\mathbb{R}$ , $h:(\mathbb{R}^m,\mathbb{R}^p)\mapsto\mathbb{R}$ son funciones continuamente diferenciables, $\mathcal{X}$ es un conjunto compacto (posiblemente no convexo). $X=(x_0,x_1,\dots,x_N)$ el vector de optimización que puede escribirse como la concatenación de los subvectores $x_i$ , y de forma similar $H(y)=(h(y,\tau_0),h(y,\tau_1),\dots,h(y,\tau_N))$ .

Hasta ahora, he podido resolver los siguientes problemas: $$\begin{equation} \tag{$ P_i $} x_i^*=\underset{x_i \in \mathcal{X}_i}{\text{argmin}}\mkern+05mu g(x_i) \end{equation}$$ $$\text{st. } \mathcal{X}_i = \left\{x_i \in \mathbb{R}^n \mid \psi(x_i) = 0, ~ \phi(x_i) \leq 0\right\} $$ donde $g:\mathbb{R}^n\mapsto\mathbb{R}$ puede ser cualquier función continuamente diferenciable.

He pasado mucho tiempo leyendo literatura sobre el tema (los libros de Bertsekas, entre otros) y creo que puede ser posible resolverlo de forma iterativa utilizando el siguiente algoritmo: $$ \begin{alignat}{2} x_i^{k+1} &= \underset{x_i \in \mathcal{X}_i}{\text{argmin}}\mkern+05mu \mathcal{L}_\rho(x_0^k,x_1^k,\dots,x_i,\dots,x_N^k,y^k,\Lambda^k), \forall i \in \{0,1,\dots,N\} \\ &= \underset{x_i \in \mathcal{X}_i}{\text{argmin}}\mkern+05mu f_i(x_i) + {\lambda_i^k}^T (x_i-h(y^k,\tau_i)) + \frac{\rho}{2} \left\|x_i-h(y^k,\tau_i)\right\|^2, \forall i \in \{0,1,\dots,N\} \tag{$ A_1^i $} \\ y^{k+1} &= \underset{y \in \mathbb{R}^m}{\text{argmin}}\mkern+05mu \mathcal{L}_\rho(X^{k+1},y,\Lambda^k) \\ &= \underset{y \in \mathbb{R}^m}{\text{argmin}}\mkern+05mu {\Lambda^k}^T (X^{k+1}-H(y)) + \frac{\rho}{2} \left\|X^{k+1}-H(y)\right\|^2 \tag{$ A_2 $} \\ \Lambda^{k+1} &= \Lambda^k + \rho (X^{k+1}-H(y^{k+1})) \end{alignat} $$ donde $\Lambda=(\lambda_0,\lambda_1,\dots,\lambda_N)$ y $\mathcal{L}_\rho(X,y,\Lambda) = \sum_{i=0}^N f_i(x_i) + \Lambda^T (X-H(y)) + \frac{\rho}{2} \left\|X-H(y)\right\|^2$ .

Ahora soy capaz de realizar este algoritmo iterativo en la práctica. Corresponde al ADMM aplicado a un problema no lineal no convexo con restricciones de acoplamiento no lineales no convexas. Lamentablemente, no he encontrado ningún teorema de convergencia sobre el ADMM en este contexto. Me gustaría demostrar la convergencia de este algoritmo para $\rho$ "suficientemente grande", ni al menos que cualquier secuencia convergente $\left\{X^k,y^k,\Lambda^k\right\}_{k=0}^\infty$ converge a un mínimo local del problema original $P$ .

He intentado combinar varios métodos y teoremas, entre ellos los métodos de penalización exacta basados en el lagrangiano aumentado, el método del lagrangiano aumentado parcial, el método de bloques de Gauss-Seidel, el método de descenso de coordenadas cíclicas, los métodos de minización alternante proximal e incluso el teorema de convergencia global de Zangwill, muy general. Parece que siempre hay alguna suposición que no se cumple en mi caso. Un trabajo relacionado muy similar a lo que estoy tratando de hacer es Sobre la convergencia de los métodos lagrangianos de dirección alterna... . Aunque las demostraciones se realizan utilizando restricciones de acoplamiento lineal, creo que es bastante sencillo adaptarlas para demostrar que si converge, converge a un mínimo local del problema original $P$ pero no se puede utilizar para demostrar la convergencia.

He observado que la función objetivo de los subproblemas $A_1^i$ es fuertemente convexo, y que $A_2^i$ puede convertirse en un problema de optimización estrictamente convexo utilizando la regulación de Moreau-Yosida wrt. $y^k$ o simplemente añadiendo la penalización cuádrica $\gamma\left\|y\right\|^2$ siempre que $\gamma$ es lo suficientemente grande. Por lo tanto, cada uno de los subproblemas $A_1^i$ y $A_2$ tienen un minimizador único, y por lo que sé es suficiente para demostrar que el algoritmo siempre converge y converge a un mínimo local del problema original. No sé si estoy en lo cierto y me gustaría saber si es posible demostrar algo sin modificar el algoritmo.

Answer 1

Creo que he conseguido probar la convergencia. El problema original se puede reescribir como sigue: $$ \begin{equation} \tag{P} X^*=\underset{x_i \in \mathcal{X}_i,~ \forall i \in \{0,1,\dots,N\} \\ z \in \mathcal{Z}}{\text{argmin}}\mkern+05mu \sum_{i=0}^N f_i(x_i) \end{equation} $$ $$ \begin{alignat}{2} \text{st. } & \mathcal{X}_i = \left\{x_i \in \mathcal{D}_x \mid \psi(x_i) = 0, ~ \phi(x_i) \leq 0\right\}, \forall i \in \{0,1,\dots,N\}\\ & \mathcal{Z} = \left\{z \in \mathcal{D}_z \mid \exists y \in \mathbb{R}^m s.t. Z-H(y)=0 \right\}=\left\{z \in \mathbb{R}^n \mid \text{dist}(Z,H)=0 \right\}\\ & X - Z = 0 \end{alignat} $$ donde $\mathcal{D}_x \subset \mathbb{R}_n, \mathcal{D}_z \subset \mathbb{R}_m$ son conjuntos compactos, y $h$ , $\psi$ , $\phi$ son dos veces continuamente diferenciables.

Sobre la base de esa formulación, las restricciones de acoplamiento son ahora lineales y el teorema principal de Sobre la convergencia de los métodos lagrangianos de dirección alterna.... puede aplicarse directamente. Mi intuición era la correcta aunque olvidé mencionar ese problema $A_2$ es fuertemente convexo wrt. $Z=H(y)$ y que $y$ nunca aparece directamente, sino sólo $H(y)$ . Después de la convergencia, $y^*$ se puede calcular resolviendo: $$ y^*= \underset{y \in \mathbb{R}^m}{\text{argmin}}\mkern+05mu \left\|X^* - H(y) \right\|^2 $$ Este problema es no convexo pero existe al menos una solución tal que $\left\|X^* - H(y) \right\|^2 = 0$ .