\documentclass[12pt]{book} \usepackage{graphicx,verbatim,fancyhdr,color,xspace,amsmath,amssymb,amsthm,hyperref,geometry} \usepackage{tikz} \usetikzlibrary{snakes} \tikzstyle{vertex}=[circle, draw, inner sep=0pt, minimum size=4pt] \newcommand{\vertex}{\node[vertex]} \tikzstyle{butterfly}=[circle, draw, inner sep=0pt, minimum size=3pt] \newcommand{\butterfly}{\node[butterfly]} \usetikzlibrary{snakes} \usetikzlibrary{topaths } \usetikzlibrary{petri} \usetikzlibrary{snakes} \usetikzlibrary{arrows,calc} \tikzset{ >=stealth', help lines/.style={dashed, thick}, axis/.style={<->}, important line/.style={thick}, connection/.style={thick, dotted}, } \usepackage{xepersian} \settextfont{Yas} \setdigitfont{Yas} \linespread{1.25} \newtheorem{definition}{تعریف}[section] \newtheorem{theorem}[section]{قضیه} \newcommand{\dd}{\,\mathrm{d}} \newcommand{\ee}{\,\mathrm{e}} \newtheorem{example}{مثال }[section] \newtheorem{remark}{تذکر}[section] \settextfont{Yas} \setcounter{chapter}{1} \begin{document} \textbf{\huge توابع محدب} \section{ویژگی‌ها و مثال‌های اساسی} \subsection{تعریف} تابع $f:\mathbf{R}^n\rightarrow\mathbf{R}$ محدب است اگر $\mathbf{dom}\:f$ به ازای هر $x,y\in\mathbf{dom}\: f $ مجموعه‌ای محدب باشد، و به ازای هر $\theta$ به‌طوری‌که $0\leq\theta\leq1$ داشته باشیم \begin{equation} f(\theta x+(1-\theta)y\leq\theta f(x)+(1-\theta)f(y).\label{1} \end{equation} به لحاظ هندسی، این نامساوی به این معنی است که پاره‌خط بین $(x,f(x))$ و $(y,f(y))$ که این وتر از $x$ به $y$ است در بالای نمودار $f$ قرار می‌گیرد (شکل(۱.۳)). تابعی از $f$ اکیدا محدب است اگر دارای نامساوی محض در \eqref{1} باشد ‌وقتی‌که $x\neq y$ و $0<\theta<1$. گفتیم $f$ مقعر است اگر $-f$ محدب باشد، و اکیدا مقعر است اگر $-f$ اکیدا محدب باشد. برای تابع آفینی همیشه برابری \eqref{1} را داریم، بنابراین تمام توابع آفینی ( و در نتیجه توابع خطی نیز) هم مقعر و هم محدب هستند. بالعکس هر تابع که محدب و مقعرباشد آفینی است. یک تابع محدب است اگر‌وتنها‌اگر زمانی‌که به هر خط که دامنه‌ی آن را قطع می‌کند محدود شود. یعنی $f$ محدب است اگر‌و‌تنها‌اگر به ازای هر $x\in\mathbf{dom}\:f$ و \begin{center} \[ \begin{tikzpicture} \draw [ultra thick](-4,2.5) to [out=-45,in=190] (0,0); \draw [ultra thick] (0,0) to [out=10,in=61] (3,3); \draw [ultra thick](-2.5,0.9) to (2.3,2); \draw [fill] (-2.5,0.9) circle [radius=0.09]; \draw [fill] (2.3,2) circle [radius=0.09]; \node at (-3.6,0.9) [color=blue]{$(x,f(x))$}; \node at (3.3,2) [color=blue]{$(y,f(y))$}; \end{tikzpicture} \] \end{center} (شکل 3.1.نمودار یک تابع محدب. وتر (یعنی پاره خط) بین هر دو نقطه بر روی نمودار در بالای این نمودار قرار دارد.) به ازای هر $\upsilon$، تابع $g(t)=f(x+t\upsilon)$ محدب باشد (بر روی دامنه‌ی آن $\lbrace t|x+t\upsilon\in\mathbf{dom}\:f\rbrace$). این ویژگی خیلی مفید است، چون به ما اجازه می‌دهد که بررسی کنیم آیا‌ تابعی به‌وسیله‌ی محدود کردن آن به یک خط، محدب است. تجزیه و تحلیل توابع محدب رشته توسعه یافته خوبی است،که در هر عمقی پیگیری نمی‌کنیم. یک نتیجه‌ی ساده، به‌عنوان مثال، تابع محدبی که در فضای داخلی نسبی از دامنه‌ی آن پیوسته باشد؛ تنها می‌تواند در مرز نسبی آن ناپیوستگی داشته باشد. \subsection{بسط مقدار تعمیم یافته} اغلب برای بسط یک تابع محدب به تمام $\mathbf{R}^n$ که با تعریف مقدار آن به $\infty$ خارج از دامنه آن باشد، مناسب است. اگر $f$ محدب باشد بسط مقدار تعمیم یافته آن را به صورت $\tilde{f}:\mathbf{R}^n\rightarrow\mathbf{R}\cup\lbrace\infty\rbrace$ تعریف می‌کنیم، به طوری‌که \[ \tilde{f}= \begin{cases} f(x) & x\in\mathbf{dom}\:f\\ \infty & x\notin\mathbf{dom}\:f. \end{cases} \] بسط $\tilde{f}$ روی تمام $\mathbf{R}^n$ تعریف می‌شود، و مقادیری در $\mathbf{R}\cup\lbrace\infty\rbrace$ می‌گیرد. می‌توانیم دامنه‌ی تابع اصلی $f$ را از بسط $\tilde{f}$ دوباره به‌دست آوریم به‌طوری‌که $\mathbf{dom}\:f=\lbrace x|\tilde{f}(x)<\infty\rbrace$. این بسط می‌تواند علامت‌گذاری را ساده کند، چون نباید آشکارا این دامنه را توصیف کنیم، یا مقدماتی به ازای هر $x\in\mathbf{dom}\:f$ ‌اضافه کنیم وقتی‌که به $f(x)$ میل می‌کنیم. برای مثال‌ نامساوی تعریف اساسی \eqref{1} را در نظر بگیرید، در بسط $\tilde{f}$، می‌توانیم آن را برای $0<\theta<1$، به ازای هر $x$ و $y$، به صورت زیر بیان کنیم \[ \tilde{f}(\theta x+(1-\theta)y)\leq\theta\tilde{f}(x)+(1-\theta)\tilde{f}(y) \] ( برای $\theta=0$ یا $\theta=1$ این نامساوی برقرار است.) البته در این کتاب باید این نامساوی را با استفاده از محاسبات گسترده و مرتب‌سازی بیان کنیم. برای $x$ و $y$ در $\mathbf{dom}\:f$ این نامساوی با \eqref{1}معادل است. در صورتی که هر دو خارج $\mathbf{dom}\:f$ باشد، آنگاه سمت راست $\infty$ است، بنابراین این نامساوی برقرار است. به‌عنوان مثال دیگر از این شیوه علامت‌گذاری فرض کنید $f_1$ و $f_2$ دو تابع محدب روی $\mathbf{R}^n$ باشد. مجموع نقطه به نقطه $f=f_1+f_2$ تابعی با دامنه‌ی $\mathbf{dom}\:f=\mathbf{dom}\:f_1\cap\mathbf{dom}\:f_2$ می‌باشد، به‌طوری‌که به ازای هر $x\in\mathbf{dom}\:f$، $f(x)=f_1(x)+f_2(x)$ باشد. با استفاده از بسط مقدار تعمیم یافته به‌سادگی می‌توانیم برای هر $\tilde{f}(x)=\tilde{f_1}(x)+\tilde{f_2}(x)$ نیز بگوییم. در این معادله دامنه‌ی $f$ به‌طور خودکار به صورت $\mathbf{dom}\:f=\mathbf{dom}\:f_1\cap\mathbf{dom}\:f_2$ تعریف شده است، بنابراین $\tilde{f}(x)=\infty$ وقتی‌که $x\notin\mathbf{dom}\:f_1$ یا $x\notin\mathbf{dom}\:f_2$. در این کتاب همین علامت را برای نشان دادن یک تابع محدب و بسط آن به‌کار می‌بریم، تا زمانی‌که هیچ زیانی از این ابهام وجود نداشته باشد. این همین فرض است که تمام توابع محدب به‌طور ضمنی تعمیم یافته، یعنی به‌طوری‌که $\infty$ خارج از دامنه‌شان تعریف می‌شود. \begin{example} تابع شاخص یک مجموعه محدب. فرض کنید $C\subseteq\mathbf{R}^n$ مجموعه‌ای محدب باشد، و تابع (محدب) $I_C$ را با دامنه‌ی $C$ و $I_C(x)=0$ به ازای هر $x\in C$ درنظر بگیرید، یعنی این تابع در مجموعه $C$ صفر است. بسط مقدار تعمیم یافته‌ی آن \begin{center} \[ \begin{tikzpicture} \draw [ultra thick](-4,2.5) to [out=-45,in=190] (0,0); \draw [ultra thick] (0,0) to [out=10,in=61] (3,3); \draw [ultra thick](-1,-1) to (3,2); \draw [fill] (0.8,0.4) circle [radius=0.09]; \node at (1.5,0) [color=blue]{$(x,f(x))$}; \node at (-3.3,2.5) [color=blue]{$f(y)$}; \node at (5.1,2) [color=blue]{$f(x)+\bigtriangledown f(x)^T(y-x)$}; \end{tikzpicture} \] \end{center} شکل3.2.اگر $f$ محدب و مشتق‌پذیر باشد‌، پس $f(x)+\bigtriangledown f(x)^T(y-x)\leq f(y)$ به ازای هر $x,y\in\mathbf{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$ (تعریف شده به ازای هر $\mathbf{R}^n$، می‌گویند) روی مجموعه‌ی $C$ همان به حداقل رساندن تابع $f+\tilde{I_c}$ بر تمام $\mathbf{R}^n$ است. درواقع، تابع $f+\tilde{I_c}$ (با قرارداد ذکر شده) $f$ به مجموعه‌ی $C$ محدود شده است. \end{example} در روشی مشابه می‌توانیم تابعی مقعر را با تعریف آن بسط دهیم تا $-\infty$ خارج از دامنه‌ی آن باشد. \subsection{شرایط مرتبه اول} فرض کنید $f$ مشتق‌پذیر باشد ( یعنی شیب آن $\bigtriangledown f$ در هر نقطه در $\mathbf{dom}\:f$ وجود دارد که باز است). آنگاه $f$ محدب است اگر‌وتنها‌اگر $\mathbf{dom}\:f$ محدب باشد و \begin{equation} f(y)\geq f(x)+\bigtriangledown f(x)^T(y-x)\label{2} \end{equation} به ازای هر $x,y\in\mathbf{dom}\:f$ برقرار باشد. این نامساوی در شکل 3.2 نشان داده می‌شود. تابع آفینی $y$ با $f(x)+\bigtriangledown f(x)^T(y-x)$داده شده است، البته تقریب تیلور مرتبه اول $f$ نزدیک $x$ است. نامساوی \eqref{2} بیان می‌کند که برای یک تابع محدب، تقریب تیلور مرتبه اول در واقع تحت برآوردگر سراسری تابع است. برعکس، اگر تقریب تیلور مرتبه اول یک تابع همیشه تحت برآوردگر سراسری تابع باشد، آنگاه تابع محدب است. نامساوی \eqref{2} اطلاعات موضعی درباره‌ی یک تابع محدب را نشان می‌دهد (یعنی مقدار و مشتق آن در یک نقطه) می‌توانیم اطلاعات کلی را دریابیم (یعنی تحت برآوردگر سراسری آن). شاید این مهمترین ویژگی توابع محدب باشد، و برخی ویژگی‌های قابل توجه توابع محدب و مسائل بهینه‌سازی محدب را توضیح می‌دهد. به‌عنوان مثالی ساده، نامساوی \eqref{2} نشان می‌دهد اگر $\bigtriangledown f(x)=0$ آنگاه به ازای هر $y\in\mathbf{dom}\:f$، $f(y)\geq f(x)$ یعنی $x$ می‌نیمم سراسری تابع $f$ است. اکیدا محدب نیز می‌تواند با یک شرط مرتبه اول مشخص شود :$f$ اکیدا محدب است اگر‌و‌تنها‌اگر $\mathbf{dom}\:f$ محدب باشد و برای $x,y\in\mathbf{dom}\:f$ و $x\neq y$، داریم \begin{equation} f(y)\geq f(x)+\bigtriangledown f(x)^T(y-x)\label{3} \end{equation} برای توابع مقعر خصوصیات متناظر را داریم: $f$ مقعر است اگر‌وتنها‌اگر $\mathbf{dom}\:f$ محدب باشد و به ازای هر $x,y\in\mathbf{dom}\:f$ داشته باشیم \[ f(y)\leq f(x)+\bigtriangledown f(x)^T(y-x) \] \subsection*{اثبات شرط تحدب درجه اول} برای ثابت کردن \eqref{2}، اول حالت $n=1$ را درنظر می‌گیریم: تابع مشتق‌پذیر $f:\mathbf{R}\rightarrow\mathbf{R}$ محدب است اگر‌و‌تنها‌اگر \begin{equation} f(y)\geq f(x)+f‌‌‌‌‌'(x)(y-x) \end{equation} به ازای هر $x$ و $y$ در $\mathbf{dom}\:f$. ابتدا فرض کنید که $f$ محدب است و $x,y\in\mathbf{dom}\:f$ باشد. نتیجه می‌گیریم که به ازای هر $00$ را به ازای هر $x \in\mathbf{dom}\:f$ ثابت می‌کند، اما یک تابع محدب نیست. \end{remark} \subsection{مثال‌ها} قبلا گفتیم که همه توابع خطی و آفینی محدب (و مقعر) هستند، و تحدب و تقعر توابع درجه دوم را شرح دادیم. در این بخش به چند نمونه از توابع محدب و مقعر می‌پردازیم. با برخی توابع در $\mathbf{R}$، با متغیر $x$ شروع می‌کنیم. \begin{itemize} \item\textbf{نمایی:} $\ee^{ax}$ در $\mathbf{R}$، برای هر $a\in\mathbf{R}$ محدب است. \item\textbf{توان‌ها:} $x^a$ در $\mathbf{R}_{++}$ محدب است زمانی‌که $a\geq 1$ یا $a\leq 0$، و مقعر است برای $0\leq a\leq 1$. \item\textbf{توان‌های قدر مطلق:} $|x|^p$، برای $p\geq 1$، در $\mathbf{R}$ محدب است. \item\textbf{لگاریتم:} $\log x$ در$\mathbf{R}_{++}$ مقعر است. \item\textbf{آنتروپی منفی:} $x\log x$ (یا در $\mathbf{R}_{++}$ یا در $\mathbf{R}_+$ برای $x=0$، $0$ تعریف می‌شود) محدب است. \end{itemize} تحدب یا تقعر این نمونه‌ها با اثبات نامساوی اولیه \eqref{1} یا با بررسی مشتق دوم که نامنفی یا نا‌مثبت است را می‌تواند نشان دهد. مثلا، $f(x)=x\log x$ را در نظر بگیرید، داریم \[ f'(x)=\log x+1,\qquad f''(x)=1/x, \] به‌طوری‌که $f''(x)>0$ برای $x>0$. این نشان می‌دهد که تابع آنتروپی منفی (اکیدا) محدب است. حالا چند نمونه جالب از توابع را در $\mathbf{R}^n$ می‌دهیم. \begin{itemize} \item\textbf{نرمها :} هر نرم در $\mathbf{R}^n$ محدب است. \item\textbf{توابع ماکسیمم :} $f(x)=\max\lbrace x_1,\ldots,x_n\rbrace$ در $\mathbf{R}^n$ محدب است. \item\textbf{تابع درجه دوم بر تابع خطی :} تابع $f(x,y)=x^2/y$، به‌طوری‌که \[ \mathbf{dom}\:f=\mathbf{R}\times\mathbf{R}_{++}=\lbrace (x,y)\in\mathbf{R}^2\:|\:y>0\rbrace, \] محدب است (شکل ۳). \item\textbf{لگاریتم ـ مجموع ـ تابع نمایی :} تابع $f(x)=\log(\ee^x_1+\cdots+\ee^x_n)$ در $\mathbf{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$ برابر هستند، نامساوی دوم برقرار است.) شکل۳.۴ ،$f$ را برای $n=2$ نشان می‌دهد. \item\textbf{میانگین هندسی:} میانگین هندسی $f(x)=(\prod_{i=1}^n x_i)^{1/n}$ در $\mathbf{dom}\:f=\mathbf{R}_{++}^n$ مقعر است. شکل۳.۴:گراف $f(x,y)=\log(\ee^x+\ee^y)$. \item\textbf{لگاریتم ـ دترمینان :} تابع $f(X)=\log\det X$ در $\mathbf{dom}\:f=S_{++}^n$ مقعر است. تحدب (یا تقعر) این نمونه‌ها می‌تواند به چند روش اثبات شود، مانند اثبات نامساوی \eqref{1}، اثبات این که هسیین نیمه معین مثبت است، یا با محدود کردن این تابع به یک خط دلخواه و اثبات تحدب تابع به‌دست آمده از یک متغیر. \end{itemize} \textbf{نرمها.} اگر $f:\mathbf{R}^n\rightarrow\mathbf{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). \] که از نامساوی مثلث، و برابری یکنواختی یک نرم به‌دست آمده است. \textbf{تابع ماکسیمم.} تابع $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*} \textbf{تابع مرتبه دوم بر تابع خطی.} برای نشان دادن اینکه تابع مرتبه دوم بر خطی $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. \] \textbf{لگاریتم ـ مجموع ـ نمایی.} هسیین تابع لگاریتم ـ مجموع ـ نمایی به صورت زیر است؛ \[ \bigtriangledown^2 f(x)=\frac{1}{(1^Tz)^2}((1^Tz)\mathbf{diag}(z)-zz^T), \] که $z=(\ee^{x_1},\ldots,\ee^{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}$ به دست آمده است. \textbf{میانگین هندسی.} در روشی مشابه می‌توانیم نشان دهیم که میانگین هندسی $f(x)=(\prod_{i=1}^n x_i)^{1/n}$ در $\mathbf{dom}\:f=\mathbf{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\mathbf{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$ به‌دست آمده است. \textbf{لگاریتم ـ دترمینان.} برای تابع $f(X)=\log\det X$ می‌توانیم تقعر را با درنظر گرفتن یک خط دلخواه اثبات کنیم، یعنی $X=Z+tV$، که $Z,V\in S^n$ می‌باشند. $g(t)$ را به صورت $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{مجموعه‌های زیرسطح} مجموعه $\alpha$-زیر‌سطح تابع $f:\mathbf{R}^n\rightarrow\mathbf{R}$ به صورت زیر تعریف می‌شود \[ C_\alpha=\lbrace x\in\mathbf{dom}\:f\:|\:f(x)\leq \alpha\rbrace. \] مجموعه‌های زیرسطح یک تابع محدب، برای هر مقدار از $\alpha$ محدب هستند. که اثبات آن از تعریف تحدب حاصل می‌شود: اگر $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)=-\ee^x$ در $\mathbf{R}$ محدب نیست (درواقع، اکیدا مقعر است) اما تمام مجموعه‌های زیرسطح آن محدب هستند. اگر $f$ مقعر باشد، پس تمام $\alpha$-فوق‌سطح آن که به صورت $\lbrace x\in\mathbf{dom}\:f\:|\:f(x)\geq\alpha\rbrace$ داده می‌شود، یک مجموعه محدب است. این ویژگی مجموعه زیرسطح، با بیان آن به‌عنوان یک مجموعه زیرسطح از تابعی محدب، یا به‌عنوان مجموعه فوق‌سطح از تابعی مقعر اغلب روش خوبی برای تحدب یک مجموعه است. \begin{example} میانگین هندسی و حسابی $x\in\mathbf{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\mathbf{R}_+^n|G(x)\geq\alpha A(x)\rbrace, \] یعنی مجموعه بردارها با میانگین هندسی از $\alpha$ برابر میانگین حسابی بزرگتر است. این مجموعه محدب است، چون مجموعه $0$ ـ فوق سطح تابع $G(x)-\alpha A(x)$ است، که مقعر است. درواقع، این مجموعه به‌طور مثبت همگن است، بنابراین مخروط محدب است. \end{example} \subsection{اپی‌گراف} نمودار تابع $f:\mathbf{R}^n\rightarrow\mathbf{R}$ به صورت زیر تعریف می‌شود \[ \lbrace(x,f(x))\:|\:x\in \mathbf{dom}\:f\rbrace, \] که ‌مجموعه‌ای زیرسطح از $\mathbf{R}^{n+1}$ است. اپی‌گراف تابع $f:\mathbf{R}^n\rightarrow\mathbf{R}$ به صورت زیر تعریف می‌شود \[ \mathbf{epi}\:f=\lbrace(x,t)\:|\:x\in\mathbf{dom}\:f,\;f(x)\leq t\rbrace, \] که زیر‌مجموعه‌ای از $\mathbf{R}^{n+1}$ است. ( $\mathbf{epi}$ به معنای بالاست پس اپی‌گراف به معنای بالای نمودار است.) این تعریف در شکل 3.5 نشان داده می‌شود. رابطه بین مجموعه‌های محدب و توابع محدب از طریق اپی‌گراف (بالای نمودار) می‌باشد: $A$ تابعی محدب است اگر‌و‌تنها‌اگر اپی‌گراف آن مجموعه‌ای محدب باشد. تابعی مقعر است اگر‌و‌تنها‌اگر هیپوگراف آن که به صورت زیر تعریف می‌شود \[ \mathbf{hypo}\:f=\lbrace(x,t)\:|\:t\leq f(x)\rbrace, \] مجموعه‌ای محدب باشد. شکل ۳.۵ \begin{example} تابع ماتریس گویا. تابع $f:\mathbf{R}^n\times\mathbf{S}^n\rightarrow\mathbf{R}$، که به صورت زیر تعریف می‌شود \[ f(x,Y)=x^T Y^{-1}x \] در $\mathbf{dom}\:f=\mathbf{R}^n\times\mathbf{S}_{++}^n$ محدب است. (این مثال تابع درجه دوم را بر تابع خطی $f(x,y)=x^2/y$، با $\mathbf{dom}\:f=\mathbf{R}\times\mathbf{R}_{++}$ تعمیم می‌دهد.) یک روش آسان برای ایجاد تحدب $f$ از طریق اپی‌گراف آن صورت می‌گیرد: \begin{align*} \mathbf{epi}\:f &=\lbrace(x,Y,t)\:|\:Y\succ 0,\;x^TY^{-1}x\leq t\rbrace\\ & =\left\lbrace (x,Y,t)\:\vert\:\begin{bmatrix} Y & x\\ x^T & t\\ \end{bmatrix} \succeq 0,\:Y\succ 0, \right\rbrace \end{align*} با استفاده از شرط مکمل شور برای ماتریس بلوکی نیمه معین مثبت. آخرین شرط نامساوی ماتریس خطی در $(x,Y,t)$ است، و بنابراین $\mathbf{epi}\:f$ محدب است. برای حالت خاص $n=1$، تابع ماتریس گویا به تابع درجه دوم بر تابع خطی $x^2/y$ ساده می‌شود، و نمایش $LMI$ وابسته به صورت زیر است \[ \begin{bmatrix} y & x\\ x & t\\ \end{bmatrix} \succeq 0 ,\quad y>0 \]\label{a} (نمودار آن در شکل 3.3 نشان داده می‌شود.) \end{example} نتایج بسیاری می‌تواند به‌طور هندسی با استفاده از اپی‌گراف‌‌ها برای توابع محدب، و با به‌کار بردن نتایج برای مجموعه‌های محدب ثابت شود (یا تفسیر شود). به عنوان مثال، شرط مرتبه اول برای تحدب را در نظر بگیرید: \[ f(y)\geq f(x)+\bigtriangledown f(x)^T(y-x), \] که $f$ محدب است و $x,y\in\mathbf{dom}\:f$ . می‌توانیم این نامساوی اساسی را به‌طور هندسی در عبارت $\mathbf{epi}\:f $ تفسیر کنیم. اگر $(y,t)\in\mathbf{epi}\:f$، آنگاه \[ t\geq f(y)\geq f(x)+\bigtriangledown f(x)^T(y-x). \] شکل ۳.۶ می‌توانیم این‌ را به صورت زیر بیان کنیم \[ (y,t)\in\mathbf{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. \] این به این معنا است که هیپوگراف تعریف شده با $(\bigtriangledown f(x),-1)$، $\mathbf{epi}\:f$ را در نقطه مرزی$(x,f(x))$ پشتیبانی می‌کند؛ شکل 3.6 را ببینید. \subsection{نامساوی و تعمیم جنسن} نامساوی اساسی \eqref{1}، یعنی \[ f(\theta x+(1-\theta)y)\leq\theta f(x)+(1-\theta)f(y), \] گاهی نامساوی جنسن هم نامیده می‌شود. که به آسانی به ترکیبات محدب بیشتر از دو نقطه تعمیم داده می‌شود: اگر $f$ محدب باشد، $x_1,\ldots,x_k\in\mathbf{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\mathbf{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, \] مشروط به اینکه انتگرال وجود دارد. در حالت کلی می‌توانیم هر احتمال اندازه‌گیری را با پشتیبانی در $\mathbf{dom}\:f$ در نظر بگیریم. اگر $x$ متغیری تصادفی با احتمال یک باشد به‌طوری‌که $x\in\mathbf{dom}\:f$، و $f$ محدب باشد، آنگاه داریم \begin{equation} f(\mathbf{E}\:x)\leq \mathbf{E}\:f(x),\label{4} \end{equation} مشروط به اینکه امید وجود دارد. می‌توانیم نامساوی اساسی \eqref{1} را از این شکل کلی، با در نظر گرفتن متغیر تصادفی $x$ که از $\lbrace x_1,x_2\rbrace$ پشتیبانی می‌کند، با $\mathbf{prob}(x=x_1)=\theta$، $\mathbf{prob}(x=x_2)=1-\theta$ بهبود ببخشیم. بنابراین نامساوی \eqref{4} تحدب را مشخص می‌کند: اگر $f$ محدب نباشد، متغیر تصادفی $x$، با احتمال یک که $x\in\textbf{dom} f$، به‌طوری‌که $f(\mathbf{E}\:x)=\mathbf{E}\:f(x)$ وجود دارد. حالا تمام این نامساوی‌ها، نامساوی جنسن نامیده می‌شود، حتی اگر نامساوی مورد مطالعه توسط جنسن یکی از نامساوی‌های ساده زیر باشد \[ f\left(\frac{x+y}{2}\right)\leq\frac{f(x)+f(y)}{2} \] \begin{remark} می‌توانیم \eqref{4} را به صورت زیر تفسیر کنیم. فرض کنید $x\in\mathbf{dom}\:f\subseteq\mathbf{R}^n$ و $z$ هر بردار تصادفی صفر در $\mathbf{R}^n$ باشد. آنگاه داریم \[ \mathbf{E}f(x+z)\geq f(x). \] بنابراین، تصادفی یا لرزشی (یعنی با اضافه کردن مقدار بردار تصادفی صفر به استدلال) نمی‌تواند مقدار تابع محدب را به‌طور متوسط کاهش دهد. \end{remark} \subsection{نامساوی‌ها} بسیاری از نامساوی‌های معروف می‌تواند با استفاده از نامساوی جنسن به تعدادی تابع محدب مناسب مشتق شود. (درواقع، تحدب و نامساوی جنسن می‌تواند پایه و اساس یک نظریه نامساوی را بسازد.) به‌عنوان یک مثال ساده، میانگین نامساوی حسابی-هندسی زیر را برای $a,b\geq 0$ در نظر بگیرید: \begin{equation} \sqrt{ab}\leq(a+b)/2\label{5} \end{equation} تابع $-\log \;x$ محدب است؛ نامساوی جنسن با $\theta=1/2$ \[ -\log\left(\frac{a+b}{2}\right)\leq\frac{-\log\;a-\log\;b}{2} \] با در نظر گرفتن دو طرف نامساوی \eqref{5} حاصل می‌شود. به‌عنوان یک مثال کم اهمیت‌تر نامساوی هولدر را ثابت می‌کنیم: برای $p> 1$، $1/p+1/q=1$ و $x,y\in\mathbf{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, \] و با جمع کردن $i$ آنگاه نامساوی هولدر به صورت زیر حاصل می‌شود. \[ \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}. \] \section{عملکردهایی که تحدب را حفظ می‌کند} در این بخش برخی عملکردهایی را که تحدب و تقعر توابع را حفظ می‌کند، یا به ما اجازه می‌دهد که توابع محدب و مقعر جدید بسازیم را شرح می‌دهیم. با برخی عملکردهای ساده مثل افزایش، مقیاس‌گذاری، و سوپریمم نقطه به نقطه شروع می‌کنیم و سپس برخی عملکردهای پیچیده‌تر مثل (برخی از آنها عبارتند از عملکردهای ساده مانند موارد خاص) را شرح می‌دهیم. \subsection{مقادیر وزن‌دار نامنفی} بدیهی است اگر $f$ تابعی محدب و $\alpha\geq 0$ باشد، آنگاه تابع $\alpha f$ محدب است. اگر $f_1$ و $f_2$ هر دو توابع محدب باشند، آنگاه مجموع آنها $f_1+f_2$ نیز محدب است. با ترکیب مقیاس‌گذاری و افزایش نامنفی، می‌بینیم که مجموعه‌ای از توابع محدب خودش مخروطی محدب است: مقادیر وزن‌دار نامنفی توابع محدب، \[ f=w_1 f_1+\cdots+w_m f_m, \] محدب است. به همین شکل، مقادیر وزن‌دار نا‌منفی توابع مقعر، مقعر است. مقادیر وزن‌دار نا‌منفی، غیر‌صفر توابع اکیدا محدب (مقعر) اکیدا محدب (مقعر ) است. این ویژگی‌ها به مقادیر نامتناهی و انتگرال‌ها تعمیم می‌یابد. مثلا، اگر $f(x,y)$ در $x$ به ازای هر $y\in\mathcal{A}$، و $w(y)\geq 0$ به ازای هر $y\in\mathcal{A}$ محدب باشد، آنگاه تابع $g$ که به صورت زیر تعریف می‌شود \[ g(x)=\int_\mathcal{A}w(y) f(x,y)\dd y \] در $x$ محدب است (مشروط به اینکه انتگرال وجود دارد.) واقعیت این است که تحدب تحت مقیاس‌گذاری و افزایش نا‌منفی به آسانی مستقیما محقق می‌شود، یا می‌تواند درشرایط اپی‌گراف‌های وابسته دیده شود. مثلا، اگر $w\geq 0$ و $f$ محدب باشد، داریم \[ \mathbf{epi}(w f)=\begin{bmatrix} I & 0\\ 0 & w\\ \end{bmatrix} \mathbf{epi}\:f, \] که محدب است چون تصویر مجموعه‌ای محدب تحت نگاشتی خطی محدب است. \subsection{ترکیب با نگاشت آفینی} فرض کنید $f:\mathbf{R}^n\rightarrow\mathbf{R}$ ، $A\in\mathbf{R}^{n\times m}$، و $b\in\mathbf{R}^n$. $g:\mathbf{R}^m\rightarrow\mathbf{R}$ را با $\mathbf{dom}\:g=\lbrace x\;|\: Ax+b\in \mathbf{dom}\:f\rbrace$ به صورت زیر تعریف کنید \[ g(x)=f(Ax+b), \] پس اگر $f$ محدب باشد آنگاه $g$ محدب است، اگر $f$ مقعر باشد، آنگاه $g$ مقعر است. \subsection{ماکزیمم و سوپریمم نقطه به نقطه} اگر $f_1$ و $f_2$ توابع محدب باشند آنگاه ماکزیمم نقطه به نقطه $f$ به صورت زیر تعریف می‌شود \[ f(x)=\max\lbrace f_1(x),f_2(x)\rbrace , \] با $\mathbf{dom}\:f=\mathbf{dom}\:f_1\cap\mathbf{dom}\:f_2$، که محدب است. این ویژگی به آسانی محقق می‌شود: اگر $0\leq\theta\leq 1$ و $x,y\in\mathbf{dom}\:f$، آنگاه \begin{align*} f(\theta x+(1-\theta)y) & =\max\lbrace f_1(\theta x+(1-\theta)y),f_2(\theta x+(1-\theta)y\rbrace\\ & \leq\max\lbrace\theta f_1(x)+(1-\theta)f_1(y),\theta f_2(x)+(1-\theta)f_2(y)\rbrace\\ & \leq\theta\max\lbrace f_1(x),f_2(x)\rbrace +(1-\theta)max\lbrace f_1(y),f_2(y)\rbrace\\ & =\theta f(x)+(1-\theta)f(y), \end{align*} که تحدب $f$ را ایجاد می‌کند. به آسانی نشان داده می‌شود که اگر $f_1,\ldots,f_m$ محدب باشند آنگاه ماکزیمم نقطه به نقطه \[ f(x)=\max\lbrace f_1(x),\ldots,f_m(x)\rbrace \] نیز محدب است. \begin{example} توابع تکه‌ای-خطی. تابع \[ f(x)=\max\lbrace a_1^T x+b_1,\ldots,a_L^T x+b_L\rbrace \] تابع تکه‌ای-خطی (یا واقعا، آفینی) (با $L$ یا ناحیه کمتر) را تعریف می‌کند. این تابع محدب است چون ماکزیمم نقطه به نقطه توابع آفینی است. معکوس این قضیه نیز می‌تواند نشان داده شود: هر تابع محدب تکه ای-خطی با $L$ یا ناحیه کمتر نیز می‌تواند به این شکل بیان شود. \end{example} \begin{example} مجموع بزرگترین مؤلفه‌های $r$. برای $x\in\mathbf{R}^n$ آن را با $x_{[i]}$ بزرگترین مؤلفه $i$ام $x$ مشخص می‌کنیم، یعنی \[ x_{[1]}\geq x_{[2]}\geq\cdots\geq x_{[n]} \] مؤلفه‌های $x$ در ترتیب غیر‌افزایشی طبقه‌بندی می‌شوند. پس تابع \[ f(x)=\sum_{i=1}^r x_{[i]}, \] مجموع بزرگترین مؤلفه‌های $r$ از $x$ تابعی محدب است. که می‌تواند به صورت زیر نوشته شود \[ f(x)=\sum_{i=1}^r x_{[i]}=\max\lbrace x_{i_1}+\cdots+x_{i_r}\:|\: 1\leq i_1< i_2<\cdots-\infty \end{Bmatrix} \] چون $g$ خانواده‌ای از توابع خطی $w$ (که با $x\in\mathbf{R}^n$ نشان داده می‌شود)، تابعی مقعر $w$ است. می‌توانیم بیانی صریح و روشن برای $g$، تقریبا بر روی بخشی از دامنه آن استنتاج کنیم. فرض کنید $W=\mathbf{diag}(w)$، ماتریس قطری با مؤلفه‌های $w_1,\ldots,w_n$ باشد، و فرض کنید $A\in\mathbf{R}^{n\times m}$ دارای سطرهای ${a_i}^T$ باشد، بنابراین داریم \[ g(w)=\underset{x}{\inf}(Ax-b)^T W(Ax-b)=\underset{x}{\inf}(x^T A^T WAx-2b^T WAx+b^T Wb). \] از این توضیحات دیدیم که اگر $A^T WA\nsucceq 0$، تابع درجه دوم زیر در $x$ بیکران است، پس $g(w)=-\infty$، یعنی $w\notin\mathbf{dom}\:g$. می‌توانیم بیان ساده‌ای برای $g$ بدهیم زمانی‌که $A^T WA\succ 0$ (که نامساوی ماتریس اکیدا خطی را تعریف می‌کند)، با به حداقل رساندن تابع درجه دوم به‌طور تحلیلی: \begin{align*} g(w) & =b^T Wb-b^T WA(A^T WA)^{-1} A^T Wb\\ & =\sum_{i=1}^n w_i b_i^2-\sum_{i=1}^n w_i^2 b_i^2 a_i^T\left(\sum_{j=1}^n w_j a_j a_j^T\right)^{-1}a_i. \end{align*} از این بیان تقعر $g$ فورا آشکار نمی‌شود (اما آن را دنبال می‌کند، مثلا، از تحدب تابع ماتریس گویا؛ مثال \eqref{a} را ببینید). \end{example} \begin{example} حداکثر مقادیر‌ویژه ماتریس متقارن. تابع $f(X)=\lambda_max(X)$، به طوری‌که $\mathbf{dom}\:f=\mathbf{S}^{rn}$، محدب است. برای دیدن این توضیح، $f$ را به صورت زیر بیان می‌کنیم \[ f(X)=\sup\lbrace y^TXy\:|\:\Vert y\Vert_2=1\rbrace, \] یعنی به صورت سوپریمم نقطه به نقطه‌ی خانواده‌ای از توابع خطی $X$ (یعنی $y^TXy$) به‌طوری‌که $y\in\mathbf{R}^m$ نشان داده می‌شود. \end{example} \begin{example} نرم یک ماتریس. $f(X)=\Vert X\Vert_2$ را با $\mathbf{dom}\: f=\mathbf{R}^{p\times q}$ درنظر بگیرید، به‌طوری‌که $\Vert\cdot\Vert_2$ نرم طیفی یا مقدار منحصر‌بفرد ماکسیمم را نشان می‌دهد. تحدب $f$ از \[ f(X)=\sup\lbrace u^T X\upsilon|\:\Vert u\Vert_2=1,\:\Vert\upsilon\Vert_2=1\rbrace, \] استنباط می‌شود که نشان می‌دهد آن سوپریمم نقطه به نقطه‌ی خانواده‌ای از توابع خطی $X$ است. به عنوان یک کلیت فرض کنید $\Vert\cdot\Vert_a$ و $\Vert\cdot\Vert_b$ به ترتیب نرم‌هایی در $\mathbf{R}^p$ و $\mathbf{R}^q$ باشند. نرم ناشی از ماتریس $X\in\mathbf{R}^{p\times q}$ به صورت زیر تعریف می‌شود \[ \Vert X\Vert_{a,b}=\underset{\upsilon\neq 0}{\sup}\frac{\Vert X_\upsilon\Vert_a}{\Vert\upsilon\Vert_b}. \] (این زمانی‌که هر دو نرم اقلیدسی باشند به نرم طیفی ساده می‌شود.) نرم به‌دست آمده می‌تواند به صورت زیر بیان شود \begin{align*} \Vert X\Vert_{a,b} &=\sup\lbrace\Vert X_\upsilon\Vert_a\:|\:\Vert\upsilon\Vert_b=1\rbrace\\ &=\sup\lbrace u^T X \upsilon\:|\:\Vert u\Vert_{a^*}=1,\:\Vert\upsilon\Vert_b=1\rbrace, \end{align*} که $\Vert\cdot\Vert_{a^*}$ نرم دوگان $\Vert\cdot\Vert_a$ است، و این حقیقت را به‌کار می‌بریم که \[ \Vert z\Vert_a=\sup\lbrace u^T z\:|\:\Vert u\Vert_{a^*}=1\rbrace. \] چون $\Vert X\Vert_{a,b}$ را به صورت سوپریمم توابع خطی $X$ بیان کردیم، پس تابعی محدب است. \end{example} \subsection*{نمایش سوپریمم نقطه به نقطه‌ی توابع آفینی} مثال‌های بالا روش خوبی برای تعمیم تحدب یک تابع را نشان می‌دهند: طبق آن‌چه بیان شد به‌عنوان سوپریمم نقطه به نقطه‌ی خانواده‌ای از توابع آفینی. جز برای شرایط خاص، معکوس را حفظ می‌کند: تقریبا هر تابع محدبی می‌تواند به عنوان سوپریمم نقطه به نقطه‌ی خانواده‌ای از توابع آفینی بیان شود. مثلا، اگر $f:\mathbf{R}^n\rightarrow\mathbf{R}$ محدب باشد، با $\mathbf{dom}\: f=\mathbf{R}^n$، آنگاه داریم \[ f(x)=\sup\lbrace g(x)\:|\:g\:\text{آفینی},\:g(z)\leq f(z)\:\text{برای هر}\: z\rbrace. \] به عبارت دیگر $f$، سوپریمم نقطه به نقطه‌ی مجموعه‌ای از تمام آفینی تحت برآوردگرهای سراسری آن است. اثبات این نتیجه را در زیر می‌دهیم، و این مورد را که $\mathbf{dom}\: f=\mathbf{R}^n$ به‌عنوان تمرین رها می‌کنیم. فرض کنید $f$ با $\mathbf{dom}\: f=\mathbf{R}^n$ محدب است. نامساوی \[ f(x)\geq\sup\lbrace g(x)\:|\:g\:\text{آفینی},\:g(z)\leq f(z)\:\text{برای هر}\:z\rbrace \] واضح است، چون اگر $g$، تحت هر برآوردگر $f$ آفینی باشد، داریم $g(x)\leq f(x)$. برای ایجاد برابری، نشان می‌دهیم که به ازای هر $x\in\mathbf{R}^n$ تابع آفینی $g$ وجود دارد، که تحت برآوردگر سراسری $f$ است و $g(x)=f(x)$ را اثبات می‌کند. البته اپی‌گراف بالای نمودار $f$ مجموعه‌ای محدب است. بنابراین، می‌توانیم یک ابرصفحه را برای آن در $(x,f(x))$ بیابیم، یعنی، $a\in\mathbf{R}^n$ و $b\in\mathbf{R}$ به‌طوری‌که $(a,b)\neq 0$ و \[ \begin{bmatrix} a\\ b\\ \end{bmatrix}^T \begin{bmatrix} x-z\\ f(x)-t\\ \end{bmatrix}\leq 0 \] به ازای هر $(z,t)\in\mathbf{epi}\:f$. این به این معنی است که \begin{equation} a^T(x-z)+b(f(x)-f(z)-s)\leq 0\label{7} \end{equation} به ازای هر $z\in\mathbf{dom}\: f=\mathbf{R}^n$ و هر $s\geq 0$ (چون $(z,t)\in\mathbf{epi}\:f$ یعنی $t=f(z)+s$ برای برخی از $s\geq 0$). نامساوی \eqref{7} که به ازای هر $s\geq 0$ برقرار است، باید داشته باشیم $b\geq 0$. اگر $b=0$، آنگاه نامساوی \eqref{7} به $a^T(x-z)\leq 0$ به ازای هر $z\in\mathbf{R}^n$ ساده می‌شود که نتیجه می‌دهد $a=0$ و $(a,b)\neq 0$. نتیجه می‌گیریم که $b>0$ یعنی اینکه، ابرصفحه عمودی نیست. با استفاده از این حقیقت که $b>0$ برای $s=0$ دوباره \eqref{7} را به ازای هر $z$ به صورت زیر می‌نویسیم \[ g(z)=f(x)+(a/b)^T(x-z)\leq f(z) \] تابع $g$ تحت برآوردگر $f$ آفینی است و $g(x)=f(x)$ را اثبات می‌کند. \subsection{ترکیب} در این بخش شرایط را در $h:\mathbf{R}^k\rightarrow\mathbf{R}$ و $g:\mathbf{R}^n\rightarrow\mathbf{R}^k$ بررسی می‌کنیم که تحدب یا تقعر ترکیب آنها را در $f=h\:o\:g:\mathbf{R}^n\rightarrow\mathbf{R}$ تضمین می‌کند، به صورت زیر تعریف می‌شود \[ f(x)=h(g(x)),\qquad\mathbf{dom}\: f=\lbrace x\in\mathbf{dom}\: g\:|\:g(x)\in\mathbf{dom}\; h\rbrace. \] \subsection*{ترکیب اسکالر} ابتدا حالت $k=1$ را در نظر می‌گیریم، پس $h:\mathbf{R}\rightarrow\mathbf{R}$ و $g:\mathbf{R}^n\rightarrow\mathbf{R}$. می‌توانیم آن را برای حالت $n=1$ محدود کنیم (چون تحدب با رفتار یک تابع در خطوط دلخواه که دامنه خود را از وسط قطع می‌کند، مشخص می‌شود). برای یافتن قواعد ترکیب، با این فرض که $h$ و $g$ دوبار مشتق‌پذیرند، با $\mathbf{dom}\:g=\mathbf{dom}\:h=\mathbf{R}$ شروع می‌کنیم. در این حالت، تحدب $f$ به $f''\geq 0$ کاهش می‌یابد. ( به این معنی که $f''(x)\geq 0$ به ازای هر $x\in\mathbf{R}$). مشتق دوم تابع مرکب $f=h\:o\:g$ به صورت زیر داده می‌شود \begin{equation} f''(x)=h''(g(x))g'(x)^2+h'(g(x))g''(x).\label{8} \end{equation} حالا فرض کنید که، مثلا، $g$ محدب (پس $g''\geq 0$) و $h$ محدب و غیر‌کاهشی باشد (پس $h''\geq 0$ و $h'\geq 0$). از \eqref{8} نتیجه می‌شود که $f''\geq 0$. یعنی،$f$ محدب است. در روشی مشابه، فرمول \eqref{8} نتایج زیر را می‌دهد: \begin{equation} \begin{split} & f \text{{محدب است اگر h \text{محدب و غیر‌کاهشی، و} g \text{محدب باشد.}\\ & f \text{محدب است اگر} h \text{محدب و غیر‌افزایشی، و} g \text{مقعر باشد.}\\ & f \text{مقعر است اگر} h \text{مقعر و غیر‌کاهشی، و} g \text{مقعر باشد.}\\ & f \text{مقعر است اگر} h \text{مقعر و غیر‌افزایشی، و} g \text{محدب باشد.} \end{split} \end{equation} زمانی‌که توابع $g$ و $h$ دو‌بار مشتق‌پذیر باشند و دامنه‌ی آنها $\mathbf{R}$ باشند این توضیحات برقرار هستند. به نظر می‌رسد که قواعد ترکیب در حالت کلی $n>1$، بدون درنظرگرفتن قابلیت مشتق‌پذیری $h$ و $g$ یا اینکه $\mathbf{dom}\:g=\mathbf{R}^n$ و $\mathbf{dom}\:h=\mathbf{R}$ برقرار است. %\begin{equation} %\begin{split} %& f \text{محدب است اگر} h \text{محدب باشد، } \tilde{h} \text{غیر‌کاهشی، و } g \text{محدب باشد.}\\ %& f \text{محدب است اگر} h \text{محدب باشد، } \tilde{h} \text{غیر‌افزایشی، و } g \text{مقعر باشد.}\\ %& f \text{مقعر است اگر} h \text{مقعر باشد، } \tilde{h} \text{ غیر‌کاهشی، و} g \text{مقعر باشد.}\\ %& f \text{مقعر است اگر} h \text{مقعر باشد، } \tilde{h} \text{ غیر‌افزایشی، و} g \text{محدب باشد.} %\end{split} %\end{equation} در اینجا $\tilde{h}$ بسط مقدار تعمیم یافته‌ی تابع $h$ را نشان می‌دهد، که مقدار $\infty$ ($-\infty$) را برای نقاط تعیین می‌کند نه در $\mathbf{dom}\:h$ برای $h$ محدب (مقعر). تنها تفاوت بین این نتایج و نتایج موجود در (3.10)، این است که ما به تابع بسط مقدار تعمیم یافته $\tilde{h}$ نیاز داریم تا روی تمام $\mathbf{R}$ غیر‌افزایشی یا غیر‌کاهشی باشد. برای اینکه بفهمیم این مطلب به چه معناست، فرض کنید $h$ محدب باشد، بنابراین $\tilde{h}$ مقدار $\infty$ خارج از $\mathbf{dom}\:h$ می‌گیرد. می‌گویند $\tilde{h}$ غیر‌کاهشی است به این معنی که به ازای هر $x,y\in\mathbf{R}$ به‌طوری‌که $x1$، بدون فرض قابلیت مشتق‌پذیری $h$ یا $g$ و دامنه‌های کلی برقرار است. برای نتایج کلی، شرایط یکنواختی در $h$ باید برای بسط مقدار تعمیم یافته‌ی $\tilde{h}$ برقرار باشد. برای درک معنای این شرایط که بسط مقدار تعمیم یافته‌ی $\tilde{h}$ یکنواخت است، این مورد را در نظر می‌گیریم که $h:\mathbf{R}^k\rightarrow\mathbf{R}$ محدب باشد و $\tilde{h}$ غیر‌کاهشی باشد، یعنی هر‌وقت $u\preceq \upsilon$ داریم $\tilde{h}(u)\leq\tilde{h}(\upsilon)$. این نشان می‌دهد که اگر $\upsilon\in\mathbf{dom}\:h$، بنابراین $u\in\mathbf{dom}\:h$ می‌باشد: دامنه $h$ باید به‌طور بی‌نهایت در جهت $-\mathbf{R}_+^k$ گسترش یابد. می‌توانیم آن را به‌طور به‌هم پیوسته بیان کنیم به‌طوری‌که $\mathbf{dom}\:h-\mathbf{R}_+^k=\mathbf{dom}\:h$. \begin{example} مثال‌های بردار ترکیبی. \begin{itemize} \item فرض کنید $h(z)=z_{[1]}+\cdots+z_{[r]}$، مجموع بزرگترین مؤلفه $r$ از $z\in\mathbf{R}^k$ باشد. پس $h$ محدب و در هر استدلال غیر‌کاهشی است. فرض کنید $g_1,\ldots,g_k$ توابع محدب در $\mathbf{R}^n$ باشند. آنگاه تابع ترکیب $f=h\:o\:g$ یعنی مجموع نقطه به نقطه بزرگترین $r$ از $g_i$ محدب است. \item تابع $h(z)=\log(\sum_{i=1}^k \ee^{z_i})$ محدب و در هر استدلالی غیر‌کاهشی است بنابراین $\log(\sum_{i=1}^k \ee^{g_i})$ محدب است هر‌وقت $g_i$ها محدب باشند. \item برای $0-\infty$ برای برخی از $x$ها (که $g(x)>-\infty$ را به ازای هر $x$ نشان می‌دهد). دامنه $g$ تصویر $\mathbf{dom}\:f$ در $x$ ـ مختصات آن است. یعنی \[ \mathbf{dom}\:g=\lbrace x\:|\:(x,y)\in\mathbf{dom}\:f\:\text{برای بعضی}\:y\in C\rbrace. \] این موضوع را با صحت نابرابری جنسن برای $x_1,x_2\in\mathbf{dom}\:g$ ثابت می‌کنیم. فرض کنید $\epsilon>0$. آنگاه $y_1,y_2\in C$ وجود دارد به‌طوریکه $f(x_i,y_i)\leq g(x_i)+\epsilon$ برای $i=1,2$. حالا فرض کنید $\theta\in[0,1]$ باشد. داریم \begin{align*} g(\theta x_1+(1-\theta)x_2) &=\underset{y\in C}{\inf}\:f(\theta x_1+(1-\theta)x_2,y)\\ &\leq f(\theta x_1+(1-\theta)x_2,\theta y_1+(1-\theta)y_2)\\ &\leq\theta f(x_1,y_1)+(1-\theta)f(x_2,y_2)\\ &\leq\theta g(x_1)+(1-\theta)g(x_2)+\epsilon. \end{align*} چون این رابطه برای هر $\epsilon>0$ برقرار است، داریم \[ g(\theta x_1+(1-\theta)x_2)\leq \theta g(x_1)+(1-\theta)g(x_2). \] این نتیجه نیز می‌تواند در عبارت اپی‌گراف‌ها دیده شود. با $f$، $g$، و $C$ همان‌طور‌که در \eqref{16} تعریف شده و با فرض اینفیمم بر $y\in C$ برای هر $x$ به‌دست آورده می‌شود، داریم \[ \mathbf{epi}\:g=\lbrace(x,t)\:|\:(x,y,t)\in\mathbf{epi}\:f\:\text{برای بعضی}\:y\in C\rbrace. \] بنابراین $\mathbf{epi}\:g$ محدب است، چون آن تصویر مجموعه‌ای محدب روی برخی از مؤلفه‌هایش است. \begin{example} مکمل اسچوار. فرض کنید تابع درجه دوم \[ f(x,y)=x^T Ax+2x^T By+y^T Cy, \] (که $A$ و $C$ متقارن هستند) در $(x,y)$ محدب باشد به این معنی که \[ \begin{bmatrix} A & B\\ B^T & C\\ \end{bmatrix} \succeq 0. \] می‌توانیم $g(x)=\inf_y f(x,y)$ را بیان کنیم به‌طوری‌که \[ g(x)=x^T(A-BC^\dagger B^T)x, \] که $C^\dagger$ شبه ـ معکوس $C$ است. به‌وسیله‌ی قاعده می‌نیمم‌سازی، $g$ محدب است، پس نتیجه می‌گیریم که $A-BC^\dagger B^T\succeq 0$. اگر $C$ معکوس‌پذیر باشد، یعنی $C\succ 0$ آنگاه ماتریس $A-BC^{-1}B^T$ مکمل اسچوار از $C$ نامیده می‌شود در ماتریس \[ \begin{bmatrix} A & B\\ B^T & C\\ \end{bmatrix} \] \end{example} \begin{example} فاصله تا یک مجموعه. فاصله‌ی نقطه‌ی $x$ تا مجموعه‌ی $S\subseteq\mathbf{R}^n$، در نرم $\Vert\cdot\Vert$، به صورت زیر تعریف می‌شود \[ \mathbf{dist}(x,S)=\underset{y\in S}{\inf}\Vert x-y\Vert. \] تابع $\Vert x-y\Vert$ در $(x,y)$ محدب است، پس اگر مجموعه‌ی $S$ محدب باشد، تابع فاصله $\mathbf{diast}(x,S)$ یک تابع محدب از $x$ است. \end{example} \begin{example} فرض کنید $h$ محدب باشد. آنگاه تابع $g$ که به‌صورت زیر تعریف می‌شود \[ g(x)=\inf\lbrace h(y)\:|\:Ay=x\rbrace \] محدب است. می‌بینیم، $f$ را به‌صورت زیر تعریف می‌کنیم \[ f(x,y)=\begin{cases} h(y) & \text{اگر}\:Ay=x\\ \infty & \text{در غیر این ‌صورت}, \end{cases} \] که در $(x,y)$ محدب است. آنگاه $g$ می‌نیمم $f$ بر $y$ است، و از این‌رو محدب است. (سخت نیست مستقیما نشان دهیم که $g$ محدب است.) \end{example} \subsection{تصویر یک تابع} اگر $f:\mathbf{R}^n\rightarrow\mathbf{R}$، آنگاه تصویر $f$ تابع $g:\mathbf{R}^{n+1}\rightarrow\mathbf{R}$ است که به صورت زیر تعریف می‌شود \[ g(x,t)=tf(x/t), \] با دامنه \[ \mathbf{dom}\:g=\lbrace(x,t)\:|\:x/t\in\mathbf{dom}\:f,\:t>0\rbrace. \] عملکرد حفظ تحدب تصویر: اگر $f$ تابعی محدب باشد آنگاه تابع تصویر آن یعنی $g$ محدب است. به‌طور مشابه، اگر $f$ مقعر باشد آنگاه $g$ مقعر است. که می‌تواند به چندین روش ثابت شود، مثلا، تایید مستقیم تعریف نامساوی. در اینجا اثبات کوتاهی با استفاده از اپی‌گراف‌ها و نگاشت تصویر در $\mathbf{R}^{n+1}$ آوردیم (که نام تصویر را نیز توضیح می‌دهد). برای $t>0$ داریم \begin{align*} (x,t,s)\in\mathbf{epi}\:g & \Longleftrightarrow tf(x/t)\leq s\\ & \Longleftrightarrow f(x/t)\leq s/t\\ & \Longleftrightarrow (x/t,s/t)\in\mathbf{epi}\:f. \end{align*} بنابراین $\mathbf{epi}\:g$ تصویر معکوس $\mathbf{epi}\:f$ تحت نگاشت تصویر $(u,\upsilon,w)$ به $(u,w)/\upsilon$ است. که نشان می‌دهد $\mathbf{epi}\:g$ محدب است، پس $g$ محدب است. \begin{example} نرم اقلیدسی مربع. تصویر تابع محدب $f(x)=x^T x$ روی $\mathbf{R}^n$ که به صورت زیر است \[ g(x,t)=t(x/t)^T(x/t)=\frac{x^T x}{t}, \] در $(x,t)$ برای $t>0$ محدب است. می‌توانیم تحدب $g$ را با استفاده از چندین روش دیگر استنباط کنیم. ابتدا می‌توانیم $g$ را به‌عنوان مجموع توابع درجه دوم بر خطی $x_i^2/t$ بیان کنیم، که قبلا نشان داده ‌شد محدب است. می‌توانیم $g$ را نیز به‌عنوان یک مورد خاص از تابع ماتریس گویا $x^T(tI)^{-1}x$ توضیح دهیم(مثال \eqref{a} را ببینید). \end{example} \begin{example} لگاریتم منفی. تابع محدب $f(x)=-\log x$ را روی $R_{++}$ در نظر بگیرید. تصویر آن به صورت زیر می‌باشد \[ g(x,t)=-t\log(x/t)=t\log(t/x)=t\log(t/x)=t\log t-t\log x, \] و روی $\mathbf{R}_{++}^2$ محدب است. تابع $g$ آنتروپی وابسته‌ی $t$ و $x$ نامیده می‌شود. برای $x=1$، $g$ به تابع آنتروپی منفی ساده می‌شود. از تحدب $g$ می‌توانیم تحدب یا تقعر چند تابع مرتبط جالب را ایجاد کنیم. ابتدا، آنتروپی وابسته‌ی دو بردار $u,\upsilon\in\mathbf{R}_{++}^n$، تعریف می‌شود به‌طوری‌که \[ \sum_{i=1}^n u_i\log(u_i/\upsilon_i), \] در $(u,\upsilon)$، محدب است، چون آن مجموع آنتروپی وابسته‌ی $u_i,\upsilon_i$ است. تابع وابسته دیورژانس کولبک-لیبر بین $u,\upsilon\in\mathbf{R}_{++}^n$ است، که به صورت زیر داده می‌شود \begin{equation} D_k(u,\upsilon)=\sum_{i=1}^n(u_i\log(u_i/\upsilon_i)-u_i+\upsilon_i), \end{equation} محدب است، چون آنتروپی وابسته پلاس تابع خطی $(u,\upsilon)$ است. دیورژانس کولبک-لیبر $D_k(u,\upsilon)\geq 0$ و $D_k(u,\upsilon)=0$ را ثابت می‌کند اگر‌و‌تنها‌اگر $u=\upsilon$ و بنابراین می‌تواند به‌عنوان اندازه انحراف بین دو بردار مثبت به‌کار برده شود؛ (توجه کنید که آنتروپی وابسته و دیورژانس کولبک-لیبر مشابه هستند وقتی‌که $u$ و $\upsilon$ بردار احتمال باشند یعنی $1^T u=1^T\upsilon=1$ را ثابت می‌کنند.) اگر $\upsilon_i=1^T u$ را در تابع آنتروپی وابسته بگیریم، تابع مقعر (و مشابه‌ی) $u\in\mathbf{R}_{++}^n$ را به‌دست می‌آوریم. به صورت زیر داده می‌شود \[ \sum_{i=1}^n u_i\log(1^T u/u_i)=(1^T u)\sum_{i=1}^n z_i\log(1/z_i), \] که $z=u/(1^T u)$ تابع آنتروپی نرمال نامیده می‌شود. بردار $z=u/(1^T u)$، یک بردار نرمال یا توزیع احتمال است، چون مجموع مؤلفه‌های آن به یک، آنتروپی نرمال $1^T u$ در آنتروپی این توزیع نرمال است. \end{example} \begin{example} فرض کنید $f:\mathbf{R}^m\rightarrow\mathbf{R}$ محدب است، و $A\in\mathbf{R}^{m\times n}$، $b\in\mathbf{R}^m$، $c\in\mathbf{R}^n$، و تعریف می‌کنیم \[ g(x)=(c^T x+d)f((Ax+b)/(c^T x+d)), \] با \[ \mathbf{dom}\:g=\lbrace x\:|\:c^T x+d>0,\:(Ax+b)/(c^T x+d)\in\mathbf{dom}\:f\rbrace. \] آنگاه $g$ محدب است. \end{example} \section{تابع مزدوج} در این بخش عملکردهایی را معرفی می‌کنیم که نقش مهمی در فصل‌های بعد ایفا می‌کند. \begin{center} \[ \begin{tikzpicture} \draw [ultra thick] (-5,-1) to(5,-1); \draw [ultra thick] (0,-4) to (0,5) ; \node at (-4.5,4) [color=blue]{$f(x)$}; \node at (4.8,2.9) [color=blue]{$xy$}; \node at (5.2,-1) [color=blue]{$x$}; \node at (1.1,-2.7) [color=blue]{$(0,-f^*(y))$}; \draw [ultra thick](-5,4) to [out=-80,in=110] (-3.5,-2.5); \draw [ultra thick] (-3.5,-2.5) to [out=-70,in=200](-0.7,1) ; \draw [ultra thick](-0.7,1) to [out=15,in=140] (0.5,0.5); \draw [ultra thick] (0.5,0.5) to [out=-50,in=166](2,-0.4); \draw [ultra thick] (2,-0.4) to [out=-15,in=86](4,4); \draw[dashed] (-3,-3.6) to (4.5,2.9); \draw[dashed] (-2,-4.3) to (4.5,1.4); \draw [fill] (0,-2.54) circle [radius=0.09]; \draw [fill] (2.7,-0.2) circle [radius=0.09]; \end{tikzpicture} \] \end{center} \subsection{تعریف و مثال‌ها} فرض کنید $f:\mathbf{R}^n\rightarrow\mathbf{R}$. تابع $f^*:\mathbf{R}^n\rightarrow\mathbf{R}$، که به صورت زیر تعریف می‌شود \begin{equation} f^*(y)=\underset{x\in\mathbf{dom}\:f}{\sup}(y^T x-f(x)), \end{equation} مزدوج تابع $f$ نامیده می‌شود. دامنه تابع مزدوج شامل $y\in\mathbf{R}^n$ که سوپریمم متناهی است، یعنی، اینکه تفاضل $y^T x-f(x)$ روی $\mathbf{dom}\:f$ از بالا کراندار است. این تعریف در شکل 3.8 نشان داده می‌شود. سریعا می‌بینیم که $f^*$ تابعی محدب است، چون سوپریمم نقطه به نقطه‌ی خانواده‌ی توابع محدب $y$ (درواقع، آفینی) است. چه $f$ محدب باشد یا نه درست است . (توجه کنید زمانی‌که $f$ محدب است، زیرنویس $x\in\mathbf{dom}\:f$ ضروری نیست چون قرارداد، $y^T x-f(x)=-\infty$ برای $x\notin\mathbf{dom}\:f$ را داریم.) با چند مثال ساده شروع می‌کنیم، و سپس برخی قواعد را برای توابع مزدوج توضیح می‌دهیم. این به ما اجازه می‌دهد که با یک بیان تحلیلی برای مزدوج بسیاری از توابع محدب معمول استنتاج کنیم. \begin{example} مزدوج برخی از توابع محدب را در $\mathbf{R}$ استنتاج می‌کنیم. \begin{itemize} \item تابع آفینی. $f(x)=ax+b$. به‌عنوان تابعی از $x$، $yx-ax-b$ کراندار است اگر‌و‌تنها‌اگر $y=a$، که در آن صورت ثابت است. بنابراین دامنه‌ی تابع مزدوج $f^*$ تک عضوی $\lbrace a\rbrace$ است، و $f^*(a)=-b$. \item · لگاریتم منفی. $f(x)=-\log x$ با $\mathbf{dom}\:f=-\mathbf{R}_{++}$. تابع $xy+\log x$ از بالا بیکران است اگر $y\geq 0$ و در ‌غیر ‌این ‌صورت ماکسیمم آن به $x=-1/y$ می‌رسد. بنابراین، $\mathbf{dom}\:f^*=\lbrace y\:|\:y<0\rbrace=-\mathbf{R}_{++}$ و $f^*(y)=-\log(-y)-1$ برای $y<0$. \item نمایی.$f(x)=\ee^x$. $xy-\ee^x$ بیکران است اگر $y<0$. برای $y>0$، $xy-\ee^x$ ماکسیمم آن به $x=\log y$ می‌رسد، پس داریم $f^*(y)=y\log y-y$. برای $y=0$، $f^*(y)=\sup_x-\ee^x=0$. خلاصه $\mathbf{dom}\:f^*=\mathbf{R}_+$ و $f^*(y)=y\log y-y$ (با بیان $0\log 0=0$). \item آنتروپی منفی. $f(x)=x\log x$، با $\mathbf{dom}\:f=\mathbf{R}_+$ (و $f(0)=0$). تابع $xy-x\log x$ روی $\mathbf{R}_+$ به ازای هر $y$ از بالا کراندار است، بنابراین، $\mathbf{dom}\:f^*=\mathbf{R}$. که در $x=\ee^{y-1}$، به ماکسیمم خود می‌رسد و با جایگزینی پیدا می‌کنیم $f^*(y)=\ee^{y-1}$. \item معکوس. $f(x)=1/x$ روی $\mathbf{R}_{++}$. برای $y>0$، $yx-1/x$ از بالا بیکران است. برای $y=0$ این تابع سوپریمم $0$ دارد؛ برای $y<0$ سوپریمم در $x=(-y)^{-1/2}$ به‌دست می‌آید. بنابراین، داریم $f^*(y)=-2(-y)^{1/2}$، با $\mathbf{dom}\:f^*=-\mathbf{R}_+$. \end{itemize} \end{example} \begin{example} تابع درجه دوم اکیدا محدب. $f(x)=\frac{1}{2} x^T Qx$، را با $Q\in\mathbf{S}_{++}^n$ در نظر بگیرید. تابع $y^Tx-\frac{1}{2}x^TQx$ به‌عنوان تابعی از $x$ به ازای هر $y$ از بالا کراندار است. که در $x=Q^{-1}y$ به ماکسیمم خود می‌رسد، پس \[ f^*(y)=\frac{1}{2}y^TQ^{-1}y. \] \end{example} \begin{example} لگاریتم ـ دترمینان. $f(X)=\log\det X^{-1}$ را روی $\mathbf{S}_{++}^n$ در نظر می‌گیریم. تابع مزدوج به صورت زیر تعریف می‌شود \[ f^*(Y)=\underset{X\succ 0}{\sup}(\mathbf{tr}(YX)+\log\det X), \] چون $\mathbf{tr}(YX)$ ضرب داخلی استاندارد روی $\mathbf{S}^n$ است. ابتدا نشان می‌دهیم که $\mathbf{tr}(YX)+\log\det X$ از بالا بیکران است مگر اینکه $Y\prec 0$. اگر $Y\nprec 0$، آنگاه $Y$ یک بردار ویژه $\upsilon$، با $\Vert\upsilon\Vert_2=1$، و مقدار‌ویژه $\lambda\geq 0$ را دارد. با توجه به $X=I+t\upsilon\upsilon^T$ درمی‌یابیم که \[ \mathbf{tr}(YX)+\log\det X=\mathbf{tr}Y+t\lambda+\log\det(I+t\upsilon\upsilon^T)=\mathbf{tr}Y+t\lambda+\log(1+t), \] که از بالا بیکران است به‌طوری‌که $t\rightarrow\infty$. حالا حالت $Y\prec 0$ را در نظر بگیرید. حداکثر $X$ را با قرار دادن گرادیان (شیب) با توجه به $X$ برابر با صفر در نظر بگیرید: \[ \bigtriangledown_X(\mathbf{tr}(YX)+\log\det X)=Y+X^{-1}=0 \] ،که $X=-Y^{-1}$ حاصل می‌شود (که درواقع به وضوح مثبت است). بنابراین، داریم \[ f^*(Y)=\log\det(-Y)^{-1}-n, \] با $\mathbf{dom}\:f^*=-\mathbf{S}_{++}^n$. \end{example} \begin{example} تابع شاخص. فرض کنید $I_S$ تابع شاخص مجموعه‌ی ( نه لزوما محدب) $S\subseteq\mathbf{R}^n$ باشد، یعنی $I_S(x)=0$ در $\mathbf{dom}\:I_S=S$. مزدوج آن به صورت زیر است \[ I_S^*(y)=\underset{x\in S}{\sup}\:y^T x, \] که تابع پشتیبان از مجموعه $S$ است. \end{example} \begin{example} تابع لگاریتم ـ مجموع ـ نمایی. برای به‌دست آوردن مزدوج لگاریتم ـ مجموع ـ نمایی، تابع $f(x)=\log(\sum_{i=1}^n \ee^{x_i})$ ابتدا مقادیر $y$ را تعیین می‌کنیم که ماکسیمم بر $x$ از $y^Tx-f(x)$ به‌دست آمده است. با قرار دادن گرادیان رابطه $x$ که برابر صفر است، به‌دست می‌آوریم \[ y_i=\frac{\ee^{x_i}}{\sum_{j=1}^n \ee^{x_j}},\qquad i=1,\ldots,n. \] این معادلات برای $x$ قابل حل هستند اگروتنهااگر $y\succ 0$ و $1^Ty=1$. با جایگزین کردن این عبارت برای $y_i$ در $y^Tx-f(x)$ به‌دست می‌آوریم $f^*(y)=\sum_{i=1}^n y_i\log y_i$. این عبارت تا زمانی‌ برای $f^*$ صحیح است اگر برخی مؤلفه‌های $y$ صفر باشند، تا زمانی‌که $y\succeq 0$ و $1^Ty=1$، تفسیر می‌کنیم $0\log 0$، $0$ است. درواقع دامنه‌ی $f^*$ دقیقا با $1^Ty=1$ داده می‌شود. برای نشان دادن این مطلب، فرض کنید که یک مؤلفه از $y$ منفی باشد، مثلا $y_k<0$. آنگاه می‌توانیم نشان دهیم که $y^Tx-f(x)$ با انتخاب $x_k=-t$ و با فرض اینکه $t$ تا بینهایت می‌رود و $x_i=0$، $i\neq k$ از بالا بیکران است، اگر $y\succeq 0$ اما $1^Ty\neq 1$، انتخاب می‌کنیم $x=t1$، به‌طوری‌که \[ y^T-f(x)=t1^Ty-t-\log n. \] اگر $1^Ty>1$، این به‌طور بیکران افزایش می‌یابد؛ به‌طوری‌که $t\rightarrow\infty$؛ اگر $1^Ty<1$، آن به‌طور بیکران افزایش می‌یابد به‌طوری‌که $t\rightarrow -\infty$. خلاصه، \[ f^*(y)= \begin{cases} \sum_{i=1}^n y_i\log y_i & \text{اگر}\:y\succeq 0 \text{و}\:1^Ty=1\\ \infty & \text{در غیر این ‌صورت}. \end{cases} \] به عبارت دیگر، مزدوج تابع لگاریتم ـ مجموع ـ نمایی تابع آنتروپی منفی است، که به احتمال ساده محدود شده است. \end{example} \begin{example} نرم. فرض کنید $\Vert\cdot\Vert$ یک نرم روی $\mathbf{R}^n$، با نرم دوگان $\Vert\cdot\Vert_*$ باشد. نشان می‌دهیم که مزدوج $f(x)=\Vert x\Vert$ به صورت زیر است: \[ f^*(y)= \begin{cases} 0 & \Vert y\Vert_*\leq 1\\ \infty & \text{در غیر این ‌صورت}, \end{cases} \] یعنی، مزدوج یک نرم، تابع شاخص نرم دوگان گوی واحد است. اگر $\Vert y\Vert_*>1$، آنگاه با تعریف نرم دوگان، $z\in\mathbf{R}^n$ با $\Vert z\Vert\leq 1$ و $y^Tz>1$ وجود دارد. باتوجه به $x=tz$ و بافرض $t\rightarrow\infty$، داریم \[ y^Tx-\Vert x\Vert=t(y^Tz-\Vert z\Vert)\rightarrow\infty, \] که نشان می‌دهد $f^*(y)=\infty$. بالعکس، اگر $\Vert y\Vert_*\leq 1$، آنگاه داریم $y^Tx\leq\Vert x\Vert\Vert y\Vert_*$ به ازای هر $x$، که نشان می‌دهد به ازای هر $x$، $y^Tx-\Vert x\Vert\leq 0$. بنابراین $x=0$ مقداری است که $y^Tx-\Vert x\Vert$، را با ماکسیمم مقدار $0$ افزایش می‌دهد. \end{example} \begin{example} نرم مربع. حالا تابع $f(x)=(1/2)\Vert x\Vert^2$ را در نظر بگیرید، که $\Vert\cdot\Vert$ یک نرم، با نرم دوگان $\Vert\cdot\Vert_*$ است. نشان می‌دهیم که مزدوج آن $f^*(y)=(1/2)\Vert y\Vert_*^2$ است. از $y^Tx\leq\Vert y\Vert_*\Vert x\Vert$، نتیجه می‌گیریم \[ y^Tx-(1/2)\Vert x\Vert^2\leq\Vert y\Vert_*\Vert x\Vert-(1/2)\Vert x\Vert^2 \] به ازای هر $x$. سمت راست یک تابع درجه دوم $\Vert x\Vert$ است، که مقدار ماکسیمم $(1/2)\Vert y\Vert_*^2$ را دارد. بنابراین به ازای هر $x$، داریم \[ y^Tx-(1/2)\Vert x\Vert^2\leq (1/2)\Vert y\Vert_*^2, \] که نشان می‌دهد $f^*(y)\leq (1/2)\Vert y\Vert_*^2$. برای نشان دادن نامساوی دیگر، فرض کنید $x$ هر بردار با $y^Tx=\Vert y\Vert_*\Vert x\Vert$ باشد، به‌طوری‌که $\Vert x\Vert=\Vert y\Vert_*$. آنگاه برای این $x$، داریم \[ y^T-(1/2)\Vert x\Vert^2=(1/2)\Vert y\Vert_*^2, \] که نشان می‌دهد $f^*(y)\geq (1/2)\Vert y\Vert_*^2$. \end{example} \begin{example} تابع درآمد و سود. یک تجارت یا سرمایه‌گذاری را در نظر می‌گیریم که $n$ منابع را مصرف می‌کند و محصولی که می‌تواند فروخته شود را تولید می‌کند. فرض می‌کنیم $r=(r_1,\ldots,r_n)$ بردار مقدار منابع مصرف شده را نشان می‌دهد و $S(r)$ درآمد حاصل از فروش محصول تولید شده (به‌عنوان تابعی از منابع مصرف شده). حالا فرض کنید $p_i$ قیمت منبع $i$ (در واحد) را نشان می‌دهد، پس مبلغ کل پرداخت شده برای منابع به‌وسیله این سرمایه‌گذاری $p^Tr$ است. پس سود به‌دست آمده از این شرکت $S(r)-p^Tr$ است. فرض کنید قیمت منابع را ثابت کنیم، و حداکثر سود که می‌تواند عاقلانه با انتخاب مقدار منابع مصرف شده ساخته شود را بخواهید. این حداکثر سود به صورت زیر داده می‌شود \[ M(p)=\underset{r}{\sup}(S(r)-p^Tr). \] تابع $M(p)$ حداکثر سود قابل دسترس را، به‌عنوان تابعی از قیمت منابع می‌دهد. در شرایطی از توابع مزدوج، می‌توانیم $M$ را به صورت زیر بیان کنیم \[ M(p)=(-S)^*(-p). \] بنابراین، حداکثر سود (به‌عنوان تابعی از قیمت‌های منابع) دقیقا به مزدوج فروش ناخالص (به‌عنوان تابعی از منابع مصرف شده) مربوط می‌شود. \end{example} \subsection{خصوصیات اولیه} \subsection*{نامساوی فنچل} از تعریف تابع مزدوج، فورا این نامساوی را به‌دست می‌آوریم \[ f(x)+f^*(y)\geq x^Ty \] به ازای هر $x, y$. این نامساوی، نامساوی فنچل نامیده می‌شود (یا نامساوی یانگ وقتی‌‌که $f$ مشتق‌پذیر باشد). مثلا با $f(x)=(1/2)x^TQx$، که $Q\in\mathbf{S}_{++}^n$، نامساوی زیر را به‌دست می‌آوریم \[ x^Ty\leq (1/2)x^TQx+(1/2)y^TQ^{-1}y. \] \subsection*{مزدوج مزدوج} مثال‌های بالا و اسم مزدوج بیان می‌کند که مزدوج مزدوج تابعی محدب تابع اصلی است. این مورد ارائه شده حاکی از این شرط است: اگر $f$ محدب باشد، و $f$ بسته باشد (یعنی $\mathbf{epi} f$ مجموعه ای بسته باشد)، آنگاه $f^{**}=f$. مثلا ، اگر $\mathbf{dom}\:f=\mathbf{R}^n$ آنگاه داریم $f^{**}=f$، یعنی مزدوج مزدوج $f$ دوباره $f$ است. \subsection*{توابع مشتق‌پذیر} مزدوج تابع مشتق‌پذیر $f$ نیز تبدیل لژاندر $f$ نامیده می‌شود. (برای تشخیص تعریف کلی از حالت مشتق‌پذیری، اصطلاح مزدوج فنچل گاهی به‌جای مزدوج استفاده می‌شود.) فرض کنید $f$ محدب و مشتق‌پذیر، با $\mathbf{dom}\:f=\mathbf{R}^n$ باشد. هر افزایش‌ دهنده $x^*$ از $y^Tx-f(x)$، $y=\bigtriangledown f(x^*)$ را ثابت می‌کند و برعکس، اگر $x^*$، $y=\bigtriangledown f(x^*)$ را ثابت کند، آنگاه $x^*$، $y^Tx-f(x)$ را افزایش می‌دهد. بنابراین اگر $y=\bigtriangledown f(x^*)$، داریم \[ f^*(y)=x^{*T}\bigtriangledown f(x^*)-f(x^*). \] این به ما اجازه می‌دهد که $f^*(y)$ را برای هر $y$ مشخص کنیم که می‌توانیم معادله گرادیان $y=\bigtriangledown f(z)$ را برای $z$ حل کنیم. می‌توانیم روش دیگر را بیان کنیم. فرض کنید $z\in\mathbf{R}^n$ دلخواه باشد و تعریف کنید $y=\bigtriangledown f(z)$. آنگاه داریم \[ f^*(y)=z^T\bigtriangledown f(z)-f(z). \] \subsection*{مقیاس‌‌گذاری و ترکیب با تبدیل آفینی} برای $a>0$ و $b\in\mathbf{R}$، مزدوج $g(x)=af(x)+b$، $g^*(y)=af^*(y/a)-b$ است. فرض کنید $A\in\mathbf{R}^{n\times n}$ منحصر‌بفرد نباشد و $b\in\mathbf{R}^n$. آنگاه مزدوج $g(x)=f(Ax+b)$ به صورت زیر است \[ g^*(y)=f^*(A^{-T}y)-b^TA^{-T}y, \] با $\mathbf{dom}\:g^*=A^T\mathbf{dom}\:f^*$. \subsection*{حاصل‌جمع توابع مستقل} اگر $f(u,\upsilon)=f_1(u)+f_2(\upsilon)$، که $f_1$ و $f_2$ توابع محدب به‌ترتیب با مزدوج $f_1^*$ و $f_2^*$ هستند، آنگاه \[ f^*(w,z)=f_1^*(w)+f_2^*(z). \] به‌عبارت دیگر، مزدوج حاصل‌جمع توابع محدب مستقل، حاصل‌جمع مزدوج‌ها است. (مستقل یعنی آن‌ها توابعی از متغیرهای مختلف هستند.) \section{توابع شبه محدب} \subsection{تعریف و مثال‌ها} تابع $f:\mathbf{R}^n\rightarrow\mathbf{R}$ شبه محدب نامیده می‌شود اگر دامنه‌ی آن و تمام مجموعه‌های زیرسطح آن \[ S_\alpha=\lbrace x\in\mathbf{dom}\:f\:|\:f(x)\leq\alpha\rbrace, \] برای $\alpha\in\mathbf{R}$، محدب باشند. تابعی شبه‌ مقعر است اگر $-f$ شبه محدب باشد، یعنی هر مجموعه فوق‌سطح $\lbrace x\:|\:f(x)\geq\alpha\rbrace$ محدب باشد. تابعی که هم شبه محدب باشد و هم شبه مقعر شبه خطی نامیده می‌شود. اگر تابع $f$ شبه خطی باشد، آنگاه دامنه آن و هر مجموعه در سطح $\lbrace x\:|\:f(x)=\alpha\rbrace$ محدب است. \begin{center} \[ \begin{tikzpicture} \draw [ultra thick] (-5,0) to(5,0); \draw [ultra thick](-5,3.5) to [out=0,in=120] (-1,2); \draw [ultra thick](-1,2) to [out=-56,in=220] (2.5,2); \draw [ultra thick] (2.5,2) to [out=45,in=260] (4.5,5.5); \draw [dashed] (-5,2.6) to (6,2.6); \draw [dashed] (-5,4.3) to (6,4.3); \draw [ultra thick] (-1.3,-0.1) to (-1.3,0.1); \draw [ultra thick] (3,-0.1) to (3,0.1); \draw [ultra thick] (3.9,-0.1) to (3.9,0.1); \node at (-1.3,0.3) [color=blue]{$a$}; \node at (3,0.3) [color=blue]{$b$}; \node at (3.9,0.3) [color=blue]{$c$}; \node at (-5.2,2.6) [color=blue]{$\alpha$}; \node at (-5.2,4.3) [color=blue]{$\beta$}; \end{tikzpicture} \] \end{center} برای تابعی روی $\mathbf{R}$، شبه تحدب مستلزم آن است که هر زیرمجموعه یک بازه باشد (احتمالا، شامل بازه نامتناهی است). مثالی از یک تابع شبه محدب روی $\mathbf{R}$ که در شکل 3.9 نشان داده می‌شود، نشان می‌دهد که عکس این قضیه درست نیست. \begin{example} چند مثال روی $\mathbf{R}$: \begin{itemize} \item لگاریتم. $\log x$ در $\mathbf{R}_{++}$ شبه محدب است (و شبه مقعر، بنابراین شبه خطی است). \item تابع سقف. $\mathbf{ceil}(x)=\inf\lbrace z\in\mathbf{Z}\:|\:z\geq x\rbrace$ شبه محدب است (و شبه مقعر). \end{itemize} \end{example} این مثال‌ها نشان می‌دهد که توابع شبه محدب می‌توانند مقعر یا ناپیوسته باشند. حالا چند تا مثال روی $\mathbf{R}^n$ می‌دهیم. \begin{example} طول بردار. طول $x\in\mathbf{R}^n$ را به‌عنوان بزرگترین شاخص یک مؤلفه‌ی غیر‌صفر تعریف می‌کنیم، یعنی، \[ f(x)=\max\lbrace i\:|\:x_i\neq 0\rbrace. \] (طول بردار صفر را تعریف کردیم که صفر باشد.) این تابع در $\mathbf{R}^n$ شبه محدب است، چون مجموعه‌های زیرسطح آن زیرفضاهای زیر می‌باشند: \[ f(x)\leq\alpha\Longleftrightarrow x_i=0\:\text{برای}\:i=\lfloor\alpha\rfloor+1,\ldots,n. \] \end{example} \begin{example} $f:\mathbf{R}^2\rightarrow\mathbf{R}$، را با $\mathbf{dom}\:f=\mathbf{R}_+^2$ و $f(x_1,x_2)=x_1x_2$ در نظر بگیرید. این تابع نه محدب است و نه مقعر چون هسین آن \[ \bigtriangledown^2f(x)=\begin{bmatrix} 0 & 1\\ 1 & 0\\ \end{bmatrix} \] نامعین است؛ که دارای یک مقدارویژه مثبت یا منفی است. تابع $f$ شبه مقعر است، بنابراین، چون مجموعه‌های فوق‌سطح \[ \lbrace x\in\mathbf{R}_+^2\:|\:x_1x_2\geq\alpha\rbrace \] به ازای هر $\alpha$ مجموعه‌های محدب هستند. (توجه کنید، که $f$ روی $\mathbf{R}^2$ شبه مقعر نیست.) \end{example} \begin{example} تابع خطی-کسری. تابع \[ f(x)=\frac{a^Tx+b}{c^Tx+d}, \] با $\mathbf{dom}\:f=\lbrace x\:|\:c^Tx+d>0\rbrace$، شبه محدب و شبه مقعر است، یعنی شبه خطی. $\alpha$ ـ مجموعه زیرسطح آن که به صورت زیر است \begin{align*} S_\alpha &=\lbrace x\:|\:c^Tx+d>0,\:(a^Tx+b)/(c^Tx+d)\leq\alpha\rbrace\\ & =\lbrace x\:|\:c^Tx+d>0,\:a^Tx+b\leq\alpha(c^Tx+d)\rbrace, \end{align*} محدب است، چون اشتراک نیم‌فضای باز و نیم‌فضای بسته است. (همین روش می‌تواند برای نشان ‌دادن اینکه مجموعه‌های فوق‌سطح آن محدب هستند به‌کار رود.) \end{example} \begin{example} تابع نسبت فاصله. فرض کنید $a, b\in\mathbf{R}^n$، و تعریف کنید \[ f(x)=\frac{\Vert x-a\Vert_2}{\Vert x-b\Vert_2}, \] یعنی نسبت فاصله اقلیدسی تا $a$ به فاصله تا $b$. آنگاه $f$ در نیم‌فضای $\lbrace x\:|\:\Vert x-a\Vert_2\leq\Vert x-b\Vert_2\rbrace$ شبه محدب است. برای دیدن این امر، $\alpha$-مجموعه زیرسطح $f$ را با $\alpha\leq 1$ در نظر می‌گیریم، چون $f(x)\leq 1$ روی نیم‌فضای $\lbrace x\:|\:\Vert x-a\Vert_2\leq\Vert x-b\Vert_2\rbrace$. این مجموعه زیرسطح، مجموعه نقاطی است که در \[ \Vert x-a\Vert_2\leq\alpha\Vert x-b\Vert_2. \] صدق می‌کند. با مربع هر دو طرف، می‌بینیم که این معادل است با \[ (1-\alpha^2)x^Tx-2(a-\alpha^2b)^Tx+a^Ta-\alpha^2b^Tb\leq 0. \] که مجموعه‌ای محدب را توصیف می‌کند (درواقع یک گوی اقلیدسی) اگر $\alpha\leq 1$. \end{example} \begin{example} نرخ داخلی بازگشتی. فرض کنید $x=(x_0,x_1,\ldots,x_n)$ جریان وجوه نقدی را بر $n$ دوره نشان می‌دهد، که $x_i>0$ یعنی پرداخت توسط ما در دوره $i$، و $x_i<0$ یعنی پرداخت توسط ما در دوره $i$. مقدار فعلی جریان وجوه نقدی را با نرخ بهره $r\geq 0$ تعریف می‌کنیم، که \[ PV(x,r)=\sum_{i=0}^n(1+r)^{-i}x_i. \] (فاکتور $(1+r)^{-i}$ تخفیف برای پرداخت به‌وسیله ما یا به ما در دوره $i$ است.) حالا جریان‌های وجوه نقدی را در نظر می‌گیریم که $x_0<0$ و $x_0+x_1+\cdots+x_n>0$. این به این معنی است که با سرمایه‌گذاری $\vert x_0\vert$ در دوره $0$ شروع می‌کنیم و اینکه مجموع جریان نقدی باقیمانده، $x_1+\cdots+x_n$، (نه با در نظر گرفتن هر فاکتور تخفیف در حساب) بیشتر از سرمایه‌گذاری اولیه ما است. برای چنین جریان نقدی، $PV(x,0)>0$ و $PV(x,r)\rightarrow x_0<0$ به‌طوری‌که $r\rightarrow\infty$، بنابراین آن به شرح زیر است که برای حداقل یک $r\geq 0$، داریم $PV(x,r)=0$. نرخ داخلی بازگشت جریان نقدی را به‌عنوان کوچکترین نرخ بهره $r\geq 0$ تعریف می‌کنیم که مقدار فعلی صفر است: \[ IRR(x)=\inf\lbrace r\geq 0\:|\:PV(x,r)=0\rbrace. \] نرخ داخلی بازگشت تابع شبه مقعر $x$ است (که به $x_0<0$، $x_1+\cdots+x_n>0$ محدود شده است). برای دیدن این امر، می‌بینیم که \[ IRR(x)\geq R\Longleftrightarrow PV(x,r)>0\:\text{برای}\:0\leq r0\rbrace$ است، که به‌وسیله $r$ اندیس‌دار شده، در محدوده $0\leq r0$ نیم‌فضای بازی تعریف می‌کند، بنابراین سمت راست مجموعه‌ای محدب را تعریف می‌کند. \end{example} \subsection{ویژگی‌های اساسی} مثال‌های بالا نشان می‌دهد که شبه تحدب تعمیم قابل توجه تحدب است. با این حال بسیاری از ویژگی‌های توابع محدب را برای توابع شبه محدب حفظ می‌کند، یا تشابه دارد. مثلا، تغییر در نامساوی جنسن وجود دارد که شبه تحدب را مشخص می‌کند: تابع $f$ شبه محدب است اگروتنهااگر $\mathbf{dom}\:f$ محدب باشد و برای هر $x, y\in\mathbf{dom}\:f$ و $0\leq\theta\leq 1$، داشته باشیم \begin{equation} f(\theta x+(1-\theta)y)\leq\max\lbrace f(x),f(y)\rbrace,\label{17} \end{equation} یعنی، مقدار این تابع روی بخشی از ماکسیمم مقدار آن در نقطه پایانی تجاوز نمی‌کند. گاهی نامساوی \eqref{17} نامساوی جنسن برای توابع شبه محدب نامیده می‌شود، و در شکل 3.10 نشان داده می‌شود. \begin{example} کاردینالیتی بردار نامنفی. کاردینالیتی یا اندازه یک بردار $x\in\mathbf{R}^n$ تعدادی از مؤلفه‌های غیرصفر است، و با $\mathbf{card}(x)$ نشان داده می‌شود. تابع $\mathbf{card}$ روی $\mathbf{R}_+^n$ (اما نه روی $\mathbf{R}$) شبه مقعر است. سریعا این از نامساوی اصلاح شده جنسن می‌آید \[ \mathbf{card}(x+y)\geq\min\lbrace\mathbf{card}(x),\mathbf{card}(y)\rbrace, \] که برای $x, y\succeq 0$ برقرار است. \end{example} \begin{example} ماتریس نیمه معین مثبت. تابع $\mathbf{rank} X$ روی $\mathbf{S}_+^n$ شبه مقعر است. این از نامساوی اصلاح شده جنسن \eqref{17} می‌آید، \[ \mathbf{rank}(X+Y)\geq\min\lbrace\mathbf{rank}X,\mathbf{rank}Y\rbrace \] که برای $X, Y\in\mathbf{S}_+^n$ برقرار است. (این می‌تواند تعمیم مثال قبلی در نظر گرفته شود، چون $\mathbf{rank}(\mathbf{diag}(x))=\mathbf{card}(x)$ برای$x\succeq 0$.) \begin{center} \[ \begin{tikzpicture} \draw [ultra thick](-6,3.2) to [out=5,in=100] (-1,1); \draw [ultra thick](-1,1) to [out=-65,in=180] (0,0); \draw [ultra thick] (0,0) to [out=-5,in=260] (4.3,6); \draw [dashed] (-1.02,1.12) to (-1.02,4); \draw [dashed] (-1.02,4) to (3.85,4); \node at (1.5,4.3) [color=blue]{$\max\lbrace f(x),f(y)\rbrace$}; \node at (4.7,4) [color=blue]{$(y,f(y))$}; \node at (-1.9,1.12) [color=blue]{$(x,f(x))$}; \draw [fill] (-1.02,1.12) circle [radius=0.09]; \draw [fill] (3.85,4) circle [radius=0.09]; \end{tikzpicture} \] \end{center} \end{example} مانند تحدب، شبه تحدب با رفتار تابع $f$ در خطوط مشخص می‌شود: $f$ شبه محدب است اگروتنهااگر محدودیت آن به هر خط متقاطع دامنه ‌اش شبه محدب باشد. مخصوصا، شبه تحدب یک تابع می‌تواند با محدود کردن آن به یک خط دلخواه و سپس با بررسی شبه تحدب تابع حاصله روی $\mathbf{R}$ تایید شود. \subsection*{توابع شبه محدب روی $\mathbf{R}$} می‌توانیم یک توصیف ساده از توابع شبه محدب روی $\mathbf{R}$ بدهیم. توابع پیوسته را در نظر می‌گیریم، چون بیان شرایط در حالت کلی مشکل است. تابع پیوسته $f:\mathbf{R}\rightarrow\mathbf{R}$ شبه محدب است اگروتنهااگر حداقل یکی از شرایط زیر را دارا باشد: \begin{itemize} \item $f$ غیرکاهشی است. \item $f$ غیرافزایشی است. \item نقطه‌ی $c\in\mathbf{dom}\:f$ وجود دارد به‌طوری‌که برای $t\leq c$ (و$t\in\mathbf{dom}\:f$)،$f$ غیرافزایشی است، و برای $t\geq c$ (و $t\in\mathbf{dom}\:f$)،$f$ غیرکاهشی است. \end{itemize} نقطه‌ی $c$ می‌تواند به‌عنوان هر نقطه انتخاب شود که یک می‌نیمم سراسری $f$ است. شکل 3.11 این را نشان می‌دهد. \subsection{توابع شبه محدب مشتق‌پذیر} \subsection*{شرایط مرتبه اول} فرض کنید $f:\mathbf{R}^n\rightarrow\mathbf{R}$ مشتق‌پذیر است. آنگاه $f$ شبه محدب است اگروتنهااگر $\mathbf{dom}\:f$ محدب باشد و به ازای هر $x,y\in\mathbf{dom}\:f$ \begin{equation} f(y)\leq f(x)\Longrightarrow\bigtriangledown f(x)^T(y-x)\leq 0.\label{18} \end{equation} \begin{center} \[ \begin{tikzpicture} \draw [ultra thick] (-5,-0.5) to(5,-0.5); \draw [ultra thick](-4.5,3.5) to [out=10,in=120] (-1,2); \draw [ultra thick](-1,2) to [out=-56,in=215] (1,0); \draw [ultra thick] (1,0) to [out=50,in=225] (4,4.2); \draw [ultra thick] (0.6,-0.6) to (0.6,-0.4); \node at (0.6,-0.8) [color=blue]{$c$}; \node at (5.2,-0.5) [color=blue]{$t$}; \end{tikzpicture} \] \end{center} این مشابه نامساوی \eqref{2} برای توابع شبه محدب است. این اثبات را به‌عنوان تمرین رها می‌کنیم شرط \eqref{18} بیان ساده هندسی دارد وقتی $\bigtriangledown f(x)\neq 0$. بیان می‌کند که $\bigtriangledown f(x)$ پشتیبان ابرصفحه برای مجموعه‌ی زیرسطح $\lbrace y\:|\:f(y)\leq f(x)\rbrace$، در نقطه $x$ است، همان‌طور که در شکل 3.12 نشان داده شد. درحالی‌که شرط مرتبه اول برای تحدب \eqref{2}، و شرط مرتبه‌ی اول برای شبه تحدب \eqref{18} مشابه هستند. چند اختلاف مهم وجود دارد. مثلا، اگر $f$ محدب باشد و $\bigtriangledown f(x)=0$ باشد، آنگاه $x$ می‌نیمم سراسری $f$ است. این بیان برای توابع شبه محدب غلط است: ممکن است که $\bigtriangledown f(x)=0$ باشد اما $x$ می‌نیمم سراسری $f$ نباشد. \subsection*{شرایط مرتبه دوم} حالا فرض کنید $f$ دوبار مشتق‌پذیر باشد. اگر $f$ شبه محدب باشد، آنگاه به ازای هر $x\in\mathbf{dom}\:f$، و هر $y\in\mathbf{R}^n$، داریم \begin{equation} y^T\bigtriangledown f(x)=0\Longrightarrow y^T\bigtriangledown^2 f(x)y\geq 0.\label{19} \end{equation} برای تابع شبه محدب روی $\mathbf{R}$، این به شرط زیر کاهش می‌یابد. \[ f'(x)=0\Longrightarrow f''(x)\geq 0, \] یعنی، در هر نقطه با شیب صفر، مشتق دوم نامنفی است. برای تابعی شبه محدب روی $\mathbf{R}^n$، تفسیر شرط \eqref{19} کمی پیچیده‌تر است. بنابراین در حالت $n=1$، نتیجه می‌گیریم که هروقت $\bigtriangledown f(x)=0$ باشد، باید داشته باشیم $\bigtriangledown^2 f(x)\succeq 0$. وقتی $\bigtriangledown f(x)\neq 0$، شرط \eqref{19} به این معنی است که $\bigtriangledown^2 f(x)$ روی زیرفضای $(n-1)$-بعدی $\bigtriangledown f(x)^\perp$ نیمه معین مثبت است. این نشان می‌دهد که $\bigtriangledown^2 f(x)$ می‌تواند حداکثر یک مقدارویژه منفی داشته باشد. به‌طور عکس اگر $f$ به ازای هر $x\in\mathbf{dom}\:f$ و هر $y\in\mathbf{R}^n$ در رابطه زیر صدق کند \begin{equation} y^T\bigtriangledown f(x)=0\Longrightarrow y^T\bigtriangledown^2 f(x)y>0\label{20} \end{equation} آنگاه $f$ شبه محدب است. این شرط همان نیازمند به این است که $\bigtriangledown^2 f(x)$ برای هر نقطه با $\bigtriangledown f(x)=0$ معین مثبت باشد، و برای تمام نقاط دیگر، $\bigtriangledown^2 f(x)$ روی زیرفضای $(n-1)$ ـ بعدی $\bigtriangledown f(x)^\perp$ معین مثبت باشد. \subsection*{اثبات شرایط مرتبه دوم برای شبه تحدب} با محدود کردن تابع به یک خط دلخواه، کافی ا‌ست این حالت را درنظر بگیرید که در آن $f:\mathbf{R}\rightarrow\mathbf{R}$. ابتدا نشان می‌دهیم که اگر $f:\mathbf{R}\rightarrow\mathbf{R}$ در بازه‌ی $(a,b)$ شبه محدب باشد، آنگاه باید \eqref{19} را ثابت کنیم، یعنی اگر $f'(c)=0$ و $c\in (a,b)$ باشد، آنگاه باید داشته باشیم $f''(c)\geq 0$. اگر $f'(c)=0$ و $c\in (a,b)$، $f''(c)<0$ باشد، آنگاه برای $\epsilon$ مثبت کوچک داریم $f(c-\epsilon)0$. این به این معنی‌ است که هروقت تابع $f'$ از مقدار صفر عبور کند، به شدت در حال افزایش است. بنابراین، می‌تواند از مقدار صفر یکبار عبور کند. اگر $f'$ از مقدار صفر اصلا عبور نکند، آنگاه $f$ در $(a,b)$ یا غیرافزایشی است یا غیرکاهشی است، و بنابراین شبه محدب است. در غیر این‌صورت آن باید از مقدار صفر دقیقا یکبار عبور کند، مثلا در $c\in (a,b)$. چون $f''(c)>0$، آن نشان می‌دهد که $f'(t)\leq 0$ برای $a0,\:(Ax+b)/(c^Tx+d)\in\mathbf{dom}\:f\rbrace. \] شبه محدب است. \subsection*{می‌نیمم‌سازی} اگر $f(x,y)$ به‌طور مشترک در $x$ و $y$ شبه محدب باشد، و $C$ مجموعه‌ای محدب باشد، آنگاه تابع \[ g(x)=\underset{y\in C}{\inf} f(x,y) \] شبه محدب است. برای نشان دادن این مطلب، باید نشان دهیم که $\lbrace x\:|\:g(x)\leq\alpha\rbrace$ محدب است، که $\alpha\in\mathbf{R}$ دلخواه است. از تعریف $g$، $g(x)\leq\alpha$ است اگروتنهااگر برای هر $\epsilon>0$ یک $y\in C$ وجود دارد که $f(x,y)\leq\alpha+\epsilon$. حالا فرض کنید $x_1$ و $x_2$ دو نقطه در $\alpha$ ـ مجموعه‌ی زیرسطح مجموعه‌ی $g$ باشد. آنگاه برای هر $\epsilon>0$، وجود دارد $y_1,y_2\in C$ که \[ f(x_1,y_1)\leq\alpha+\epsilon,\qquad f(x_2,y_2)\leq\alpha+\epsilon, \] و چون $f$ در $x$ و $y$ شبه محدب است، همچنین داریم \[ f(\theta x_1+(1-\theta)x_2,\theta_{y_1}+(1-\theta)y_2)\leq\alpha+\epsilon, \] برای $0\leq\theta\leq 1$. بنابراین $g(\theta x_1+(1-\theta)x_2)\leq\alpha$ است، که ثابت می‌کند $\lbrace x\:|\:g(x)\leq\alpha\rbrace$ محدب است. \subsection{نمایش از طریق خانواده‌ی توابع محدب} در نتیجه، این روش برای نشان دادن مجموعه‌های زیرسطح تابع شبه محدب $f$ (که محدب هستند) از طریق نامساوی توابع محدب مناسب است. ما به دنبال خانواده‌ای از توابع محدب $\phi_t:\mathbf{R}^n\rightarrow\mathbf{R}$ هستیم، که با $t\in\mathbf{R}$ نشان داده می‌شود، به‌طوری‌که \begin{equation} f(x)\leq t\Longleftrightarrow \phi_t\leq 0, \end{equation} یعنی، $t$ ـ مجموعه زیرسطح تابع شبه محدب $f$، $0$ ـ مجموعه زیرسطح تابع محدب $\phi_t$ است. واضح است $\phi_t$ باید این ویژگی را ثابت کند که به ازای هر $x\in\mathbf{R}^n$، $\phi_t(x)\leq 0\Longrightarrow\phi_s(x)\leq 0$ برای $s\geq t$. این ثابت می‌شود اگر برای هر $x$، $\phi_t(x)$ یک تابع غیرافزایشی $t$، یعنی $\phi_s(x)\leq \phi_t(x)$ باشد وقتی‌که $s\geq t$. برای دیدن اینکه چنین نمایشی همیشه وجود دارد، می‌توانیم درنظر بگیریم \[ \phi_t(x)= \begin{cases} 0 & f(x)\leq t\\ \infty & \text{در غیر این ‌صورت}, \end{cases} \] یعنی، $\phi_t$ تابع شاخص $t$ ـ مجموعه زیرسطح $f$است. بدیهی است این نمایش بی‌مانند نیست؛ مثلا اگر مجموعه‌های زیرسطح $f$ بسته باشند، می‌توانیم در نظر بگیریم \[ \phi_t(x)=\mathbf{dist}(x,\lbrace z\:|\:f(z)\leq t\rbrace). \]‌ ما معمولا در خانواده‌ی $\phi_t$ با ویژگی‌های خوبی، مانند مشتق‌پذیری علاقه مند هستیم. \begin{example} تابع محدب بر تابع مقعر. فرض کنید $p$ تابعی محدب، و $q$ تابعی مقعر در مجموعه‌ی محدب $C$ باشد، به‌طوری‌که $p(x)\geq 0$ و $q(x)>0$ . آنگاه تابع $f$ که به صورت $f(x)=p(x)/q(x)$ تعریف شده، روی $C$، شبه محدب است. در اینجا داریم \[ f(x)\leq t\Longleftrightarrow p(x)-tq(x)\leq 0, \] بنابراین می‌توانیم $\phi_t(x)=p(x)-tq(x)\leq 0$ را برای $t\geq 0$ درنظر بگیریم. برای هر $t$، $\phi_t$ محدب است و برای هر $x$، $\phi_t(x)$ در $t$ کاهشی است. \end{example} \section{توابع لگاریتم ـ مقعر و لگاریتم ـ محدب} \subsection{تعریف} تابع $f:\mathbf{R}^n\rightarrow\mathbf{R}$ لگاریتمی مقعر یا لگاریتم ـ مقعر است اگر به ازای هر $x\in\mathbf{dom}\:f$، $f(x)>0$ و $\log f$ مقعر باشد. و لگاریتمی محدب یا لگاریتم ـ‌ محدب گفته می‌شود اگر $\log f$ محدب باشد. بنابراین $f$ لگاریتم ـ محدب است اگروتنهااگر $1/f$ لگاریتم ـ مقعر باشد. می‌پذیریم $f$ مقدار صفر می‌گیرد، که در این صورت $\log f(x)=-\infty$ می‌شود. در این مورد می‌گوییم $f$ لگاریتم ـ مقعر است اگر تابع مقدار ـ افزایش یافته‌ی $\log f$ مقعر باشد. می‌توانیم مستقیما لگاریتم ـ‌ تحدب را بدون لگاریتم‌ها، بیان کنیم: تابع $f:\mathbf{R}^n\rightarrow\mathbf{R}$، با دامنه‌ی محدب و $f(x)>0$ به ازای هر $x\in\mathbf{dom}\:f$، لگاریتم ـ مقعر است اگروتنهااگر به ازای هر $x,y\in\mathbf{dom}\:f$ و $0\leq\theta\leq 1$، داشته باشیم \[ f(\theta x+(1-\theta)y)\geq f(x)^{\theta}f(y)^{1-\theta}. \] به‌ویژه، مقدار تابع لگاریتم ـ مقعر در حد وسط دونقطه حداقل میانگین هندسی مقادیر در دو نقطه است. از قواعد ترکیب می‌دانیم که $\ee^h$ محدب است اگر $h$ محدب باشد، بنابراین تابع لگاریتم ـ محدب، محدب است. به همین ترتیب، یک تابع مقعر نامنفی لگاریتم ـ مقعر است. همچنین واضح است که یک تابع لگاریتم ـ محدب شبه محدب است و یک تابع لگاریتم ـ مقعر شبه مقعر است، چون این لگاریتم یکنواخت در حال افزایش است. \begin{example} چند مثال ساده از تابع لگاریتم ـ مقعر و تابع لگاریتم ـ محدب. \begin{itemize} \item تابع آفینی. $f(x)=a^Tx+b$ روی $\lbrace x\:|\:a^Tx+b>0\rbrace$ لگاریتم ـ مقعر است. \item توان‌ها. $f(x)=x^a$، روی $\mathbf{R}_{++}$، برای $a\leq 0$، لگاریتم ـ محدب است و برای $a\geq 0$ لگاریتم ـ مقعر است. \item نمائی. $f(x)=\ee^{ax}$ لگاریتم ـ محدب و لگاریتم ـ مقعر است. \item تابع توزیع تجمعی چگالی نرمال، \[ \Phi(x)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^x \ee^{-u^2/2}\dd u, \] لگاریتم ـ مقعر است. \item ،تابع گاما. تابع گاما \[ \Gamma(x)=\int_{0}^{\infty} u^{x-1}\ee^{-u}\dd u, \] برای $x\geq 1$ لگاریتم ـ محدب است. \item دترمینان. $\det X$ در $\mathbf{S}_{++}^n$ لگاریتم مقعر است. \item دترمینان بر اثر. $\det X/\mathbf{tr} X$در $\mathbf{S}_{++}^n$ لگاریتم مقعر است. \end{itemize}\label{b} \end{example} \begin{example} توابع چگالی لگاریتم ـ مقعر. بسیاری از توابع چگالی احتمال معمول لگاریتم ـ مقعر هستند. دو مثال توزیع نرمال چند متغیری به صورت زیر داریم، \[ f(x)=\frac{1}{\sqrt{(2\pi)^n\det\Sigma}} \ee^{-\frac{1}{2}(x-\bar{x})^T\Sigma^{-1}(x-\bar{x})} \] (که $\bar{x}\in\mathbf{R}^n$ و $\Sigma\in\mathbf{S}_{++}^n$)، توزیع نمایی روی $\mathbf{R}_+^n$، \[ f(x)=\left(\prod_{i=1}^n\right)\ee^{-\lambda^Tx} \] (که $\lambda\succ 0$). مثال دیگر توزیع یکنواخت بر مجموعه محدب $C$، \[ f(x)= \begin{cases} 1/\alpha & x\in C\\ 0 & x\notin C \end{cases} \] که $\alpha=\mathbf{vol}(C)$ حجم $C$ ( اندازه لبگ) است. در این حالت $\log f$ روی مقدار $-\infty$ در خارج از $C$، و $-\log\alpha$ روی $C$ گرفته می‌شود، بنابراین مقعر است. به‌عنوان مثالی عجیب‌تر توزیع ویشارت را در نظر بگیرید، که به صورت زیر تعریف می‌شود. فرض کنید $x_1,\ldots,x_p\in\mathbf{R}^n$ بردار تصادفی مستقل نرمال با میانگین صفر و واریانس $\Sigma\in\mathbf{S}^n$ باشد، که $p>n$. ماتریس تصادفی $X=\sum_{i=1}^p x_i x_i^T$ چگالی ویشارت را به صورت زیر دارد \[ f(X)=a(\det X)^{(p-n-1)/2} \ee^{-\frac{1}{2}\mathbf{tr}(\Sigma^{-1} X)}, \] که $\mathbf{dom}\:f=\mathbf{S}_{++}^n$ و $a$ ثابتی مثبت است. چگالی ویشارت لگاریتم ـ مقعر است، چون \[ \log f(X)=\log a+\frac{p-n-1}{2} \log\det X-\frac{1}{2}\mathbf{tr}(\Sigma^{-1} X), \] که تابع مقعر $X$ است. \end{example} \subsection{ویژگی‌ها} \subsection*{توابع دوبار مشتق‌پذیر لگاریتم ـ محدب/مقعر} فرض کنید $f$ با $\mathbf{dom}\:f$ محدب، دوبار مشتق‌پذیر باشد آنگاه \[ \bigtriangledown^2\log f(x)=\frac{1}{f(x)}\bigtriangledown^2f(x)-\frac{1}{f(x)^2}\bigtriangledown f(x)\bigtriangledown f(x)^T. \] نتیجه می‌گیریم که $f$ لگاریتم ـ محدب است اگروتنهااگر به ازای هر $x\in\mathbf{dom}\:f$، داشته باشیم \[ f(x)\bigtriangledown^2f(x)\succeq\bigtriangledown f(x)\bigtriangledown f(x)^T, \] و لگاریتم ـ مقعر اگروتنهااگر به ازای هر $x\in\mathbf{dom}\:f$، داشته باشیم \[ f(x)\bigtriangledown^2f(x)\preceq\bigtriangledown f(x)\bigtriangledown f(x)^T. \] \subsection*{ضرب، جمع، انتگرال} لگاریتم ـ تحدب و لگاریتم ـ تقعر تحت ضرب و مقیاس مثبت بسته است. مثلا، اگر $f$ و $g$ لگاریتم ـ مقعر باشند، آنگاه حاصل‌ضرب نقطه به نقطه‌ی $h(x)=f(x)g(x)$ لگاریتم ـ مقعر است، چون $\log h(x)=\log f(x)+\log g(x)$، و $\log f(x)$ و $\log g(x)$ توابع مقعر $x$ هستند. به‌طور کلی، مثال‌های ساده نشان می‌دهند که مجموع توابع لگاریتم ـ مقعر، لگاریتم ـ مقعر نیستند. اگرچه، لگاریتم ـ محدب تحت حاصل‌جمع حفظ می‌شود. فرض کنید $f$ و $g$ توابع لگاریتم ـ محدب باشند یعنی $F=\log f$ و $G=\log g$ محدب باشند. از قواعد ترکیب برای توابع محدب، به صورت زیر داریم \[ \log(\exp F+\exp G)=\log(f+g) \] که محدب است. بنابراین حاصل‌جمع دو تابع لگاریتم ـ محدب، لگاریتم ـ محدب است. به‌طور کلی‌تر، اگر $f(x,y)$ لگاریتم ـ محدب در $x$ برای هر $y\in C$ باشد آنگاه \[ g(x)=\int_{C} f(x,y) \dd y \] لگاریتم ـ محدب است. \begin{example} تبدیل لاپلاس تابعی نامنفی و گشتاور و توابع مولد جمعی. فرض کنید $p:\mathbf{R}^n\rightarrow\mathbf{R}$، $p(x)\geq 0$ را به ازای هر $x$ ثابت کند. تبدیل لاپلاس $p$، \[ P(z)=\int p(x)\ee^{-z^Tx} \dd x, \] روی $\mathbf{R}^n$ لگاریتم ـ محدب است. (در اینجا بدیهی است $\mathbf{dom}\:P$، $\lbrace z\:|\:P(z)<\infty\rbrace$ باشد.) حالا فرض کنید $p$ چگالی باشد، یعنی $\int p(x) \dd x=1$ را ثابت می‌کند. تابع $M(z)=P(-z)$ تابع مولد گشتاور چگالی نامیده می‌شود. نام آن را از این حقیقت که گشتاورهای چگالی می‌تواند از مشتقات تابع مولد گشتاور یافت شود، می‌گیرد. که در $z=0$، مورد بررسی قرار داده می‌شود، یعنی، \[ \bigtriangledown M(0)=\mathbf{E}\upsilon,\qquad \bigtriangledown^2 M(0)=\mathbf{E}\upsilon\upsilon^T, \] که $\upsilon$ متغیر تصادفی با چگالی $p$ نامیده می‌شود. تابع $\log M(z)$، که محدب است، تابع مولد جمعی برای $p$ نامیده می‌شود، چون مشتقات آن تجمع چگالی را بیان می‌کند. مثلا، مشتقات اول و دوم تابع مولد جمعی، ارزیابی شده در صفر، میانگین و واریانس متغیر تصادفی وابسته هستند: \[ \bigtriangledown\log M(0)=\mathbf{E}\upsilon,\qquad \bigtriangledown^2\log M(0)=\mathbf{E}(\upsilon-\mathbf{E}\upsilon)(\upsilon-\mathbf{E}\upsilon)^T. \] \end{example} \subsection*{انتگرال توابع لگاریتم ـ مقعر} در برخی موارد خاص لگاریتم ـ تقعر به‌وسیله‌ی انتگرال حفظ می‌شود. اگر $f:\mathbf{R}^n\times\mathbf{R}^m\rightarrow\mathbf{R}$ لگاریتم ـ مقعر باشد، آنگاه \[ g(x)=\int f(x,y) \dd y \] تابعی لگاریتم ـ مقعر $x$ (روی $\mathbf{R}^n$) است. (در اینجا انتگرال بر $\mathbf{R}^m$ است.) اثبات این نتیجه ساده نیست، ارجاعات را ببینید. این نتیجه پیامد مهم بسیاری دارد، تعدادی از آنها را در ادامه این بخش شرح می‌دهیم. مثلا، نشان می‌دهد که توزیع‌های حاشیه‌ای چگالی احتمال لگاریتم ـ مقعر، لگاریتم ـ مقعر است. همچنین نشان می‌دهد که لگاریتم ـ محدب تحت پیچیدگی بسته است، یعنی اگر $f$ و $g$ روی $\mathbf{R}^n$ لگاریتم ـ مقعر باشند، آنگاه داریم \[ (f*g)(x)=\int f(x-y)g(y) \dd y. \] (برای دیدن این موضوع، توجه کنید که $g(y)$ و $f(x-y)$ لگاریتم ـ مقعر در $(x,y)$ هستند، بنابراین حاصل‌ضرب $f(x-y)g(y)$ نیز لگاریتم ـ مقعر است؛ آنگاه نتیجه انتگرال به‌کار می‌رود.) فرض کنید $C\subseteq\mathbf{R}^n$ مجموعه‌ای محدب باشد و $w$ بردار تصادفی در $\mathbf{R}^n$ با چگالی احتمال لگاریتم ـ مقعر $p$ باشد. آنگاه تابع \[ f(x)=\mathbf{prob}(x+w\in C) \] در $x$ لگاریتم ـ مقعر است. برای دیدن این موضوع، $f$ را به ‌صورت زیر بیان می‌کنیم \[ f(x)=\int g(x+w)p(w)\dd w, \] که $g$ به صورت زیر تعریف می‌شود \[ g(u)= \begin{cases} 1 & u\in C\\ 0 & u\notin C, \end{cases} \] (که لگاریتم ـ مقعر است) و نتیجه انتگرال به‌دست می‌آید. \begin{example} تابع توزیع تجمعی تابع چگالی احتمال $f:\mathbf{R}^n\rightarrow\mathbf{R}$ به صورت زیر تعریف می‌شود \[ F(x)=\mathbf{prob}(w\preceq x)=\int_{-\infty}^{x_n}\cdots\int_{-\infty}^{x_1} f(z)\dd z_1\cdots\dd z_n, \] که $w$ متغیر تصادفی با چگالی $f$ است. اگر $f$ لگاریتم ـ مقعر باشد، آنگاه $F$ لگاریتم ـ مقعر است. قبلا با موردی خاص مواجه شدیم: تابع توزیع تجمعی متغیر تصادفی نرمال، \[ f(x)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^x \ee^{-t^2/2} \dd t, \] لگاریتم ـ مقعر است. (مثال \eqref{b} را ببینید.) \end{example} \begin{example} تابع محصول. فرض کنید $x\in\mathbf{R}^n$ نشان‌دهنده ارزش اسمی یا هدف از مجموعه‌ای از پارامترهای محصولی است که تولید شده است. تنوع در فرآیند تولید باعث می‌شود که پارامترهای محصول، زمانی‌که به مقدار $x+w$ تولید شد، که $w\in\mathbf{R}^n$ برداری تصادفی‌ است که تنوع تولید را نشان می‌دهد، و معمولا فرض می‌شود که میانگین صفر دارد. محصول فرآیند تولید به‌عنوان تابعی از مقادیر پارامتر اسمی، به صورت زیر داده می‌شود \[ Y(x)=\mathbf{prob}(x+w\in S), \] که $S\in\mathbf{R}^n$ مجموعه‌ای از مقادیر پارامتر قابل قبول را معنی می‌دهد، یعنی مشخصات تولید. اگر چگالی خطای تولید $w$ لگاریتم ـ مقعر باشد (مثلا نرمال) و مجموعه $S$ مشخصات تولید، محدب باشد، آنگاه تابع محصول $Y$ لگاریتم ـ مقعر است. این ناحیه $\alpha$ ـ محصول را نشان می‌دهد، که به صورت مجموعه‌ی پارامترها‌یی که محصول $\alpha$ را افزایش می‌دهد تعریف می‌شود، محدب است. مثلا، $95$ درصد ناحیه محصول \[ \lbrace x\:|\:Y(x)\geq 0.95\rbrace=\lbrace x\:|\:\log Y(x)\geq \log 0.95\rbrace \] محدب است، چون مجموعه فوق‌سطح تابع مقعر $\log Y$ است. \end{example} \begin{example} حجم جسم چند وجهی. فرض کنید$A\in\mathbf{R}^{m\times n}$ . تعریف کنید \[ P_u=\lbrace x\in\mathbf{R}^n\:|\:Ax\preceq u\rbrace. \] آنگاه حجم آن $\mathbf{vol}P_u$ تابع لگاریتم ـ مقعر $u$ است. برای ثابت کردن این موضوع، توجه کنید که تابع \[ \Psi(x,u)=\begin{cases} 1 & Ax\preceq u\\ 0 & \text{در غیر این صورت}, \end{cases} \] لگاریتم ـ مقعر است. به‌وسیله‌ی انتگرال، نتیجه می‌گیریم که \[ \int \Psi(x,u)\dd x=\mathbf{vol}P_u \] لگاریتم ـ مقعر است. \end{example} \section{تحدب با توجه به نامساوی‌های کلی} حالا کلیت مفاهیم یکنواختی و تحدب را با استفاده از نامساوی‌های کلی به‌جای ترتیب معمولی روی $\mathbf{R}$ درنظر می‌گیریم. \subsection{یکنواختی با توجه به نامساوی کلی} فرض کنید $K\subseteq\mathbf{R}^n$ مخروطی مناسب با نامساوی کلی وابسته‌ی $\preceq_K$ باشد. تابع $f:\mathbf{R}^n\rightarrow\mathbf{R}$، $K$ ـ غیرکاهشی نامیده می‌شود اگر \[ x\preceq_K y\Longrightarrow f(x)\leq f(y), \] و $K$ ـ افزایشی نامیده می‌شود اگر \[ x\preceq_K y,\:x\neq y\Longrightarrow f(x)0$ باشد (اما عکس آن درست نیست). این شرایط به‌طور واضح به حالت یکنواختی با توجه به نامساوی کلی تعمیم داده می‌شود. تابع مشتق‌پذیر $f$، با دامنه‌ی محدب، به ازای هر $x\in\mathbf{dom}\:f$، $K$ ـ غیرکاهشی است اگروتنهااگر \begin{equation} \bigtriangledown f(x)\succeq_{K^*} 0\label{21} \end{equation} به تفاوت آن با حالت ساده اسکالر توجه کنید: گرادیان باید در نامساوی دوگان نامنفی باشد. برای نمونه، اگر به ازای هر $x\in\mathbf{dom}\:f$ داشته باشیم \begin{equation} \bigtriangledown f(x)\succ_{K^*} 0\label{22} \end{equation} آنگاه $f$، $K$ ـ افزایشی است. مانند حالت اسکالر عکس آن درست نیست. اجازه دهید شرایط مرتبه اول را برای یکنواختی ثابت کنیم. ابتدا، فرض کنید که $f$ به ازای هر $x$ در \eqref{21} صدق کند، اما $K$ ـ غیرکاهشی نباشد، یعنی $x$، $y$ وجود دارد به‌طوری‌که $x\preceq_K y$ و $f(y)0$ به‌طوری‌که $h(t)=f(z+t\upsilon)