Cómo resolver la minimización de la matriz para actualizar optimización quasi-Newton BFGS

Question

Estoy interesado en la obtención de la solución única para el siguiente Cuasi-Newton problema de minimización $$ \min_{H}|| H-H_k||\\ H=H^\la parte superior,\quad Hy_k =s_k $ De$ la norma es la ponderación de la norma de Frobenius $$ ||A||_W \equiv ||W^{1/2}W^{1/2}||_F $$where the weight matrix $W$ is any positive definite matrix that satisfies $Ws_k=y_k$, and $||\cdot||_F$ is defined by $||C||^2_F= \sum_{i,j}^n c^2_{ij}$. The quantity $H$ is the inverse hessian which is symmetric, positive definite and satisfies the secant equation above, $Hy_k=s_k$. We can assume that $W=G^{-1}_k $ where $G_k$ el promedio de hesse está dada por $$ G_k= \int_0^1 \nabla^2 f(x_k+\tau \alpha_k p_k)d\tau $$ La única solución está dada por $$ H_{k+1} = (1-\rho_k s_k y^\top_k)H_k (1-\rho_k y_k s^\top_k)+ \rho_k s_k s^\top_k $$ where $\rho_k = (y^\top_k s_k)^{-1}$. Note, this is an iterative scheme where $k$ represents the current iteration and $H_{k+1}$ es una aproximación a la inversa de hess.

La notación que estoy usando es directamente desde el libro Nocedal & Wright - Optimización Numérica. Yo no soy capaz de encontrar un total de derivación de este lugar, todo lo escrito anteriormente es todo lo que Nocedal/Wright tiene en cuanto a este tema. Para una referencia, esto es en el capítulo 6 - Cuasi Newton Métodos, de su más reciente, 2ª edición.

Todos los enlaces que he tratado de google y otros libros también tienen ninguna derivación. Yo no soy capaz de encontrar nada más minucioso que el Nocedal & Wright, sin embargo, que todavía no tienen una derivación. Gracias

Answer 1

Voy a esbozar los pasos principales. Ver las explicaciones y las respuestas a los comentarios de abajo.

1. Introducir algunas notaciones $$ \hat H=W^{1/2}HW^{1/2},\quad \hat H_k=W^{1/2}H_kW^{1/2},\quad \hat s_k=W^{1/2}s_k,\quad \hat y_k=W^{-1/2}y_k.\la etiqueta{1} $$ Entonces el problema se convierte en $$ \min\|\sombrero H_k-\hat H\|_F\quad\text{objeto }\hat H\hat y_k=\hat y_k\ (=\hat s_k). $$
2. Usar el hecho de que $\hat y_k$ es el vector propio de a $\hat H$, vamos a presentar la nueva base ortonormales $$ U=[u\ |\ u_\bot] $$ donde $u$ es la normalizado $\hat y_k$, es decir, $$u=\frac{\hat y_k}{\|\hat y_k\|}\tag{2},$$ and $u_\bot$ is any ON-complement to $u$. Dado que la norma de Frobenius es unitaria invariante (como lo es la suma de los cuadrados de los valores singulares) tenemos $$ \|\sombrero H_k-\hat H\|_F=\|U^T\hat H_kU-U^T\hat HU\|_F= \left\|\begin{bmatrix}\color{blue}* & \color{blue}*\\\color{blue}* & \color{red}*\end{bmatrix}\begin{bmatrix}\color{blue}1 & \color{blue}0\\\color{blue}0 & \color{red}*\end-{bmatrix}\right\|_F. $$ La parte azul no puede ser afectado por la optimización, y para minimizar la norma de Frobenius, es claro que debemos hacer la parte roja llegara a cero, es decir, la solución óptima satisface $$ \color{red}{u_\bot^T\hat Hu_\bot}=\color{red}{u_\bot^T\hat H_ku_\bot}. $$ Se da la solución óptima para el ser $$ \hat H=U\begin{bmatrix}\color{blue}1 & \color{blue}0\\\color{blue}0 & \color{red}{u_\bot^T\hat H_ku_\bot}\end{bmatrix}U^T. $$
3. Para escribir de una forma más explícita $$ \hat H=\begin{bmatrix}u & u_\bot\end{bmatrix}\begin{bmatrix}1 & 0\\0 & u_\bot^T\hat H_ku_\bot\end{bmatrix}\begin{bmatrix}u^T \\ u_\bot^T\end{bmatrix}=uu^T+u_\bot u_\bot^T\hat H_ku_\bot u_\bot^T= uu^T+(I-uu^T)\hat H_k(I-uu^T) $$ donde hemos utilizado la siguiente representación de la proyección del operador para el complemento de $u$ $$ u_\bot u_\bot^T=I-uu^T. $$
4. Variables que cambian de nuevo a la original (1), (2) es sencillo.

---

Explicaciones:

Paso 1. La conveniencia de que la $\hat H$ $\hat H_k$ proviene directamente del problema $$ \min\|\underbrace{W^{1/2}H_kW^{1/2}}_{\hat H_k}-\underbrace{W^{1/2}HW^{1/2}}_{\hat H}\|_F. $$ Entonces tenemos que reescribir los datos \begin{align} Hy_k=s_k\quad&\Leftrightarrow\quad \underbrace{\color{blue}{W^{1/2}}H\color{red}{W^{1/2}}}_{\hat H}\underbrace{\color{red}{W^{-1/2}}y_k}_{\hat y_k}=\underbrace{\color{blue}{W^{1/2}}s_k}_{\hat s_k},\\ Ws_k=y_k\quad&\Leftrightarrow\quad \underbrace{\color{red}{W^{-1/2}}Ws_k}_{\hat s_k}=\underbrace{\color{red}{W^{-1/2}}y_k}_{\hat y_k}. \end{align} Por lo tanto, $\hat H\hat y_k=\hat y_k$. También es igual a $\hat s_k$.

Paso 2. Desde $\hat Hu=u$ sabemos que $u^T\hat Hu=u^Tu=1$$u_\bot^THu=u_\bot^Tu=0$, por lo que podemos representar la optimización de la variable como $$ U^T\hat HU=\begin{bmatrix}u^T\\ u_\bot^T\end{bmatrix}\hat H\begin{bmatrix}u & u_\bot\end{bmatrix}= \begin{bmatrix}u^T\hat Hu & u^T\hat Hu_\bot\\u_\bot^T\hat Hu & u_\bot^T\hat Hu_\bot\end{bmatrix}= \begin{bmatrix}1 & 0\\0 & u_\bot^T\hat Hu_\bot\end{bmatrix}. $$ Se da la siguiente \begin{align} U^T\hat H_kU-U^T\hat HU&=\begin{bmatrix}u^T\\ u_\bot^T\end{bmatrix}\hat H_k\begin{bmatrix}u & u_\bot\end{bmatrix}\begin{bmatrix}u^T\\ u_\bot^T\end-{bmatrix}\hat H\begin{bmatrix}u & u_\bot\end{bmatrix}=\\ y=\begin{bmatrix}\color{blue}{u^T\hat H_ku} & \color{blue}{u^T\hat H_ku_\bot}\\\color{blue}{u_\bot^T\hat H_ku} & \color{red}{u_\bot^T\hat H_ku_\bot}\end{bmatrix}\begin{bmatrix}\color{blue}{1} & \color{blue}{0}\\\color{blue}{0} & \color{red}{u_\bot^T\hat Hu_\bot}\end-{bmatrix}. \end{align} Esta particular estructura de la optimización de la variable fue la idea de cambiar a la nueva base. Debido a $\hat H$ no tiene la libertad para variar en la parte azul, no podemos cambiar la correspondiente parte azul de $\hat H_k$, por lo que es fijo para todos los posibles $\hat H$. La parte roja, aunque puede ser cambiado como deseamos, y el más pequeño de la norma de Frobenius \begin{align} \|U^T(\hat H_k-\hat H)U\|_F^2&= \left\|\begin{bmatrix}\color{blue}{u^T\hat H_ku-1} & \color{blue}{u^T\hat H_ku_\bot}\\\color{blue}{u_\bot^T\hat H_ku} & \color{red}{u_\bot^T\hat H_ku_\bot-u_\bot^T\hat Hu_\bot}\end{bmatrix}\right\|_F^2=\\ &=\color{blue}{(u^T\hat H_ku-1)^2+\|u^T\hat H_ku_\bot\|_F^2+\|u_\bot^T\hat H_ku\|_F^2}+\color{red}{\|u_\bot^T\hat H_ku_\bot-u_\bot^T\hat Hu_\bot\|_F^2} \end{align} se obtiene cuando la parte roja es cero.

Paso 3. La matriz $U$ es ortogonal, por lo tanto, $$ I=UU^T=\begin{bmatrix}u & u_\bot\end{bmatrix}\begin{bmatrix}u^T \\ u_\bot^T\end{bmatrix}=uu^T+u_\bot u_\bot^T\quad\Leftrightarrow\quad u_\bot u_\bot^T=I-uu^T. $$