\documentclass[12pt]{article} \usepackage{amsmath} \usepackage{xepersian} \settextfont{XB Zar} \linespread{1.25} \newtheorem{definition}{تعریف}[section] \newtheorem{theorem}[definition]{قضیه} \newcommand{\dd}{\,\mathrm{d}} \newtheorem{example}{مثال }[section] \newtheorem{remark}{تذکر}[section] \settextfont[Scale=1.1]{Yas} \begin{document} \chapter{توابع محدب} \section*{ویژگیها و نمونه‌های پایه} \subsection{تعریف} تابع$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$).این ویژگی خیلی مفید است,چون به ما اجازه می‌دهد که بررسی کنیم آیا‌ تابعی بوسیله‌ی محدود کردن آن به یک خط,محدب است.تجزیه و تحلیل توابع محدب رشته توسعه یافته خوبی است,که در هر عمقی پیگیری نمیکنیم.یک نتیجه ساده,بعنوان مثال,این است که یک تابع محدب در فضای داخلی نسبی از دامنه‌ی آن پیوسته است;می‌تواند ناپیوستگی تنها در مرز نسبی آن داشته باشد. \subsection{پسوندهای مقدار توسعه یافته} اغلب برای گسترش یک تابع محدب برای تمام $R^n$ با تعریف مقدار آن که $\infty$ خارج از دامنه آن باشد,مناسب است. اگر f محدب باشد پسوند مقدار توسعه یافته آن را $\tilde{f}$تعریف می‌کنیم $\tilde{f}:R^n\rightarrow R\cup\lbrace\infty\rbrace$ با \[ \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$ خارج از دامنه شان تعریف می‌شوند. مثال۱.۳:شاخص تابع یک مجموعه محدب.فرض کنید $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$ خارج از دامنه آن باشد. \subsection{شرایط مرتبه اول} فرض کنید $f$ مشتق‌پذیر باشد ( یعنی شیب آن $\bigtriangledown f$ در هر نقطه در $dom f$ وجود دارد که باز است).پس $f$ محدب است اگر‌وتنها‌اگر $dom f$ محدب باشد و \begin{equation} f(y)\geq f(x)+\bigtriangledown f(x)^T(y-x) \end{equation} برای تمام $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$ ,داریم \begin{equation} f(y)\geq f(x)+\bigtriangledown f(x)^T(y-x) \end{equation} برای توابع مقعر خصوصیات متناظر داریم:$f$ مقعر است اگر‌وتنها‌اگر $dom f$ محدب باشد و \[ f(y)\leq f(x)+\bigtriangledown f(x)^T(y-x) \] برای تمام $x,y\in dom f$. \chapter*{اثبات شرط محدب درجه اول} برای ثابت کردن (3.2), اول حالت $n=1$ را درنظر میگیریم:تابع مشتق‌پذیر $f:R\rightarrow R$محدب است اگر‌و تنها‌اگر \begin{equation} f(y)\geq f(x)+f‌‌‌‌‌'(x)(y-x) \end{equation} برای تمام $x$ و $y$ در $dom f$.اول فرض کنید که $f$ محدب است و $x,y\in dom f$.چون $dom f$ محدب است (یعنی یک فاصله),نتیجه می‌گیریم که برای تمام $00$ را برای تمام $x \in dom f$,براورده می‌کند,اما یک تابع محدب نیست. \subsection{مثالها} قبلا گفتیم که همه توابع خطی و پیوسته محدب هستند(و مقعر),و محدب و مقعر توابع درجه دوم را شرح دادیم.در این بخش به چند نمونه از توابع محدب و مقعر می‌پردازیم.با برخی توابع در $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_{++}$ مقعر است. \item آنتروپی منفی: $x\:log\:x$ (یا در $R_{++}$ یا در $R_+$ به عنوان $0$ تعریف می‌شود برای $x=0$) محدب است. \end{itemize} تحدب یا تقعر این نمونه‌ها با اثبات نابرابری اولیه (3.1) یا با بررسی مشتق دوم ,غیر‌منفی یا غیر‌مثبت است را می‌تواند نشان دهد . مثلا, با $f(x)=x\:log\:x$ داریم \[ f'(x)=log\:x+1,\qquad f''(x)=1/x, \] بطوریکه $f''(x)>0$ برای $x>0$ . این نشان می‌دهد که تابع آنتروپی منفی (شدیداٌ) محدب است.حالا چند نمونه جالب از توابع را در $R^n$ می‌دهیم. \begin{itemize} \item نرمها : هر نرم در $R^n$ محدب است. \item توابع $max$ : $f(x)=max\lbrace x_1,\ldots,x_n\rbrace$ در $R^n$ محدب است. \item تابع درجه دوم بر تابع خطی : تابع $f(x,y)=x^2/y$, با \[ dom f=R\times R_{++}=\lbrace (x,y)\in R^2|y>0\rbrace, \] محدب است (شکل ۳). \item لگاریتم ـ مجموع ـ تابع نمایی : تابع $f(x)=log(e^x_1+\cdots+e^x_n)$ در $R$ محدب است. این تابع می‌تواند بعنوان یک تقریب مشتق‌پذیر (در واقع,تحلیلی) از تابع $max$ تفسیر شود,چون \[ max\lbrace x_1,\ldots,x_n\rbrace\leq f(x)\leq max\lbrace x_1\ldots x_n\rbrace+log\: n \] برای تمام $x$.(زمانیکه تمام اجزای $x$ برابر هستند,نابرابری دوم برقرار است.)شکل 4, $f$ را برای $n=2$ نشان می‌دهد. \item میانگین هندسی : میانگین هندسی $f(x)=(\prod_{i=1}^n x_i)^{1/n}$ در $dom f=R_{++}^n$ مقعر است. شکل۳.۴:گراف $f(x,y)=log(e^x+e^y)$. \item لگاریتم ـ دترمینان : تابع $f(\mathbf{x})=log\: det\:\mathbf{x}$ در $dom f=S_{++}^n$ مقعر است. تحدب (یا تقعر) این نمونه‌ها می‌تواند به چند روش اثبات شود,مانند اثبات نابرابری بطور مستقیم (3.1), اثبات این که هسیین نیمه معین مثبت است , یا با محدود کردن این تابع به یک خط دلخواه و اثبات تحدب تابع بدست آمده از یک متغیر. \end{itemize} نرمها: اگر $f:R^n\rightarrow R$ یک نرم باشد , و $0\leq \theta\leq 1$, \[ f(\theta x+(1-\theta)y)\leq f(\theta x)+f((1-\theta)y)=\theta f(x)+(1-\theta)f(y). \] نابرابری به شرح زیر از نابرابری مثلث , و برابری به شرح زیر از یکنواختی یک نرم. تابع حداکثر:تابع $f(x)=max_i x_i$ برای $0\leq\theta\leq 1$, \begin{align*} f(\theta\:x+(1-\theta)y) & =\underset{i}{max}(\theta x_i+(1-\theta)y_i)\\ & \leq \theta\:\underset{i}{max}\:x_i+(1-\theta)\underset{i}{max}\:y_i\\ &=\theta f(x)+(1-\theta)f(y). \end{align*} تابع مرتبه دوم بر تابع خطی:برای نشان دادن اینکه تابع مرتبه دوم بر خطی $f(x,y)=x^2/y$ محدب است , توجه داشته باشید که (برای$y>0$), \[ \bigtriangledown^2 f(x,y)=\frac{2}{y^3}\begin{bmatrix} y^2 & -{xy}\\ -{xy} & x^2\\ \end{bmatrix} =\frac{2}{y^3}\begin{bmatrix} y\\ -x\\ \end{bmatrix} \begin{bmatrix} y\\ -x\\ \end{bmatrix} ^T \succeq 0. \] لگاریتم ـ مجموع ـ نمایی: هسیین تابع $(log-sum-exp)$ هست; \[ \bigtriangledown^2 f(x)=\frac{1}{(1^Tz)^2}((1^Tz) diag(z)-zz^T), \] که $z=(e^{x_1},\ldots,e^{x_n})$. به منظور بررسی $\bigtriangledown^2 f(x)\succeq 0$ باید نشان دهیم که برای تمام $\upsilon$, $\upsilon^T\bigtriangledown^2 f(x)\upsilon\geq 0$ یعنی \[ \upsilon^T\bigtriangledown^2 f(x)\upsilon=\frac{1}{(1^Tz)^2}\left( \left( \sum_{i=1}^n z_i\\ \right) \left( \sum_{i=1}^n\upsilon_i^2 z_i\\ \right) -\left( \sum_{i=1}^n\upsilon_i z_i\\ \right) ^2\\ \right) \geq 0. \] اما این اصل از نابرابری کوشی ـ شوارتز$(a^T a)(b^T b)\geq(a^Tb)^2$ برای بردارها با اجزا $a_i=\upsilon_i\sqrt{z_i}$ , $ b_i=\sqrt{z_i}$ بکار برده شد. میانگین هندسی:در روشی مشابه می‌توانیم نشان دهیم که میانگین هندسی $f(x)=(\prod_{i=1}^n x_i)^{1/n}$ در $dom f=R_{++}^n$ مقعر است.هسیین آن $\bigtriangledown^2 f(x)$ داده می‌شود با \[ \frac{\partial^2 f(x)}{\partial x_k^2}=-(n-1)\frac{(\prod_{i=1}^n x_i)^{1/n}}{n^2 x_k^2},\qquad\frac{\partial^2 f(x)}{\partial x_k\partial x_l}=\frac{(\prod_{i=1}^n x_i)^{1/n}}{n^2 x_k x_l}\qquad for\quad k\neq l, \] و می‌تواند بیان شود بعنوان \[\bigtriangledown^2 f(x)=-\frac{\prod_{i=1}^n x_i^{1/n}}{n^2}(n diag(1/x_1^2,ldots,1/x_n^2)-qq^T) \] که $q_i=1/x_i$.باید نشان دهیم که .$\bigtriangledown^2 f(x)\preceq 0$, یعنی, که \[ \upsilon^T\bigtriangledown^2 f(x)\upsilon=-\frac{\prod_{i=1}^n x_i^{1/n}}{n^2}\left( n\sum_{i=1}^n\upsilon_i^2/x_i^2-\left( \sum_{i=1}^n\upsilon_i/x_i \right)^2 \right) \leq 0 \] برای تمام $\upsilon$ .دوباره این اصل از نابرابری کوشی شوارتز $(a^T a)(b^T b)\geq(a^Tb)^2$ برای بردارهای $a=1$ و $b_i=\upsilon_i/x_i$ بکار برده شده. لگاریتم ـ دترمینان:برای تابع $f(\mathbf{x})=log\;det\mathbf{x}$, می‌توانیم تقعر را با درنظر گرفتن یک خط دلخواه اثبات کنیم , داده شده با $\mathbf{x}=Z+tV$, که $Z,V\in S^n$ . تعریف می‌کنیم $g(t)=f(Z+tV)$, و $g$ را محدود می‌کنیم که فاصله مقادیر $t$ که برای $Z+tV\succ 0$. بدون از دست دادن کلیت , می‌توانیم فرض کنیم که $t=0$ داخل این فاصله است, یعنی $Z\succ 0$ . داریم \begin{align*} g(t) & =log\;det(Z+tV)\\ & =log\;det(Z^{1/2}(I+tZ^{-1/2}VZ^{-1/2})Z^{1/2})\\ & =\sum_{i=1}^n log(1+t\lambda_i)+log\;det Z\\ \end{align*} که $\lambda_1,\ldots,\lambda_n$ مقادیر ویژه $Z^{-1/2}VZ^{-1/2}$.بنابراین داریم \[ g'(t)=\sum_{i=1}^n\frac{\lambda_i}{1+t\lambda_i}\:,\qquad g''(x)=-\sum_{i=1}^n\frac{\lambda_i^2}{(1+t\lambda_i)^2}. \] از آنجائیکه $g''(t)\leq 0$, نتیجه می‌گیریم که $f$ مقعر است. \subsection{زیرمجموعه‌ها} مجموعه ( زیر سطح- α) تابع $f:R^n\rightarrow R$ تعریف می‌شود بعنوان \[ C_\alpha=\lbrace x\in\textbf{dom} f|f(x)\leq \alpha\rbrace. \] زیرمجموعه‌های یک تابع محدب ,برای هر مقدار از $a$ محدب هستند.این اثبات از تعریف تحدب ضروری است: اگر $x,y\in C_\alpha$, پس $f(x)\leq \alpha$ و $f(y)\leq\alpha$ , و بنابراین $f(\theta x+(1-\theta)y)\leq\alpha$ برای $0\leq\theta\leq 1$, و از‌این‌رو $\theta x+(1-\theta)y\in C_\alpha$ . معکوس این قضیه درست نیست:یک تابع می‌تواند همه‌ی زیرمجموعه‌های محدب آن را داشته باشند ,اما یک تابع محدب نباشد.مثلا ,$f(x)=-e^x$ در $R$محدب نیست(درواقع ,شدیداٌ مقعر است) اما تمام زیرمجموعه‌های آن محدب هستند.اگر $f$ مقعر باشد, پس تمام( ) آن داده می‌شود با$\lbrace x\in \textbf{dom} f|f(x)\geq\alpha\rbrace$ , یک مجموعه محدب است.این ویژگی زیرمجموعه , با بیان آن به عنوان یک زیرمجموعه از تابعی محدب , یا به عنوان مجموعه مرجع از تابعی مقعر اغلب روش خوبی برای تحدب یک مجموعه است. مثال۳.۳:میانگین هندسی و ریاضی $x\in R_+^n$ بترتیب هستند; \[ G(x)=\left( \prod_{i=1}^n x_i\\ \right)^{1/n} ,\qquad A(x)=\frac{1}{n}\sum_{i=1}^n x_i , \] (که $0^{1/n}=0$ را در تعریفمان از $G$ میگیریم.)میانگین ریاضی - هندسی نابرابری بیان می‌کند که $G(x)\leq A(x)$ . فرض کنید $0\leq\alpha\leq 1$ و درنظر بگیرید مجموعه \[ \lbrace x\in R_+^n|G(x)\geq\alpha A(x)\rbrace, \] یعنی مجموعه بردارها با میانگین هندسی حداقل به بزرگی عامل $a$ با میانگین ریاضی متقارن است.این مجموعه محدب است,چون( مجموعه فوق سطح – 0 ) از تابع $G(x)-\alpha A(x)$ است,که مقعر است.درواقع,این مجموعه به طور مثبت همگن است,بنابراین آن مخروط محدب است. \subsection{بالای نمودار} نمودار تابع $f:R^n\rightarrow R$ تعریف می‌شود بعنوان \[ \lbrace(x,f(x))|x\in \textbf{dom} f\rbrace, \] که زیر‌مجموعه‌ای از $R^{n+1}$, است.بالای نمودار یک تابع $f:R^n\rightarrow R$ تعریف می‌شود بعنوان \[ \textbf{epi} f=\lbrace(x,t)|x\in\textbf{dom} f,\;f(x)\leq t\rbrace, \] که زیر‌مجموعه‌ای از $R^{n+1}$ است.( $epi$ به معنای بالاست پس $epigraph$ به معنای بالای نمودار است.)این تعریف در شکل 3.5 نشان داده می‌شود.رابطه بین مجموعه‌های محدب و توابع محدب از طریق $epigraph$ (بالای نمودار) است: $A$یک تابع محدب است اگر‌و‌تنها‌اگر بالای نمودار آن یک مجموعه محدب است.یک تابع مقعر است اگر‌و‌تنها‌اگر $hypograph$ آن تعریف شد به عنوان \[ \textbf{hypo} f=\lbrace(x,t)|t\leq f(x)\rbrace, \] مجموعه‌ای محدب است. شکل ۳.۵ \begin{description} \item[مثال:] تابع کسری ماتریس.تابع $f:R^n\times S^n\rightarrow R$, تعریف می‌شود به عنوان \[ f(x,Y)=x^T Y^{-1}x \] در $dom f=R^n\times S_{++}^n$ محدب است.(این مثال تابع درجه دوم را بر تابع خطی$f(x,y)=x^2/y$, با $dom f=R\times R_{++}$ کلیت می‌بخشد.)یک روش آسان برای ایجاد تحدب $f$ از طریق $epigraph$ آن صورت می‌گیرد: \begin{align*} \textbf{epi} f &=\lbrace(x,Y,t)|Y\succ 0,\;x^TY^{-1}x\leq t\rbrace\\ & =\begin{Bmatrix} (x,Y,t)\vert \begin{bmatrix} Y & x\\ x^T & t\\ \end{bmatrix} \succeq 0,\:Y\succ 0, \end{Bmatrix} \end{align*} با استفاده از حالت مکمل اسچور برای نیمه معین مثبت ماتریس بلوکی (5 .5.A §را ببینید).آخرین حالت نابرابری ماتریس خطی در $(x,Y,t)$ است,و بنابراین $\textbf{epi} f$ محدب است.برای این حالت خاص $n=1$ , تابع کسری ماتریس به تابع درجه دوم بر تابع خطی $x^2/y$ ساده می‌شود, و ارائه $LMI$ وابسته است \[ \begin{bmatrix} y & x\\ x & t\\ \end{bmatrix} \succeq 0 ,\quad y>0 \] (نمودار آن در شکل 3.3 نشان داده می‌شود.) \end{description} نتایج بسیاری برای توابع محدب می‌تواند به طور هندسی با استفاده از اپی‌گراف‌‌ها , و با به کار بردن نتایج برای مجموعه‌های محدب ثابت شود(یا تفسیر شود).به عنوان یک مثال ,حالت مرتبه اول برای تحدب را در نظر بگیرید: \[ f(y)\geq f(x)+\bigtriangledown f(x)^T(y-x), \] که $f$ محدب است و $x,y\in dom f$ . می‌توانیم این نابرابری اساسی را به طور هندسی در عبارت $\textbf{epi} f $ تفسیر کنیم.اگر $(y,t)\in \textbf{epi} f$, پس \[ t\geq f(y)\geq f(x)+\bigtriangledown f(x)^T(y-x). \] شکل ۳.۶ می‌توانیم این‌ را بیان کنیم مانند: \[ (y,t)\in\textbf{epi} f\Longrightarrow \Longrightarrow\begin{bmatrix} \bigtriangledown f(x)\\ -1\\ \end{bmatrix} ^T\left( \begin{bmatrix} y\\ t\\ \end{bmatrix} -\begin{bmatrix} x\\ f(x)\\ \end{bmatrix} \right) \leq 0. \] این به این معناست که$hyperplane$ تعریف شده با $(\bigtriangledown f(x),-1)$ پشتیبانی می‌کند$\textbf{epi} f$ را در نقطه مرزی $(x,f(x))$;شکل 3.6 را ببینید. \subsection{نابرابری و پسوندهای جنسن} نابرابری اساسی (3.1), یعنی \[ f(\theta x+(1-\theta)y)\leq\theta f(x)+(1-\theta)f(y), \] گاهی نابرابری جنسن نامیده می‌شود.آن به آسانی به ترکیبات محدب بیشتر از دو نقطه گسترش داده می‌شود:اگر $f$ محدب باشد,$x_1,\ldots,x_k\in\textbf{dom} f$ , و $\theta_1,\ldots,\theta_k\geq 0$ با $\theta_1+\cdots+\theta_k=1$, پس \[ f(\theta_1 x_1+\cdots+\theta_k x_k)\leq \theta_1 f(x_1)+\cdots+\theta_k f(x_k). \] در نتیجه , در مورد مجموعه‌های محدب ,این نابرابری به حاصل جمع نامتناهی ,انتگرال, و مقادیر مورد انتظار گسترش داده می‌شود.مثلا, اگر $p(x)\geq 0$ در $S\subseteq\textbf{dom} f$ , $\int_S p(x)\dd x$ پس \[ f\left(\int_S p(x)x\dd x\right)\leq\int_S f(x)p(x)\dd x, \] مشروط به انتگرالهایی که وجود دارد.در حالت کلی می‌توانیم هر احتمال اندازه‌گیری را با حمایت در $\textbf{dom}$ در نظر بگیریم.اگر $x$ متغیری تصادفی باشد به طوریکه $x\in \textbf{dom} f$با احتمال یک , و $f$ محدب است ,پس داریم \begin{equation} f(Ex)\leq E f(x), \end{equation} مشروط به انتظاراتی که وجود دارد.میتوانیم نابرابری اساسی (3.1) را ازاین شکل کلی , با در نظر گرفتن متغیر تصادفی $x$ که از $\lbrace x_1,x_2\rbrace$ حمایت می‌کند , با $\textbf{prob}(x=x_1)=\theta$, $\textbf{prob}(x=x_2)=1-\theta$ بازیابی کنیم.بنابراین نابرابری (3.5) تحدب را مشخص می‌کند:اگر $f$ محدب نباشد,متغیر تصادفی $x$,با $x\in\textbf{dom} f$ با احتمال یک , به طوریکه $f(Ex)=Ef(x)$ وجود دارد.حالا تمام این نابرابریها ,نابرابری جنسن نامیده می‌شود,حتی اگر نابرابری مورد مطالعه توسط جنسن یک \[ f\left(\frac{x+y}{2}\right)\leq\frac{f(x)+f(y)}{2} \] بسیار ساده بود. \section{تذکر} می‌توانیم (3.5) را به شرح زیر تفسیر کنیم.فرض کنید $x\in\textbf{dom} f\subseteq R^n$ و $z$ هرمقدار بردار تصادفی صفر در $R^n$ است . پس داریم \[ Ef(x+z)\geq f(x). \] بنابراین ,تصادفی یا لرزشی (یعنی با اضافه کردن مقدار بردار تصادفی صفر برای استدلال )نمی‌تواند مقدار تابع محدب را به طور متوسط کاهش دهد. \subsection{نابرابری} بسیاری از نابرابریهای معروف می‌تواند با استفاده از نابرابری جنسین به تعدادی تابع محدب مناسب مشتق شود.(درواقع, تحدب و نابرابری جنسین می‌تواند پایه و اساس یک نظریه نابرابری را بسازد.)به عنوان یک مثال ساده,میانگین نابرابری ریاضی – هندسی را در نظر بگیرید: \begin{equation} \sqrt{ab}\leq(a+b)/2 \end{equation} برای $a,b\geq 0$. تابع $-log \;x$ محدب است.نابرابری جنسن با .$\theta=1/2$ حاصل \[ -log\left(\frac{a+b}{2}\right)\leq\frac{-log\;a-log\;b}{2} \] با در نظر گرفتن نمایی از دو سمت (3.6) حاصل می‌شود. به عنوان یک مثال کم اهمیت‌تر نامساوی هولدر را ثابت می‌کنیم:برای $p> 1$,$1/p+1/q=1$ و $x,y\in R^n$ , \[ \sum_{i=1}^n x_i y_i\leq\left(\sum_{i=1}^n |x_i|^p\right)^{1/p}\left(\sum_{i=1}^n |y_i|^q\right)^{1/q}. \] با تحدب$-log\;x$, و نابرابری جنسن به طور کلی $\theta$ ,میانگین نابرابری ریاضی هندسی کلی‌تری را بدست می آوریم. \[ a^\theta b^{1-\theta}\leq \theta a+(1-\theta)b, \] برای $a,b\geq 0$ و $0\leq\theta\leq 1$ معتبر است.به کار بردن این را با \[ a=\frac{|x_i|^p}{\sum_{j=1}^n |x_j|^p},\qquad b=\frac{|y_i|^q}{\sum_{j=1}^n |y_j|^q},\qquad \theta=1/p, \] حاصل می‌شود \[ \left(\frac{|x_i|^p}{\sum_{j=1}^n |x_j|^p\right)^{1/p}}\left(\frac{|y_i|^q}{\sum_{j=1}^n |y_j|^q}\right)^{1/q}\leq\frac{|x_i|^p}{p\sum_{j=1}^n |x_j|^p}+\frac{|y_i|^q}{q\sum_{j=1}^n |y_j|^q}.\] \end{document}