آشنایی با روش‌های بهینه‌سازی نامقید (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}} .
نتیجه: جهت‌های تولید شده توسط روش 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