\documentclass{thesis}
%\usepackage{setspace,xargs}
% برای فاصله گذاری استاندارد بین خطوط و دستورات با چند آرگومان اختیاری
\usepackage{amsthm,amssymb}
\usepackage{amsmath}
\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}{ملاحظه}


\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{(پانویس) روش‌های مبتنی بر تقریب}
گروهی از تاثیرگذارترین الگوریتم‌ها برای بهینه‌سازی نامقید الگوریتم‌هایی هستند که گام‌های آن با کمینه کردن یک تقریب درجه دوم از تابع هدف  $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 ||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+1})}{m_{k}(x_{k})-m_{k}(x_{k+1})},
\end{equation}
است انجام می‌گیرد.


































\end{document}}