آشنایی با روش‌های بهینه‌سازی نامقید (3)
روش گرادیان مزدوج:
روش گرادیان مزدوج، یک روش تکراری برای حل دستگاه معادلات خطی $Ax=b$ می‌باشد که در آن $A$ ماتریسی $n\times n$ متقارن و معین مثبت است. به سادگی دیده می‌شود که حل دستگاه فوق، هم‌ارز با حل مسئله‌ی بهینه‌سازی درجه دوم زیر است:
$$\min f\left( x \right)=\frac{1}{2}{{x}^{t}}Ax-{{b}^{t}}x$$
این هم‌ارزی موجب می‌شود که روش گرادیان مزدوج به‌عنوان روشی برای یافتن کمینه‌ی توابع محدب درجه دوم مورد استفاده قرار گیرد. البته همانند بخش قبل می‌توان آن را برای توابع غیر درجه دوم نیز به‌کار برد. توجه کنید که: $$\nabla f\left( x \right)=Ax-b=r\left( x \right).$$ از آن‌جا که روش گرادیان مزدوج، بر پایه‌ی جهت‌های مزدوج بنا شده است، بنابراین ابتدا شرح مختصری از جهت‌های مزدوج می‌آوریم.
تعریف: فرض کنید $A$ یک ماتریس متقارن باشد. بردارهای ${{p}_{1}}$ و ${{p}_{2}}$ را $A$-متعامد یا مزدوج نسبت به $A$ می‌نامیم هرگاه $p_{1}^{t}A{{p}_{2}}=0$. یک مجموعه‌ی متناهی از بردارها مانند $\left\{ {{p}_{1}},{{p}_{2}},\ldots ,{{p}_{l}} \right\}$ را یک مجموعه‌ی $A$-متعامد یا مزدوج نسبت به $A$ می‌نامیم هرگاه به‌ازای هر $i\ne j$ داشته باشیم $p_{i}^{t}A{{p}_{j}}=0$.
مثال: بردارهای ${{p}_{1}}=\left(\begin{matrix}-7\\4\\\end{matrix}\right)$ و ${{p}_{2}}=\left(\begin{matrix}5\\-2 \\\end{matrix} \right)$ نسبت به ماتریس $A=\left( \begin{matrix}2 & 3\\ 3 & 4 \\\end{matrix} \right)$ مزدوج هستند. اگر $A=0$ آن‌گاه هر دو بردار دلخواه، مزدوج هستند و اگر $A=I$ آن‌گاه بردارهای مزدوج بر هم عمودند.
قضیه: فرض کنید $A$ یک ماتریس معین مثبت باشد. اگر مجموعه بردارهای ناصفر $\left\{ {{p}_{1}},{{p}_{2}},\ldots ,{{p}_{l}} \right\}$ ،$A$-متعامد باشند، آن‌گاه این بردارها مستقل خطی هستند.
اثبات: فرض کنید ثابت‌های ${{\lambda }_{1}},{{\lambda }_{2}},\ldots ,{{\lambda }_{l}}$ موجود باشند به‌طوری که:\[{{\lambda }_{1}}{{p}_{1}}+{{\lambda }_{2}}{{p}_{2}}+\ldots+{{\lambda }_{l}}{{p}_{l}}=0\]
چون برای $i\ne j$ ، $p_{i}^{t}A{{p}_{j}}=0$ ، پس با ضرب رابطه‌ی فوق در $A$ و تشکیل ضرب داخلی با ${{p}_{i}}$ داریم ${{\lambda }_{i}}p_{i}^{t}A{{p}_{i}}=0$ و از آن‌جا که $A$ معین مثبت است، پس ${{\lambda }_{i}}=0$.در ادامه، روش جهت‌های مزدوج را بیان می‌کنیم. این روش به‌خوبی اهمیت جهت‌های مزدوج را نشان می‌دهد.
فرض کنید که $\left\{ {{p}_{0}},{{p}_{1}},\ldots ,{{p}_{n-1}} \right\}$ مجموعه‌ای از بردارهای ناصفر $A$-متعامد در ${{\mathbb{R}}^{n}}$ باشند که $A$ یک ماتریس معین مثبت است. به‌ازای هر ${{x}_{0}}\in {{\mathbb{R}}^{n}}$، دنباله‌ی $\left\{ {{x}_{k}} \right\}$ را توسط رابطه‌ی بازگشتی ${{x}_{k+1}}={{x}_{k}}+{{\alpha }_{k}}{{p}_{k}}$ تعریف می‌کنیم به‌گونه‌ای که ${{\alpha }_{k}}$ کمینه‌کننده‌ی تابع اکیداً محدب یک‌بعدی $\varphi \left( \alpha \right)=f\left( {{x}_{k}}+\alpha {{p}_{k}} \right)$ در امتداد نیم‌خط $\left\{ {{x}_{k}}+\alpha {{p}_{k}}|\alpha >0 \right\}$ باشد. برای این منظور، مشتق تابع
$$\varphi \left( \alpha \right)=f\left( {{x}_{k}}+\alpha {{p}_{k}} \right)=\frac{1}{2}{{\left( {{x}_{k}}+\alpha {{p}_{k}} \right)}^{t}}A\left( {{x}_{k}}+\alpha {{p}_{k}} \right)-{{b}^{t}}\left( {{x}_{k}}+\alpha {{p}_{k}} \right),$$ را نسبت به $\alpha $ برابر صفر قرار می‌دهیم. از آن‌جا خواهیم داشت:$${{\alpha }_{k}}=\alpha =-\frac{{{\left( \nabla {{f}_{k}} \right)}^{t}}{{p}_{k}}}{p_{k}^{t}A{{p}_{k}}}=-\frac{r_{k}^{t}{{p}_{k}}}{p_{k}^{t}A{{p}_{k}}}.$$ قضیه: فرض کنید که $\left\{ {{p}_{0}},{{p}_{1}},\ldots ,{{p}_{n-1}} \right\}$ مجموعه‌ای از بردارهای ناصفر $A$-متعامد در ${{\mathbb{R}}^{n}}$ باشند که $A$ یک ماتریس معین مثبت است. در این‌صورت به‌ازای هر ${{x}_{0}}\in {{\mathbb{R}}^{n}}$ ، دنباله‌ی $\left\{ {{x}_{k}} \right\}$ تعریف شده توسط رابطه‌ی بازگشتی ${{x}_{k+1}}={{x}_{k}}+{{\alpha }_{k}}{{p}_{k}}$ که در آن $${{\alpha }_{k}}=-\frac{{{\left( \nabla {{f}_{k}} \right)}^{t}}{{p}_{k}}}{p_{k}^{t}A{{p}_{k}}}=-\frac{r_{k}^{t}{{p}_{k}}}{p_{k}^{t}A{{p}_{k}}}$$ در حداکثر $n$ گام به جواب دستگاه معادلات خطی $Ax=b$ همگرا خواهد شد. به علاوه: $$r_{k}^{t}{{p}_{i}}={{\left( \nabla {{f}_{k}} \right)}^{t}}{{p}_{i}}=0,~~~~i=0,1,2,\ldots ,k-1.$$قضیه‌ی فوق نشان می‌دهد که اگر بتوان $n$ جهت مزدوج نسبت به ماتریس معین مثبت $A$ پیدا نمود، آن‌گاه با روابط موجود در قضیه می‌توان دستگاه معادلات خطی $Ax=b$ را حل نمود. به‌منظور انتخاب یک مجموعه از جهت‌های مزدوج، راه‌های زیادی وجود دارند. برای مثال می‌توان بردارهای ویژه ماتریس $A$ را، که دو به دو متعامد هستند، به‌عنوان جهت‌های مزدوج انتخاب نمود. اما این‌کار در مسائل با مقیاس بزرگ بسیار پرهزینه است. راه دیگر استفاده از روش متعامدسازی گرام- اشمیت است، که البته این روش هم به دلیل این‌که نیاز به ذخیره‌سازی بردارهای وارد شده دارد، به‌صرفه نمی‌باشد. روش گرادیان مزدوج در واقع همان روش جهت‌های مزدوج است با این تفاوت که در آن جهت‌های جستجو از قبل مشخص نمی‌شوند، بلکه طوری تعیین می‌شوند که شرط مزدوج بودن جهت‌ها (به‌ازای هر $i\ne j$، $p_{i}^{t}A{{p}_{j}}=0$) در هر تکرار برقرار باشد. هم‌چنین این روش، دارای این ویژگی خاص است که هر بردار ${{p}_{k+1}}$ واقع در مجموعه جهت‌های مزدوج تنها با استفاده از بردار ${{p}_{k}}$ محاسبه می‌شود. در حقیقت در روش گرادیان مزدوج نیازی به ذخیره‌سازی جهت‌های قبلی ${{p}_{0}},{{p}_{1}},\ldots ,{{p}_{k-1}}$ نیست و به‌طور خودکار ${{p}_{k+1}}$ همراه با جهت‌های ${{p}_{0}},{{p}_{1}},\ldots ,{{p}_{k}}$ مجموعه‌ای مزدوج نسبت به $A$ را تشکیل می‌دهد. در روش گرادیان مزدوج،${{p}_{0}}=-\nabla f\left( {{x}_{0}} \right)$ اختیار می‌شود و هر جهت ${{p}_{k+1}}$ ترکیبی خطی از $-\nabla f\left( {{x}_{k+1}} \right)$ و جهت ${{p}_{k}}$ به‌صورت زیر است:$${{p}_{k+1}}=-\nabla f\left( {{x}_{k+1}} \right)+{{\beta }_{k}}{{p}_{k}},$$اسکالر ${{\beta }_{k}}$، که پارامتر روش گرادیان مزدوج نامیده می‌شود، با در نظر گرفتن این مطلب که ${{p}_{k}}$ و ${{p}_{k+1}}$ باید نسبت به $A$ مزدوج باشند محاسبه می‌گردد. انتخاب‌های متفاوت ${{\beta }_{k}}$ منجر به روش‌های گرادیان مزدوج متفاوتی می‌شود که برخی از مشهورترین آن‌ها عبارتند از:$$\beta _{k}^{HS}=\frac{g_{k+1}^{t}\left({{g}_{k+1}}-{{g}_{k}}\right)}{p_{k}^{t}\left({{g}_{k+1}}-{{g}_{k}}\right)}, \beta_{k}^{FR}=\frac{{{\left\| {g}_{k+1}
\right\|}}^{2}}{{\left\| {g}_{k}
\right\|}^2}, \beta _{k}^{PR}=\frac{g_{k+1}^{t}\left({{g}_{k+1}}-{{g}_{k}} \right)}{{\left\| {g}_{k}
\right\|}^2}$$ که از چپ به راست، به‌ترتیب روش‌های هستینز-اشتیفل، فلچر-ریوز و پولاک-ریبیه نامیده می‌شوند. در اینجا، ${{g}_{k}}$ به معنای $\nabla f\left( {{x}_{k}} \right)$ است.
با توجه به مطالب فوق می‌توان الگوریتم روش گرادیان مزدوج را به‌صورت زیر بیان نمود:
الگوریتم روش گرادیان مزدوج
گام 1. نقطه‌ی شروع ${{x}_{0}}$ را انتخاب کنید. قرار دهید $k=0$.
گام 2. ${{g}_{0}}\leftarrow \nabla f\left( {{x}_{0}} \right)$. اگر ${{g}_{0}}=0$، توقف کنید. در غیر این‌صورت قرار دهید ${{p}_{0}}=-{{g}_{0}}$.
گام 3. طول گام ${{\alpha }_{k}}$ را محاسبه کنید.
گام 4. با استفاده از رابطه‌ی ${{x}_{k+1}}={{x}_{k}}+{{\alpha }_{k}}{{p}_{k}}$ نقطه‌ی جدید را محاسبه کنید.
گام 5. قرار دهید ${{g}_{k+1}}=\nabla f\left( {{x}_{k+1}} \right)$. اگر ${{g}_{k+1}}=0$، توقف کنید.
گام 6. جهت جدید را از رابطه‌ی ${{p}_{k+1}}=-{{g}_{k+1}}+{{\beta }_{k}}{{p}_{k}}$ محاسبه کنید.
گام 7. قرار دهید $k=k+1$ و به گام 3 بروید.
روش‌های تعیین طول گام
همان‌طور که قبلاً بیان شد، در هر تکرار از الگوریتم‌های جستجوی خطی ابتدا یک جهت کاهشی ${{p}_{k}}$ و سپس یک طول گام $\alpha $ تعیین و سرانجام توسط رابطه‌ی ${{x}_{k+1}}={{x}_{k}}+\alpha {{p}_{k}}$ نقطه‌ی بعدی محاسبه می‌شود. جهت جستجوی کاهشی ${{p}_{k}}$ را می‌توان به‌صورت زیر در نظر گرفت:$${{p}_{k}}=-{{\left( {{B}_{k}} \right)}^{-1}}\nabla f\left( {{x}_{k}} \right),$$ شرط کاهشی‌بودن ${{p}_{k}}$ ایجاب می‌کند که ماتریس ${{B}_{k}}$ معین مثبت باشد. چنان‌چه در هر تکرار قرار دهیم ${{B}_{k}}=I$، روش تندترین کاهش و اگر قرار دهیم ${{B}_{k}}={{\nabla }^{2}}f\left( {{x}_{k}} \right)$، روش نیوتن حاصل می‌شود. چنان‌چه ${{B}_{k}}$ تقریبی از ${{\nabla }^{2}}f\left( {{x}_{k}} \right)$ در نظر گرفته شود، یک روش شبه‌نیوتن خواهیم داشت. روش‌های شبه‌نیوتن را بعداً به‌تفصیل شرح خواهیم داد.
راه حل عملی آن است که در طی یک جستجوی خطی تقریبی و با یک روند کم‌هزینه‌تر دنباله‌ای از مقادیر $\alpha $ تولید کنیم تا جایی که شرط یا شرایط مشخصی برآورده شود و سپس فرآیند جستجو را متوقف کنیم. برای شروع ابتدا توجه کنید که از تعریف $\varphi $ نتیجه می‌شود: $$\varphi \left( 0 \right)=f\left( {{x}_{k}} \right),~~{\varphi }'\left( \alpha \right)=p_{k}^{t}\nabla f\left( {{x}_{k}}+\alpha {{p}_{k}} \right),~~{\varphi }'\left( 0 \right)=p_{k}^{t}\nabla f\left( {{x}_{k}} \right),$$
هم‌چنین از آن‌جا که ${{p}_{k}}$ جهت کاهشی است همواره داریم: ${\varphi }'\left( 0 \right)<0$. یعنی $\varphi $ در همسایگی صفر نزولی است. در ادامه برخی از شرایط متعارف برای پایان دادن به یک جستجوی خطی را معرفی می‌کنیم.
1. شرط آرمیژو: یک معیار عملی و متداول برای پایان بخشیدن به جستجوی خطی، قاعده‌ی آرمیژو است. این شرط برای کنترل کاهش کافی در تابع هدف می‌باشد و به‌صورت زیر بیان می‌شود:$$f\left( {{x}_{k}}+\alpha {{p}_{k}} \right)\le f\left( {{x}_{k}} \right)+\alpha {{c}_{1}}\nabla f{{\left( {{x}_{k}} \right)}^{t}}{{p}_{k}},~~~{{c}_{1}}\in \left( 0,1 \right),$$با توجه با تعریف $\varphi $ می‌توان شرط آرمیژو را به شکل ساده‌تر زیر نوشت:$$\varphi \left( \alpha \right)\le \varphi \left( 0 \right)+\alpha {{c}_{1}}{\varphi }'\left( 0 \right),~~~{{c}_{1}}\in \left( 0,1 \right).$$معمولاً ${{c}_{1}}={{10}^{-4}}$ در نظر گرفته می‌شود. هر چه ${{c}_{1}}$ به صفر نزدیک‌تر باشد بازه‌ی $\alpha $های قابل قبول بزرگ‌تر و هر چه ${{c}_{1}}$ به 1 نزدیک‌تر باشد بازه‌ی $\alpha $های قابل قبول کوچک‌تر می‌شود. از آن‌جا که ${\varphi }'\left( 0 \right)<0$ داریم ${{c}_{1}}{{\varphi }^{'}}\left( 0 \right)<0$ و بنابراین مجموعه‌ی$$\left\{ \alpha |~\varphi \left( \alpha \right)\le \varphi \left( 0 \right)+\alpha {{c}_{1}}{\varphi }'\left( 0 \right),{{c}_{1}}\in \left( 0,1 \right) \right\}$$ناتهی خواهد بود. در نتیجه شرط آرمیژو همواره کاهش کافی در $f$ ایجاد کرده و طول گام $\alpha $ را به‌دست می‌دهد. نقص این شرط آن است که طول گام‌های خیلی کوچک نیز در آن صدق می‌کنند. برای برطرف نمودن این مشکل شرط زیر معرفی می‌شود.
شرط انحنا: برای این‌که طول گام‌های خیلی کوچک $\alpha $ مورد قبول واقع نشود شرط دیگری به نام شرط انحنا را بر روی $\alpha $ اعمال می‌کنیم؛ بدین ترتیب که $\alpha $ باید در نابرابری$$\nabla f{{\left( {{x}_{k}}+\alpha {{p}_{k}} \right)}^{t}}{{p}_{k}}\ge {{c}_{2}}\nabla f{{\left( {{x}_{k}} \right)}^{t}}{{p}_{k}},~~~{{c}_{2}}\in \left( {{c}_{1}},1 \right),$$نیز صدق کند. می‌توان این شرط را به‌صورت ساده‌تر زیر نوشت:$${\varphi }'\left( \alpha \right)\ge {{c}_{2}}{\varphi }'\left( 0 \right),~~~{{c}_{2}}\in \left( {{c}_{1}},1 \right).$$شرط انحنا بیان می‌کند که اگر ${\varphi }'\left( \alpha \right)$ خیلی منفی باشد با پیش‌روی در امتداد جهت کاهشی می‌توان کاهش بیش‌تری در $f$ ایجاد نمود و اگر ${\varphi }'\left( \alpha \right)$ کم‌تر منفی و یا این‌که مثبت باشد با حرکت در امتداد جهت کاهشی امکان کاهش بیش‌تر $f$ وجود ندارد. بنابراین بهتر است حرکت متوقف شود.
2. شرایط ولف: ترکیب دو شرط آرمیژو و انحنا به‌عنوان شرایط ولف شناخته می‌شود؛ یعنی:$$\left\{ \begin{matrix}
f\left({{x}_{k}}+\alpha {{p}_{k}}\right)\le f\left({{x}_{k}} \right)+\alpha {{c}_{1}}\nabla f{{\left( {{x}_{k}}\right)}^{t}}{{p}_{k}},{{c}_{1}}\in \left( 0,1 \right), \\
\nabla f{{\left({{x}_{k}}+\alpha {{p}_{k}} \right)}^{t}}{{p}_{k}}\ge{{c}_{2}}\nabla f{{\left( {{x}_{k}}\right)}^{t}}{{p}_{k}},{{c}_{2}}\in \left( {{c}_{1}},1 \right). \\\end{matrix} \right.
$$یا به‌طور معادل: $$\left\{\begin{matrix} \varphi \left( \alpha \right)\le \varphi \left( 0 \right)+\alpha {{c}_{1}}{\varphi }'\left( 0 \right),{{c}_{1}}\in \left( 0,1 \right), \\{\varphi }'\left(\alpha \right)\ge {{c}_{2}}{\varphi }'\left( 0 \right),{{c}_{2}}\in \left( {{c}_{1}},1 \right). \\\end{matrix} \right.$$هر چه‌قدر ${{c}_{2}}$ به ${{c}_{1}}$ نزدیک‌تر باشد، بازه‌ی $\alpha $ های قابل قبول بزرگ‌تر و هر چه ${{c}_{2}}$ به 1 نزدیک‌تر باشد بازه‌ی $\alpha $های قابل قبول کوچک‌تر می‌شود. شرایط ولف نیز نقایصی دارد؛ ممکن است $\alpha $های صادق در این شرط، از کمینه‌ی $\varphi $ دور باشند؛ یعنی طول گام‌های مناسب را از دست بدهیم. برای برطرف نمودن این نقص شرایط قوی ولف معرفی می‌شوند.
3. شرایط قوی ولف: این شرایط به صورت زیرند: $$\left\{ \begin{matrix}
f\left({{x}_{k}}+\alpha {{p}_{k}} \right)\le f\left( {{x}_{k}} \right)+\alpha {{c}_{1}}\nabla f{{\left( {{x}_{k}} \right)}^{t}}{{p}_{k}},~~~{{c}_{1}}\in \left( 0,1 \right), \\
\left| \nabla f{{\left({{x}_{k}}+\alpha {{p}_{k}} \right)}^{t}}{{p}_{k}} \right|\le {{c}_{2}}\left| \nabla f{{\left( {{x}_{k}} \right)}^{t}}{{p}_{k}} \right|,~~~{{c}_{2}}\in \left( {{c}_{1}},1 \right). \\
\end{matrix} \right.
$$که می‌توان آن را به‌صورت ساده‌تر زیر نیز نشان داد:$$\left\{\begin{matrix}\varphi \left( \alpha \right)\le \varphi \left( 0 \right)+\alpha {{c}_{1}}{\varphi }'\left( 0 \right),~~{{c}_{1}}\in \left( 0,1 \right), \\ \left| {\varphi }'\left( \alpha \right) \right|\le {{c}_{2}}\left| {\varphi }'\left( 0 \right) \right|,~~~{{c}_{2}}\in \left( {{c}_{1}},1 \right). \\\end{matrix} \right.$$تنها تفاوت شرایط ولف و قوی ولف آن است که اجازه نمی‌دهیم $\left| {\varphi }'\left( \alpha \right) \right|$ زیاد مثبت شود. از این‌رو نقاطی که از نقاط ایستای $\varphi $ دور هستند در نظر گرفته نمی‌شوند.
قضیه: (ولف) فرض کنید $f:{{\mathbb{R}}^{n}}\to \mathbb{R}$ به‌طور پیوسته مشتق‌پذیر و ${{p}_{k}}$ یک جهت کاهشی در ${{x}_{k}}$ باشد. هم‌چنین فرض کنید $f$ در امتداد نیم‌خط $\left\{ {{x}_{k}}+\alpha {{p}_{k}}|\alpha >0 \right\}$ از پایین کراندار باشد. در این‌صورت اگر $0<{{c}_{1}}<{{c}_{2}}<1$ آن‌گاه بازه‌هایی از طول گام‌های صادق در شرایط ولف و قوی ولف وجود دارند.
4. شرایط گلدشتین: همانند شرایط ولف، شرایط گلدشتین تضمین می‌کنند که طول گام $\alpha $ کاهش کافی را در $f$ ایجاد کند اما زیاد کوچک نشود. این شرایط به‌صورت زیر بیان می‌شوند:$$f\left( {{x}_{k}} \right)+\alpha \left( 1-c \right)\nabla f{{\left( {{x}_{k}} \right)}^{t}}{{p}_{k}}\le f\left( {{x}_{k}}+\alpha {{p}_{k}} \right)\le f\left( {{x}_{k}} \right)+\alpha c\nabla f{{\left( {{x}_{k}} \right)}^{t}}{{p}_{k}},~~$$
که در آن $c\in \left( 0,1 \right)$. نابرابری نخست از سمت چپ برای کنترل طول گام به‌کار می‌رود و نامساوی دوم، همان شرایط آرمیژو است. شرایط گلدشتین به‌صورت ساده‌تر زیر قابل بیان هستند:$$\varphi \left( 0 \right)+\alpha \left( 1-c \right)\varphi '\left( 0 \right)\le \varphi \left( \alpha \right)\le \varphi \left( 0 \right)+\alpha c\varphi '\left( 0 \right),~~~c\in \left( 0,1 \right).$$
نقطه‌ی‌ضعف شرایط گلدشتین نسبت به شرایط ولف آن است که نابرابری سمت چپ (کنترل‌کننده‌ی طول گام) ممکن است برخی از کمینه‌های $\varphi $ را نادیده بگیرد. با این وجود، شرایط گلدشتین و ولف نقاط مشترک زیادی دارند و نظریه‌ی همگرایی آن‌ها کاملاً مشابه است. شرایط گلدشتین معمولاً در روش‌های نیوتن استفاده می‌شوند و استفاده از آن‌ها برای روش‌های شبه‌نیوتن، که معین مثبت بودن تقریب هسین در آن‌ها هدف اصلی است مناسب نیست.
الگوریتم پیمایش معکوس:
متذکر می‌شویم که شرط کاهش کافی (آرمیژو) به تنهایی برای اطمینان از این که الگوریتم در طی جهت جستجوی مورد نظر پیشرفت معقولی داشته باشد کافی نیست. با این وجود اگر الگوریتم جستجوی خطی مقادیر طول گام را متناسب با روش پیمایش معکوس انتخاب نماید، می‌توان شرایط اضافی (قسمت دوم شرایط ولف و قوی ولف) را کنار گذاشته و تنها از شرط کاهش کافی برای پایان دادن به جستجوی خطی استفاده نمود. الگوریتم پیمایش معکوس به قرار زیر است:
الگوریتم پیمایش معکوس همراه با شرط آرمیژو
1. طول گام اولیه $\bar{\alpha }>0$ و مقادیر $\rho \in \left( 0,1 \right)$ و $c\in \left( 0,1 \right)$ را انتخاب کنید. قرار دهید $\alpha =\bar{\alpha }$ .
2. تا زمانی که شرط کاهش کافی برقرار نیست، یعنی:$f\left( {{x}_{k}}+\alpha {{p}_{k}} \right)>f\left( {{x}_{k}} \right)+\alpha c\nabla f{{\left( {{x}_{k}} \right)}^{t}}{{p}_{k}},$ قرار دهید $\alpha =\rho \alpha $.
3. قرار دهید ${{\alpha }_{k}}=\alpha $ .
4. پایان.
معمولاً طول گام اولیه‌ی $\bar{\alpha }$ در روش‌های نیوتن و شبه‌نیوتن، برابر با 1 اختیار می‌شود. اما در الگوریتم‌های دیگر مانند تندترین کاهش و گرادیان‌های مزدوج می‌تواند مقادیر دیگری داشته باشد. طول گام قابل قبول پس از تعداد متناهی تکرار پیدا می‌شود؛ زیرا سرانجام ${{\alpha }_{k}}$ آن قدر کوچک می‌شود که در شرط کاهش کافی صدق نماید. ضریب انقباض $\rho $ را معمولاً $1/2~$ در نظر می‌گیرند که در عمل می‌تواند در هر تکرار به‌هنگام شود.
همگرایی روش‌های جستجوی خطی
برای دست‌یابی به همگرایی سراسری، علاوه بر این‌که باید طول گام‌های خوبی انتخاب کنیم، لازم است انتخاب‌های خوبی برای جهت جستجوی ${{p}_{k}}$ داشته باشیم. در این بخش به بحث درباره‌ی نیازمندی‌های جهت جستجو می‌پردازیم و روی این خاصیت کلیدی تمرکز می‌کنیم که زاویه‌ی ${{\theta }_{k}}$ بین ${{p}_{k}}$ و جهت تندترین کاهش $-\nabla f\left( {{x}_{k}} \right)$، به‌صورت زیر تعریف می‌شود:$$\cos {{\theta }_{k}}=-\frac{\nabla f{{\left( {{x}_{k}} \right)}^{t}}{{p}_{k}}}{\left\| \nabla f\left( {{x}_{k}} \right) \right\|{\left\| {p}_{k}\right\|}}(*)$$
قضیه: (زوتندیک) هر تکرار به شکل ${{x}_{k+1}}={{x}_{k}}+{{\alpha }_{k}}{{p}_{k}}$ را در نظر بگیرید که ${{p}_{k}}$ جهت جستجوی کاهشی و ${{\alpha }_{k}}$ صادق در شرایط ولف باشد. فرض کنید که $f$ در ${{\mathbb{R}}^{n}}$ از پایین کراندار و روی یک مجموعه‌ی باز $\mathcal{N}$ شامل مجموعه سطح $\mathcal{L}=\left\{ x~|~f\left( x \right)<f\left( {{x}_{0}} \right) \right\}$ به‌طور پیوسته مشتق‌پذیر باشد که ${{x}_{0}}$ نقطه‌ی شروع تکرار است. هم‌چنین فرض کنید که $\nabla f$ روی $\mathcal{N}$ پیوسته لیپشیتس باشد، یعنی ثابت $L>0$ موجود است به‌طوری که:$$\left\| \nabla f\left( x \right)-\nabla f\left( {\tilde{x}} \right) \right\|\le L\left\| x-\tilde{x} \right\|$$برای تمام $x,\tilde{x}\in \mathcal{N}$. آن‌گاه:$$
\underset{k\ge 0}{\mathop \sum }\,{{{\cos }^{2}}{{\theta }_{k}}\left\| \nabla f{{\left( {{x}_{k}} \right)}} \right\|^{2}}<\infty .$$رابطه‌ی اخیر شرط زوتندیک نامیده می‌شود.
چنان‌چه در قضیه‌ی قبل به جای شرط ولف از شرایط قوی ولف یا گلدشتین استفاده شود، نتیجه‌ی مشابهی برقرار است. توجه داریم که فرضیات قضیه‌ی فوق، چندان محدود کننده نیست. اگر تابع $f$ از پایین کراندار نباشد آن‌گاه مسئله‌ی بهینه‌سازی خوش‌تعریف نیست. هم‌چنین فرض همواری $f$ و پیوستگی لیپشیتس $\nabla f$، به‌وسیله‌ی بسیاری از شرایط همواری که در قضایای همگرایی موضعی استفاده می‌شوند، ایجاب می‌گردند.
از شرط زوتندیک نتیجه می‌شود که:$${{\cos }^{2}}{{\theta }_{k}}\left\| \nabla f{{\left( {{x}_{k}} \right)}} \right\|^{2}\to 0,~~k\to \infty $$از این حد می‌توان برای رسیدن به نتایج همگرایی سراسری الگوریتم‌های جستجوی خطی استفاده کرد. اگر روش‌های انتخاب جهت جستجوی ${{p}_{k}}$ این اطمینان را بدهند که زاویه‌ی ${{\theta }_{k}}$ حاده است، آن‌گاه ثابت $\delta >0$ موجود است که $\cos {{\theta }_{k}}\ge \delta >0$. بنابراین بلافاصله از رابطه‌ی قبل نتیجه می‌شود که:$$\underset{k\to \infty }{\mathop{\lim }}\,\nabla f\left( {{x}_{k}} \right)=0.$$
به عبارت دیگر می‌توانیم مطمئن باشیم که دنباله‌ی $\left\{ \nabla f\left( {{x}_{k}} \right) \right\}$ به صفر همگراست به شرطی که جهت جستجو زیاد به زیرفضای عمود بر بردار گرادیان نزدیک نباشد. در حالت خاص در روش تندترین کاهش (که در آن جهت جستجو با منفی گرادیان موازی است) دنباله‌ی گرادیان‌های همگرا به صفر تولید می‌شود به شرطی که از یک جستجوی خطی صادق در شرایط ولف یا گلدشتین استفاده کنیم. اصطلاح همگرایی سراسری در مورد الگوریتم‌هایی که نتیجه شرط برای آن‌ها برقرار باشد، استفاده می‌شود. اما توجه کنید که این اصطلاح گاهی اوقات در زمینه‌های دیگر با معنای متفاوتی به‌کار می‌رود. تا اینجا این نتیجه را به‌دست آورده‌ایم که روش تندترین کاهش، همگرایی سراسری دارد. حال جهت جستجوی ${{p}_{k}}=-{{\left( {{B}_{k}} \right)}^{-1}}\nabla f\left( {{x}_{k}} \right)$ را در نظر بگیرید که در آن ${{B}_{k}}$ ماتریسی معین مثبت است. اگر ${{B}_{k}}$ دارای عدد شرطی کراندار باشد، به این معنی که ثابت $M>0$ی چنان موجود باشد که برای تمام $k$ها، ${{B}_{k}}B_{k}^{-1}\le M$، آن‌گاه با توجه به رابطه‌ی (*) داریم: $$\cos {{\theta }_{k}}\ge \frac{1}{M},$$و در نتیجه از بحث قبل خواهیم داشت $\underset{k\to \infty }{\mathop{\lim }}\,\nabla f\left( {{x}_{k}} \right)=0$. از اینجا نتیجه می‌شود، زمانی که ${{B}_{k}}$ معین مثبت و دارای عدد شرطی کراندار باشد روش‌های نیوتن و شبه‌نیوتن همگرایی سراسری دارند به شرطی که طول گام در شرایط ولف صدق کند. برای بعضی از الگوریتم‌ها مانند روش گرادیان مزدوج، می‌توان از نتیجه‌ی ضعیف‌تر $\underset{k\to \infty }{\mathop{\liminf}}\,\nabla f\left( {{x}_{k}} \right)=0$ استفاده کرد و همگرایی سراسری روش را نشان داد. برای مشاهده‌ی جزئیات کتاب بهینه‌سازی عددی نوسدال و رایت را ببینید.
خلاصه مطالب تاکنون
ما ابتدا، ضرورت و پیشینه‌ی روش‌های بهینه‌سازی نامقید را بیان نمودیم. سپس نظریه‌ی الگوریتمی بهینه‌سازی نامقید را مورد بحث قرار دادیم و دیدیم که برای حل عددی یک مسئله‌ی بهینه‌سازی نامقید به دو پارامتر اساسی جهت جستجو و طول گام حرکت نیاز داریم و با توجه نحوه‌ی انتخاب این پارامترها، دو راهبرد جستجوی خطی و ناحیه‌ی مطمئن را بیان کردیم. همان‌گونه که گفتیم، در این آموزش رویکرد جستجوی خطی را مدنظر قرار خواهیم داد. سپس، روش‌های تندترین کاهش، نیوتن و گرادیان مزدوج را برای تعیین جهت جستجو معرفی کردیم. در اینجا، چند نکته را در رابطه با این روش‌ها بیان می‌کنیم. در اولین نگاه، ممکن است روش تندترین کاهش را بهترین روش کمینه‌سازی بدانیم. زیرا هر جستجوی خطی در «بهترین» سویش آغاز می‌شود. ولی متأسفانه، سوی تندترین کاهش یک خاصیت موضعی است و نه کلی، و تغییرات سویی زیادی که غالباً لازم‌اند، روش را در بسیاری از موارد ناکارا می‌سازند. همگرایی روش تندترین کاهش از مرتبه 1 است و بنابراین روش بسیار کندی است. روش نیوتن اگر همگرا باشد، دارای مرتبه‌ی همگرایی 2 است و بنابراین بسیار سریع است. اما این روش مستلزم محاسبه‌ی معکوس یک ماتریس $n\times n$ در هر گام است که ممکن است محاسبات پرهزینه‌ای داشته باشد؛ هم‌چنین همگرایی آن به نقطه‌ی شروع بستگی دارد. روش گرادیان مزدوج نسبت به روش تندترین کاهش کارآمدتر بوده و محاسبات ساده‌ای دارد. این روش از روش‌های نیوتن و شبه‌نیوتن سریع‌تر نیست، اما در آن نیازی به ذخیره‌سازی ماتریس‌ها نداریم. در ادامه روش‌های تعیین طول گام و الگوریتم پیمایش معکوس را بیان کردیم. معمولاً شرط آرمیژو به دلیل آن‌که همواره طول گام را به‌دست می‌دهد مورد استفاده قرار می‌گیرد. در انتها، درباره‌ی همگرایی روش‌های جستجوی خطی بحث نمودیم و نحوه‌ی به‌کارگیری شرط زوتندیک در همگرایی این روش‌ها را بیان کردیم. در آموزشهای بعد، به بررسی روش‌های شبه‌نیوتن خواهیم پرداخت.
nasrin