در آموزش‌های قبل با برخی از روش‌های کمینه‌سازی نامقید آشنا شدیم. در این قسمت به معرفی روش‌های شبه‌نیوتن می‌پردازیم که برای رفع اشکالات روش نیوتن معرفی شده‌اند. انگیزه‌ی اصلی طرح روش‌های شبه‌نیوتن دست‌یابی به همگرایی سریع روش نیوتن حداقل به‌طور میانگین است بدون آن‌که نیاز به محاسبه‌ی ماتریس هسین و وارون آن در هر گام باشد. این کار با به‌دست آوردن تقریب‌هایی برای وارون هسین بر اساس اطلاعات جمع‌آوری شده در فرآیند کاهشی انجام میشود و روش‌هایی که از این طریق بدست می‌آیند عموماً دارای همگرایی فوق‌خطی می‌باشند.
تاریخچه‌ی کوتاهی از روش‌های شبه‌نیوتن
در اواسط دهه‌ی 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}}$ تضمین شود. در حقیقت اگر نقطه‌ی شروع به اندازه‌ی کافی به جواب نزدیک نباشد ماتریس هسین ممکن است معین مثبت نباشد و الگوریتم خاصیت کاهشی را حفظ نکند.
روش‌های شبه‌نیوتن برای رفع مشکلات روش نیوتن طراحی شده‌اند و جانشین مناسبی برای آن هستند. از آن‌جا که این روش‌ها تنها از اطلاعات تابع هدف و مشتقات اول آن استفاده می‌کنند در آن‌ها نیازی به محاسبه‌ی وارون ماتریس هسین و ذخیره‌سازی آن نیست. هم‌چنین این روش‌ها معمولاً دارای همگرایی فوق‌خطی هستند که از این نظر بینابین روش تندترین کاهش و نیوتن قرار دارند.
تاریخچه‌ی کوتاهی از روش‌های شبه‌نیوتن
در اواسط دهه‌ی 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}}$ تضمین شود. در حقیقت اگر نقطه‌ی شروع به اندازه‌ی کافی به جواب نزدیک نباشد ماتریس هسین ممکن است معین مثبت نباشد و الگوریتم خاصیت کاهشی را حفظ نکند.
روش‌های شبه‌نیوتن برای رفع مشکلات روش نیوتن طراحی شده‌اند و جانشین مناسبی برای آن هستند. از آن‌جا که این روش‌ها تنها از اطلاعات تابع هدف و مشتقات اول آن استفاده می‌کنند در آن‌ها نیازی به محاسبه‌ی وارون ماتریس هسین و ذخیره‌سازی آن نیست. هم‌چنین این روش‌ها معمولاً دارای همگرایی فوق‌خطی هستند که از این نظر بینابین روش تندترین کاهش و نیوتن قرار دارند.
