¿Por qué actualiza el estándar BFGS determinación positiva de preservar la regla?

Question

Mi clase ha aprendido recientemente el método BFGS para optimización sin restricciones. En este procedimiento, tenemos una actualización de la fila 1 de una matriz definida positiva a cada paso.

Esto se especifica como:

$H_{k+1} = H_k + \frac{\eta\eta^T}{\delta^T\eta}-\frac{H_k\delta\delta^TH_k^T}{\delta^TH_k\delta}$

$\forall \eta, \delta \in \mathbb{R}^n$.

Muestran que para cualquier matriz definida positiva simétrica $Hk,$ tenemos que $H{k+1}$el % es positiva definida tanto como $\delta^T\eta > 0$. No supongas nada de $H_k$ aparte de que es simétrico p.d.

Answer 1

$\def\skp#1{\left}$ $H_k$ Es spd, el % de forma $(x,y) \mapsto \skp{x,y}_k := x^tH_ky$define un producto escalar. De Cauchy-Schwarz tenemos \ [\skp{x,y}_k^2 \le \skp{x,x}_k\skp{y,y}k ] cualquier $x,y \in \mathbb R^n$ y con la desigualdad terminante si $x$ y $y$ no lineal dependiente. Ahora que $x \in \mathbb R^n\setminus {0}$, entonces \begin{align*} \skp{x,x}{k+1} &= x^tH_{k+1}x\ &= x^tH_k x + x^t\frac{\eta\eta^t}{\delta^t\eta}x - x^t\frac{H_k\delta\delta^tH_k^t}{\delta^tH_k\delta}x\ &= \skp{x,x}_k + \frac 1{\delta^t\eta}x^t\eta\eta^tx - \frac 1{\skp{\delta, \delta}_k}\skp{x,\delta}_k\skp{\delta, x}_k\ &= \skp{x,x}_k + \frac 1{\delta^t\eta}(x^t\eta)^2 - \frac 1{\skp{\delta, \delta}_k}\skp{x,\delta}k^2\ \end{align} si ahora $x$ y $\delta$ no dependiente linear, entonces podemos estimar aún más usando Cauchy-Schwarz:\begin{align} \skp{x,x}{k+1} &> \skp{x,x}_k + 0 - \frac 1{\skp{\delta,\delta}_k}\skp{x,x}_k\skp{\delta,\delta}k\ &= 0. \end{align} de otra manera, si, decir $x = \lambda\delta$, entonces el $x^t\eta = \lambda \delta^t\eta \ne 0$ y, por tanto\begin{align} \skp{x,x}{k+1} &= \skp{x,x}_k + \frac 1{\delta^t\eta}(x^t\eta)^2 - \frac 1{\skp{\delta,\delta}_k}\skp{x,x}_k\skp{\delta,\delta}k\ &= \frac 1{\delta^t\eta}(x^t\eta)^2\ &> 0. \end{align*} $\skp{x,x}{k+1} > 0$ $x \ne 0$ y $H_{k+1}$ es positiva definida.

Answer 2

Sabemos que $H_k$ es definida positiva simétrica (SPD).

Para cualquier vector $v$, es fácil demostrar que $vv^T$ es semidefinite positivo simétrica (SPSD).

Así $\eta\eta^T$ es SPSD. Se da que $\delta^T\eta$ es positivo, por lo que es de $(\eta\eta^T)/(\delta^T\eta)$ SPSD.

$H_k\delta\delta^TH_k^T = (H_k\delta)(H_k\delta)^T$ es de la forma $vv^T$, por lo que también es SPSD. Porque $H_k$ es SPD, $\delta^TH_k\delta$ es positiva. Así $(H_k\delta\delta^TH_k^T)/(\delta^TH_k\delta)$ es SPSD.

Ahora $H_{k+1}$ es la suma de una matriz SPD y dos matrices de la SPSD, así que también es SPD.