Descenso por gradiente con restricción esférica y simplex

Question

He estado trabajando en un problema con una restricción esférica y otra de normalización.

Para ser precisos tengo una función $\mathrm{H}(X_{i})$ y el $X_{i}$ son las variables que deseo optimizar. Las restricciones son

\begin{equation} \sum_{i=1}^{N} X_{i}^2 = 1 \qquad \sum_{i=1}^{N} X_{i} = m \end{equation}

He probado el método de los multiplicadores de Lagrange para construir la función $\mathrm{H}'$ de la siguiente forma:

\begin{equation} \mathrm{H}' = H + \nu_{1}(\sum_{i=1}^{N} X_{i}^2 - 1) + \nu_{2} (\sum_{i=1}^{N} X_{i} - m) \end{equation} .

Sin embargo, por alguna razón que no he podido averiguar esto no parece funcionar numéricamente. (Puedo calcular $\nu_{1}$ y $\nu_{2}$ analíticamente. Esto es lo que inyecté en la rutina final de descenso de gradiente).

Tras el respuesta aquí, me preguntaba si se podría hacer algo similar para la restricción de normalización anterior. He probado el siguiente procedimiento:

1. Calcular el gradiente de la función $\mathrm{H}$ es decir, sin las restricciones. A continuación, siga el enlace anterior. Esto fija la restricción esférica.

2. A continuación, "reproyecte" la nueva variable $X_{i}(t+\Delta t)$ en el plano definido por $\sum_{i}^{N} X_{i} = m$ .

Para el último paso, elegí un vector $((1-m)/N, ... (1-m)/N)$ y luego realizó operaciones estándar de álgebra lineal para proyectar $X_{i}(t+\Delta t)$ .

Sin embargo, esto no parece funcionar demasiado bien en la práctica: El gradiente disminuye y también lo hace la función $\mathrm{H}$ . La restricción esférica también se cumple. Sin embargo, la restricción de normalización no lo es.

¿Alguna sugerencia/idea/referencia para este problema? He buscado en la web problemas de este tipo. La restricción esférica parece bastante estándar, pero la otra no parece darse en muchos sitios. No he visto ninguna referencia que trate las dos juntas. Gracias.

Answer 1

En primer lugar, la solución general de "fuerza bruta" de hacer el descenso de gradiente proyectado debería funcionar:

1. Calcular el gradiente sin restricciones $\nabla H$ ;
2. Proyectar el gradiente sobre el espacio tangente de las restricciones (opcional pero puede reducir la dificultad numérica del siguiente paso). En otras palabras, resolver el subproblema $$\min_{v} \|v-\nabla H\|^2 \quad \mathrm{s.t}\quad 2X \cdot v = 0; \mathbf{1}\cdot v = 0.$$
3. Da un paso $X \leftarrow X + v$ .
4. Proyectar de nuevo sobre la superficie de la restricción: resolver $$\min_{\tilde X} \|X-\tilde X\|^2 \quad \mathrm{s.t.} \quad \|\tilde X\|^2=1; \tilde X\cdot \mathbf{1} = m$$ utilizando, por ejemplo, el método de Newton.

En la pregunta que has enlazado, han utilizado el hecho de que la esfera tiene un mapa exponencial de forma cerrada para simplificar sustancialmente el paso 4: calculan una posición $\tilde X$ directamente en la esfera sin necesidad de pisar + proyectar.

Por lo general, el conjunto de restricciones es demasiado complejo para permitir este tipo de trucos. Sin embargo, en tu caso, fíjate en que la colector de restricciones es la intersección de una esfera y un plano, por ejemplo, es una esfera de dimensión $N-1$ y, por tanto, es posible escribir una representación reducida del conjunto de todos los puntos factibles. En particular, dejemos que $v_1,\ldots,v_{n-1}$ sea una terminación de una base ortonormal para $\mathbb{R}^N$ junto con $\mathbf{1}/\sqrt{N}.$ Entonces todos los puntos que satisfacen sus restricciones son de la forma $$X = \frac{m}{N}\mathbf{1} + \sum_{i=1}^{n-1} \alpha_iv_i$$ con $\|\alpha\|^2 = 1-\frac{m^2}{N^2}.$

Por lo tanto, se puede realizar el descenso de gradiente directamente en $h(\alpha) = H \circ X$ utilizando la técnica del post enlazado, y evitar tener que lidiar con las restricciones en absoluto.