Abstract

Conjugate gradient methods are conjugate direction or gradient deflection methods which lie somewhere between the method of steepest descent and Newton's method. Their principal advantage is that they do not require the storage of any matrices as in Newton's method, or as in quasi-Newton methods, and they are designed to converge faster than the method of steepest descent. Unlike quasi-Newton or variable-metric methods, these are fixed-metric methods in which the search direction at each iteration is based on an approximation to the inverse Hessian constructed by updating a fixed, symmetric, positive definite matrix, typically the identity matrix. The resulting approximation is usually not symmetric, although some variants force symmetry and hence derive memoryless quasi-Newton methods. In this paper, we present a scaled modified version of the conjugate gradient method suggested by Perry, which employs the quasi-Newton condition rather than conjugacy under inexact line searches, in order to derive the search directions. The analysis is extended to the memoryless quasi-Newton modification of this method, as suggested by Shanno. Computational experience on standard test problems indicates that the proposed method, along with Beale and Powell's restarts, improves upon existing conjugate gradient strategies

چکیده

روش های گردایان مزدوج، روش های جهت دار شدن مزدوج یا روش های انحراف گرادیان هستند که جایی بین روش تندترین کاش و روش نیوتن قرار می گیرد. مزیت اصلی آنها، این است که مانند روش نیوتن، یا روش های شبه نیوتن، نیازی به ذخیره هیچ ماتریسی ندارند و برای همگرایی سریع تر از تندترین کاهش، طراحی شده اند. بر خلاف روش های شبه نیوتن یا متری متغیر، این روش ها، روشهای متری ثابت هستند که در آن، جهت دار شدن جست جو در هر تکرار، بر پایه یک تقریب به یک هسیان معکوس است که با به هنگام سازی یک ماتریس معین مثبت، متقارن، ثابت نوعاً ماتریس یکانی، ایجاد می شود. تقریب حاصل، معمولاً متقارن نیست، اگرچه، برخی ناورداها، تقارن را تحمیل می کنندو در نتیجه، روش های شبه نیوتن بی حافظه را استخراج می کنند. در این مقاله، ما یک نسخه اصلاح شده مقیاس بندی شده از روش گرادیان مزدوج پیشنهاد شده توسط پری را ارائه می کنیم، که به جای تزویج تحت جستجوهای خطی غیردقیق، شرایط شبه نیوتنی را به کار می گیرد. تحلیل به اصلاح شبه نیوتنی بی حافظه از این روش بسط یافته است، همانگونه که توسط شانو پیشنهاد شده است. تجربه محاسباتی در مسائل آزمون استاندارد، نشان می دهد که روش پیشنهاد شده ،همراه با شروع مجددهای بیل – پاول، استراتژی های گرادیان مزدوج موجود را بهبود می بخشد.

1-مقدمه

روش های گرادیان مزدوج، یک بهبود قابل توجه را در الگوریتم های تندترین کاهش در افزایش متوسط الزامات انبارش حاصل می کنند و در نتیجه، برای کاربردهای بزرگ مقیاس، بسیار مناسب هستند. آنها الگوریتم های جهت دار شدن مزودج هستند که نهایتاً در n تکرار برای مسائل بهینه سازی درجه دوم نامحدود در Rn همگرا می شوند، زمانی که از جستجوهای خطی دقیق استفاده می شود. با این وجود، آنها بر مسائل غیردرجه دوم نیز اعمال می شوند، زیرا توابع هموار، در همسایگی بهینه، رفتار درجه دوم نشان می دهند. در چنین مواردی، روند معمولاً بعد از هر n تکرار دوباره شروع می شود (راه اندازی مجدد) تا نرخ همگرایی را بهبود دهد. اصلاحات مختلف در استراتژی گرادیان مزدوج تحت واهلش فرض های جستجوی خطی دقیق یا/و مربعی پیشنهاد شده اند و شرایط شروع مجدد مختلف توصیه شده اند...