\documentclass{thesis}
%\usepackage{setspace,xargs}
% برای فاصله گذاری استاندارد بین خطوط و دستورات با چند آرگومان اختیاری
\usepackage{amsthm,amssymb}
\usepackage{amsmath}
\usepackage{arydshln}
\usepackage{tikz}
% فونت‌ها، نمادها و محیط‌های ams
\usepackage{float}
\usepackage{fancyhdr}
%\usepackage [pagebackref=true, colorlinks, linkcolor=blue, citecolor=magenta, urlcolor=cyan] {hyperref}
% چنانچه قصد پرینت گرفتن نوشته خود را دارید، خط بالا را غیرفعال و  از دستور زیر استفاده کنید. در ضمن pagebackref برای نشان دادن شماره صفحه ارجاعات مراجع در بخش bibliography است.
\usepackage[pagebackref=false]{hyperref}
\hypersetup{
pdftitle={بهینه‌سازی بی‌مشتق},
pdfauthor={sara shahriari},
pdfsubject={پروژه کارشناسی},
pdfkeywords={keywords},
pdfdirection={R2L}
}
\usepackage{graphicx,xcolor}
\usepackage{tabularx}
%%%%%%%%%%%%%%%%%%%%%
% اضافه کردن مراجع و نمایه به فهرست مطالب
\usepackage[textfont=it]{caption}
\usepackage[nottoc]{tocbibind} 
\usepackage{titlesec}
%\usepackage[usenames , dvipsnames]{color , xcolor}
\usepackage{listings}
\usepackage{hyperref} 
\usepackage{titlesec}
\usepackage{multirow} 

\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{setspace}

\usepackage{xepersian}

\settextfont[Scale=1.1]{B Nazanin}
%\setdigitfont[Scale=1.1]{XB Zar}
%\setlatintextfont[ExternalLocation,BoldFont={lmroman10-bold},BoldItalicFont={lmroman10-bolditalic},ItalicFont={lmroman10-italic}]{lmroman10-regular}
\setlatintextfont{Times New Roman}
%\defpersianfont\nastaliq[Scale=2]{IranNastaliq}
%\defpersianfont\titr[Scale=1]{B Titr}
%\defpersianfont\traffic[Scale=1]{B Traffic}

\newtheorem{theorem}{قضیه}
\newtheorem{lemma}{لم}
\newtheorem{proposition}{گزاره}
\theoremstyle{definition}
\newtheorem{definition}{تعریف}
%\theoremstyle{remark}{تبصره}
\newtheorem{corollary}{نتیجه}
\newtheorem{remark}{ملاحظه}

\renewcommand{\algorithmicif}{\textbf{اگر}}
\renewcommand{\algorithmicthen}{\textbf{آنگاه}}
\renewcommand{\algorithmicelse}{\textbf{وگرنه}}
\renewcommand{\algorithmicprint}{\textbf{چاپ کن}}
\renewcommand{\algorithmicendif}{\textbf{پایان شرط}}
\renewcommand{\algorithmicrepeat}{\textbf{تکرار کن}}
\renewcommand{\algorithmicend}{\textbf{پایان}}


\headheight = 20pt
\pagestyle{plain}
\fancyhf{}
%\doublespacing
\allowdisplaybreaks[1]


\begin{document}
\vfill
\vspace*{1cm}
%\hspace*{1cm}
\begin{center}
\includegraphics[scale=1]{bsm3.jpg}
\end{center}
\vfill

\university{دانشگاه صنعتی شریف}
\department{دانشکده علوم ریاضی}
\subject{ نگارش }
%\type{پروژه کارشناسی}
\field{پروژه کارشناسی}
\title{ بهینه‌سازی بی‌مشتق}
% اگر عنوان پایان‌نامه شما طولانی است می‌توانید بخشی از آن را در قسمت زیر وارد کنید. 
%\tit{در حل معادله‌های روزنا-برگرز}
%%تاریخ دفاع
%\newcommand{\repdate}{$\ \ 93 / \  6/ \  23$}
%%زمان دفاع
%\reptime{ یک‌‌شنبه \hspace{5pt} \repdate ساعت\ \space $8$   صبح}
%%محل دفاع
%\repplace{سالن خوارزمی دانشکده علوم ریاضی}
\supervisor{دکتر نظام‌الدین مهدوی‌امیری}
%\advisor{ دکتر ....}
%\mrmiss{خانم}
%%جنسیت نویسنده
\author{سارا شهریاری}
%%داور اول
%\refreeA{ دکتر ...}
%%داور دوم
%\refreeB{ دکتر ...}
%%سرپرست تحصیلات تکمیلی
%\DGC{دکتر ... }
\thesisdate{ ۱۳۹6}

%\approval
%\makefatitle
%\makethat
%  Acknowledgement & Rights ______________________________________
%\input{./chapters/acknowledge}
%
\newpage
\thispagestyle{empty}
 \thispagestyle{plain}\mbox{}\clearpage
  
 سپاس بی‌کران پروردگار یکتا را که هستی‌مان بخشید و به طریق علم و دانش رهنمونمان شد و به همنشینی رهروان علم و دانش مفتخرمان نمود و خوشه‌چینی از علم و معرفت را روزیمان ساخت.
 \vspace{2cm}
 
 از استاد گرامیم جناب آقای دکتر نظام‌الدین مهدوی‌امیری بسیار سپاسگزارم چرا که بدون راهنمایی‌های ایشان نگارش این اثر بسیار مشکل می‌نمود. 
 \vspace{2cm}
 
 
\begin{LTR}
شهریاری سارا

 1396
\end{LTR}
 
\tableofcontents

\chapter*{چکیده} \addcontentsline{toc}{chapter}{چکیده} 
بسیاری از نرم‌افزارهای کاربردی به بهینه‌سازی توابعی نیاز دارند که مشتق‌های آن‌ها در دسترس نیست. این دسته از مسائل را می‌توان با تقریب گرادیان تابع، که با استفاده از تفاضلات متناهی محاسبه می‌شود، حل کرد. گرچه به کارگیری تفاضلات متناهی در برخی مسائل تاثیرگذار است، نمی‌توان از آن به عنوان یک روش کلی در حل مسائل بی‌مشتق یاد کرد چون در صورت نامعلوم بودن تابع، تخمین آن از روش‌های عددی  با خطا همراه خواهد بود درنتیجه تقریب گرادیان دقت کافی نخواهد داشت. از طرفی در دسترس بودن تابع نیز در نرم‌افزارها با مشکلاتی همچون زمان زیاد محاسبه گرادیان مواجه است. \\
به همین دلیل تاکنون روش‌های متعددی بدون نیاز به تقریب گرادیان تابع گسترش یافته‌اند. در این روش‌ها به جای تقریب گرادیان از مقدار تابع در مجموعه‌ای از نقاط دامنه برای تعیین گام بعدی استفاده می‌شود و تفاوت آن‌ها در نحوه استفاده از مقادیر تابع در مجموعه نقاط مورد استفاده است. 
برخی از این روش‌ها عبارتند از:روش مبتنی بر مدل($model-based \,\,method$)، روش نلدر-مید($Nelder-Mead\,\, method$)، روش جستجوی مبتنی بر الگو($pattern-search \,\,method$)، و روش مسیرهای مزدوج($conjugate-direction \,\,method$) .\\
در این گزارش به بررسی این روش‌ها برای مسائل بهینه‌سازی نامقید  
\begin{equation}
min_{x \in \mathbb{R}^n} f(x)
\end{equation}
خواهیم پرداخت که در آن  $f(x)$ تابعی هموار با مشتقات پیوسته است . \\ 

باید توجه داشت که روش‌های بهینه‌سازی بی‌مشتق مانند روش‌های مبتنی بر گرادیان پیشرفته چندانی نداشته‌اند و تنها برای مسائل کوچک با قیدهای ساده، مانند کران‌ها، نتایج خوبی ارائه می‌کنند. 
\chapter{مفاهیم اولیه}
\begin{definition}
اگر تابع $f(x)$ از حل معادله دیفرانسیل یا مسیرهای عددی پیچیده دیگری حاصل شود، خطاهای کوچک و ناصفر که در جریان محاسبات استفاده شده‌اند در مقدار تابع $f$ اختلال ایجاد می‌کنند. در این حالت تابع $f$ به صورت زیر است
\begin{equation}
f(x)=h(x) + \phi (x)
\end{equation}
که در آن $h$ تابعی هموار و $\phi$ بیانگر اختلال است. این طرح از تابع برای شرح دادن مشکلات ایجاد شده توسط اختلال و گسترش الگوریتم‌های بهینه‌سازی بی‌مشتق بسیار کاربردی است. 
\end{definition}
\begin{definition}
برای تابع اختلال $\phi$ در مکعبی به مرکز $x$ و طول اضلاع $2\epsilon$ تراز اختلال $\eta$ تعریف می‌شود
\begin{equation}
\eta(x;\epsilon) = sup_{||z-x||_{infty} \leq \epsilon} |\phi(z)|.
\end{equation}
\end{definition}

\chapter{روش‌های بهینه‌سازی بی‌مشتق}
در این فصل ابتدا  برخی روش‌های کاربردی در زمینه بهینه‌سازی بی‌مشتق از لحاظ نظری بررسی می‌شوند، سپس الگوریتم‌های تدوین شده ارائه خواهند شد.
\section{تفاضلات متناهی و اختلال}
   یک روش بهینه‌سازی بی‌مشتق که در اولین برخورد با مسائل مورد توجه قرار می‌گیرد، تقریب گرادیان با استفاده از تفاضلات متناهی و به کار بستن یک روش مبتنی بر گرایان است.  \\
   برای بازه تفاضل داده شده  $\epsilon$ تقریب تفاضلات متناهی مرکزی برای گرادیان $f$ در $x$ به صورت زیر تعریف می‌شود
\begin{equation}
\nabla_{\epsilon} f(x) = [\frac{f(x+\epsilon e_{i}) - f(x-\epsilon e_{i})}{2\epsilon}]_{i=1,2,...,n} ,
\end{equation}
که در آن    $e_{i}$       ،
   $i$  
  امین بردار یکه است (برداری که تنها عضو ناصفر آن $1$  درجایگاه  $i$ ام است).
 هدف یافتن ارتباطی میان $\nabla_{\epsilon} f(x)$ و گرادیان تابع هموار $h(x)$ است. به این منظور با بهره‌گیری از تراز اختلال $\phi$ و رابطه تفاضل مرکزی (1.2) نتیجه زیر حاصل می‌شود.
\begin{lemma}
فرض کنید  $\nabla^2h$  در یک همسایگی از  $\{z| ||z-x||_{\infty} \leq \epsilon\}$  با ثابت لیپ‌شیتس  $L_{h}$ پیوسته لیپ‌شیتس باشد، آنگاه خواهیم داشت
\begin{equation}
||\nabla_{\epsilon}f(x) - \nabla h(x)||_{infty} \leq L_{h} \epsilon^2 + \frac{\eta(x;\epsilon)}{\epsilon}.
\end{equation}
\end{lemma}
بنابراین خطا در تقریب (1.2) از خطای تقریب تفاضلات متناهی و اختلال (عنصر  $\frac{\eta(x;\epsilon)}{\epsilon} $ ) سرچشمه می‌گیرد و اگر میزان اختلال از $\epsilon$ بیشتر شود، نمی‌توان از تقریب $\nabla_{\epsilon} f(x)$  انتظار دقت داشت.
برای بهبود روش به جای محاسبه مقادیر  تابع حول نقطه مورد نظر در هر تکرار، که در تقریب گرادیان با تفاضلات متناهی مورد نیاز است، از این نقاط برای ساخت تقریبی از تابع هدف بهره می‌بریم. این ترفند، که در بخش بعد بررسی می‌کنیم، در حضور اختلال بهتر عمل می‌کند.
\section{روش‌های مبتنی بر تقریب}
روش‌های مبتنی بر تقریب،
 \footnote{$Model-Based  Method$}
  دسته‌ای از تاثیرگذارترین الگوریتم‌ها برای بهینه‌سازی نامقید الگوریتم‌هایی هستند که گام‌های آن با کمینه کردن یک تقریب درجه دوم از تابع هدف  $f$ دنبال می‌شود.
این تقریب با استفاده از اطلاعات حاصل از تابع و مشتق آن تشکیل می‌شود. 

فصل 8
\\
هنگامی که مشتقات در دسترس نباشند، تقریب  $m_{k}$ را به عنوان تابع درجه دومی که  $f$ را در مجموعه مناسبی از نقاط منتخب درونیابی می‌کند. چون تقریب حاصل از این روش معمولا محدب نیست، روش مبتنی بر گرادیان در این مبحث از روش ناحیه اعتماد برای حل تقریب تابع و محاسبه طول گام استفاده می‌کند. در ادامه به توصیف روش می‌پردازیم

فرض کنید در  تکرار $x_{k}$ مجموعه‌ای از نقاط نمونه 
$Y=\{y^1,y^2,...,y^q\}$
که در آن $ y^i \in \mathbb{R}^n $  و  $i=1,2,...,q $ در دست است.
هم‌چنین قرض کنید $x_{k}$ عضوی از این مجموعه است به طوری که هیچ نقطه‌ای در مجموعه $Y$ دارای مقدار تابع کم‌تر از $x_{k}$  نباشد. تابع تقریبی درجه دوم مورد نظر به صورت زیر است
\begin{equation}
m_{k}(x_{k}+p)=c+g^Tp+\frac{1}{2}p^TGp.
\end{equation}
که در آن  $g=\nabla f(x_{k})$  و $G=\nabla^2f(x_{k})$  غیر قابل تعریف‌اند چون مشتقات تابع در دسترس نیست. جایگزین این مقادیر، ثابت $c$، بردار $g \in \mathbb{R}^n$ و ماتریس متقارن $G \in \mathbb{R}^{n \times n}$  است که از حل دستگاه حاصل از برقراری شرایط درونیابی 
\begin{equation}
m_{k}(y^l)= f(y^l),  \quad \quad l=1,2,...,q.
\end{equation}
به دست می‌آیند.
با توجه به  $\frac{1}{2}(n+1)(n+2)$   عضو نامعلوم در تقریب (3.2) ($c$ یک، بردار $g$، $n$ و ماتریس متقارن $G$ با فرض تقارن  $\frac{(n+1)(n+2)}{2}$ عضو نامعلوم دارند)، شرایط درونیابی (4.2)، $m_{k}$  را به صورت یکتا مشخص می‌کنند اگر 
\begin{equation}
q=\frac{1}{2}(n+1)(n+2).
\end{equation}
در این حالت (4.3)، به صورت یک دستگاه خطی مربعی از معادلاتی برحسب متغیرهای تقریب نوشته می‌شود. اگر مجموعه نقاط $y^1,y^2,...,y^q$ به گونه‌ای انتخاب شوند که دستگاه خطی حاصل ناتکین شود، تقریب  $m_{k}$  به صورت یکتا تعیین می‌شود.

س از تشکیل $m_{k}$، با حل تقریبی زیر مسئله ناحیه اعتماد 
\begin{equation}
min_{p} m_{k}(x_{k}+p), \quad \quad subject \quad to \quad ||p||_{2} \leq \Delta ,
\end{equation}
برای برخی شعاع ناحیه اعتماد $\Delta \geq 0$گام $p$ محاسبه می‌شود. برای حل این زیر مسئله از روش نقطه کوشی بهره می‌گیریم.

روش کوشی

پس از به کارگیری روش نقطه کوشی، اگر $x_{k}+p$
کاهش مناسبی در تابع هدف ایجاد کند، در تکرار بعد نقطه جدید به صورت   $x_{k+1}=x_{k}+p$  تعریف و شعاع ناحیه اعتماد به روز می‌شود. درغیراینصورت به نقطه جدید منتقل نمی‌شویم و با تغییر مجموعه $Y$ یا کاهش شعاع ناحیه اعتماد الگوریتم ادامه می‌یابد.

برای کاهش هزینه‌های محاسباتی در الگوریتم، در هر تکرار به روز کردن تقریب  $m_{k}$، جایگزین محاسبه مجدد آن می‌شود. برای به کار بستن این ایده، پایه‌ مناسبی برای فضای چندجمله‌ای های درجه دو (با استفاده از چندجمله‌ای های نیوتنی یا لاگرانژی) انتخاب می‌کنیم. ویژگی این پایه‌ها به انتخاب مجموعه $Y$ و در ضورت نیاز تغییر آن کمک بسیاری می‌کند. الگوریتم کاملی که تمام این شرایط را دارا باشد بسیار پیچیده است. در ادامه به شرح مختصری از الگوریتم روش مبتنی بر تقریب  می‌پردازیم.\\ 
باید توجه داشت مانند الگوریتم‌های ناحیه اعتماد، در هر گام پذیرش نقطه جدید و به‌هنگام سازی ناحیه اعتماد براساس نسبت کاهش تابع هدف به کاهش تقریب تابع که به صورت 
\begin{equation}
\rho=\frac{f(x_{k})-f(x_{k}^+)}{m_{k}(x_{k})-m_{k}(x_{k}^+)},
\end{equation}
است انجام می‌گیرد.

\begin{algorithm}[h]
\caption{(روش بی‌مشتق مبتنی بر تقریب)} 
\begin{algorithmic}[1]
\REQUIRE یک مجموعه درونیابی $Y$ 
به طوری که دستگاه خطی (4.2) ناتکین باشد، $x_{0}$ نقطه‌ای درون این مجموعه به طوری که
 $f(x_{0}) \leq f(y^i)$
برای هر  $y^i \in Y$
. شعاع اولیه ناحیه اعتماد $\Delta_{0}$، یک ثابت $\eta \in (0,1)$ و قرار دهید $k=0$.    \\
 \STATE مادامی که شرط همگرایی برقرار نشده است تکرار کن 
  \STATE \quad           تقریب درجه دوم $m_{k}(x_{k}+p)$ صادق در (4.2) را تشکیل بده.
  \STATE \quad           با حل تقریبی زیر مسئله (6.2) گام $p$ را محاسبه کن.
  \STATE \quad          نقطه جدید را به صورت  $x_{k}^+ = x_{k}+p$ تعریف کن.
  \STATE \quad       نسبت $\rho$ تعریف شده در (7.2) را محاسبه کن.
  \STATE \quad         اگر {$\rho \geq \eta$} 
  \STATE \quad \quad   یکی از اعضا  $Y$ را با  $x_{k}^+$ جایگزین کن.
  \STATE \quad \quad      یک شعاع   $\Delta_{k+1} \geq \Delta_{k}$  انتخاب کن.
  \STATE \quad \quad      قرار ده .$x_{k+1} \leftarrow x_{k}^+$
  \STATE \quad \quad      قرار ده $k \leftarrow k+1$  و به تکرار بعد برو.
  \STATE \quad   وگرنه
  \STATE \quad \quad       یک شعاع  $\Delta_{k+1} < \Delta_{k}$ انتخاب کن.
  \STATE \quad \quad       قرار ده .$x_{k+1} \leftarrow x_{k}$
  \STATE \quad \quad        قرار ده $k \leftarrow k+1$  و به تکرار بعد برو.
  \STATE \quad    پایان  شرط
\\
 روندی برای به‌هنگام $Y$ با هدف بهبود عدد حالت (4.2):
  \STATE \quad     قرار ده   .$\Delta_{k+1} \leftarrow \Delta_{k}$
  \STATE  \quad    $\hat{x}$ را به عنوان عضوی از $Y$ با کم‌ترین مقدار تابع انتخاب کن.
  \STATE  \quad     قرار بده $x_{k}^+ \leftarrow \hat{x}$  و  $\rho$ را با استفاده از (7.2) دوباره محاسبه کن.
  \STATE \quad     اگر {$\rho \geq \eta$} 
  \STATE \quad \quad      قرار ده .$x_{k+1} \leftarrow x_{k}^+$
  \STATE  \quad   وگرنه
  \STATE \quad \quad       قرار ده .$x_{k+1} \leftarrow x_{k}$
  \STATE \quad  پایان شرط
  \STATE \quad   قرار بده .$k \leftarrow k+1$
  \STATE پایان تکرار
\end{algorithmic}
\end{algorithm}
\newpage
در حالت$\rho \geq \eta$ ، که در آن کاهش متاسبی در تابع رخ داده است، نقطه  به عنوان نقطه جدید پذیرفته می‌شود. $x_{k}^+$ به مجموعه $Y$ افزوده و یک عضو از آن حذف می‌شود. هرگاه کاهش کافی حاصل نشود    $(\rho < \eta)$ ، دو علت در این شرایط قابل بررسی است:\\
نامناسب بودن مجموعه درونیابی $Y$ و بزرگ بودن ناحیه اعتماد. مورد اول زمانی رخ می‌دهد که تکرارهای الگوریتم در فضایی با بعد کمتر از$\mathbb{R}^n $  
و فاقد جواب  محصور و به یک نقطه مینیمم‌کننده در همین زیرفضا همگرا می‌شود. چنین رفتاری با بررسی عدد حالت ماتریس حاصل از دستگاه خطی (4.2) قابل تشخیص است. اگر عدد حالت ماتریس بیشتر از حد مشخص شده باشد یکی از اعضا مجموعه $Y$ با عضوی جدید جایگزین می‌شود. در ضورتی که مجموعه $Y$ مناسب باشد، علت دوم دخیل است. با کاهش شعاع ناحیه اعتماد الگوریتم ادامه می‌یابد.

استفاده از تقریب درجه دوم توابع تعداد مسائلی که در عمل قابل حل هستند را کاهش می‌دهد. اجرای $O(n^2)$ تخمین تابع برای شروع الگوریتم،حتی برای تعداد تخمین کم $(n=50)$ ،بسیار زمان‌بر و مشکل است. علاوه بر این هزینه تخمین تابع با وجود به‌هنگام کردن تقریب $m_{k}$ در هر تکرار بالاست. برای کاهش مشکلات می‌توان تقریب درجه دو را با یک تقریب خطی جایگزین کرد به طوری که ماتریس $G$ در (3.2) صفر در نظر گرفته می‌شود. این تقریب دارای $n+1$ متغیر است و الگوریتم با هزینه کمتری قابل اجراست. باید توجه داشت این الگوریتم‌ها همگرایی سریعی ندارند.

\subsection{درونیابی و پایه‌های چندجمله‌‌ای} 
اکنون با جزییات بیشتر چگونگی تشکیل تقریب درجه دو از تابع هدف با استفاده از روش‌های درونیابی را بررسی می‌کنیم. ابتدا یک تقریب خطی به صورت
\begin{equation}
m_{k}(x_{k}+p) = f(x_{k}) + g^Tp.
\end{equation}
در نظر می‌گیریم.
برای تعیین بردار $g \in \mathbb{R}^n$ ، شرایط درونیابی $m_{k}(y^l)=f(y^l),l=1,2,...,n$ را برقرار می‌کنیم. این شرایط با تساوی زیر معادل است
\begin{equation}
(s^l)^Tg = f(y^l) - f(x_{k}), \quad \quad l=1,2,...,n
\end{equation}
که در آن 
\begin{equation}
s^l = y^l - x_{k}, \quad \quad  l=1,2,...,n.
\end{equation}
حال چگونگی ساخت یک تقریب درجه دو به صورت (3.2) برای تابع $f=f(x_{k})$ را دنبال می‌کنیم. تقریب مانند تساوی زیر بازنویسی می‌کنیم
\begin{align}
m_{k}(x_{k}+p) = f(x_{k}) + g^Tp + \sum_{i<j}G_{ij}p_{i}p_{j} + \frac{1}{2} \sum_{i}G_{ii}p_{i}^2 
\end{align}
\begin{align}
\overset{def}{=} f(x_{k}) + \hat{g}^T\hat{p}.
\end{align}
که در آن عناصر $g$ و $G$ در یک بردار با  $(q-1)$ عضو نامعلوم  به صورت
\begin{align}
\hat{g} \equiv \Big(g^T, \{G_{ij}\}_{i<j}, \Big\{ \frac{1}{\sqrt(2)} G_{ii}\Big\}\Big)^T,
\end{align}
کنار هم آورده شده‌اند و بردار $(q-1)$ عضوی  $\hat{p}$ به شکل زیر تعریف می‌شود
\begin{align}
\hat{p} \equiv \Big( p^T, \{p_{i}p_{j}\}_{i<j}, \Big\{ \frac{1}{\sqrt(2)} p_{i}^2\Big\}\Big)^T.
\end{align}
تقریب (12.2) ساختاری مشابه (8.2) دارد و عناصر نامعلوم $\hat{g}$ در حل مسائل با حالت خطی حاصل می‌شوند.

با در نظر گرفتن $\{ \phi_{i}(.)\}_{i=1}^q$ به عنوان پایه‌ای برای فضای خطی توابع درجه دو $n$بعدی، تابع (8.2) را می‌توان برای برخی ضرایب $\alpha_{i}$ به صورت زیر بیان کرد 
\begin{align}
m_{k}(x)= \sum_{i=1}^q \alpha_{i} \phi_{i}(x).
\end{align}
اگر دترمینان ماتریس 
\begin{align}
\sigma(Y) \overset{def}{=} det 
\end{align}
ناصفر باشد، مجموعه درونیابی  $Y=\{y^1,y^2,...,y^q\}$ ضرایب $\alpha_{i}$ را به طور یکتا تعیین می‌کند.
\subsection{به‌هنگام مجموعه درونیابی}
به‌هنگام مجموعه درونیابی $Y$ یکی از گزینه‌های حل مشکل نبود کاهش مناسب در تابع است. در این روش، هدف تعویض یکی از اعضا مجموعه است به طوری که دترمینان (16.2) افزایش یابد. به این منظور از ویژگی توابع لاگرانژی برای $\sigma(Y)$ استفاده می‌کنیم. 

برای هر $y \in Y$ تابع لاگرانژی $L(.,y)$ چندجمله‌ای از درجه حداکثر دو است به طوری که  $L(y,y)=1$  و $L(\hat{y},y)=0$  برای $\hat{y} \neq y , \hat{y} \in Y$.
حال فرض کنید مجموعه $Y$ با جایگزین کردن $y_{-}$ با عضوی دیگر مانند $y$  به‌هنگام و مجموعه $Y^{+}$ حاصل شود. می‌توان نشان داد (تحت شرایط خاص [256])
\begin{align}
|\sigma (Y^{+})| \leq |L(y_{+}, y_{-})| |\sigma (Y)|.
\end{align}
الگوریتم 1 می‌تواند به خوبی برای به‌هنگام مجموعه درونیابی از این نامساوی بهره ببرد. ابتدا حالتی را در نظر بگیرید که نقطه جدید   $x^{+}$ 
کاهش مناسبی در تابع هدف ایجاد کند $(\rho \geq \eta)$. نقطه $x^{+}$ را به $y$  اضافه و نقطه دیگری مانند $y_{-}$ را از $y$  حذف می‌کنیم. با استفاده از (17.2) نقطه مناسب برای خروج از مجموعه به صورت زیر انتخاب می‌شود
\begin{align}
y_{-} = argmax_{y \in Y} |L(x^{+},y)|.
\end{align}
حالت دوم زمانی است که کاهش ایجاد شده در تابع مناسب نباشد $(\rho < \eta)$
. ابتدا نیاز یا عدم نیاز مجموعه $Y$  به بهبود را مشخص می‌کنیم و برای این هدف از قانون زیر استفاده می‌کنیم

اگر برای هر $y^i \in Y$ به طوری که $||x_{k}-y^i|| \leq \Delta$ نتوان $ |\sigma (Y)|$ را با جایگزین کردن یکی از اعضا این مجموعه با نقطه دلخواه  $y$در ناحیه اعتماد افزایش داد، در نقطه $x_{k}$ مجموعه $Y$ مناسب است. به علاوه اگر  $Y$ مناسب باشد و کاهش مورد نظر در تابع رخ ندهد، شعاع ناحیه اعتماد را کاهش می‌دهیم و تکرار جدیدی را شروع می‌کنیم.

\section{روش‌های جستجوی مختصاتی و الگویی}
روش‌های جستجوی مختصاتی و جستجوی الگویی برخلاف روش مبتنی یر تقریب تابع، در هر تکرار در جستجوی یافتن مسیرهایی برای یافتن نقاط با مقدار تابع کمتر هستند. اگر این نقطه یافت شود، الگوریتم به این نقطه منتقل و تکرار بعد شروع می‌شود. اگر نقطه جدید کاهش خوبی در تابع ایجاد نکند، طول گام در راستای مسیرهای جستجو تنظیم می‌شود، یا مسیرهای جستجوی جدید انتخاب می‌شوند.

ابتدا روشی ساده را که در عمل کاربرد دارد دنبال می‌کنیم. سپس روش کلی که از ویژگی‌های تئوری قوی‌تر برخوردار است بیان می‌کنیم.
\subsection{روش جستجوی مختصاتی}
روش جستجوی الگویی (روش کاهش مختصاتی) با حرکت دورانی از طریق $n$
مسیر  $e_{1},e_{2},...,e_{n}$  و با انجام جستجوی خطی در راستای هر مسیر نقاط جدیدی برای تکرار بعد فراهم می‌کند. در تکرار اول تمام مولفه‌های  $x$ جز $x_{1}$ ثابت در نظر گرفته می‌شوند و برای این مولفه مقداری را می‌یابیم که تابع هدف را مینیمم کند(یا حداقل کاهش دهد). در تکرارهای بعدی همین روند برای مولفه‌های دیگر تکرار می‌شود. بعد از $n$ تکرار به متغیر اول می‌رسیم و این روند دورانی ادامه می‌یابد. گرچه اجرای این روش ساده است، در عمل می‌تواند بسیار ناکارآمد باشد. در حالت کلی روش جستجوی مختصاتی بدون رسیدن به نقطه‌ای که در آن گرادیان تابع به صفر میل کند، حتی با استفاده از جستجوی خطی دقیق، می‌تواند تا بی‌نهایت ادامه یابد. 
زمانی که روش جستجوی مختصاتی به نقطه‌ای همگرا می‌شود، همگرایی آن بسیار آهسته‌تر از روش بیشترین شیب است. تشخیص تفاوت این دو روش با افزایش تعداد متغیرها آسان‌تر خواهد بود. به علاوه، با افزایش تعداد متغیرها روش جستجوی مختصاتی کاربرد بیشتری خواهد داشت چون این روش نیازی به محاسبه $\nabla f_{k}$ ندارد.

تاکنون گونه‌های متفاوتی از روش جستجوی مختصاتی ارائه و همگرایی سراسری آن‌ها ثابت شده است. یک نمونه ساده از این روش "پس و پیش" \footnote{"back and forth"} است که در آن جستجو در راستای مسیرهای زیر صورت می‌گیرد
\begin{align}
e_{1}, e_{2}, ..., e_{n-1}, e_{n}, e_{n-1}, ... , e_{2}, e_{1}, e_{2},...
\end{align}
روش جستجوی الگویی نسخه‌ای کامل‌تر از جستجوی محتصاتی است، چون از مسیرهای جستجوی بیشتری در هر تکرار بهره می‌برد. در بخش بعد به بررسی این روش می‌پردازیم.
\subsection{روش‌های جستجوی الگویی}
 روش جستجوی الگویی در هر تکرار و در نقطه مورد نظر $(x_{k})$  یک مجموعه مشخص از مسیرهای جستجو انتخاب می‌کند و در طول گام داده شده در راستای هریک از مسیرها مقدار $f$ را در هر نقطه تخمین می‌زند. نقاط روی مسیرهای جستجو اطراف  $x_{k}$ یک چهارچوب حول این نقطه شکل می‌دهند. اگر بین این نقاط، نقطه‌ای با مقدار تابع هدف کم‌تر یافت شود به عنوان نقطه جدید و مرکز چهارچوب در تکرار بعد به کار می‌رود. طبیعی است که مسیرهای حاضر در چهارچوب نیز در تکرار بعد تغییر می‌کنند. برای روش‌های مشابه آنچه گفته  شد همگرایی سراسری قابل اثبات است. وجود اختلال یا دقیق نبودن مقادیر تابع در نقاط مختلف می‌تواند در اجرای الگوریتم‌های جستجوی الگویی و همگرایی آن تاثیر بگذارد. به علاوه ناهموار بودن تابع هدف نیز می‌تواند تاثیرات نامطلوبی بر اجرای روش داشته باشد.
 
 برای تعریف روش جستجوی الگویی ابتدا به بیان برخی نمادهای پرکاربرد در الگوریتم می‌پردازیم. در نقطه $x_{k}$ در تکرار $k$ام،  $D_{k}$ مجموعه‌ای از مسیرهای جستجوی ممکن حول نقطه $x_{k}$  و  $\gamma_{k}$ پارامتر جستجوی خطی است. چهارچوب مورد نظر شامل نقاط $x_{k}+\gamma_{k} p_{k}$ برای هر $p_{k} \in D_{k}$ است. هرگاه یکی از نقاط چهارچوب کاهش مناسبی در تابع هدف ایجاد کند، الگوریتم به گام بعد می‌رود و پس از گسترش چهارچوب،$\gamma_{k}$  افزایش می‌یابد. اگر هیچکدام از نقاط چهارچوب در مقدار تابع هدف کاهش مناسبی ایجاد نکنند، $\gamma_{k}$ را کاهش می‌دهیم و با قرار دادن  $x_{k+1}=x_{k}$ الگوریتم به تکرار بعد می‌رود. 
 
صورت دقیق الگوریتم به شرح زیر است

\begin{algorithm}[h]
\caption{(جستجوی الگویی)} 
\begin{algorithmic}[2]
\REQUIRE  


 \STATE برای $k=1,2,...$
  \STATE \quad         اگر $\gamma_{k} \leq \gamma_{tol}$ 
  \STATE \quad  \quad      .الگوریتم متوقف شود
  \STATE \quad        اگر برای برخی $p_{k} \in D_{k}$ ، $f(x_{k}+ \gamma_{k}p_{k}) \leq f(x_{k}) - \rho(\gamma_{k})$ 
  \STATE \quad \quad   برای آن دسته $p_{k}$ قرار ده $x_{k+1} \leftarrow x_{k}+ \gamma_{k} p_{k}$
  \STATE \quad \quad      برای $\phi_{k} \leq 1$ دلخواه،  قرار ده $\gamma_{k} \leftarrow \phi_{k} \gamma_{k}$
  \STATE \quad       در غیر اینصورت
  \STATE \quad \quad       قرار ده .$x_{k+1} \leftarrow x_{k}$
  \STATE \quad \quad        هرگاه $0 \leq \theta_{k} \leq \theta_{max} < 1$ ، قرار ده $\gamma_{k+1} \leftarrow \theta_{k} \gamma_{k}$
  \STATE \quad    پایان  شرط
  \STATE \quad  پایان حلقه تکرار
\end{algorithmic}
\end{algorithm}




























































\end{document}}