آشنایی با روش‌های بهینه‌سازی نامقید (4)
سه شنبه, ۱۵ تیر ۱۳۹۵، ۰۴:۱۹ ق.ظ
در آموزش‌های قبل با برخی از روش‌های کمینه‌سازی نامقید آشنا شدیم. در این قسمت به معرفی روش‌های شبه‌نیوتن می‌پردازیم که برای رفع اشکالات روش نیوتن معرفی شده‌اند. انگیزه‌ی اصلی طرح روش‌های شبه‌نیوتن دست‌یابی به همگرایی سریع روش نیوتن حداقل به‌طور میانگین است بدون آن‌که نیاز به محاسبه‌ی ماتریس هسین و وارون آن در هر گام باشد. این کار با به‌دست آوردن تقریب‌هایی برای وارون هسین بر اساس اطلاعات جمع‌آوری شده در فرآیند کاهشی انجام میشود و روش‌هایی که از این طریق بدست می‌آیند عموماً دارای همگرایی فوق‌خطی می‌باشند.
تاریخچه‌ی کوتاهی از روش‌های شبه‌نیوتن
در اواسط دهه‌ی 1950 دیویدان، فیزیکدان شاغل در آزمایشگاه ملی آرگون، روش کاهش مختصاتی را برای انجام محاسبات بهینه‌سازی به کار می‌برد. در آن زمان دستگاه‌های کامپیوتری از توانایی محاسباتی بالایی برخوردار نبودند. بنابراین دیویدان تصمیم گرفت راهی پیدا کند که فرآیند تکرار الگوریتم را بهبود بخشد. الگوریتم او اولین الگوریتم شبه‌نیوتن بود که انقلابی در بهینه‌سازی غیرخطی ایجاد کرد. دیری نپایید که توسط فلچر و پاول ثابت شد که این الگوریتم جدید بسیار سریع‌تر و قابل اطمینان‌تر از دیگر روش‌های موجود آن زمان است و این پیشرفت به‌طور چشمگیری بهینه‌سازی غیرخطی را دگرگون کرد. در طول بیست سال بعد الگوریتم‌های شبه‌نیوتن متعددی مطرح و در صدها مقاله به مطالعه‌ی آن‌ها پرداخته شد. حکایت تاریخی جالبی که در این زمینه وجود دارد آن است که، مقاله‌ی دیویدان حدود 30 سال و به بهانه‌ی این‌که صرفاً گزارشی فنی است برای انتشار پذیرفته نشد تا این‌که سرانجام در سال 1991 در مجله‌ی بهینه‌سازی $SIAM$ به چاپ رسید.
همان‌گونه که گفته شد پس از معرفی اولین روش شبه‌نیوتن توسط دیویدان، فلچر و پاول (1963) که به الگوریتم $DFP$ معروف است، الگوریتم‌های شبه‌نیوتن متعددی مطرح شدند. ابتدا روش تصحیح رتبه یک ($SR1$) به وسیله‌ی دیویدان و برویدن (1967) عرضه شد و سپس روش $BFGS$ را برویدن، فلچر، گلدفارب و شانو در سال 1970 مستقل از یکدیگر معرفی کردند. ادبیات موضوع نشان می‌دهد که این الگوریتم به‌عنوان مؤثرترین الگوریتم به‌هنگام‌سازی در مسائل نامقید پذیرفته شده است. روش خانواده‌ی برویدن در سال 1970 توسط برویدن مطرح شد. این روش که از ترکیب محدب دو روش $DFP$ و $BFGS$ حاصل میشود به صورت زیر است:
$${{H}_{k}}\left( B \right)={{\varphi }_{k}}{{H}_{BFGS}}+\left( 1-{{\varphi }_{k}} \right){{H}_{DFP}},~~~~~~~0\le {{\varphi }_{k}}\le 1,$$ یک روش برویدن بنا به تعریف روشی است که در هر تکرار آن یکی از اعضای خانواده‌ی برویدن به عنوان تقریب معکوس هسین در نظر گرفته میشود. ابتدا کوشش‌های فراوانی برای یافتن بهترین دنباله‌ی ${{\varphi }_{k}}$ها در یک روش برویدن انجام شد تا این‌که سرانجام دیکسون در سال 1972 نشان داد که همه‌ی روش‌ها در حالت جستجوی خطی دقیق معادل یک‌دیگرند.
رده‌ی دیگری از روش‌های شبه‌نیوتن که محبوبیت خاصی در میان محققان پیدا کرده‌اند، روش‌های $LBFGS$ یا روش‌های $BFGS$ حافظه‌محدود هستند که الگوریتم $BFGS$ را با استفاده‌ی حداقلی از حافظه‌ی کامپیوتر برای مسائل در مقیاس بزرگ تقریب می‌کنند. نخستین الگوریتم $LBFGS$ را نوسدال در سال 1980 برای حل عددی مسائل بهینه‌سازی نامقید در ابعاد بزرگ ارائه داد.
ایده‌ی کلی روش‌های شبه‌نیوتن
همان‌طور که قبلاً گفته شد، روش نیوتن دو عیب اساسی دارد؛ اولین عیب این روش آن است که اگر تعداد متغیر‌های تابع هدف زیاد باشد به دست آوردن و معکوس کردن ماتریس هسین تابع، که در هر گام این روش انجام میشود، مستلزم محاسباتی سنگین است. عیب دوم این روش آن است که برای یک تابع هدف کلی همگرایی آن به جواب نمی‌تواند با شروع از هر نقطه‌ی ${{x}_{0}}$ تضمین شود. در حقیقت اگر نقطه‌ی شروع به اندازه‌ی کافی به جواب نزدیک نباشد ماتریس هسین ممکن است معین مثبت نباشد و الگوریتم خاصیت کاهشی را حفظ نکند.
روش‌های شبه‌نیوتن برای رفع مشکلات روش نیوتن طراحی شده‌اند و جانشین مناسبی برای آن هستند. از آن‌جا که این روش‌ها تنها از اطلاعات تابع هدف و مشتقات اول آن استفاده می‌کنند در آن‌ها نیازی به محاسبه‌ی وارون ماتریس هسین و ذخیره‌سازی آن نیست. هم‌چنین این روش‌ها معمولاً دارای همگرایی فوق‌خطی هستند که از این نظر بینابین روش تندترین کاهش و نیوتن قرار دارند.
ایده‌ی کلی روش‌های شبه‌نیوتن این است که به جای محاسبه‌ی مستقیم ماتریس هسین، ${{\nabla }^{2}}f$، یک تقریب ${{B}_{k}}$ در تکرار $k$ام محاسبه و این تقریب در هر گام به‌هنگام شود. ما در این‌جا شرطی را بیان می‌کنیم که دنباله‌ی تقریب‌های $\left\{ {{B}_{k}} \right\}$ در آن صدق می‌کنند و این شرط نقطه‌ی شروع بحث ما در روش‌های شبه‌نیوتن خواهد بود.
فرض کنید $f:{{\mathbb{R}}^{n}}\to \mathbb{R}$ تابعی دوبار به‌طور پیوسته مشتق‌پذیر باشد. با استفاده از قضیه‌ی تیلور داریم:$$\begin{align}
\nabla f\left( {{x}_{k}}+p \right)& =\nabla f\left( {{x}_{k}} \right)+{\int_0^1 }{{\nabla }^{2}}f\left( {{x}_{k}}+tp \right)pdt\\& =\nabla f\left( {{x}_{k}} \right)+{{\nabla }^{2}}f\left( {{x}_{k}} \right)p+{\int_0^1 }\left[ {{\nabla }^{2}}f\left( {{x}_{k}}+tp \right)-{{\nabla }^{2}}f\left( {{x}_{k}} \right) \right]~pdt.
\end{align}$$ از آن‌جا که $\nabla f$ تابعی پیوسته است انتگرال سمت راست آخرین تساوی هم‌مرتبه با $o\left( p \right)$ است. لذا اگر قرار دهیم ${{p}_{k}}={{x}_{k+1}}-{{x}_{k}}$، آن‌گاه:
$$\nabla {{f}_{k+1}}=\nabla {{f}_{k}}+{{\nabla }^{2}}{{f}_{k}}\left( {{x}_{k+1}}-{{x}_{k}} \right)+o\left( {{x}_{k+1}}-{{x}_{k}} \right),$$ و بنابراین برای ${{x}_{k}}$ و ${{x}_{k+1}}$ های نزدیک به‌هم می‌توانیم بنویسیم:
$${{\nabla }^{2}}{{f}_{k}}\left( {{x}_{k+1}}-{{x}_{k}} \right)\simeq \nabla {{f}_{k+1}}-\nabla {{f}_{k}}~,$$ توجه کنید که اگر $f$ تابعی درجه دوم باشد آن‌گاه به‌وضوح رابطه‌ی فوق به‌صورت تساوی برقرار است. اکنون تقریب جدید ماتریس هسین (${{B}_{k+1}}$ ) را به‌گونه‌ای انتخاب می‌کنیم که در رابطه‌ی زیر صدق کند:
$${{B}_{k+1}}\left( {{x}_{k+1}}-{{x}_{k}} \right)=\nabla {{f}_{k+1}}-\nabla {{f}_{k}}~,$$ به‌عبارت دیگر، چنانچه قرار دهیم ${{s}_{k}}={{x}_{k+1}}-{{x}_{k}}$ و ${{y}_{k}}=\nabla {{f}_{k+1}}-\nabla {{f}_{k}}$ در این‌صورت ${{B}_{k+1}}$ را چنان تعیین می‌کنیم که در معادله‌ی شبه‌نیوتن زیر صدق کند:$${{B}_{k+1}}{{s}_{k}}={{y}_{k}}$$این معادله به معادله‌ی سکانت موسوم است.
چون ${{B}_{k+1}}$ تقریب ماتریس هسین است طبیعی است که انتظار داشته باشیم متقارن باشد. البته شرایط دیگری نیز روی ${{B}_{k+1}}$ اعمال میشود از جمله این‌که معین مثبت باشد و تفاضل ${{B}_{k}}$ و ${{B}_{k+1}}$ دارای رتبه‌ی کم‌تری باشد ولی مهمترین شرط روی $B_{k+1}$ این است که این ماتریس معین مثبت باشد؛ چون در غیر این‌صورت جهت به‌دست آمده توسط آن، یعنی ${{p}_{k+1}}=-{{\left( {{B}_{k+1}} \right)}^{-1}}\nabla {{f}_{k}},$ کاهشی نخواهد بود. با در نظر گرفتن شرط معین مثبت بودن ${{B}_{k+1}}$، از معادله‌ی سکانت خواهیم داشت:
$${{B}_{k+1}}{{s}_{k}}={{y}_{k}}\Rightarrow 0<s_{k}^{t}{{B}_{k+1}}{{s}_{k}}=s_{k}^{t}{{y}_{k}},$$ یعنی $s_{k}^{t}{{y}_{k}}>0$ . چنانچه تابع $f$ اکیداً محدب باشد این شرط همواره برقرار است. اگر $f$ اکیداً محدب نباشد تعیین ${{x}_{k+1}}$ با استفاده از شرایط ولف ایجاب خواهد نمود که $s_{k}^{t}{{y}_{k}}>0$.
توجه داریم که به‌دست آوردن ماتریس ${{B}_{k+1}}$ از معادله‌ی سکانت به‌طور منحصر به فرد امکان پذیر نیست؛ زیرا این معادله تشکیل یک دستگاه $n$ معادله‌ی خطی می‌دهد که تعداد مجهولات آن (درایه‌های ${{B}_{k+1}}$) با توجه به متقارن بودن ${{B}_{k+1}}$ برابر است با:
$$1+2+3+\ldots +n=\frac{n\left( n+1 \right)}{2}$$ بنابراین با انتخاب‌های گوناگون ${{B}_{k+1}}$ می‌توان روش‌های شبه‌نیوتن متعددی یافت. در نتیجه هر روش خاص، ملاحظات دیگری را ممکن است در بر داشته باشد. با داشتن تقریب هسین، جهت کاهشی در هر تکرار، از رابطه‌ی زیر محاسبه میشود: $${{p}_{k+1}}=-{{\left( {{B}_{k+1}} \right)}^{-1}}\nabla {{f}_{k}}=-{{H}_{k+1}}\nabla {{f}_{k}}$$به‌هنگام‌سازی تقریب وارون هسین به جای خود هسین نیز امکان‌پذیر است. زیرا اگر ${{H}_{k+1}}$ وارون ${{B}_{k+1}}$ باشد، آن‌گاه با توجه به معادله‌ی سکانت، معادله‌ی شبه‌نیوتن ${{H}_{k+1}}{{y}_{k}}={{s}_{k}}$ را خواهیم داشت، که آن را معادله‌ی شبه‌نیوتن مربوط به $H$ می‌نامیم. با داشتن تقریب وارون هسین در هر گام می‌توان الگوریتم کلی یک روش شبه‌نیوتن را به‌صورت زیر بیان کرد:
تاریخچه‌ی کوتاهی از روش‌های شبه‌نیوتن
در اواسط دهه‌ی 1950 دیویدان، فیزیکدان شاغل در آزمایشگاه ملی آرگون، روش کاهش مختصاتی را برای انجام محاسبات بهینه‌سازی به کار می‌برد. در آن زمان دستگاه‌های کامپیوتری از توانایی محاسباتی بالایی برخوردار نبودند. بنابراین دیویدان تصمیم گرفت راهی پیدا کند که فرآیند تکرار الگوریتم را بهبود بخشد. الگوریتم او اولین الگوریتم شبه‌نیوتن بود که انقلابی در بهینه‌سازی غیرخطی ایجاد کرد. دیری نپایید که توسط فلچر و پاول ثابت شد که این الگوریتم جدید بسیار سریع‌تر و قابل اطمینان‌تر از دیگر روش‌های موجود آن زمان است و این پیشرفت به‌طور چشمگیری بهینه‌سازی غیرخطی را دگرگون کرد. در طول بیست سال بعد الگوریتم‌های شبه‌نیوتن متعددی مطرح و در صدها مقاله به مطالعه‌ی آن‌ها پرداخته شد. حکایت تاریخی جالبی که در این زمینه وجود دارد آن است که، مقاله‌ی دیویدان حدود 30 سال و به بهانه‌ی این‌که صرفاً گزارشی فنی است برای انتشار پذیرفته نشد تا این‌که سرانجام در سال 1991 در مجله‌ی بهینه‌سازی $SIAM$ به چاپ رسید.
همان‌گونه که گفته شد پس از معرفی اولین روش شبه‌نیوتن توسط دیویدان، فلچر و پاول (1963) که به الگوریتم $DFP$ معروف است، الگوریتم‌های شبه‌نیوتن متعددی مطرح شدند. ابتدا روش تصحیح رتبه یک ($SR1$) به وسیله‌ی دیویدان و برویدن (1967) عرضه شد و سپس روش $BFGS$ را برویدن، فلچر، گلدفارب و شانو در سال 1970 مستقل از یکدیگر معرفی کردند. ادبیات موضوع نشان می‌دهد که این الگوریتم به‌عنوان مؤثرترین الگوریتم به‌هنگام‌سازی در مسائل نامقید پذیرفته شده است. روش خانواده‌ی برویدن در سال 1970 توسط برویدن مطرح شد. این روش که از ترکیب محدب دو روش $DFP$ و $BFGS$ حاصل میشود به صورت زیر است:
$${{H}_{k}}\left( B \right)={{\varphi }_{k}}{{H}_{BFGS}}+\left( 1-{{\varphi }_{k}} \right){{H}_{DFP}},~~~~~~~0\le {{\varphi }_{k}}\le 1,$$ یک روش برویدن بنا به تعریف روشی است که در هر تکرار آن یکی از اعضای خانواده‌ی برویدن به عنوان تقریب معکوس هسین در نظر گرفته میشود. ابتدا کوشش‌های فراوانی برای یافتن بهترین دنباله‌ی ${{\varphi }_{k}}$ها در یک روش برویدن انجام شد تا این‌که سرانجام دیکسون در سال 1972 نشان داد که همه‌ی روش‌ها در حالت جستجوی خطی دقیق معادل یک‌دیگرند.
رده‌ی دیگری از روش‌های شبه‌نیوتن که محبوبیت خاصی در میان محققان پیدا کرده‌اند، روش‌های $LBFGS$ یا روش‌های $BFGS$ حافظه‌محدود هستند که الگوریتم $BFGS$ را با استفاده‌ی حداقلی از حافظه‌ی کامپیوتر برای مسائل در مقیاس بزرگ تقریب می‌کنند. نخستین الگوریتم $LBFGS$ را نوسدال در سال 1980 برای حل عددی مسائل بهینه‌سازی نامقید در ابعاد بزرگ ارائه داد.
ایده‌ی کلی روش‌های شبه‌نیوتن
همان‌طور که قبلاً گفته شد، روش نیوتن دو عیب اساسی دارد؛ اولین عیب این روش آن است که اگر تعداد متغیر‌های تابع هدف زیاد باشد به دست آوردن و معکوس کردن ماتریس هسین تابع، که در هر گام این روش انجام میشود، مستلزم محاسباتی سنگین است. عیب دوم این روش آن است که برای یک تابع هدف کلی همگرایی آن به جواب نمی‌تواند با شروع از هر نقطه‌ی ${{x}_{0}}$ تضمین شود. در حقیقت اگر نقطه‌ی شروع به اندازه‌ی کافی به جواب نزدیک نباشد ماتریس هسین ممکن است معین مثبت نباشد و الگوریتم خاصیت کاهشی را حفظ نکند.
روش‌های شبه‌نیوتن برای رفع مشکلات روش نیوتن طراحی شده‌اند و جانشین مناسبی برای آن هستند. از آن‌جا که این روش‌ها تنها از اطلاعات تابع هدف و مشتقات اول آن استفاده می‌کنند در آن‌ها نیازی به محاسبه‌ی وارون ماتریس هسین و ذخیره‌سازی آن نیست. هم‌چنین این روش‌ها معمولاً دارای همگرایی فوق‌خطی هستند که از این نظر بینابین روش تندترین کاهش و نیوتن قرار دارند.
ایده‌ی کلی روش‌های شبه‌نیوتن این است که به جای محاسبه‌ی مستقیم ماتریس هسین، ${{\nabla }^{2}}f$، یک تقریب ${{B}_{k}}$ در تکرار $k$ام محاسبه و این تقریب در هر گام به‌هنگام شود. ما در این‌جا شرطی را بیان می‌کنیم که دنباله‌ی تقریب‌های $\left\{ {{B}_{k}} \right\}$ در آن صدق می‌کنند و این شرط نقطه‌ی شروع بحث ما در روش‌های شبه‌نیوتن خواهد بود.
فرض کنید $f:{{\mathbb{R}}^{n}}\to \mathbb{R}$ تابعی دوبار به‌طور پیوسته مشتق‌پذیر باشد. با استفاده از قضیه‌ی تیلور داریم:$$\begin{align}
\nabla f\left( {{x}_{k}}+p \right)& =\nabla f\left( {{x}_{k}} \right)+{\int_0^1 }{{\nabla }^{2}}f\left( {{x}_{k}}+tp \right)pdt\\& =\nabla f\left( {{x}_{k}} \right)+{{\nabla }^{2}}f\left( {{x}_{k}} \right)p+{\int_0^1 }\left[ {{\nabla }^{2}}f\left( {{x}_{k}}+tp \right)-{{\nabla }^{2}}f\left( {{x}_{k}} \right) \right]~pdt.
\end{align}$$ از آن‌جا که $\nabla f$ تابعی پیوسته است انتگرال سمت راست آخرین تساوی هم‌مرتبه با $o\left( p \right)$ است. لذا اگر قرار دهیم ${{p}_{k}}={{x}_{k+1}}-{{x}_{k}}$، آن‌گاه:
$$\nabla {{f}_{k+1}}=\nabla {{f}_{k}}+{{\nabla }^{2}}{{f}_{k}}\left( {{x}_{k+1}}-{{x}_{k}} \right)+o\left( {{x}_{k+1}}-{{x}_{k}} \right),$$ و بنابراین برای ${{x}_{k}}$ و ${{x}_{k+1}}$ های نزدیک به‌هم می‌توانیم بنویسیم:
$${{\nabla }^{2}}{{f}_{k}}\left( {{x}_{k+1}}-{{x}_{k}} \right)\simeq \nabla {{f}_{k+1}}-\nabla {{f}_{k}}~,$$ توجه کنید که اگر $f$ تابعی درجه دوم باشد آن‌گاه به‌وضوح رابطه‌ی فوق به‌صورت تساوی برقرار است. اکنون تقریب جدید ماتریس هسین (${{B}_{k+1}}$ ) را به‌گونه‌ای انتخاب می‌کنیم که در رابطه‌ی زیر صدق کند:
$${{B}_{k+1}}\left( {{x}_{k+1}}-{{x}_{k}} \right)=\nabla {{f}_{k+1}}-\nabla {{f}_{k}}~,$$ به‌عبارت دیگر، چنانچه قرار دهیم ${{s}_{k}}={{x}_{k+1}}-{{x}_{k}}$ و ${{y}_{k}}=\nabla {{f}_{k+1}}-\nabla {{f}_{k}}$ در این‌صورت ${{B}_{k+1}}$ را چنان تعیین می‌کنیم که در معادله‌ی شبه‌نیوتن زیر صدق کند:$${{B}_{k+1}}{{s}_{k}}={{y}_{k}}$$این معادله به معادله‌ی سکانت موسوم است.
چون ${{B}_{k+1}}$ تقریب ماتریس هسین است طبیعی است که انتظار داشته باشیم متقارن باشد. البته شرایط دیگری نیز روی ${{B}_{k+1}}$ اعمال میشود از جمله این‌که معین مثبت باشد و تفاضل ${{B}_{k}}$ و ${{B}_{k+1}}$ دارای رتبه‌ی کم‌تری باشد ولی مهمترین شرط روی $B_{k+1}$ این است که این ماتریس معین مثبت باشد؛ چون در غیر این‌صورت جهت به‌دست آمده توسط آن، یعنی ${{p}_{k+1}}=-{{\left( {{B}_{k+1}} \right)}^{-1}}\nabla {{f}_{k}},$ کاهشی نخواهد بود. با در نظر گرفتن شرط معین مثبت بودن ${{B}_{k+1}}$، از معادله‌ی سکانت خواهیم داشت:
$${{B}_{k+1}}{{s}_{k}}={{y}_{k}}\Rightarrow 0<s_{k}^{t}{{B}_{k+1}}{{s}_{k}}=s_{k}^{t}{{y}_{k}},$$ یعنی $s_{k}^{t}{{y}_{k}}>0$ . چنانچه تابع $f$ اکیداً محدب باشد این شرط همواره برقرار است. اگر $f$ اکیداً محدب نباشد تعیین ${{x}_{k+1}}$ با استفاده از شرایط ولف ایجاب خواهد نمود که $s_{k}^{t}{{y}_{k}}>0$.
توجه داریم که به‌دست آوردن ماتریس ${{B}_{k+1}}$ از معادله‌ی سکانت به‌طور منحصر به فرد امکان پذیر نیست؛ زیرا این معادله تشکیل یک دستگاه $n$ معادله‌ی خطی می‌دهد که تعداد مجهولات آن (درایه‌های ${{B}_{k+1}}$) با توجه به متقارن بودن ${{B}_{k+1}}$ برابر است با:
$$1+2+3+\ldots +n=\frac{n\left( n+1 \right)}{2}$$ بنابراین با انتخاب‌های گوناگون ${{B}_{k+1}}$ می‌توان روش‌های شبه‌نیوتن متعددی یافت. در نتیجه هر روش خاص، ملاحظات دیگری را ممکن است در بر داشته باشد. با داشتن تقریب هسین، جهت کاهشی در هر تکرار، از رابطه‌ی زیر محاسبه میشود: $${{p}_{k+1}}=-{{\left( {{B}_{k+1}} \right)}^{-1}}\nabla {{f}_{k}}=-{{H}_{k+1}}\nabla {{f}_{k}}$$به‌هنگام‌سازی تقریب وارون هسین به جای خود هسین نیز امکان‌پذیر است. زیرا اگر ${{H}_{k+1}}$ وارون ${{B}_{k+1}}$ باشد، آن‌گاه با توجه به معادله‌ی سکانت، معادله‌ی شبه‌نیوتن ${{H}_{k+1}}{{y}_{k}}={{s}_{k}}$ را خواهیم داشت، که آن را معادله‌ی شبه‌نیوتن مربوط به $H$ می‌نامیم. با داشتن تقریب وارون هسین در هر گام می‌توان الگوریتم کلی یک روش شبه‌نیوتن را به‌صورت زیر بیان کرد:
الگوریتم عمومی روش‌های شبه‌نیوتن
گام 1. نقطه‌ی شروع ${{x}_{0}}$ و ماتریس متقارن و معین مثبت ${{H}_{0}}$ را انتخاب کنید. قرار دهید $k=0$.
گام 2. اگر شرط توقف برقرار است توقف کنید. در غیر این‌صورت قرار دهید ${{p}_{k}}=-{{H}_{k}}{{g}_{k}}$.
گام 3. طول گام حرکت و نقطه‌ی بعدی را به صورت زیر محاسبه کنید:$$\begin{align}
& {{\alpha }_{k}}=\arg \underset{\alpha >0}{\mathop{\min }}\,f\left( {{x}_{k}}+\alpha {{p}_{k}} \right), \\
& {{x}_{k+1}}={{x}_{k}}+{{\alpha }_{k}}{{p}_{k}}.
\end{align}$$ گام 4. ${{H}_{k+1}}$ را از روی ${{H}_{k}}$ با استفاده از یک روش شبه‌نیوتن به‌هنگام کنید.
گام 5. قرار دهید $k=k+1$ و به گام 2 بروید.
هم‌چنین گام‌های 1 و 2 و 4 از الگوریتم فوق را می‌توان به‌صورت زیر تعویض نمود:
گام 1*. نقطه‌ی شروع ${{x}_{0}}$ و ماتریس حقیقی معین مثبت ${{B}_{0}}$ را انتخاب کنید. قرار دهید $k=0$.
گام 2*. اگر شرط توقف برقرار است توقف کنید. در غیر این‌صورت ${{p}_{k}}$ را از حل دستگاه ${{B}_{k}}{{p}_{k}}=-{{g}_{k}}$ محاسبه کنید.
گام 4*. ${{B}_{k+1}}$ را از روی ${{B}_{k}}$ با استفاده از یک روش شبه‌نیوتن به‌هنگام کنید.
روش SR1
همان‌گونه که از الگوریتم قبل نیز برمی‌آید، کلید اصلی روش‌های شبه‌نیوتن، تولید ماتریس ${{H}_{k+1}}$ از روی ${{H}_{k}}$ (یا ماتریس ${{B}_{k+1}}$ از روی ${{B}_{k}}$) با در نظر داشتن معادله‌ی شبه‌نیوتن است. در ادامه برخی از روش‌های شبه‌نیوتن متداول را معرفی می‌کنیم. در این‌جا نخست یک فرمول به‌هنگام‌سازی رتبه یک ساده را معرفی می‌کنیم که در معادله‌ی شبه‌نیوتن صدق کند. فرض کنید ${{H}_{k}}$ تقریب وارون هسین در گام $k$ام باشد. سعی می‌کنیم ${{H}_{k+1}}$ را بر حسب ${{H}_{k}}$ به‌هنگام کنیم. امکان تعریف یک رابطه‌ی بازگشتی به‌صورت:$${{H}_{k+1}}={{H}_{k}}+{{E}_{k}}$$را بررسی می‌کنیم، که در آن ${{E}_{k}}$ معمولاً یک ماتریس با رتبه‌ی پایین‌تر است. در حالت رتبه یک داریم:$${{H}_{k+1}}={{H}_{k}}+u{{v}^{t}}~~(1)$$که در آن $u,v\in {{\mathbb{R}}^{n}}$ . با استفاده از معادله‌ی شبه‌نیوتن ${{H}_{k+1}}{{y}_{k}}={{s}_{k}}$ به‌دست می‌آوریم:${{H}_{k+1}}{{y}_{k}}=\left( {{H}_{k}}+u{{v}^{t}} \right){{y}_{k}}={{s}_{k}}$ که نتیجه می‌دهد:$$\left( {{v}^{t}}{{y}_{k}} \right)u={{s}_{k}}-{{H}_{k}}{{y}_{k}}~~(2)$$و از این‌جا نتیجه میشود که بردار $u$ باید در راستای ${{s}_{k}}-{{H}_{k}}{{y}_{k}}$ باشد.
فرض کنید که ${{s}_{k}}-{{H}_{k}}{{y}_{k}}\ne 0$ (در غیر این‌صورت ${{H}_{k}}$ در معادله‌ی شبه‌نیوتن صدق می‌کند) و بردار $v$ در ${{v}^{t}}{{y}_{k}}\ne 0$ صدق کند. آن‌گاه از روابط (1) و (2) نتیجه میشود که:$${{H}_{k+1}}={{H}_{k}}+\frac{1}{{{v}^{t}}{{y}_{k}}}\left( {{s}_{k}}-{{H}_{k}}{{y}_{k}} \right){{v}^{t}} ~~(3)$$ از آن‌جا که تقریب معکوس هسین ${{H}_{k}}$ بایستی متقارن باشد می‌توانیم به‌سادگی قرار دهیم $v={{s}_{k}}-{{H}_{k}}{{y}_{k}}$ و به دست آوریم:$${{H}_{k+1}}={{H}_{k}}+\frac{\left( {{s}_{k}}-{{H}_{k}}{{y}_{k}} \right){{\left( {{s}_{k}}-{{H}_{k}}{{y}_{k}} \right)}^{t}}}{{{({{s}_{k}}-{{H}_{k}}{{y}_{k}})}^{t}}{{y}_{k}}~}$$ این رابطه، فرمول به‌هنگام‌سازی رتبه یک متقارن ($SR1$) نامیده میشود.
رابطه‌ی (3) بیان‌گر فرمول به‌هنگام‌سازی رتبه یک برویدن است. در حالت خاص اگر $v={{y}_{k}}$، آن‌گاه (3) تصحیح رتبه یک برویدن نامیده میشود که نخستین بار توسط برویدن (1965) برای حل دستگاه‌های معادلات غیرخطی ارائه گردید.
قضیه: (فیاکو و مک‌کورمیک)
فرض کنید ${{s}_{0}},{{s}_{1}},\ldots ,{{s}_{n-1}}$ مستقل خطی باشند. در این‌صورت برای یک تابع درجه دوم $n$ متغیره با یک هسین معین مثبت، روش $SR1$ در $n+1$ گام به جواب می‌رسد؛ به‌عبارت دیگر داریم: ${{H}_{n}}=G$ که $G$ هسین تابع درجه دوم است.
نتیجه: با توجه به این قضیه، روش $SR1$ به‌طور طبیعی حل مسائل درجه دوم را پشتیبانی می‌کند. هم‌چنین در این روش خاصیت زیر برقرار است:$${{H}_{i}}{{y}_{j}}={{s}_{j}},~~~j<i.$$ مهمترین مزیت روش $SR1$ سادگی آن است. حتی این روش گاهی ممکن است کاراتر از روش $BFGS$ باشد. اما این روش دارای مشکلاتی نیز هست. اول آن‌که رابطه‌ی به‌هنگام‌سازی $SR1$ معین مثبت بودن را فقط در صورتی حفظ می‌کند که ${{({{s}_{k}}-{{H}_{k}}{{y}_{k}})}^{t}}{{y}_{k}}>0$ و برقراری این نابرابری را نمی‌توان تضمین نمود. به‌علاوه حتی اگر ${{({{s}_{k}}-{{H}_{k}}{{y}_{k}})}^{t}}{{y}_{k}}$ مثبت باشد، ممکن است مقدار آن کوچک باشد و این امر ممکن است به مشکلات عددی منجر شود.
پاول، مثال ساده‌ی زیر را برای بیان اشکالات روش $SR1$ ارائه می‌کند.
مثال: فرض کنید $f\left( x \right)=\frac{1}{2}\left( 2x_{1}^{2}+\frac{1}{2}x_{2}^{2} \right)$ ،$H=I$ و $s={{\left( 1,2 \right)}^{t}}$. اگر $\tilde{H}$ با استفاده از روش $SR1$ محاسبه شود، خواهیم داشت:$$\tilde{H}=\left( \begin{matrix}
0 & 1 \\
1 & 0 \\
\end{matrix} \right)$$ که معین مثبت نیست. به‌علاوه اگر به جای $s={{\left( 1,2 \right)}^{t}}$ قرار دهیم $s={{\left( \frac{1}{2},\sqrt{2} \right)}^{t}}$ ، آن‌گاه ${{({{s}_{k}}-{{H}_{k}}{{y}_{k}})}^{t}}{{y}_{k}}=0$ و در نتیجه $\tilde{H}$ حتی تعریف هم نمی‌شود.
این مثال ساده نشان می‌دهد که حتی اگر تابعی درجه دوم و اکیداً محدب باشد، استفاده از روش $SR1$ می‌تواند سبب شکست الگوریتم شبه‌نیوتن گردد. بنابراین بایستی هر الگوریتم شبه‌نیوتن را که در آن فرمول $SR1$ به‌عنوان فرمول به‌هنگام‌سازی به کار می‌رود، با احتیاط به کار برد. این مردودی‌ها شامل شرایط زیر است:
1) $\tilde{H}$ معین مثبت نیست.
2) ${{({{s}_{k}}-{{H}_{k}}{{y}_{k}})}^{t}}{{y}_{k}}=0$ و در نتیجه $\tilde{H}$ تعریف نمی‌شود.
روش ساده‌ای که می‌توان برای محافظت روش $SR1$ در مقابل مردودی‌های ناشی از شرایط فوق بهکار برد آن است که، هرگاه هریک از این شرایط برقرار باشد، آن‌گاه $H$ را برابر با ماتریس واحد ($I$) قرار دهیم. در واقع در چنین حالاتی جهت جستجو را به جای آن که از رابطه‌ی: $${{p}_{k}}=-{{\left( {{B}_{k}} \right)}^{-1}}\nabla {{f}_{k}}=-{{H}_{k}}\nabla {{f}_{k}}$$ به‌دست آوریم، برابر با $${{p}_{k}}=-\nabla {{f}_{k}}$$ قرار می‌دهیم. به عبارت دیگر، نقطه‌ی بعدی را از روش تندترین کاهش محاسبه می‌کنیم. راه دیگر جلوگیری از شکست روش $SR1$ این است که از روش $SR1$ تنها زمانی استفاده کنیم که:$$\left| {{\left( {{s}_{k}}-{{H}_{k}}{{y}_{k}} \right)}^{t}}{{y}_{k}} \right|\ge r{{s}_{k}}-{{H}_{k}}{{y}_{k}}{{y}_{k}}~~(4)$$که در آن $0<r<1$.
قضیه: (گولد، کان و توینت)
فرض کنید تابع $f$ دو بار به‌طور پیوسته مشتق پذیر باشد، هسین آن کراندار و بر یک همسایگی نقطه‌ی ${{x}^{*}}$ پیوسته‌ی لیپشیتس باشد و $\left\{ {{x}_{k}} \right\}$ دنباله‌ای از تکرارها باشد که ${{x}_{k}}\to {{x}^{*}}$. هم‌چنین فرض کنید که قاعده‌ی (4) برای تمام $k$ها برقرار باشد. آن‌گاه برای دنباله‌ی ماتریسی $\left\{ {{H}_{k}} \right\}$ تولید شده توسط روش $SR1$ خواهیم داشت:$$\underset{k\to \infty }{\mathop{\lim }}\,{{H}_{k}}-{{\left[ {{\nabla }^{2}}f\left( {{x}^{*}} \right) \right]}^{-1}}=0.$$
روشDFP
روش $DFP$ یکی دیگر از روش‌های معمول به‌هنگام‌سازی شبه‌نیوتن است. این روش یک به‌هنگام‌سازی رتبه دو است؛ به این معنی که ${{H}_{k+1}}$ با اضافه نمودن ${{H}_{k}}$ به دو ماتریس رتبه یک حاصل شده است. برای این منظور فرمول کلی به‌هنگام‌سازی رتبه دو زیر که متقارن بودن $\left\{ {{H}_{k}} \right\}$ را حفظ می‌کند در نظر می‌گیریم:
$${{H}_{k+1}}={{H}_{k}}+au{{u}^{t}}+bv{{v}^{t}}~~(5)$$ که در آن $u,v\in {{\mathbb{R}}^{n}}$ و $a$ و $b$ اسکالرهایی هستند که محاسبه می‌شوند. با استفاده از (5) و معادله‌ی شبه‌نیوتن مربوط به $H$ داریم:$${{H}_{k+1}}{{y}_{k}}={{s}_{k}}\Rightarrow {{H}_{k}}{{y}_{k}}+au{{u}^{t}}{{y}_{k}}+bv{{v}^{t}}{{y}_{k}}={{s}_{k}}~~(6)$$ به‌وضوح $u$ و $v$ به‌طور منحصر به‌فرد تعیین نمی‌شوند. اما اگر انتخاب کنیم:$$u={{s}_{k}},~~v={{H}_{k}}{{y}_{k}}$$ آن‌گاه از (6) خواهیم داشت:$$a=\frac{1}{{{u}^{t}}{{y}_{k}}}=\frac{1}{s_{k}^{t}{{y}_{k}}},~~~~~~~b=-\frac{1}{{{v}^{t}}{{y}_{k}}}=-\frac{1}{y_{k}^{t}{{H}_{k}}{{y}_{k}}}$$ و در نتیجه خواهیم داشت:
$${{H}_{k+1}}={{H}_{k}}+\frac{{{s}_{k}}s_{k}^{t}}{s_{k}^{t}{{y}_{k}}}-\frac{{{H}_{k}}{{y}_{k}}y_{k}^{t}{{H}_{k}}}{y_{k}^{t}{{H}_{k}}{{y}_{k}}}.$$ این رابطه نخستین فرمول روش شبه‌نیوتن است که اول بار توسط دیویدان معرفی و سپس توسط فلچر و پاول توسعه داده شد. از این رو معمولاً با نام روش $DFP$ خوانده میشود. روش $DFP$ دارای خواص زیر است:
الف. برای توابع درجه دوم (تحت جستجوی خطی دقیق)
به‌طور طبیعی مسائل درجه دوم را در $n$ گام حل می‌کند. یعنی ${{H}_{n}}={{G}^{-1}}$ .
دارای این خاصیت است که ${{H}_{i}}{{y}_{j}}={{s}_{j}}$ برای تمام $j<i$ .
این روش جهت‌های مزدوج تولید می‌کند. اگر ${{H}_{0}}=I$ گرادیان‌های مزدوج تولید می‌کند.
ب. برای توابع کلی
با شروع از یک ماتریس حقیقی معین مثبت ${{H}_{0}}$ معین مثبت بودن $\left\{ {{H}_{k}} \right\}$ حفظ میشود.
هر تکرار آن نیاز به $3{{n}^{2}}+O\left( n \right)$ عمل محاسباتی دارد.
به‌طور فوق خطی همگراست.
برای یک تابع اکیداً محدب با جستجوی خطی دقیق به‌طور سراسری همگراست.
در این‌جا خاصیت حفظ معین مثبت بودن و حل مسائل درجه دوم را اثبات می‌کنیم.
روش $DFP$ یکی دیگر از روش‌های معمول به‌هنگام‌سازی شبه‌نیوتن است. این روش یک به‌هنگام‌سازی رتبه دو است؛ به این معنی که ${{H}_{k+1}}$ با اضافه نمودن ${{H}_{k}}$ به دو ماتریس رتبه یک حاصل شده است. برای این منظور فرمول کلی به‌هنگام‌سازی رتبه دو زیر که متقارن بودن $\left\{ {{H}_{k}} \right\}$ را حفظ می‌کند در نظر می‌گیریم:
$${{H}_{k+1}}={{H}_{k}}+au{{u}^{t}}+bv{{v}^{t}}~~(5)$$ که در آن $u,v\in {{\mathbb{R}}^{n}}$ و $a$ و $b$ اسکالرهایی هستند که محاسبه می‌شوند. با استفاده از (5) و معادله‌ی شبه‌نیوتن مربوط به $H$ داریم:$${{H}_{k+1}}{{y}_{k}}={{s}_{k}}\Rightarrow {{H}_{k}}{{y}_{k}}+au{{u}^{t}}{{y}_{k}}+bv{{v}^{t}}{{y}_{k}}={{s}_{k}}~~(6)$$ به‌وضوح $u$ و $v$ به‌طور منحصر به‌فرد تعیین نمی‌شوند. اما اگر انتخاب کنیم:$$u={{s}_{k}},~~v={{H}_{k}}{{y}_{k}}$$ آن‌گاه از (6) خواهیم داشت:$$a=\frac{1}{{{u}^{t}}{{y}_{k}}}=\frac{1}{s_{k}^{t}{{y}_{k}}},~~~~~~~b=-\frac{1}{{{v}^{t}}{{y}_{k}}}=-\frac{1}{y_{k}^{t}{{H}_{k}}{{y}_{k}}}$$ و در نتیجه خواهیم داشت:
$${{H}_{k+1}}={{H}_{k}}+\frac{{{s}_{k}}s_{k}^{t}}{s_{k}^{t}{{y}_{k}}}-\frac{{{H}_{k}}{{y}_{k}}y_{k}^{t}{{H}_{k}}}{y_{k}^{t}{{H}_{k}}{{y}_{k}}}.$$ این رابطه نخستین فرمول روش شبه‌نیوتن است که اول بار توسط دیویدان معرفی و سپس توسط فلچر و پاول توسعه داده شد. از این رو معمولاً با نام روش $DFP$ خوانده میشود. روش $DFP$ دارای خواص زیر است:
الف. برای توابع درجه دوم (تحت جستجوی خطی دقیق)
به‌طور طبیعی مسائل درجه دوم را در $n$ گام حل می‌کند. یعنی ${{H}_{n}}={{G}^{-1}}$ .
دارای این خاصیت است که ${{H}_{i}}{{y}_{j}}={{s}_{j}}$ برای تمام $j<i$ .
این روش جهت‌های مزدوج تولید می‌کند. اگر ${{H}_{0}}=I$ گرادیان‌های مزدوج تولید می‌کند.
ب. برای توابع کلی
با شروع از یک ماتریس حقیقی معین مثبت ${{H}_{0}}$ معین مثبت بودن $\left\{ {{H}_{k}} \right\}$ حفظ میشود.
هر تکرار آن نیاز به $3{{n}^{2}}+O\left( n \right)$ عمل محاسباتی دارد.
به‌طور فوق خطی همگراست.
برای یک تابع اکیداً محدب با جستجوی خطی دقیق به‌طور سراسری همگراست.
در این‌جا خاصیت حفظ معین مثبت بودن و حل مسائل درجه دوم را اثبات می‌کنیم.
قضیه: (خاصیت حفظ معین مثبت بودن روش $DFP$)
فرمول به‌هنگام‌سازی $DFP$ ، معین مثبت بودن $\left\{ {{H}_{k}} \right\}$ را حفظ می‌کند اگر و تنها اگر $s_{k}^{t}{{y}_{k}}>0$.
اثبات: اگر هر یک از جملات دنباله‌ی $\left\{ {{H}_{k}} \right\}$ معین مثبت باشد، آن‌گاه از معادله‌ی شبه‌نیوتن ${{H}_{k+1}}{{y}_{k}}={{s}_{k}}$ نتیجه میشود:$$y_{k}^{t}{{H}_{k+1}}{{y}_{k}}=y_{k}^{t}{{s}_{k}}=s_{k}^{t}{{y}_{k}}>0.$$برای اثبات عکس قضیه با استقرا نشان خواهیم داد که:$$\forall z\ne 0:~{{z}^{t}}{{H}_{k}}z>0.$$ به‌وضوح $H_0$ متقارن و معین مثبت است. فرض می‌کنیم این رابطه برای یک $k\ge 0$ برقرار باشد و نشان می‌دهیم برای $k+1$ نیز برقرار است. فرض کنیم ${{H}_{k}}=L{{L}^{t}}$ تجزیه‌ی چولسکی ماتریس ${{H}_{k}}$ باشد. قرار می‌دهیم:$$a={{L}^{t}}z~,b={{L}^{t}}{{y}_{k}}.$$ با استفاده از فرمول به‌هنگام‌سازی $DFP$ خواهیم داشت:$$\begin{align}
{{z}^{t}}{{H}_{k+1}}z&={{z}^{t}}\left( {{H}_{k}}-\frac{{{H}_{k}}{{y}_{k}}y_{k}^{t}{{H}_{k}}}{y_{k}^{t}{{H}_{k}}{{y}_{k}}} \right)z+{{z}^{t}}\frac{{{s}_{k}}s_{k}^{t}}{s_{k}^{t}{{y}_{k}}}z \\
&=\left[ {{a}^{t}}a-\frac{{{\left( {{a}^{t}}b \right)}^{2}}}{{{b}^{t}}b} \right]+\frac{{{\left( {{z}^{t}}{{s}_{k}} \right)}^{2}}}{s_{k}^{t}{{y}_{k}}}.~
\end{align}$$ از نامساوی کوشی- شوارتز واضح است که:$${{a}^{t}}a-\frac{{{\left( {{a}^{t}}b \right)}^{2}}}{{{b}^{t}}b}\ge 0.$$ یعنی اولین عبارت سمت راست تساوی نامنفی است. از طرفی جمله‌ی دوم نیز نامنفی است، زیرا $s_{k}^{t}{{y}_{k}}>0$. بنابراین داریم ${{z}^{t}}{{H}_{k+1}}z\ge 0$. برای تکمیل اثبات کافی است نشان دهیم که هر دوی جملات سمت راست همزمان صفر نمی‌شوند. جمله‌ی اول تنها زمانی که $a$ و $b$ با یکدیگر متناسب باشند صفر میشود. این ایجاب می‌کند که $z$ و ${{y}_{k}}$ با یکدیگر متناسب باشند، مثلاً $z=\beta {{y}_{k}}$ که $\beta \ne 0$ . ولی در این حالت:$$\frac{{{\left( {{z}^{t}}{{s}_{k}} \right)}^{2}}}{s_{k}^{t}{{y}_{k}}}={{\beta }^{2}}s_{k}^{t}{{y}_{k}}>0$$ یعنی جمله‌ی دوم اکیداً بزرگ‌تر از صفر خواهد بود. بنابراین $z_{k}^{t}{{H}_{k+1}}z>0$ و در نتیجه ${{H}_{k+1}}$ معین مثبت است.
نتیجه: جهت‌های تولید شده توسط روش $DFP$ کاهشی هستند، زیرا:$${{p}_{k}}=-{{H}_{k}}{{g}_{k}}\Rightarrow g_{k}^{t}{{p}_{k}}=-g_{k}^{t}{{H}_{k}}{{g}_{k}}<0.$$ قضیه: فرض کنید $f$ یک تابع درجه دوم n متغیره با هسین معین مثبت $G$ باشد و روش $DFP$ به‌همراه جستجوی خطی دقیق برای $f$ بهکار رود. آن‌گاه:
الف) به‌ازای هر $i=0,1,\ldots ,m$ که در آن $m\le n-1$ داریم: ${{H}_{i+1}}{{y}_{j}}={{s}_{j}},~~j=0,1,\ldots ,i$.
ب) به‌ازای هر $i=0,1,\ldots ,m$ که در آن $m\le n-1$ داریم: $s_{i}^{t}G{{s}_{j}}=0,~~j=0,1,\ldots ,i$.
ج) روش $DFP$ در $n$ گام به جواب می‌رسد و ${{H}_{n}}={{G}^{-1}}$ .
اثبات: قسمت‌های (الف) و (ب) را با استقرا ثابت می‌کنیم. وقتی $i=0$ احکام (الف) و (ب) نتایجی سرراست هستند. فرض کنید این احکام برای $i>0$ برقرار باشند. نشان می‌دهیم آن‌ها برای $i+1$ نیز برقرارند. با فرض ${{g}_{i+1}}\ne 0$، انجام جستجوی خطی دقیق و این که$${{y}_{k}}={{g}_{k+1}}-{{g}_{k}}=G\left( {{x}_{k+1}}-{{x}_{k}} \right)=G{{s}_{k}},~~~~1\le k\le i$$ از فرض‌های استقرا، برای هر $j\le i$ داریم:$$g_{i+1}^{t}{{s}_{j}}=g_{j+1}^{t}{{s}_{j}}+\underset{k=j+1}{\overset{i}{\mathop \sum }}\,{{\left( {{g}_{k+1}}-{{g}_{k}} \right)}^{t}}{{s}_{j}}=g_{j+1}^{t}{{s}_{j}}+\underset{k=j+1}{\overset{i}{\mathop \sum }}\,y_{k}^{t}{{s}_{j}}=0+\underset{k=j+1}{\overset{i}{\mathop \sum }}\,s_{k}^{t}G{{s}_{j}}=0~~(7)$$اکنون با استفاده از تساوی ${{s}_{i+1}}=-{{\alpha }_{i+1}}{{H}_{i+1}}{{g}_{i+1}}$، مفروضات استقرا در قسمت (الف) و رابطه‌ی (7) نتیجه می‌گیریم که:$$s_{i+1}^{t}G{{s}_{j}}=-{{\alpha }_{i+1}}g_{i+1}^{t}{{H}_{i+1}}{{y}_{j}}=-{{\alpha }_{i+1}}g_{i+1}^{t}{{s}_{j}}=0~~(8)$$که قسمت (ب) را برای $i+1$ ثابت می‌کند. نشان می‌دهیم (الف) نیز برای $i+1$ برقرار است؛ یعنی:$${{H}_{i+2}}{{y}_{j}}={{s}_{j}},~~j=0,1,\ldots ,i+1~~(9)$$وقتی $j=i+1$، حکم (الف) از به‌هنگام‌سازی $DFP$ حاصل میشود؛ یعنی:$${{H}_{i+2}}{{y}_{i+1}}={{s}_{i+1}}.~~(10)$$ اگر $j\le i$، آن‌گاه رابطه‌ی (8) و فرض استقرا در قسمت (الف) نتیجه می‌دهند که:$$\begin{align}
& s_{i+1}^{t}{{y}_{j}}=s_{i+1}^{t}G{{s}_{j}}=0, \\
& y_{i+1}^{t}{{H}_{i+1}}{{y}_{j}}=y_{i+1}^{t}{{s}_{j}}=s_{i+1}^{t}G{{s}_{j}}=0.
\end{align}$$ بنابراین:$$\begin{align}
{{H}_{i+2}}{{y}_{j}}&={{H}_{i+1}}{{y}_{j}}+\frac{{{s}_{i+1}}s_{i+1}^{t}{{y}_{j}}}{s_{i+1}^{t}{{y}_{i+1}}}-\frac{{{H}_{i+1}}{{y}_{i+1}}y_{i+1}^{t}{{H}_{i+1}}{{y}_{j}}}{y_{i+1}^{t}{{H}_{i+1}}{{y}_{i+1}}} \\
& ={{H}_{i+1}}{{y}_{j}} \\
& ={{s}_{j}}.
\end{align}$$این به‌همراه رابطه‌ی (10)، رابطه‌ی (9) را ثابت می‌کنند. پس قسمت (الف) نیز ثابت شد. برای اثبات قسمت (ج) توجه می‌کنیم که بنابر قسمت (ب)، بردارهای ${{s}_{i}}\left( i=0,1,\ldots ,n-1 \right)$ $G$ مزدوج هستند. بنابراین روش $DFP$ یک روش جهت‌های مزدوج خواهد بود. در نتیجه طبق قضیه‌ی جهت‌های مزدوج ، روش $DFP$ پس از $n$ گام به جواب می‌رسد. سرانجام از استقلال خطی بردارهای ${{s}_{i}}\left( i=0,1,\ldots ,n-1 \right)$ و قسمت (الف) خواهیم داشت:$${{H}_{n}}G{{s}_{j}}={{H}_{n}}{{y}_{j}}={{s}_{j}},~~~j=0,1,\ldots ,n-1$$که نتیجه می‌دهد ${{H}_{n}}={{G}^{-1}}$ .
{{z}^{t}}{{H}_{k+1}}z&={{z}^{t}}\left( {{H}_{k}}-\frac{{{H}_{k}}{{y}_{k}}y_{k}^{t}{{H}_{k}}}{y_{k}^{t}{{H}_{k}}{{y}_{k}}} \right)z+{{z}^{t}}\frac{{{s}_{k}}s_{k}^{t}}{s_{k}^{t}{{y}_{k}}}z \\
&=\left[ {{a}^{t}}a-\frac{{{\left( {{a}^{t}}b \right)}^{2}}}{{{b}^{t}}b} \right]+\frac{{{\left( {{z}^{t}}{{s}_{k}} \right)}^{2}}}{s_{k}^{t}{{y}_{k}}}.~
\end{align}$$ از نامساوی کوشی- شوارتز واضح است که:$${{a}^{t}}a-\frac{{{\left( {{a}^{t}}b \right)}^{2}}}{{{b}^{t}}b}\ge 0.$$ یعنی اولین عبارت سمت راست تساوی نامنفی است. از طرفی جمله‌ی دوم نیز نامنفی است، زیرا $s_{k}^{t}{{y}_{k}}>0$. بنابراین داریم ${{z}^{t}}{{H}_{k+1}}z\ge 0$. برای تکمیل اثبات کافی است نشان دهیم که هر دوی جملات سمت راست همزمان صفر نمی‌شوند. جمله‌ی اول تنها زمانی که $a$ و $b$ با یکدیگر متناسب باشند صفر میشود. این ایجاب می‌کند که $z$ و ${{y}_{k}}$ با یکدیگر متناسب باشند، مثلاً $z=\beta {{y}_{k}}$ که $\beta \ne 0$ . ولی در این حالت:$$\frac{{{\left( {{z}^{t}}{{s}_{k}} \right)}^{2}}}{s_{k}^{t}{{y}_{k}}}={{\beta }^{2}}s_{k}^{t}{{y}_{k}}>0$$ یعنی جمله‌ی دوم اکیداً بزرگ‌تر از صفر خواهد بود. بنابراین $z_{k}^{t}{{H}_{k+1}}z>0$ و در نتیجه ${{H}_{k+1}}$ معین مثبت است.
نتیجه: جهت‌های تولید شده توسط روش $DFP$ کاهشی هستند، زیرا:$${{p}_{k}}=-{{H}_{k}}{{g}_{k}}\Rightarrow g_{k}^{t}{{p}_{k}}=-g_{k}^{t}{{H}_{k}}{{g}_{k}}<0.$$ قضیه: فرض کنید $f$ یک تابع درجه دوم n متغیره با هسین معین مثبت $G$ باشد و روش $DFP$ به‌همراه جستجوی خطی دقیق برای $f$ بهکار رود. آن‌گاه:
الف) به‌ازای هر $i=0,1,\ldots ,m$ که در آن $m\le n-1$ داریم: ${{H}_{i+1}}{{y}_{j}}={{s}_{j}},~~j=0,1,\ldots ,i$.
ب) به‌ازای هر $i=0,1,\ldots ,m$ که در آن $m\le n-1$ داریم: $s_{i}^{t}G{{s}_{j}}=0,~~j=0,1,\ldots ,i$.
ج) روش $DFP$ در $n$ گام به جواب می‌رسد و ${{H}_{n}}={{G}^{-1}}$ .
اثبات: قسمت‌های (الف) و (ب) را با استقرا ثابت می‌کنیم. وقتی $i=0$ احکام (الف) و (ب) نتایجی سرراست هستند. فرض کنید این احکام برای $i>0$ برقرار باشند. نشان می‌دهیم آن‌ها برای $i+1$ نیز برقرارند. با فرض ${{g}_{i+1}}\ne 0$، انجام جستجوی خطی دقیق و این که$${{y}_{k}}={{g}_{k+1}}-{{g}_{k}}=G\left( {{x}_{k+1}}-{{x}_{k}} \right)=G{{s}_{k}},~~~~1\le k\le i$$ از فرض‌های استقرا، برای هر $j\le i$ داریم:$$g_{i+1}^{t}{{s}_{j}}=g_{j+1}^{t}{{s}_{j}}+\underset{k=j+1}{\overset{i}{\mathop \sum }}\,{{\left( {{g}_{k+1}}-{{g}_{k}} \right)}^{t}}{{s}_{j}}=g_{j+1}^{t}{{s}_{j}}+\underset{k=j+1}{\overset{i}{\mathop \sum }}\,y_{k}^{t}{{s}_{j}}=0+\underset{k=j+1}{\overset{i}{\mathop \sum }}\,s_{k}^{t}G{{s}_{j}}=0~~(7)$$اکنون با استفاده از تساوی ${{s}_{i+1}}=-{{\alpha }_{i+1}}{{H}_{i+1}}{{g}_{i+1}}$، مفروضات استقرا در قسمت (الف) و رابطه‌ی (7) نتیجه می‌گیریم که:$$s_{i+1}^{t}G{{s}_{j}}=-{{\alpha }_{i+1}}g_{i+1}^{t}{{H}_{i+1}}{{y}_{j}}=-{{\alpha }_{i+1}}g_{i+1}^{t}{{s}_{j}}=0~~(8)$$که قسمت (ب) را برای $i+1$ ثابت می‌کند. نشان می‌دهیم (الف) نیز برای $i+1$ برقرار است؛ یعنی:$${{H}_{i+2}}{{y}_{j}}={{s}_{j}},~~j=0,1,\ldots ,i+1~~(9)$$وقتی $j=i+1$، حکم (الف) از به‌هنگام‌سازی $DFP$ حاصل میشود؛ یعنی:$${{H}_{i+2}}{{y}_{i+1}}={{s}_{i+1}}.~~(10)$$ اگر $j\le i$، آن‌گاه رابطه‌ی (8) و فرض استقرا در قسمت (الف) نتیجه می‌دهند که:$$\begin{align}
& s_{i+1}^{t}{{y}_{j}}=s_{i+1}^{t}G{{s}_{j}}=0, \\
& y_{i+1}^{t}{{H}_{i+1}}{{y}_{j}}=y_{i+1}^{t}{{s}_{j}}=s_{i+1}^{t}G{{s}_{j}}=0.
\end{align}$$ بنابراین:$$\begin{align}
{{H}_{i+2}}{{y}_{j}}&={{H}_{i+1}}{{y}_{j}}+\frac{{{s}_{i+1}}s_{i+1}^{t}{{y}_{j}}}{s_{i+1}^{t}{{y}_{i+1}}}-\frac{{{H}_{i+1}}{{y}_{i+1}}y_{i+1}^{t}{{H}_{i+1}}{{y}_{j}}}{y_{i+1}^{t}{{H}_{i+1}}{{y}_{i+1}}} \\
& ={{H}_{i+1}}{{y}_{j}} \\
& ={{s}_{j}}.
\end{align}$$این به‌همراه رابطه‌ی (10)، رابطه‌ی (9) را ثابت می‌کنند. پس قسمت (الف) نیز ثابت شد. برای اثبات قسمت (ج) توجه می‌کنیم که بنابر قسمت (ب)، بردارهای ${{s}_{i}}\left( i=0,1,\ldots ,n-1 \right)$ $G$ مزدوج هستند. بنابراین روش $DFP$ یک روش جهت‌های مزدوج خواهد بود. در نتیجه طبق قضیه‌ی جهت‌های مزدوج ، روش $DFP$ پس از $n$ گام به جواب می‌رسد. سرانجام از استقلال خطی بردارهای ${{s}_{i}}\left( i=0,1,\ldots ,n-1 \right)$ و قسمت (الف) خواهیم داشت:$${{H}_{n}}G{{s}_{j}}={{H}_{n}}{{y}_{j}}={{s}_{j}},~~~j=0,1,\ldots ,n-1$$که نتیجه می‌دهد ${{H}_{n}}={{G}^{-1}}$ .
مسلماً روش $DFP$ یکی از هوشمندانه‌ترین روش‌هایی است که برای حل مسائل بهینه‌سازی ارائه شده است. این روش در بسیاری از کدهای کامپیوتری نیز مورد استفاده قرار می‌گیرد. هم‌چنین این روش، نقش مهمی در آنالیز نظری و محاسبات عددی ایفا می‌کند. با وجود این متأسفانه مطالعات عددی نشان داده‌اند که روش $DFP$ از لحاظ عددی ناپایدار است و گاهی اوقات در عمل به واسطه‌ی خطاهای گرد کردن تقریبات منفردی از ماتریس هسین تولید می‌کند. روش معروف $BFGS$ که در ادامه معرفی میشود، این اشکال را ندارد و در عمل کارایی بیش‌تری نسبت به روش $DFP$ دارد.
روش BFGS
یادآوری می‌کنیم که معادله‌ی سکانت برای تقریب ماتریس هسین به‌صورت ${{B}_{k+1}}{{s}_{k}}={{y}_{k}}$ و معادله‌ی شبه‌نیوتن متناظر با آن برای تقریب معکوس ماتریس هسین به‌صورت زیر است:$${{H}_{k+1}}{{y}_{k}}={{s}_{k}}.$$ نکته‌ی جالبی که در رابطه‌ی قبل وجود دارد آن است که این رابطه دقیقاً همان شکل معادله‌ی سکانت را دارد به‌جز آن‌که ${{s}_{k}}$ و ${{y}_{k}}$ با هم جابه‌جا شده‌اند و $H$ جایگزین $B$ شده است. این مطلب منجر به یک مفهوم دوگانی می‌گردد که از آن فلچر است. به بیان دقیق‌تر هر فرمول به‌هنگام‌سازی برای $B$ با انجام جابه جایی‌های $H\longleftrightarrow B$ و ${{s}_{k}}\longleftrightarrow {{y}_{k}}$، قابل تبدیل به یک فرمول مکمل برای به‌هنگام‌سازی $H$ است و برعکس با داشتن یک فرمول به‌هنگام‌سازی برای $H$ می‌توان به یک فرمول برای به‌هنگام‌سازی $B$ دست یافت. هم‌چنین با مکمل گرفتن از یک مکمل فرمول اولیه بازسازی میشود. حال اگر فرمول به‌هنگام‌سازی $DFP$ برای به‌هنگام‌سازی $H$ را در نظر بگیریم می‌توانیم به‌دست آوریم:$$B_{k+1}^{\left( BFGS \right)}={{B}_{k}}+\frac{{{y}_{k}}y_{k}^{t}}{y_{k}^{t}{{s}_{k}}}-\frac{{{B}_{k}}{{s}_{k}}s_{k}^{t}{{B}_{k}}}{s_{k}^{t}{{B}_{k}}{{s}_{k}}}$$که فرمول به‌هنگام‌سازی $BFGS$ نامیده میشود. به همین دلیل روش $BFGS$ دوگان روش $DFP$ نیز نامیده میشود. این فرمول مستقلاً توسط برویدن، فلچر، گلدفارب و شانو معرفی است. از آن‌جا که ${{B}_{k}}{{s}_{k}}=-{{\alpha }_{k}}{{g}_{k}}$ و ${{B}_{k}}{{p}_{k}}=-{{g}_{k}}$، رابطه‌ی بالا به‌صورت زیر نیز می‌تواند نوشته شود:$$B_{k+1}^{\left( BFGS \right)}={{B}_{k}}+\frac{{{g}_{k}}g_{k}^{t}}{g_{k}^{t}{{p}_{k}}}+\frac{{{y}_{k}}y_{k}^{t}}{{{\alpha }_{k}}y_{k}^{t}{{p}_{k}}}$$ اکنون با دوبار استفاده از فرمول شرمن- موریسون- وودبری (پیوست همین مطلب) خواهیم داشت:$$\begin{align}
H_{k+1}^{\left( BFGS \right)}&={{H}_{k}}+\left( 1+\frac{y_{k}^{t}{{H}_{k}}{{y}_{k}}}{s_{k}^{t}{{y}_{k}}} \right)\frac{{{s}_{k}}s_{k}^{t}}{s_{k}^{t}{{y}_{k}}}-\frac{{{s}_{k}}y_{k}^{t}{{H}_{k}}+{{H}_{k}}{{y}_{k}}s_{k}^{t}}{s_{k}^{t}{{y}_{k}}}
\\&={{H}_{k}}+\frac{\left( {{s}_{k}}-{{H}_{k}}{{y}_{k}} \right)s_{k}^{t}+{{s}_{k}}{{\left( {{s}_{k}}-{{H}_{k}}{{y}_{k}} \right)}^{t}}}{s_{k}^{t}{{y}_{k}}}-\frac{{{\left( {{s}_{k}}-{{H}_{k}}{{y}_{k}} \right)}^{t}}{{y}_{k}}}{{{\left( s_{k}^{t}{{y}_{k}} \right)}^{2}}}{{s}_{k}}s_{k}^{t}
\\&=\left( I-\frac{{{s}_{k}}y_{k}^{t}}{s_{k}^{t}{{y}_{k}}} \right){{H}_{k}}\left( I-\frac{{{y}_{k}}s_{k}^{t}}{s_{k}^{t}{{y}_{k}}} \right)+\frac{{{s}_{k}}s_{k}^{t}}{s_{k}^{t}{{y}_{k}}}
\end{align}$$این روابط سه شکل از به‌هنگام‌سازی $BFGS$ برای ${{H}_{k}}$ هستند. علاوه بر این با جابجایی‌های $H\longleftrightarrow B$ و ${{s}_{k}}\longleftrightarrow {{y}_{k}}$ در آن‌ها می‌توانیم سه شکل از به‌هنگام‌سازی $DFP$ برای ${{B}_{k}}$ به‌دست آوریم:$$\begin{align}
B_{k+1}^{\left( DFP \right)}&={{B}_{k}}+\left( 1+\frac{s_{k}^{t}{{B}_{k}}{{s}_{k}}}{y_{k}^{t}{{s}_{k}}} \right)\frac{{{y}_{k}}y_{k}^{t}}{y_{k}^{t}{{s}_{k}}}-\frac{{{y}_{k}}s_{k}^{t}{{B}_{k}}+{{B}_{k}}{{s}_{k}}y_{k}^{t}}{s_{k}^{t}{{y}_{k}}}\\
&={{B}_{k}}+\frac{\left( {{y}_{k}}-{{B}_{k}}{{s}_{k}} \right)y_{k}^{t}+{{y}_{k}}{{\left( {{y}_{k}}-{{B}_{k}}{{s}_{k}} \right)}^{t}}}{y_{k}^{t}{{s}_{k}}}-\frac{{{\left( {{y}_{k}}-{{B}_{k}}{{s}_{k}} \right)}^{t}}{{s}_{k}}}{{{\left( y_{k}^{t}{{s}_{k}} \right)}^{2}}}{{y}_{k}}y_{k}^{t}\\&=\left( I-\frac{{{y}_{k}}s_{k}^{t}}{y_{k}^{t}{{s}_{k}}} \right){{B}_{k}}\left( I-\frac{{{s}_{k}}y_{k}^{t}}{y_{k}^{t}{{s}_{k}}} \right)+\frac{{{y}_{k}}y_{k}^{t}}{y_{k}^{t}{{s}_{k}}}.
\end{align}$$بحث فوق یک روش کلی برای یافتن دوگان یک روش به‌هنگام‌سازی در اختیار ما قرار می‌دهد. فرض کنید یک روش شبه‌نیوتن ${{H}_{k+1}}$ را بر حسب ${{H}_{k}}$ به‌هنگام کند. ابتدا با جابجایی‌های $H\leftrightarrow B$ و ${{s}_{k}}\leftrightarrow {{y}_{k}}$ به‌هنگام‌سازی دوگان آن، $B_{k+1}^{\left( D \right)}$، را می‌یابیم. اکنون با اعمال فرمول شرمن- موریسون- وودبری بر $B_{k+1}^{\left( D \right)}$ می‌توانیم فرمول $H_{k+1}^{\left( D \right)}$ را برای به‌هنگام‌سازی $H$ به‌دست آوریم. اجازه دهید این کار را برای روش $SR1$ بهکار ببریم. یادآور می‌شویم که روش به‌هنگام‌سازی $SR1$ به‌صورت زیر است:$$H_{k+1}^{\left( SR1 \right)}={{H}_{k}}+\frac{\left( {{s}_{k}}-{{H}_{k}}{{y}_{k}} \right){{\left( {{s}_{k}}-{{H}_{k}}{{y}_{k}} \right)}^{t}}}{{{({{s}_{k}}-{{H}_{k}}{{y}_{k}})}^{t}}{{y}_{k}}~}.$$با انجام تغییرات $H\longleftrightarrow B$ و ${{s}_{k}}\longleftrightarrow {{y}_{k}}$ خواهیم داشت: $$B_{k+1}^{\left( D \right)}={{B}_{k}}+\frac{\left( {{y}_{k}}-{{B}_{k}}{{s}_{k}} \right){{\left( {{y}_{k}}-{{B}_{k}}{{s}_{k}} \right)}^{t}}}{{{({{y}_{k}}-{{B}_{k}}{{s}_{k}})}^{t}}{{s}_{k}}~}$$حال اگر فرمول شرمن- موریسون- وودبری را اعمال کنیم، به‌دست می‌آوریم:$$H_{k+1}^{\left( D \right)}={{H}_{k}}+\frac{\left( {{s}_{k}}-{{H}_{k}}{{y}_{k}} \right){{\left( {{s}_{k}}-{{H}_{k}}{{y}_{k}} \right)}^{t}}}{{{({{s}_{k}}-{{H}_{k}}{{y}_{k}})}^{t}}{{y}_{k}}~}.$$همان‌طور که می‌بینیم که نتیجه‌ی $H_{k+1}^{\left( D \right)}$ تفاوتی با به‌هنگام‌سازی $H_{k+1}^{\left( SR1 \right)}$ نکرده است. به این دلیل اصطلاحاً می‌گوییم که به‌هنگام‌سازی $SR1$ یک به‌هنگام‌سازی خود دوگان است. همان‌گونه که پیش‌تر نیز اشاره کردیم به‌هنگام‌سازی $SR1$ معین مثبت بودن را لزوماً حفظ نمی‌کند. با این حال، یک روش به‌هنگام‌سازی خود دوگان دیگر به نام هوشینو وجود دارد که معین مثبت بودن را نیز حفظ می‌کند.
قضیه: (خاصیت حفظ معین مثبت بودن روش $BFGS$)
به‌هنگام‌سازی $BFGS$ معین مثبت بودن $\left\{ {{H}_{k}} \right\}$ را حفظ می‌کند اگر و تنها اگر $s_{k}^{t}{{y}_{k}}>0$.
اثبات: اگر هر یک از جملات دنباله‌ی $\left\{ {{H}_{k}} \right\}$ معین مثبت باشد آن‌گاه از معادله‌ی شبه‌نیوتن ${{H}_{k+1}}{{y}_{k}}={{s}_{k}}$ نتیجه میشود $y_{k}^{t}{{H}_{k+1}}{{y}_{k}}=y_{k}^{t}{{s}_{k}}=s_{k}^{t}{{y}_{k}}>0$ برای اثبات عکس قضیه، با استقرا نشان خواهیم داد که:$$\forall z\ne 0:{{z}^{t}}{{H}_{k}}z>0.$$به‌وضوح ${{H}_{0}}$ متقارن و معین مثبت است. فرض می‌کنیم این رابطه‌ی برای یک $k\ge 0$ برقرار باشد، نشان می‌دهیم رابطه برای $k+1$ نیز برقرار است. به‌ازای هر بردار $z\ne 0$ قرار می‌دهیم:$$w=z-{{\rho }_{k}}{{y}_{k}}\left( s_{k}^{t}z \right),~~~{{\rho }_{k}}=\frac{1}{s_{k}^{t}{{y}_{k}}}$$ در این‌صورت با کمی محاسبات جبری خواهیم داشت:$$z_{k}^{t}{{H}_{k+1}}z={{w}^{t}}{{H}_{k}}w+{{\rho }_{k}}{{\left( {{z}^{t}}{{s}_{k}} \right)}^{2}}$$که بزرگ‌تر یا مساوی صفر است. اما سمت راست تساوی بالا تنها زمانی صفر میشود که داشته باشیم $s_{k}^{t}z=0$، ولی در این حالت خواهیم داشت $w=z\ne 0$ و در این‌صورت فرض استقرا نتیجه می‌دهد اولین جمله اکیداً بزرگ‌تر از صفر است. بنابراین $z_{k}^{t}{{H}_{k+1}}z>0$ و در نتیجه ${{H}_{k+1}}$ معین مثبت است.
روش $BFGS$ در حال حاضر بهترین روش شبه‌نیوتن است. این روش تمام خواص خوب روش $DFP$ را دارد. علاوه بر آن وقتی از جستجوی خطی دقیق یا جستجوی خطی نادقیق با شرایط ولف استفاده شود این روش همگرای سراسری است. ذکر این نکته در این‌جا لازم است که همگرایی سراسری روش $DFP$ تحت جستجوی خطی نادقیق با شرایط ولف هم‌چنان یک مسئله‌ی باز است. بنابراین با وجودی که روش $DFP$ سال‌های متمادی به عنوان یک روش موفق برای حل مسائل بهکار گرفته شده است اخیراً از روش $BFGS$ استفاده میشود. در کاربردهای عملی روش $BFGS$ می‌تواند به همراه جستجوی خطی در تصویرسازی بهکار گرفته شود.
فرمول شرمن- موریسون- وودبری:
اگر $A$ ماتریسی $n\times n$ و وارون‌پذیر و $U$ و $V$ ماتریس‌هایی باشند که $U{{V}^{t}}$ هم‌مرتبه با $A$ باشد، آن‌گاه وارون ماتریس $A+U{{V}^{t}}$ در صورت وجود برابر است با:$${{\left( A+U{{V}^{t}} \right)}^{-1}}={{A}^{-1}}-{{A}^{-1}}U{{\left( I+{{V}^{t}}{{A}^{-1}}U \right)}^{-1}}{{V}^{t}}{{A}^{-1}}$$
اثبات: \[\begin{align}
& \left( A+U{{V}^{t}} \right)\left( {{A}^{-1}}-{{A}^{-1}}U{{\left( I+{{V}^{t}}{{A}^{-1}}U \right)}^{-1}}{{V}^{t}}{{A}^{-1}} \right) \\
& =I+U{{V}^{t}}{{A}^{-1}}-U{{\left( I+{{V}^{t}}{{A}^{-1}}U \right)}^{-1}}{{V}^{t}}{{A}^{-1}}-U{{V}^{t}}{{A}^{-1}}U{{\left( I+{{V}^{t}}{{A}^{-1}}U \right)}^{-1}}{{V}^{t}}{{A}^{-1}} \\
& =I+U\left( I-{{\left( I+{{V}^{t}}{{A}^{-1}}U \right)}^{-1}}-{{V}^{t}}{{A}^{-1}}U{{\left( I+{{V}^{t}}{{A}^{-1}}U \right)}^{-1}} \right){{V}^{t}}{{A}^{-1}} \\
& =I+U\left( I+{{V}^{t}}{{A}^{-1}}U-I-{{V}^{t}}{{A}^{-1}}U \right){{\left( I+{{V}^{t}}{{A}^{-1}}U \right)}^{-1}}{{V}^{t}}A \\
& =I \\
\end{align}\]
im