\documentclass{article}
\usepackage{xepersian}
\settextfont{XB Zar}
\begin{document}
توابع محدب



ویژگیها و نمونه‌های پایه:



تابع$f:R^n\rightarrow R$محدب است اگر$domf$یک مجموعه محدب و اگر برای همه$x,y\in dom f $ باشد,و$\theta$  با$0\leq\theta\leq1$  داریم
\begin{equation}
f(\theta x+(1-\theta)y\leq\theta f(x)+(1-\theta)f(y).
\end{equation}
به لحاظ هندسی,این نابرابری به این معنی است که پاره‌خط بین$(x,f(x))$و$(y,f(y))$ که این وتر از$x$  به$y$  است در بالای این نمودار از $f$ قرار می‌گیرد(شکل(۱.۳)).تابعی از $f$ که صرفاٌ محدب است اگر دارای نابرابری محض در(۱.۳) باشد هر‌وقت که $x\neq y$ و$0<\theta<1$.گفتیم $f$ مقعر است اگر $f$محدب باشد و اگر$f$ شدیدا محدب باشد $f$ شدیدا مقعر است.برای یک تابع معین همیشه در (3.1) برابری داریم,بنابراین تمام توابع معین ( و در نتیجه توابع خطی نیز) هم مقعر و هم محدب هستند.بالعکس هر تابع که محدب و مقعرباشد معین است.یک تابع محدب است اگر وتنها اگر زمانی‌که به هر خط که دامنه‌ی آن را قطع میکند محدود شد آن محدب است.یعنی $f$ محدب است اگر و تنها اگر برای همه $x\in dom f$ و 
شکل 3.1.نمودار یک تابع محدب . وتر (یعنی پاره خط) بین هر دو نقطه بر روی نمودار در بالای این نمودار قرار دارد.
تمام $\upsilon$ تابع $g(t)=f(x+t\upsilon)$ محدب است (بر روی دامنه‌ی آن $\lbrace t|x+t\upsilon\in dom f\rbrace$).این ویژگی خیلی مفید است,چون به ما اجازه می‌دهد که بررسی کنیم آیا‌ تابعی بوسیله‌ی محدود کردن آن به یک خط,محدب است.تجزیه و تحلیل توابع محدب رشته توسعه یافته خوبی است,که در هر عمقی پیگیری نمیکنیم.یک نتیجه ساده,بعنوان مثال,این است که یک تابع محدب در فضای داخلی نسبی از دامنه‌ی آن پیوسته است;می‌تواند ناپیوستگی تنها در مرز نسبی آن داشته باشد.



3.1.2.
پسوندهای مقدار توسعه یافته:




اغلب برای گسترش یک تابع محدب برای تمام $R^n$ با تعریف مقدار آن که $\infty$ خارج از دامنه آن باشد,مناسب است. اگر f محدب باشد پسوند مقدار توسعه یافته آن را $\tilde{f}$تعریف می‌کنیم بوسیله
\[
\tilde{f}=
\begin{cases}
f(x) & x\in dom f\\
\infty & x\notin dom f.
\end{cases}
\]
پسوند $\tilde{f}$ برای تمام $R^n$, تعریف می‌شود و مقادیری در $R\cup\lbrace\infty\rbrace$ میگیرد.میتوانیم دامنه تابع  اصلی $f$از پسوند $\tilde{f}$ دوباره بدست آوریم بطوریکه $dom f=\lbrace x|\tilde{f}(x)<\infty\rbrace$.این پسوند می‌تواند علامت‌گذاری را ساده کند,چون آشکارا  نباید این دامنه را توصیف کنیم, یا مقدماتی برای تمام $x\in dom f$ هر وقت که به $f(x)$,مراجعه می‌کنیم اضاافه کنیم.برای مثالنابرابری تعریف پایه (3.1) را در نظر بگیرید, به لحاظ پسوند $\tilde{f}$ میتوانیم آن را بیان کنیم مانند: برای $0<\theta<1$.
\[
\tilde{f}(\theta x+(1-\theta)y)\leq\theta\tilde{f}(x)+(1-\theta)\tilde{f}(y)
\]
برای هر$x$ و$y$ .( برای $\theta=0$ یا $\theta=1$ همیشه دارای این نابرابری است.)البته در این کتاب باید این نابرابری را با استفاده از محاسبات گسترده و مرتب‌سازی بیان کنیم.برای $x$  و $y$  هر دو در $dom f$ این نابرابری مقارن است با (3.1).درصورتی که هر دو خارج  $dom f$ باشد,پس سمت راست $\infty$ است,بنابراین این نابرابری را دارا است.بعنوان مثال دیگر از این شیوه علامت‌گذاری فرض کنید $f_1$ و $f_2$دو تابع محدب این روی $R^n$ است. مجموع نقطه به نقطه $f=f_1+f_2$ تابع با دامنه $dom f=dom f_1\cap dom f_2$, با $f(x)=f_1(x)+f_2(x)$ برای هر $x\in dom f$است.با استفاده از پسوندهای مقدار گسترده به سادگی می‌توانیم بگوییم برای هر $\tilde{f}(x)=\tilde{f_1}(x)+\tilde{f_2}(x)$. در این معادله دامنه $f$ بطور خودکار بعنوان $dom f=dom f_1\cap dom f_2$تعریف شده است,چون $\tilde{f}(x)=\infty$ هروقت $x\notin dom f_1$ یا $x\notin dom f_2$.در این کتاب همان علامت را برای نشان دادن یک تابع محدب و پسوند آن بکار می‌بریم ,هر وقت هیچ زیانی از این ابهام وجود نداشته باشد. این همان است که همانطور که فرض شد که تمام توابع محدب بطور ضمنی گسترش داده در این مثال بر محاسبات گسترده که بطور خودکار این دامنه را تعریف می‌کند تکیه می‌کنیم.در می‌شوند یعنی بعنوان $\infty$ خارج از دامنه شان تعریف می‌شوند.
مثال 3.1.شاخص تابع یک مجموعه محدب.فرض کنید $C\subseteq R^n$,یک مجموعه محدب باشد و تابع (محدب) $I_c$ را با دامنه $c$ و $I_c(x)=0$ برای تمام $x\in C$ درنظر بگیرید,یعنی این تابع در مجموعه $C$ عیناٌ صفر است.پسوند مقدار گسترده آن. 
شکل3.2.اگر f محدب و مشتق پذیر باشد ,پس $f(x)+\bigtriangledown f(x)^T(y-x)\leq f(y)$برای تمام $x,y\in dom f$.
داده میشود با:
\[
\tilde{I_c}(x)=
\begin{cases}
0 ,& x\in C\\
\infty ,& x\notin C.
\end{cases}

تابع محدب $\tilde{I_c}$ شاخص تابع مجموعه $C$ نامیده میشود.می‌توانیم چند ترفند را با شاخص تابع $\tilde{I_c}$ بکار ببریم.مثلا مسئله‌ی به حداقل رساندن یک تابع $f$ (تعریف شده برای تمام $R^n$,می‌گویند) بر مجموعه $C$ همان به حداقل رساندن تابع $f+\tilde{I_c}$ بر تمام $R^n$است.درواقع,تابع $f+\tilde{I_c}$ (با کنوانسیونمان) $f$ محدود شده به مجموعه $C$ است. در روشی مشابه میتوانیم تابعی مقعر را با تعریف آن گسترش دهیم تا $-\infty$ خارج از دامنه آن باشد.



شرایط مرتبه اول:



فرض کنید $f$ مشتق‌پذیر  باشد ( یعنی شیب آن $\bigtriangledown f$ در هر نقطه در $dom f$ وجود دارد که باز است).پس $f$ محدب است اگر‌وتنها‌اگر $dom f$ محدب باشد و 

\[
f(y)\geq f(x)+\bigtriangledown f(x)^T(y-x)
\]

برای تمام $x,y\in dom f$حفظ می‌کند.این نابرابری در شکل 3.2 نشان داده می‌شود.تابع معین $y$ با $f(x)+\bigtriangledown f(x)^T(y-x)$ داده شده ,البته تقریب تیلور  مرتبه اول $f$ نزدیک $x$ است.نابرابری (3.2)بیان می‌کند که برای یک تابع محدب ,تقریب تیلور مرتبه اول در واقع تحت براوردگر جهانی تابع است.برعکس ,اگر تقریب تیلور مرتبه اول یک تابع همیشه تحت براوردگر جهانی تابع باشد ,پس تابع محدب است.نابرابری (3.2) اطلاعات محلی درباره یک تابع محدب را نشان می‌دهد (یعنی مقدار و مشتق ان در یک نقطه) می‌توانیم اطلاعات جهانی را استنتاج کنیم(یعنی تحت براوردگر جهانی ان).شاید این مهمترین ویژگی توابع محدب باشد,و برخی ویژگیهای قابل توجه توابع محدب و مسائل بهینه‌سازی محدب را توضیح می‌دهد.بعنوان یک مثال ساده,نابرابری  (3.2)نشان می‌دهد اگر $\bigtriangledown f(x)=0$پس برای تمام $y\in dom f$ ,$f(y)\geq f(x)$,یعنی $x$ یک کوچک شمار جهانی تابع $f$ است.محدب شدیدا نیز می‌تواند با یک شرط مرتبه اول مشخص شود:$f$ به شدت محدب است اگر‌و‌تنها‌اگر $dom f$محدب است و برای $x,y\in dom f$ و$x\neq y$ ,داریم 

\[
f(y)>f(x)+\bigtriangledown f(x)^T(y-x).
\]

برای توابع مقعر خصوصیات متناظر داریم:$f$ مقعر است اگر‌وتنها‌اگر $dom f$ محدب باشد و 


\[
f(y)\leq f(x)+\bigtriangledown f(x)^T(y-x)
\]

                                 
برای تمام $x,y\in dom f$.

اثبات شرط محدب درجه اول:

برای ثابت کردن (3.2), اول حالت $n=1$ را درنظر میگیریم:تابع مشتق‌پذیر $f:R\rightarrow R$محدب است اگر‌و تنها‌اگر 

\[
f(y)\geq f(x)+f‌‌‌‌‌'(x)(y-x)
\]                           
برای تمام $x$ و $y$ در $dom f$.اول فرض کنید که $f$ محدب است و $x,y\in dom f$.چون $dom f$ محدب است (یعنی یک فاصله),نتیجه می‌گیریم که برای تمام $0<t\leq 1$, $x+t(y-x)\in dom f$ و به وسیله‌ی تحدب $f$ , 

\[
f(x+t(y-x))\leq (1-t)f(x)+tf(y).
\]

اگر هر دو سمت را به $t$ تقسیم کنیم ,بدست می آوریم

\[
f(y)\geq f(x)+\frac{f(x+t(y-x))-f(x)}{t},
\]

و با گرفتن حد بعنوان بازده $t\rightarrow o$.

برای نشان دادن قابلیت ,فرض کنید این تابع (3.4) را برای تمام  $x$ و $y$ در $dom f$ برآورده کند (که یک فاصله است). هر $x\neq y$, و $0\leq \theta\leq 1$, را انتخاب کنید و فرض کنید $z=\theta x+(1-\theta)y$. با دو برابر بازدهی 

\[
f(x)\geq f(z)+f'(z)(x-z),\qquad f(y)\geq f(z)+f'(z)(y-z).
\]

با ضرب کردن اولین نابرابری با $\theta$, و دومین نابرابری با $1-\theta$, و با اضافه کردن آنها به بازده

\[
\theta f(x)+(1-\theta)f(y)\geq f(z),
\]

که ثابت می‌کند $f$ محدب است.حالا می‌توانیم از دیدگاه کلی ثابت کنیم ,با $f:R^n\rightarrow R$.فرض کنید $x,y\in R^n$ و در نظر بگیرید $f$ به خطی که از میان آنها می‌گذرد محدود شده یعنی این تابع تعریف شده با 

\[
g(t)=f(ty+(1-t)x), so\quad g'(t)=\bigtriangledown f(ty+(1-t)x)^T(y-x).
\]

اول فرض کنید $f$ محدب است ,که اشاره دارد $g$
 محدب است ,پس با استدلال بالا داریم $g(1)\geq g(0)+g'(0)$ به این معنی که                         

\[
f(y)\geq f(x)+\bigtriangledown f(x)^T(y-x).
\]

حالا فرض کنید که این نابرابری را برای هر $x$ و $y$ حفظ می‌کند,پس اگر $ty+(1-t)x\in dom f$   و $\tilde{t}y+(1-\tilde{t})x\in dom f$, داریم 

\[
f(ty+(1-t)x\geq f(\tilde{t}y+(1-\tilde{t})x)+\bigtriangledown f(\tilde{t}y+(1-\tilde{t})x)^T(y-x)(t-\tilde{t}),
\]

یعنی $g(t)\geq g(\tilde{t})+g'(\tilde{t})(t-\tilde{t})$. دیدیم که این نشان می‌دهد که $g$ محدب است.

۱.۴ شرایط مرتبه دوم :

حالا فرض می‌کنیم که $f$ دو بار مشتق‌پذیر است‌,یعنی هسیین آن یا مشتق دوم $\bigtriangledown^2f$ در هر نقطه در $dom f$ وجود دارد,که باز است.پس $f$ محدب است اگر‌و‌تنها‌اگر $dom f$ محدب باشد و هسیین آن نیمه معین مثبت است: برای تمام $x\in dom f$,

\[
\bigtriangledown^2f(x)\succeq 0.
\]
برای تابعی بر روی $R$ ,این به شرط ساده $f''(x)\geq 0$ساده می‌شود (و $dom f$محدب , یعنی  یک فاصله),که به این معنی است که مشتق غیر‌کاهشی است.این شرط $\bigtriangledown^2f(x)\succeq 0$ می‌تواند به لحاظ هندسی بعنوان نیاز تفسیر شود که نمودار تابع انحنای مثبت (رو به بالا)در $x$ دارد.اثبات شرطمرتبه دوم را بعنوان یک تمرین رها می‌کنیم (تمرین 3.8).به همین ترتیب,$f$مقعر است اگر‌وتنها‌اگر $dom f$محدب باشد و $\bigtriangledown^2f(x)\preceq 0$ برای تمام $x\in dom f$ .تحدب شدید می‌تواند تاحدی با شرایط مرتبه دوم مشخص شود.اگر $\bigtriangledown^2f(x)\succ 0$ برای تمام $x\in dom f$ ,پس $f$ شدیدا محدب است.با این حال معکوس این درست نیست:مثلا,تابع $f:R\rightarrow R$داده می‌شود با $f(x)=x^4$ شدیدا محدب است اما در $x=0$ مشتق دوم صفر دارد.

مثال 3.2. توابع درجه دوم.تابع درجه دوم $f:R^n\rightarrow R$ را با $f=R^n$ در نظر بگیرید,داده می‌شود با 

\[
f(x)=\frac{1}{2}x^TPx+q^Tx+r,
\]

با$P\in S^n$,$q\in R^n$ و $r\in R$ .از آنجائیکه $\bigtriangledown^2f(x)=P$برای تمام $x$,$f$ محدب است اگرو‌تنها‌اگر $P\succeq 0$(و مقعر است اگر‌و‌تنها‌اگر $P\preceq 0$).برای توابع درجه دوم ,تحدب شدید بسادگی مشخص می‌شود:$f$ شدیدا محدب است اگر‌و‌تنها‌اگر $P\succ 0$(و شدیدا مقعر است اگر‌و‌تنها‌اگر $P\prec 0$).
تذکر3.1:شرط جداگانه که $dom f$ محدب باشد نمی‌تواند از مشخصه‌های مرتبه اول و دوم تحدب و تقعر کاهش یابد.مثلا, تابع .$f(x)=\frac{1}{x^2}$ با $dom f=\lbrace x\in R|x\neq 0\rbrace $  , $f''(x)>0$ را برای تمام $x  
\in dom f$,براورده می‌کند,اما یک تابع محدب نیست.

۱.۵ مثالها

قبلا گفتیم که همه توابع خطی و پیوسته محدب هستند(و مقعر),و محدب و مقعر توابع درجه دوم را شرح دادیم.در این بخش به چند نمونه از توابع محدب و مقعر می‌پردازیم.با برخی توابع در $R$ ,با متغیر $x$ شروع می‌کنیم.

\begin{itemize}
\item نمایی:$e^{ax}$ در $R$, برای هر $a\in R$ محدب است.
\item توانها:$x^a$ در $R_{++}$ محدب است زمانیکه $a\geq 1$ یا $a\leq 0$,و مقعر است برای $0\leq a\leq 1$.
\item توانهای قدر مطلق:$|x|^p$,برای $p\geq 1$,در $R$ محدب است.
\item لگاریتم:$log x$ در$R_++$ مقعر است.
\end{itemize}
                                    












 
 


\end{document}