\documentclass{mc} %%%%% journal info -- DO NOT CHANGE %%%%%%%%% \setcounter{page}{57} \renewcommand\thisnumber{1} \renewcommand\thisyear {2014} \renewcommand\thismonth{xxx} \renewcommand\thisvolume{19} \renewcommand\datereceived{August 30, 2013} \renewcommand\dateaccepted{November 26, 2013} \def\C{\mathbb C} \def\R{\mathbb R} \def\Q{\mathbb Q} \def\Z{\mathbb Z} \def\N{\mathbb N} \usepackage[displaymath,mathlines,pagewise]{lineno} \begin{document} %%\begin{linenumbers} \markboth{S.\,Zlobec}{Separation property of continuously differentiable functions} \title{Separation property of continuously differentiable functions\thanks{Research partly supported by NSERC of Canada.}} \author[S.\,Zlobec]{Sanjo Zlobec\affil{1}\comma\corrauth} \address{\affilnum{1}\ Department of Mathematics and Statistics, McGill University, Burnside Hall, 805 Sherbrooke Street West, Montreal, Quebec, Canada H3A\,2K6} \email{{\tt zlobec@math.mcgill.ca} (S.\,Zlobec)} \begin{abstract} We show that every continuously differentiable function in several variables with a global Lipschitz derivative on a compact convex set with interior points has a separation property. It separates two classes of quadratic functions given in terms of either the function's convexifiers or its concavifiers. The separation is used to obtain new global characterizations of the derivative and zero derivative points. \end{abstract} \keywords{function separation property, method of convexification, convexifier, concavifier, global properties of the gradient, zero-derivative point} \ams{26A06, 26A24, 26A36, 26B20, 90C30} \maketitle \section{Introduction} This paper is based on a decomposition theorem which says that every continuously differentiable function in several variables with a global Lipschitz derivative on a compact convex set can be represented on this set as the difference of a convex function and a convex quadratic function \cite{7}. The decomposition is used in various areas of mathematics where it is sometimes referred to as the ``method of convexification''. The basic idea of the method is to apply properties of convex functions to the leading convex function in the decomposition. This often yields new results for generally non-convex functions. For example, the well-known inequalities of Jensen and Karamata for convex functions were thus extended to non-convex functions, e.g., \cite{4, 6}. A noise-determined equation in quantum mechanics can be established by means of Jensen's inequality and further improved by the method of convexification, as it is noted in \cite{3}. We used the method of convexification to characterize zero-derivative points and the gradient in \cite{8, 7}. Here we use the method to establish a separation property of continuously differentiable functions. In Section 2, we show that every continuously differentiable function with a global Lipschitz derivative on a compact convex set with interior points separates classes of quadratic functions given in terms of free convexifiers and free concavifiers. The separation property is used in Section 3 to introduce new global characterizations of the gradient and zero derivative points and in Section 4 to determine regions with prescribed tolerances around a fixed point. \newpage \noindent The term ``convexification procedures'' is used in a different context in numerical optimization where nonconvex programs with twice differentiable functions are transformed into ones which can be solved with the aid of primal-dual methods \cite{1, 2}. \section{The function separation theorem} We use the notions of ``global Lipschitz property'' of the gradient and the ``uniform bound property'' of functions. Following \cite{8,7,9}, the gradient of a continuously differentiable function $f$ is said to have the global Lipschitz property on a set $K$ if \[ ||\nabla^T f(x) - \nabla^T f(y)||\leq L ||x - y|| \] for some constant $L$ and every $x$ and $y$ in $K$. Here $||u||$ denotes the Euclidean norm of an $n$-tuple $u$ and $u^T$ denotes its transpose. We note that $L$ can only increase if the set $K$ is enlarged by inclusion. The second notion is less familiar. \begin{definition}[Uniform bound property of functions]\label{Definition 1} Consider a compact convex set $K$ in $\R^n$ and its point $x^*$. A function $\varphi(x)$ in $n$ variables is said to have the uniform bound property on $K\backslash\{x^*\}$ if $\varphi$ is defined on $K\backslash\{x^*\}$ and if there exists a constant $c$ such that $|\varphi(x)|\leq c$ for every $x$ in $K\backslash\{x^*\}$. \end{definition} It is well known that a continuously differentiable function $f$ with the global Lipschitz property of its gradient on a compact convex set $K$ can be made convex by adding to it a suitable quadratic term. In particular, if $f(x)$ is a convex function then $C(x, \alpha) = f(x) + \tfrac{1}{2}\alpha ||x||^2$ is convex for any ``convexifier'' $\alpha \geq 0$. However, in some cases $C(x, \alpha)$ can be convex also for $\alpha < 0$. In order to include this possibility, we extend the definition of convexifiers from \cite{7} to ``sign unrestricted'' numbers which we call ``free'' convexifiers. \begin{definition}[Free convexifiers and concavifiers] Consider a continuously differentiable function $f$ in $n$ variables defined on an open set of $\R^n$ containing a compact convex set $K$. A number $\alpha$ such that $C(x, \alpha) = f(x) + \tfrac{1}{2}\alpha ||x||^2$ is a convex function on $K$ is called a free convexifier of $f$ on $K$. A number $\beta$ such that $\tilde{C}(x, \beta) = f(x) + \tfrac{1}{2}\beta ||x||^2$ is a concave function on $K$ is called a free concavifier of $f$ on $K$. \end{definition} \begin{example}\label{Example 1} Consider $f(x) = x^4$ on $I = [1/\sqrt{6}, 1]$. Function $C(x,\alpha) = x^4 + \frac{1}{2}\alpha x^2$ is convex for $\alpha = -2$ and $\tilde{C}(x, \beta) = f(x) + \tfrac{1}{2}\beta ||x||^2$ is concave for $\beta = -12$. Therefore $\alpha= -2$ and $\beta = -12$ are a free convexifier and a free concavifier, respectively, of $f(x)$ on $I$. \end{example} Given a compact convex set $K$ and its interior point $x^*$, let us use free convexifiers and concavifiers to show that $f$ separates particular classes of quadratic functions. First we consider the tangent hyperplane $T(x^*,x) = f(x^*) + \nabla f(x^*)\cdot(x-x^*)$ at $x^*$ and then we construct the ``deviation function'' $D(x^*,x) = f(x) - T(x^*,x)$. This function has a global separation property. \begin{theorem}\label{tm2} Let us consider a continuously differentiable function $f$ in $n$ variables defined on an open set of $\R^n$ containing a compact convex set $K$. It is assumed that the gradient of $f$ has the global Lipschitz property on $K$. If $\alpha$ and $\beta$ are, respectively, a free convexifier and a free concavifier of $f$ on $K$, then at every interior point $x^*$ of $K$ we have \begin{eqnarray}\label{eq1} -\frac{1}{2}\alpha ||x-x^*||^2 \leq D(x^*,x) \leq -\frac{1}{2}\beta ||x-x^*||^2, \end{eqnarray} for every $x$ in $K$. \end{theorem} \proof With a free convexifier $\alpha$ we know that $f(x) = C(x,\alpha) - \frac{1}{2}\alpha ||x||^2$ where $C(x,\alpha) = f(x) + \frac{1}{2}\alpha ||x||^2$ is a convex function on $K$. Therefore for an arbitrary $x$ in $K$, $C(\lambda x + (1-\lambda )x^*,\alpha) \leq \lambda C(x,\alpha) + (1-\lambda) C(x^*,\alpha)$, for every $0 \leq \lambda \leq 1$. Hence, as in \cite{8} \begin{eqnarray*} f(\lambda x + (1-\lambda )x^*)&\leq& \frac{1}{2}\alpha ||\lambda x + (1-\lambda )x^*||^2 +\lambda f(x)-\frac{1}{2}\alpha \lambda ||x||^2\\ &&+(1-\lambda ) f(x^*) + \frac{1}{2}\alpha (1-\lambda )||x^*||^2. \end{eqnarray*} Using properties of the norm, and after division by $\lambda > 0$, this yields \[ \frac{f(x^*+\lambda(x-x^*))-f(x^*)}{\lambda}\leq f(x)-f(x^*) + \frac{1}{2}\alpha (1-\lambda )||x-x^*||^2. \] On the left hand side we have a quotient of functions in the single variable $\lambda$ of the type $0/0$. Using L'Hopital's rule, in the limit $\lambda \to 0$ this becomes \[ \nabla f(x^*)\cdot(x-x^*) \leq f(x)-f(x^*) + \frac{1}{2}\alpha ||x-x^*||^2, \] which is the left-hand side inequality in \eqref{eq1}. But also $\tilde{C}(x,\beta) = f(x) + \frac{1}{2}\beta ||x||^2$ is a concave function for an arbitrary free concavifier $\beta$. Using concavity of $\tilde{C}(\cdot,\beta)$, then switching to $f(x)$, rearrangement and using L'Hopital's rule we have \[ \nabla f(x^*)\cdot(x-x^*) \geq f(x)-f(x^*)+\frac{1}{2}\beta ||x-x^*||^2, \] the right-hand side inequality in \eqref{eq1}. \endproof The inequalities in Theorem~\ref{tm2} can be rearranged yielding the main result of the paper. \begin{theorem} [The function separation theorem] \label{tm3} Consider a continuously differentiable function $f$ in $n$ variables defined on an open set of $\R^n$ containing a compact convex set $K$. It is assumed that the gradient of $f$ has the global Lipschitz property on $K$. Let $x^*$ be an interior point of $K$ and let $\alpha$ and $\beta$, respectively, be a free convexifier and a free concavifier of $f$ on $K$. Then \[ -\frac{1}{2}\alpha ||x-x^*||^2+f(x^*)+\nabla f(x^*)\cdot(x-x^*)\!\leq\! f(x)\!\leq\! f(x^*)+\nabla f(x^*)\cdot(x-x^*)-\frac{1}{2}\beta ||x-x^*||^2\!, \] for every $x \in K$. \end{theorem} \noindent {\it Observations} If $x^*$ in Theorem~\ref{tm3} is a zero-derivative point of $f$ then for every $x\in K$ \[ -\frac{1}{2}\alpha ||x-x^*||^2+f(x^*) \leq f(x)\leq -\frac{1}{2}\beta ||x-x^*||^2 + f(x^*). \] The theorem is a statement about the two variables $x \in \R^n$ and $x^*\in R^n$. Its depiction may be given in $\R^{2n+1}$ and, for a fixed $x^*$ in $\R^{n+1}$. \begin{example}\label{Example 2} Consider $f(x) = \sin x$. We can specify a free convexifier $\alpha = 1$ and a free concavifier $\beta = - 1$ of $f$ on every compact interval around $x^* = 0$. Theorem~\ref{tm3} says that \[ x-\frac{1}{2}x^2 \leq \sin x \leq x+\frac{1}{2}x^2, \] for every $x$. The separation property of $f(x)$ at this fixed $x^*$ is depicted in Figure~\ref{Fig1}. \begin{figure}[h!] \centering \includegraphics[scale=0.8]{Zlobec1.eps} \caption{\it Function separation theorem} \label{Fig1} \end{figure} \end{example} The separation property, at the fixed extreme point $x^* = \frac{\pi}{2}$, is depicted in Figure~\ref{Fig2}. \begin{figure}[h!] \centering \includegraphics[scale=0.8]{Zlobec2.eps} \caption{\it Function separation theorem at zero-derivative point} \label{Fig2} \end{figure} \section{Global characterizations of the gradient} Using Theorem~\ref{tm3} one can globally characterize the gradient. \begin{theorem} [Global characterization of the gradient]\label{tm4} Consider a continuously differentiable function $f$ in $n$ variables defined on an open set of $\R^n$ containing a compact convex set $K$ with a nonempty interior. It is assumed that the gradient of $f$ has the global Lipschitz property on $K$. Let $x^*$ be an interior point of $K$ and let $\alpha$ and $\beta$, respectively, be a free convexifier and a free concavifier of $f$ on $K$. Denote by $G = G(x^*)$ an arbitrary row $n$-tuple. Then $G=\nabla f(x^*)$ if, and only if \begin{eqnarray}\label{eq2} -\frac{1}{2}\alpha ||x-x^*||^2 \leq f(x)-f(x^*)-G\cdot(x-x^*)\leq -\frac{1}{2}\beta ||x-x^*||^2, \end{eqnarray} for every $x$ in $K$. \end{theorem} \proof In view of Theorem~\ref{tm3} we only have to show that the $n$-tuple $G = (G_i)$ in \eqref{eq2} is the gradient. The idea is to separate $G$ from $x-x^*$ in $G\cdot(x-x^*)$. This can be done if we specify $x$ to be $x = x^* + h$, where $h = (h_i)$ is a column $n$-tuple with zero components everywhere except in the $i$-th place where we set $h_i\ne 0$. Since $x\ne x^*$, we can divide the inequalities in \eqref{eq2} by $||x - x^*||=|h_i|$ to obtain \[ -\frac{1}{2}\alpha |h_i|\leq \frac{f(x^*+h)-f(x^*)-G_i h_i}{h_i}\leq -\frac{1}{2}\beta |h_i|. \] After sending $h_i \to 0$, the above yields $G_i=~\partial f(x^*)/ \partial x_i$. Repeating this process for every $i=1,\dots,n$ yields $G = \nabla f(x^*)$. \endproof After specifying $G = 0$, Theorem~\ref{tm4} gives sharper characterizations of zero-derivative points than those given in \cite{8, 7}. The above results can be simplified. We note that the convexifier $\alpha$ and the concavifier $\beta$ in Theorem~\ref{tm4} are some fixed numbers. Regardless of their signs and magnitudes there exists a number $\Lambda \geq 0$ such that $\Lambda \geq \frac{1}{2}\alpha$ and $\Lambda \geq -\frac{1}{2}\beta$. For this $\Lambda$, using the absolute value function, the inequalities in \eqref{eq2} yield $|f(x) - f(x^*) - G\cdot(x - x^*)|\leq \Lambda ||x-x^*||^2$. Theorem~\ref{tm4} thus recovers the following characterizations of the gradient from \cite{9} where they were proved differently. \begin{theorem} [\cite{9}, Simplified characterizations of the gradient] \label{tm5} Consider a continuously differentiable function $f(x)$ in $n$ variables defined on an open set of $\R^n$ containing a compact convex set $K$. It is assumed that the gradient of $f$ has the global Lipschitz property on $K$. At an arbitrary interior point $x^*$ of $K$, consider an arbitrary row $n$-tuple $G = G(x^*)$. Then the following four statements are equivalent, i.e., any of them implies the other three: \begin{itemize} \item[$($i$)$] $G =\nabla f(x^*)$; \item[$($ii$)$] There is a constant $\Lambda \geq 0$ such that $|f(x) - f(x^*) - G\cdot(x - x^*)|\leq \Lambda ||x-x^*||^2$ for every $x$ in $K$; \item[$($iii$)$] $\frac{1}{\Lambda}| f(x) - f(x^*) - G\cdot(x - x^*)|\leq ||x-x^*||^2$ for every $\Lambda > 0$ sufficiently large and for every $x$ in $K$; \item[$($iv$)$] The ratio function $\displaystyle\varphi(x) =\frac{|f(x) - f(x^*) - G\cdot(x - x^*)|}{||x-x^*||^2}$ is uniformly bounded on $K\backslash \{x^*\}$. \end{itemize} \end{theorem} One can specify $\Lambda = \frac{1}{2} L$ in (ii) and (iii). This $\Lambda$ is an upper bound of the ratio function $\varphi(x)$ in (iv). The above theorem provides multiple equivalent answers to the following basic question: Given a continuously differentiable function $f$, a row $n$-tuple $G$, and an interior point $x^*$ in a compact convex set, what are necessary and sufficient conditions that $G$ be the gradient of $f$ at $x^*$? Properties (ii), (iii) and (iv) are called, respectively, the ``quadratic envelope'', ``normalized quadratic envelope'', and ``uniform bound'' property of the gradient. Let us depict the latter. \begin{example} \label{Example 3} Consider the product function $f(x) = x_1 x_2$ around some given interior point $x^* =(x_1^*, x_2^*)$ in $K=\{-1\leq x_1, x_2 \leq 1\}$. We wish to know whether the row $G = (x_2^*, x_1^*)$ (note the reverse order of the components!) is the gradient of $f$ at $x^*$. This is true if and only if \[ \frac{|(x_1-x_1^*)(x_2-x_2^*)|}{(x_1-x_1^*)^2+(x_2-x_2^*)^2}, \] representing $\varphi(x)$ in (iv), is uniformly bounded on $K\backslash \{x^*\}$. The latter is verified after denoting $u_1 = x_1-x_1^*$ and $u_2 = x_2-x_2^*$ and noting that $(|u_1|-|u_2|)^2\geq 0$. The graph of the ratio function $\varphi(x)$ around $x^*=0$ is depicted by Figure~\ref{Fig3}. It is uniformly bounded on $K\backslash \{x^*\}$ and we conclude that $G=\nabla f(x^*)=(0, 0)$. \begin{figure}[h!] \centering \includegraphics[scale=0.8]{Zlobec3.eps} \caption{\it Uniform bound property of the gradient} \label{Fig3} \end{figure} \end{example} We have verified the gradient without calculating partial derivatives! \section{Estimating bounds of functions} One of the applications of the Function separation theorem and Theorem~\ref{tm5}(ii) is to determine regions around $x^*$ where $f(x)$ approximates $f(x^*)$ within a prescribed tolerance. \begin{theorem}\label{tm6} Consider a continuously differentiable function $f(x)$ in $n$ variables defined on an open set of $\R^n$ containing a compact convex set $K$. It is assumed that the gradient of $f$ has the global Lipschitz property on $K$ with a Lipschitz constant $L \ne 0$. Let $x^*$ be an arbitrary interior point of K and specify some $\epsilon \geq 0$. Then for every $x$ satisfying \[ ||x - x^*|| \leq \left(\frac{2\epsilon}{L}\right)^{\frac{1}{2}} \] we have \begin{eqnarray}\label{eq3} |f(x)-f(x^*)-\nabla f(x^*)\cdot (x-x^*)|\leq \epsilon. \end{eqnarray} \end{theorem} \begin{example}\label{Example 4} Consider $f(x) = \sin x$ around $x^* = 0$. Take $\epsilon=0.01$. Let us find an interval around $x^*$ where $|sin x - x|\leq 0.01$ using Theorem~\ref{tm6}. One can specify $L = 1$. We know, after substituting $f(x^*) = 0$ and $\nabla f(x^*) = 1$ in \eqref{eq3}, that $\sin x-x \leq 0.01$ whenever $0 x^*$ is defined as \[ A(x,x^*)=\frac{\displaystyle \int_{x^*}^x f(t) dt}{x-x^*}. \] Assuming that $f(t)$ has the Lipschitz property on $I$ with a Lipschitz constant $L^*$ we can apply Theorem~\ref{tm5}(ii) to the function \[ y(x)=\int_{x^*}^x f(t) dt. \] Since $y'(x) = f(x), y(x^*) = 0$ and we can set $\Lambda= 1/L^*$. After division by $|x-x^*|\ne 0$, Theorem~\ref{tm5}(ii) yields the following result. \begin{corollary}\label{cor1} Consider a continuous function of the single variable $f(x)$ on a compact interval $I$ with an interior point $x^*$. Assume that $f$ satisfies the global Lipschitz property on $I$ with a constant $L^*$. Then \[ |A(x,x^*)-f(x^*)|\leq \frac{1}{2}L^* |x-x^*|, \] for every $x\ne x^*$ in $I$. \end{corollary} \begin{example} \label{Example 5} For $f(x) = \sin x$, from $x^* = 0$ to any $x > 0$, we have $A(x,x^*) =~(1-\cos x)/x$. Let us specify $L^* = 1$ and take $\epsilon = 0.01$. Now we conclude that the average value of $\sin x$ on the interval $0 < x \leq 0.02$ is bounded by $0.01$. \end{example} \section{Conclusion} We have shown that every continuously differentiable function with a global Lipschitz derivative on a compact convex set with interior points globally separates two classes of quadratic functions stated in terms of the function's either free convexifiers or its free concavifiers. The separation yields global characterizations of the derivative and zero-derivative points in the interior of the set. We have also estimated regions around a fixed point where values of the function fall within a specified tolerance. This may be useful in the study of average values of functions over an interval. \section*{Acknowledgement} The author is indebted to the referee for his careful reading of the manuscript and constructive comments. \begin{thebibliography}{99} \bibitem{1} {\sc D.\,P.\,Bertsekas}, {\it Convexification procedures and decomposition methods for nonconvex optimization problems}, J. Optim. Theory Appl. {\bf 29}(1979), 169--197. \bibitem{2} {\sc C.\,A.\,Floudas, C.\,E.\,Gounaris}, {\it An overview of advances in global optimization during 2003-2008}, in: {\it Lectures on global optimization}, (P.M. Pardalos and T.F. Coleman, Eds.), Fields Institute Communications 55, 2009, 105--154. \bibitem{3} {\sc R.\,Heese, M.\,Freyberger}, {\it Entropic uncertainty relation for pointer-based simultaneous measurements of conjugate observables}, Physical Review A {\bf 87}(2013), issue 1, available at \verb"http://link.aps.org/doi/10.1103/PhysRevA.87.012123". \bibitem{4} {\sc A.\,M.\,Khan}, {\it Majorization theorem for convexifiable functions}, Math. Commun. {\bf 18}(2013), 61--65. \bibitem{5} {\sc L.\,Nerali\'c, B.\,\v{S}ego}, {\it Matematika}, Second edition, Element, Zagreb, 2013. \bibitem{6} {\sc S.\,Zlobec}, {\it Jensen's inequality for nonconvex functions}, Math. Commun. {\bf 9}(2004), 119--124. \bibitem{8} {\sc S.\,Zlobec}, {\it On the behaviour of functions around zero-derivative points}, Int. J. Optim. Theory, Methods, Appl. {\bf 1}(2009), 329--340. \bibitem{7} {\sc S.\,Zlobec}, {\it Characterizing zero-derivative points}, J. Global Optimization {\bf 46}(2010), 155--161, (Published online on 2nd July 2009). \bibitem{9} {\sc S.\,Zlobec}, {\it Equivalent formulations of the gradient}, J. Global Optimization {\bf 50}(2011), 549--553. \end{thebibliography} %%\end{linenumbers} \end{document}