0$, let $r_\eps \suchthat \R \toarrow \R$ be a positive smooth even unimodal function\footnote{Recall $f$ is {\it even} if $f(-x)=f(x)$ and {\it odd} if $f(-x)=-f(x)$ for all $x$ in the domain.} with support $[-\eps,\eps]$ and $\int_{\R}r_\eps(t)dt=1$ such that the $n$th derivative $r_\eps^{(n)}$ is an odd function for $n\in \N$ odd and an even function for $n\in \N$ even. We can use $r_\eps$ as a mollifier: starting from $f\in L^p$, for $p\in [1,\infty]$, the convolution $f_\eps$ defined by $f_\eps(x) = \int_{\R}r_{\eps}(x-t)f(t)\,dt$ is a smooth strictly increasing function which converges to $f$ in $L^p$ as $\eps\toarrow 0$. If $f\in W^{k,p}$ then $f_\eps$ converges to $f$ in $W^{k,p}$. Note that since $f$ is strictly increasing and $r_{\eps}'$ is odd, $f_\eps'(x)=\int_{\R}r_{\eps}'(x-t)f(t)dt$ is strictly positive. In particular, $f_\eps$ is also strictly increasing. In light of Remark \ref{remark--unnecessary}, with respect to Theorem \ref{thm:1-d}'s notation we need only check condition (iii). For $f\suchthat [a,b] \toarrow \R$, we can always find for each $\eps>0$, a function $g_\eps \in C^2$ such that $$ (\log g_\eps')' > (\log (h_\eps \of \rest{{f_\eps}}{(m,b]}^{\scriptscriptstyle -1})' )', $$ where $h_\eps=-\left(\rest{{f_\eps}} {(a,m]}\right)^{\scriptscriptstyle -1}$. The function $g_\eps'$ has a bounded limit if and only if, for all $\eps>0$, \begin{equation} \label{conditionx} \lim_{\eps\to 0} \log (h_\eps \of \rest{{f_\eps}} {(m,b]}^{\scriptscriptstyle -1})'\in\op{BV}_{loc}((f(m),f(b))). \end{equation} Condition \ref{conditionx} is equivalent to Theorem \ref{thm:1-d}'s bounded variation condition (iii). \end{remark} \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Objective Functions on $\R^n$ and More General Manifolds and Geodesic Metric Spaces} Our discussion so far has been for functions whose domain is $\R^1$. The next natural step would be to consider functions on $\R^n$. However, with a little extra effort we will make the leap to consider functions on an arbitrary geodesic metric space $X$ with a distance function $d\suchthat X\times X \to \R$.\footnote{Recall that a geodesic metric space is a space $X$ such that there is a curve $\ga$ (``a geodesic'') between any two points $x,y\in X$ such that the distance $d(x,y)$ is realized by the length of $\ga$, also measured with respect to $d$ (see e.g. Papadopoulos (2005)).} This is a vast generalization at low cost, allowing for spaces of innumerable types of behavior (allowing for infinite dimensions, fractal pathologies, graphs, surfaces, and so forth). Distance must be defined, but the space need not have a norm, so distance can be purely ordinal. That the space be geodesic does rule out disconnected spaces, e.g., a space consisting of two disjoint line segments. We do not exclude non-proper\footnote{A metric space $X$ is proper if its closed metric balls $B(x,r)=\set{y\in X \,\suchthat\, d(x,y)\leq r}$ are compact.} geodesic metric spaces, e.g. the Banach space of all differentiable functions of one variable with the $C^1$ norm. Applications of infinite or arbitrary dimensional domains arise when considering consumption over an unspecified or infinite number of years, whether time is continuous or discrete, choice of contract functions over a space of functions, choice of present action given an arbitrary parameter space of histories, and maximization of profit by choice of network design for employees. We will also look at a special case of a geodesic metric space, namely the smooth Riemannian\footnote{That is, $M$ is equipped with a Riemannian metric coming from an inner product $g_x$ on each tangent space $T_xM$.} manifold $M$, in which case we will discover that conditions for concavifiability can be found that are amenable to easy verification. Manifolds are objects that are locally like $\R^n$, e.g. planes, donuts, and spheres, so they include $\R^n$ as a special case. Economists ordinarily work in $\R^n$, but we will go beyond it here since the added complexity is not too great and the results may be of interest in special economic applications (e.g., function spaces) and to mathematicians. We allow $M$ to be a manifold with boundary (e.g. a smooth subdomain of a larger manifold.) In all cases we will assume the regularity of the manifold: that its metric and its boundary are sufficient to support the regularity required of the functions. The required relative regularity is straightforward to determine in particular cases, but is slightly different for each case, so we will leave this to the reader. We will now expand our definition of quasiconcavity to spaces more general than $\R^1$. \fboxsep=12pt\begin{boxedminipage}[c]{.9 \linewidth} \begin{definition}\label{def:qc_metric} (QUASICONCAVITY AND CONCAVITY ON A GEODESIC METRIC SPACE) A function $f \suchthat X\toarrow \R$ on a geodesic metric space is {\em quasiconcave} if and only if $f \of \gamma \suchthat [0,1] \toarrow \R$ is quasiconcave for every geodesic $\gamma \suchthat [0,1]\toarrow \R$, where we assume that $\ga$ is parameterized proportional to, but not necessarily by, arclength.\addtocounter{footnote}{1}\footnotemark[\value{footnote}] \hspace{18pt}Similarly, $f$ is {\em concave} if and only if for each geodesic $\ga \suchthat[0,1]\to X$, $f\of \ga$ is concave as a function on $[0,1]$. \end{definition} \end{boxedminipage}\fboxsep= 3pt \footnotetext[\value{footnote}]{ That is, we assume that our geodesics are parameterized so that if $\ga(0)=x$ and $\ga(1)=y$ then $d(\ga(s),\ga(t))=\abs{t-s}d(x,y)$ for all $s,t\in [0,1]$.} Since geodesics are straight lines in $\R^n$ with its standard metric, in Euclidean space this definition agrees with our definitions for $\R^n$ at the start of the paper. In what follows, we let $m\in X$ be the unique point maximizing $f$ if $f$ is quasiconcave or minimizing $f$ if $-f$ is quasiconcave. Also recall that for a function $F:X\to \R$, the negative part of $F$, $F^{-}$, is defined by $$ \fbox{ $ F^-(x)$} \equiv \begin{cases} F(x) & F(x)<0\\ 0 & F(x)\geq 0\end{cases}. $$ We can now state the complete criterion for concavification of quasiconcave functions, the generalization of Theorem 2 for geodesic metric spaces instead of $R^1$. \begin{comment} %In what follows, let $\op{BV}_C$ denote the subset of $f\in\op{BV}([0,1])$ such %that $\op{Var}(f)\leq C$. %Following Remark \ref{rem:1-d} after Theorem \ref{thm:1-d}, for any constant $C>0$, we denote by $\Omega$ the family of strictly increasing functions $f \suchthat [0,1]\toarrow \R$ with \comment{Does $\overline{\abs{D}}(f)$ exist for arbitrary metric spaces, with no norm?} %\begin{enumerate} %\item[(i)] % $\log \overline{D}(f)$ bounded above on $[0,t]$ for any $t<1$ and bounded below on $[s,t]$ for any $0~~1$ the term $\inner{\grad f,e_j}$ identically vanishes, and so $$f_{ij}=-\inner{\grad f,\nabla_{e_i}e_j}=-\norm{\grad f}\inner{e_1,\nabla_{e_i}e_j}=-\norm{\grad f}(\nabla_{e_i}\inner{e_1,e_j}-\inner{\nabla_{e_i}e_1,e_j})=\norm{\grad f}(\inner{\nabla_{e_i}e_1,e_j}).$$ In particular $f_{ii}=-\norm{\grad f}\la_i$ when $i>1$. Putting this together we compute the Hessian of $g\of f$ to be, \begin{equation} \label{e21} \grad^2 (g \of f)=(g'' \of f)\begin{pmatrix} \norm{\grad f}^2& 0 & 0 & \cdots &0\\ 0& 0 & 0 & \cdots &0\\ 0& 0 & 0 & \cdots &0\\ \vdots & \vdots & \ddots & \vdots &\vdots\\ 0& 0 & 0 & \cdots &0 \end{pmatrix}+ (g' \of f)\begin{pmatrix} f_{11}& f_{12} & f_{13} &\cdots & f_{1n} \\ f_{21} & -\lambda_2 \norm{\grad f} & 0 & \cdots & 0 \\ f_{31} & 0 & -\lambda_3 \norm{\grad f}& \cdots &0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ f_{n1} &0 &\cdots & 0 &-\lambda_{n}\norm{\grad f} \end{pmatrix}, \end{equation} Note we have $f_{1j}=-\inner{\grad f,\nabla_{e_1}e_j}$, and moreover, $$ f_{11}=\frac{1}{\norm{\nabla f}^2} \inner{\nabla_{\nabla f}\nabla f,\nabla f}= \frac{\nabla_{\nabla f}\norm{\nabla f}^2}{2\norm{\nabla f} ^2}=\frac{\nabla_{\nabla f}(\norm{\nabla f})} {\norm{\nabla f}}=\partial_{e_1}\norm{\nabla f}, $$ or, in other words, $f_{11}$ is the growth rate of $\norm{\nabla f}$ in the $\nabla f$ direction. Similarly, since $\inner{e_1,e_1}=1$ identically, $\inner{e_1,\nabla_{e_j}e_1}=\frac12 e_j(\inner{e_1,e_1})= 0$. Therefore, \begin{equation} \label{e22} f_{1,j}=f_{j,1}=\nabla_{e_j}\inner{\grad f,e_1}-\inner{\grad f,\nabla_{e_j}e_1}=\nabla_{e_j} \norm{\nabla f}. \end{equation} Since the values $\la_i$ are all positive, we see that the principal minors, starting from the lower right, alternate sign. Hence in order to show that the eigenvalues of $\op{Hess}(g\of f)$ are all negative it remains to show that the sign of the entire determinant is $(-1)^n$. Observe that for $j>1$, the minor of the combined matrix corresponding to the pivot $f_{1j}$ along the first row becomes lower triangular after moving the row whose entry begins with $f_{j1}$ to the first row. This introduces a $(-1)^{j-2}$ to the determinant of the minor, which is then $(-1)^{j-2}(g' \of f) ^{n-1} f_{j1}\lambda_2\dots\lambda_{j-1} \lambda_{j+1}\dots\lambda_n (-\norm{\grad f})^{n-2}$. In particular the cofactor for $j>1$, namely $(-1)^{j-1}f_{1j}(g'\of f)$ times this, is simply $$(-1)^{n-1}(g' \of f)^{n} \norm{\grad f}^{n-2} \frac{f_{1j}^2}{\lambda_j}\prod_{i=2}^n\lambda_i.$$ Hence, adding in the first cofactor, the entire determinant of $\op{Hess}(g \of f) $, found by expanding on minors across the first row, yields \begin{equation} \label{e23} \det \op{Hess}(g \of f)=(-1)^{n-1}\left( \frac{g'' \of f}{g' \of f} \norm{\grad f}^2+f_{11}+\sum_{j=2}^n \frac{f_{1j}^2}{\lambda_j\norm{\grad f}}\right)(\norm{\grad f})^{n-1}(g' \of f)^{n}\prod_{i=2}^n \lambda_i. \end{equation} We care about when expression \eqref{e23} has sign $(-1)^n$. Since $\norm{\grad f}$, $g'$, $f_{1j}^2$ and $\la_i$ are all positive, this happens if and only if \begin{equation} \label{e24} (g'' \of f)\leq \frac{(g' \of f)}{\norm{\grad f}^2}\left(-f_{\s 11}-\sum_{j=2}^n \frac{f_{{\s 1}j}^2}{\lambda_j}\right), \end{equation} which can be satisfied for a given $f$ by a $g$ with $g'> 0$ and $g''<0$, provided that for almost every value $y$ in the range of $f$, the quantity $$ \frac{1}{\norm{\nabla f}^2} \left(-f_{\s 11}+\sum_{j=2}^n \frac{f_{{\s 1}j}^2}{\lambda_j \norm{\grad f}}\right) $$ is bounded below by $q(y)$ on the level set $f^{\scriptscriptstyle -1}(y) $, where $q\in L^1_{loc}$. By the theorem's assumption we have such a bound. The $g$ function in the statement of Theorem 4 satisfies these necessary conditions. Conversely, $\grad f$ must be bounded, away from the maximum point $m$, by Theorem \ref{thm:metric}'s condition, and if $q\not\in L^1_{loc}$ then we cannot obtain a $g$ which everywhere satisfies the needed inequality. \begin{comment} Since we assumed that the $C^1$ norm of $\nabla f$ is bounded, and the eigenvalues of the second fundamental form are uniformly bounded away from 0 (uniform quasiconcavity), it follows that each term $\frac{f_{1j}^2}{\lambda_j}$ is uniformly bounded. Hence if the gradient is uniformly positive on each level set, then we can solve for a smooth $g$. \end{comment} \end{proof} Theorem 4 generalizes the ``one-point'' conditions of Fenchel (1953) for $\R^n$ (as reformulated in Section 4 of Kannai (1977)) to the Riemannian setting. Kannai's condition (I) on utility $v$ corresponds to our condition (ii) on $f$. However he is allowing for weak concavifiability, which accounts for his necessary conditions (II) and (III) differing from our condition (i) when the sublevel sets of $v$ are not strictly convex. Otherwise, these conditions are equivalent to our condition (i) and his conditions (IV) and (V) are folded into our condition (iii). This is best seen through the rephrasing of Kannai's condition (IV) as (IV$'$) and noting that his $k$ equals our $\norm{\grad f}$ and that under our assumptions in the case when $M=\R^n$, $-\la_j \norm{\grad f}=f_{jj}$ under our assumptions when $M = \R^n$. Note that Kannai's perspective is that of constructing a concave utility function based on weakly convex preference relations, whereas we start with an arbitrary function and see if it can be concavified. \fboxsep=12pt \begin{boxedminipage}[c]{.9 \linewidth} \begin{small}{\bf Figure 11’s example: What condition (iii) excludes. } Condition (iii) can be easily violated by a $C^2$ function $f$ satisfying conditions (i) and (ii) by making the (necessarily noncompact) level sets become asymptotically flat sufficiently quickly as points tend to infinity. A simple example is the quasiconcave function $f(x,y)=e^{e^x} y$ defined in the open positive quadrant of $\R^2$, shown in Figure \ref{fig:condition3}. Its gradient, $\left(e^{x+e^x} y,e^{e^x}\right)$, is nonvanishing and its Hessian restricted to the level set of value $t$ as a function of the $x$ coordinate is $-\frac{t e^x \left(e^x-1\right)}{t^2 e^{2 x-2 e^x}+1}$. The negative definiteness shows that $f$ is strictly quasiconcave. The quantity in condition (iii) on the level set of $t$ works out to be $\frac{1}{-t+te^{-x}}$, whose infimum is always $-\infty$, and thus $f$ is not concavifiable. \end{small} \end{boxedminipage} \fboxsep= 3pt \begin{figure}[h!] \centering \includegraphics[width=2in]{condition3} \caption{\sc A function violating condition (iii) of Theorem \ref{thm:manifold}} \label{fig:condition3} \end{figure} \bigskip \begin{remark} Since $f_{1j}=-\inner{\grad f,\nabla_{e_1}e_j}$, in the special case that the integral curves of the vector field $\grad f$ lie along geodesics of $M$, then $f_{1j}=0$ for all $j>1$. This occurs, for instance, when $f$ is constant on distance spheres about a fixed point. \end{remark} \bigskip \begin{remark} Some twice-differentiable functions $f$ with $\grad f$ vanishing at points other than the maximum can also be concavified, provided we are willing to concavify using a $g$ which is not twice differentiable. The more general condition is that after an initial postcomposition by a non-twice differentiable function $g_o$ the resulting $g_o\of f$ must satisfy conditions (ii) and (iii). In particular, when $\grad f$ vanishes at a point, it must do so on the entire level set, though this alone is not sufficient. \end{remark} \bigskip \begin{remark} % Remark 14 In contrast to Theorems \ref{thm:1-d} and \ref{thm:metric}, here $f$ is Lipschitz from the beginning, by virtue of being twice differentiable, and moreover $\log (h\of f\of \ga)'$ automatically belongs to $\op{BV}_{loc}$ for any twice differentiable increasing function $h$ and geodesic $\ga$ under the assumption of condition (ii). Also, Theorem \ref{thm:manifold}'s condition (iii) is vacuous for one-dimensional $M$ and $C^2$ function $f$ when condition (ii) holds. So testing the theorem with one-dimensional examples is pointless. \end{remark} If $f$ is $C^2$ with nonvanishing gradient, then the quantity \eqref{e20} in the infimum of the definition of $q(t)$ in condition (iii) of Theorem \ref{thm:manifold} is uniformly bounded and continuous on compact sets. Moreover, the infimum of any compact family of continuous functions is always continuous. Hence, we immediately obtain that the variation function $q$ from \eqref{e20} is continuous if $f$ is $C^2$ with compact level sets. We express this as the following especially simple corollary. \bigskip \fboxsep=12pt\begin{boxedminipage}[c]{.9 \linewidth} \begin{corollary}\label{cor:1} If $f \suchthat M\toarrow \R$ is strictly quasiconcave and $C^2,$ with compact level sets, then there is a $C^2$ strictly concavifying $g$ if and only if $\grad f$ does not vanish except at $f$'s maximum. \end{corollary} \end{boxedminipage}\fboxsep= 3pt \bigskip \begin{remark} Fenchel's Example in Figure \ref{quasifig-aumann.jpg} does not satisfy Corollary \ref{cor:1}’s conditions, because it is not strictly quasiconcave. In fact, for any function not strictly quasiconcave, at least one of the principal curvatures $\la_i$ vanishes somewhere and thus quantity \eqref{e20} becomes unbounded. \end{remark} We can also work with the weak Hessian of $f$ for functions $f\in W^{2,1}$. A weak gradient for $f \suchthat \Omega\subset\R^n\toarrow \R$ is any vector function $\phi \suchthat \Omega\toarrow \R^n$ such that for every smooth compactly supported function $\rho \suchthat \Omega\toarrow \R$, \begin{equation} \label{e26} \int_{\Omega}\phi(x) \rho(x)dx=-\int_\Omega f(x) (\grad \rho)(x) dx. \end{equation} We will denote any such weak gradient by $\nabla f$. This is justified, since from the definition any two weak gradients agree almost everywhere. By taking charts and using the volume forms one can see that this definition extends to arbitrary tensors on arbitrary smooth manifolds.\footnote{A chart is a bijective continuous mapping of an open set of a manifold onto $\R^n$.} Define $W^{0,p}(M)$ to be $L^p(M)$, which we extend to denote the space of $L^p$ tensors of any type on $M$. We then extend inductively by defining $f\in W^{k,p}$ if $\nabla f\in W^{k-1,p}$. We only used $L^1$ existence of second derivatives in Theorem \ref{thm:manifold}'s proof, so we obtain another corollary. \fboxsep=12pt\begin{boxedminipage}[c]{.9 \linewidth} \begin{corollary}\label{cor:2} The results of Theorem \ref{thm:manifold} and Corollary \ref{cor:1} hold verbatim for $f\in W^{2,1}$. \end{corollary} \end{boxedminipage}\fboxsep= 3pt For $f\in W^{2,1}$, the smooth local convolution functions $f_\eps \suchthat M\toarrow \R$ have Hessians which converge in $L^1$ to the weak Hessian of $f$. Hence, the $W^{2,1}$ Sobolev space provides a class of functions which are reasonably easy to work with in the sense that the condition in Theorem \ref{thm:manifold} is ``differential'' and hence easy to check. The space $W^{2,1}$ is a fairly large, and flexible, class frequently used in the theory of partial differential equations because of its closure properties and techniques for embedding it in other function spaces. %--------------------------------------------------------- \section{Discontinuous or Weakly Quasiconcave Objective Functions}\label{sec:discont} We did not require differentiability for Theorems \ref{thm:1-d} and \ref{thm:metric}, but we did assume functions were continuous. Also, we characterized strict quasiconcavity, but not quasiconcavity generally. It turns out that our results are true for some but not all discontinuous functions and that we can also characterize quasiconcavity generally. \subsection{Discontinuous Functions }\label{subsec:discont} First, let us see why our theorems are false for discontinuous functions generally. For simplicity we will assume throughout the section that we are in the case where the domain is a manifold $M$. By collapsing intervals in the range of a quasiconcave $f\suchthat M\toarrow \R$ we can always find a nondecreasing $g$ such that $g\of f$ is continuous. However, $g$ might have to be the constant function since the interval gaps between values at discontinuities can cover the entire range of $f$. \fboxsep=12pt \begin{boxedminipage}[c]{.9 \linewidth} \begin{small} {\bf Figure 12’s example: A discontinuous quasiconcave function.} The following strictly quasiconcave function $f\suchthat [0,1]\toarrow \R$ is shown in Figure \ref{quasi7}: \begin{equation} \label{notmappable} f(x)=\begin{cases} 5+10x & x \leq \frac12 \\ 5 - 10(x-.5) & x > \frac12. \end{cases} \end{equation} The dotted line shows a particular $g(f(x))$. It must have a discontinuous drop at $ x=.5$ because for $x$ less than 5, $g(5) > g(x)$, a strict inequality. Such a discontinuity prevents $g(f(x))$ from being concave. \end{small} \end{boxedminipage}\fboxsep= 3pt \begin{figure}[ht] \centering \includegraphics[width=4in]{quasifig10-discontinuous} \caption{\sc A Discontinuous Quasiconcave Function Which Cannot Be Mapped to a Concave Function } \label{quasi7} \end{figure} What we would like to do is to postcompose $f$ by a function $h$ to make it continuous, so we could apply our earlier sections' theorems. We can do that for certain discontinuous functions, such as the $f(x)$ in Figure \ref{quasi6}. \begin{figure}[ht] \centering \includegraphics[width=5in]{quasifig11-hump.pdf} \caption{\sc A Concavifiable Discontinuous Function } \label{quasi6} \end{figure} Recalling that $f(x)$ is defined over $(a,b)$ and reaches its maximum at $m$, define $A \equiv (a,m)$ and $B \equiv [m,b)$ (see Figure \ref{quasi6}). Define $R_A$ as the union of the images of $f(x)$ from $A$ and $R_B$ as the union from $B$. Define the gap sets $$G_A \equiv [\inf_{x\in A} f(x),f(m)) - R_A\quad\text{and}\quad G_B \equiv [ \inf_{x\in B} f(x),f(m)] - R_B.$$ \fboxsep=12pt\begin{boxedminipage}[c]{.9 \linewidth} \begin{proposition}\label{prop:discont} For any, possibly discontinuous, strictly quasiconcave $f \suchthat M\toarrow \R$, there is a function $h \suchthat f(M)\toarrow \R$ such that $h \of f$ is strictly quasiconcave and continuous if and only if the range of $f$, $R_A \cup R_B$, and the interior of the union of the gap sets, Interior $ G_A \cup G_B $, are disjoint. Any such $h$ may be chosen to be nondecreasing. \end{proposition} \end{boxedminipage}\fboxsep= 3pt \begin{proof} If the hypothesis applies, then whenever $s>t$, the (closed) superlevel sets satisfy either $S_t(f)=S_s(f)$ or else $S_t(f)$ is contained in the interior of $S_s(f)$. The hypothesis is exactly the hypothesis that the discontinuous jumps in $f$ occur along entire level sets and are the same height. So each gap in the image can be closed by a piecewise linear nondecreasing $h$ which is constant on the gap interval. The gaps are disjoint so the whole procedure can be accomplished by a single $h$. Since no interval of level sets are sent to the same value, strict quasiconcavity is clearly preserved by this operation. Conversely, suppose $h$ makes $h \of f$ continuous and strictly quasiconcave but the hypothesis on the gaps of $f$ is not satisfied. Let $[a,b]\subset \op{Range}(f)$ be an interval in the range of $f$ where for each $t\in[a,b]$ the superlevel sets $S_t(f)$ share a common boundary point. Then $h$ must carry these to the same value. However, by assumption they are not the same superlevel set, so there is a nondegenerate curve $c \suchthat [a,b]\toarrow M$, and so $h \of f$ is constant on $c(t)$. This contradicts strict quasiconcavity. \end{proof} %--------------------------------------------------------- \section{Weakly Quasiconcave Objective Functions } One might think that if strictly quasiconcave functions satisfying Theorem \ref{thm:metric}'s necessary conditions are those that can be transformed strictly monotonically into concave functions, then we should have a similar statement for weakly quasiconcave functions, along the lines of the following. \begin{conjecture} If weakly quasiconcave functions satisfy an analogue to Theorem \ref{thm:metric}'s conditions, then they can be transformed weakly monotonically into weakly concave functions. \end{conjecture}\vspace{-12pt} Unfortunately, this conjecture is false.\\ \fboxsep=12pt\begin{boxedminipage}[c]{.95 \linewidth} \begin{small} {\bf Figure 14’s example: A weakly quasiconcave function.} Figure \ref{quasifig12-weak} shows a function $f$ which is only weakly quasiconcave because the values of $x$ between $1$ and $2$ map to the same $f(x)$ (and likewise for values between 3 and 5). It is still quasiconcave because the upper level set $[1, 5.5]$ is convex and though multiple values of $x$ maximize $f(x)$, the only maximal value is $2$. \end{small} \end{boxedminipage}\fboxsep= 3pt \begin{figure}[ht] \centering \includegraphics[width=4in]{quasifig12-weak} \caption{\sc A Weakly Quasiconcave Function } \label{quasifig12-weak} \end{figure} If we apply a monotonically increasing $g$ to the function $f$ in Figure \ref{quasifig12-weak}, that $g$ will have to map all the values of $x$ in $[1,2]$ to the same $g(f(x))$. As a result, $g(f(x))$ will have a flat part as shown and cannot be even weakly concave. The conjecture is false because the word ``weakly'' is used differently for concavity and for quasiconcavity. Consider a twice-differentiable function $f\suchthat\R\toarrow \R$. If $f$ is strictly concave, it cannot have any linear portions; its second derivatives cannot vanish (though they can if it is only weakly concave, e.g., $f(x) =x$). If $f$ is strictly quasiconcave, it can have linear portions. The function $f$ is only weakly quasiconcave if it has horizontal segments aside from its peak; that is, if the first derivative vanishes over some segment other than the maximum. The slope's rate of change is irrelevant for quasiconcavity. What does matter about the slope--- the essence of quasiconcavity--- is that it must not switch sign more than once. What make $f$ weakly quasiconcave is if its slope is zero over an interval, coming as close as possible to switching sign more than once. What can we do, then, to extend our constructions to concavify weakly concave functions? What we will do is approximate the function $f$ by a series of strictly concavifiable functions. Recall that even strictly quasiconcave functions may not be concavifiable, as not all such functions satisfy Theorem \ref{thm:metric}'s regularity conditions. Therefore we would also like to make sure that our strictly quasiconcave approximations are concavifiable. Fortunately, both properties of approximations are easy to arrange with the ``connect-the-dots'' approach we use below. For simplicity we will assume that the domain of $f$ is a convex subset $D\subset\R^n$, but the constructions and resulting properties apply straightforwardly to convex domains in any Riemannian manifold since they are purely local and Riemannian manifolds always have small convex neighborhoods around each point which look similar to a convex set in $\R^n$. \bigskip We will use a two-step process. The first step is to approximate the function by one whose level sets all have empty interior. At most a countable number of level sets for $f$ can contain nonempty interior, since any disjoint family of open sets in $\R^n$ is countable, and the same holds for manifolds. We may enumerate these exceptional level sets by $f^{-1}(c_1),f^{-1}(c_2),\dots$, where the values $c_i$ are not necessarily in increasing order. For now, fix a choice of small $\eps>0$. Also, fix the constant $k_1= 2^{-1}$. We make a new function $f_1$ from $f$ as follows. For all values of $c\leq c_1$ that belong to the range of $f$, we set $f_1^{-1}(c-\eps k_1)$ to be the set at distance $\eps k_1$ from the super-level set $S_c(f)$. Whenever there are points other than $S_c(f)$ contained in the set bounded by $f_1^{-1}(c-\eps k_1)$, we assign the $f_1$ value of $c-\eps 2^{-1}$ to these as well. For values $c\leq c_1$ not in the $\op{Range}(f)$ we exclude the value $c-\eps k_1 $ from $\op{Range}(f_1)$. For all $c>c_1$ and $x\in S_c(f)$, we set $f_1(x)=f(x)$. We finish by explaining how to assign the $f_1$ values in the range interval $(c_1-\eps k_1,c_1]$. Let $A=\cup_{c>c_1} S_c(f)$, i.e. the open $c_1$ super-level set of $f$, and set $B$ to be the set of all points at distance at most $\eps k_1$ from $S_{c_1}(f)$. Since $A$ is weakly convex, the integral curves tangent to the gradient vector field of the function $x\mapsto d(x,A)$, where $d(x,A)$ is the distance from $x$ to the set $A$, consist of geodesic segments. For any point $x\in B\setminus A$, let $l(x)\geq \eps k_1$ be the length of the maximal such integral geodesic segment passing through $x$ and contained in $B\setminus A$. We then set $f_1(x)=c_1-d(x,A)\frac{\eps k_1}{l(x)}$. This defines a new function $f_1$ whose domain consists of all points at distance at most $\eps k_1$ of the domain $D$ of $f$. Since uniform distance sets to weakly convex sets are weakly convex, the super-level sets of $f_1$ remain weakly convex, and so $f_1$ is again weakly quasiconcave. We now construct $f_2,f_3,\dots$ successively in a similar manner. Namely, for $i\geq 2$, $f_{i}$ is constructed from $f_{i-1}$, by replacing $f$ in the construction above by $f_{i-1}$, the constant $k_1=2^{-1}$ everywhere by the constant $k_i=2^{-i}$, and $c_1$ everywhere by $c_i-\eps \sum_{j=1}^{i-1} k_j$. After repeating this process a countable number of times, we arrive at the limiting function, denoted $f_\eps=\lim_{i\to\infty} f_i$. This function inherits certain nice properties. \begin{lemma}\label{lem:feps} The function $f_\eps$ has the following properties: \begin{enumerate}[(i)] \item $f_\eps$ is weakly quasiconcave, \item $f_\eps$ has level sets with empty interior, and \item $f_\eps$ converges pointwise almost everywhere to $f$ as $\eps\to 0$, and it converges uniformly on compacta if $f$ is continuous. \end{enumerate} \end{lemma} \begin{proof} The first item was explained in the construction. For the second item, by the construction, all of the level sets with nonempty interior of $f$ have been enlarged and broken into a new family of level sets with empty interior in $f_\eps$. Lastly, we note that the $c$-level set of $f_\eps$ is displaced at most by $\sum_{i=1}^\infty \eps k_i=\eps$ from that of $f$. Hence for any point $x$ where a discontinuity of $f$ does not occur, $f_\eps(x)$ converges pointwise to $f(x)$. There can be at most a countable set of level sets where a discontinuity occurs since $f$ is quasiconcave. On each such level set, a discontinuity cannot occur at an interior point. Since the super-level sets are convex, and a countable union of measure $0$ sets has measure $0$, this is a measure $0$ set of points. If $f$ is continuous then the displacement of the level sets implies that the convergence is uniform on compacta, although not necessarily globally uniform even on a single level set. \end{proof} \begin{remark} Note that $f_\eps$ is continuous when $f$ is, but may not be if $f$ is discontinuous. Even so, $f_\eps$ does not always converge pointwise at points of discontinuity of $f$. For instance, this occurs for functions that take on two values such as $f \suchthat [-1,1]\to \set{0,1}$ with $f^{-1}(0)=[-1,-\frac12]\cup [\frac12,1]$ and $f^{-1}(1)=(-\frac12,\frac12)$ where the convergence does not occur at $x\in\set{-\frac12,\frac12}$. \end{remark} The second stage of the construction is to turn a weakly quasiconcave function $f$ with the properties of $f_\eps$ above into a strictly quasiconcave function that is concavifiable. \fboxsep=12pt\begin{boxedminipage}[c]{.9 \linewidth} \begin{definition}\label{def:PL_approx} (PIECEWISE LINEAR APPROXIMATION) Suppose $f\suchthat D\to \R$ is any weakly quasiconcave function, possibly discontinuous, whose level sets have nonempty interior. A {\bf piecewise linear approximation}\addtocounter{footnote}{1} \footnotemark[\value{footnote}] $f_\eps$ is constructed for $f$ as follows. Choose $\Lambda=\Lambda_\eps\subset D$ be a subset of the domain of $f$ with the following properties: \begin{enumerate} \item $\Lambda$ is a discrete set, that is it intersects any compacta in a finite set, \item No two points in $\Lambda$ belong to the same level set, i.e. they all have distinct values, \item Each open ball $B(p,\eps)$ of radius $\eps$ in $D$ contains at least one point of $\Lambda$. \end{enumerate} We now produce a Delaunay-Voronoi triangulation\addtocounter{footnote}{1} \footnotemark[\value{footnote}] $T$ corresponding to the discrete set $\Lambda$. The function $f_\eps$ is now defined to be the linear interpolation along each simplex of $T$ of the values of $f$ on the vertices of the simplex, which form a set of $n+1$ points belonging to $\Lambda$. \end{definition} \end{boxedminipage}\fboxsep= 3pt \addtocounter{footnote}{-1} \footnotetext[\value{footnote}]{ This definition is quite different than the notion of ``$PL$'' map commonly used in mathematics. We use a very constrained triangulation, but we do not require links of points to be spheres, or even for the triangulation $T$ to be a $PL$ approximation of $D$.} \addtocounter{footnote}{1} \footnotetext[\value{footnote}]{ This is a simplicial complex $T$ of a set of points $P\subset \R^n$ such that no point of $P$ lies in the interior of the circumscribing ball of the vertices of any simplex of $T$. The triangulation $T$ is unique if there is no $k$-dimensional plane containing $k+2$ points or $k$-sphere containing $k+3$ points for $1\leq k\leq n-1$. For intuition, see Paul Chew's Java applet at \url{http://www.cs.cornell.edu/info/people/chew/Delaunay.html}. } It is not immediately obvious that the above definition is well defined, particularly that such a set $\Lambda$ exists. However, to satisfy the third criterion, any such ball intersects an uncountable continuum of level sets (otherwise the intersection with one of the level sets is open), and so a point can be always added to $\Lambda$ (which is a countable set) within the ball on a new level set. This linear interpolation of $f$ on each simplex is accomplished by standard barycentric averaging. Namely, if the vertices of a given simplex in $T$ are $v_0,\dots,v_{n}$ and $x=t_0 v_0+\dots +t_n v_n$ for any $t_0,\dots,t_1\in [0,1]$ then the value at the interpolated point $x$ is given explicitly by $f_\eps(x)=\sum_{i=0}^n t_i f(v_i)$. Lastly, since the Delauney-Voronoi triangulation of a discrete set in $\R^n$ always exists and consists of non-overlapping simplices (except on the boundaries where the definition of $f_\eps$ agrees), $f_\eps$ is well defined. When the domain $D$ is a weakly convex subset of a manifold, the same is true provided that $\eps$ is chosen sufficiently small, so that all simplices lie inside a convex neighborhood of their vertices. Such neighborhoods are uniquely geodesic, and combinatorially behave like $\R^n$. \fboxsep=12pt\begin{boxedminipage}[c]{.9 \linewidth} \begin{proposition}\label{prop:rectify} Suppose $f$ is a weakly quasiconcave function whose level sets have no interior. \begin{enumerate} \item[(i)] Every choice of piecewise linear approximation $f_\eps$ is strictly quasiconcave, continuous and strictly concavifiable, regardless of the regularity of $f$ (e.g. the discontinuity or nondifferentiability). \item[(ii)] The functions $f_\eps$ converge to $f$ pointwise almost everywhere and uniformly on compact domains if $f$ is continuous. \end{enumerate} \end{proposition} \end{boxedminipage}\fboxsep= 3pt \begin{proof} Since the points of $\Lambda$ belong to distinct level sets of $f$ the values at the vertices are distinct and hence the linear interpolation has no geodesic line segments\footnote{Or geodesics, in more general metric spaces. We have limited the proposition to $\R^n$ only for simplicity, but its extension is straightforward.} on which $f_\eps$ is constant. Moreover, since the complex $T$ is connected, the function $f_\eps$ is automatically continuous. To prove concavifiability, we cannot simply apply the finite point domain version of Theorem \ref{thm:finite} since we are interpolating, but it is still quite straightforward. We note that, by the construction, along any line segment in the domain there are only a finite number of piecewise linear changes, and no horizontal flat portions. After inverting one side, say $f_1$, of the resulting restricted function, the other side remains piecewise linear with a finite number of pieces, none of which are flat. Hence, the upper derivative along the resulting monotone increasing piece, say $f_2$, is always strictly positive, taking on only a finite number of values. The log of this function trivially belongs to $\op{BV}_{loc}$ on its domain interval. In particular, it is concavifiable, by Theorem \ref{thm:metric}. We will prove the converse of statement (i) at the end of the proof. For statement (ii), since the functions are locally monotonic we note that on any simplex of diameter at most $\eps$ in the domain, the difference $\abs{f-f_\eps}$ is bounded by the supremum of the derivative of $f_\eps$, not of $f$, on the simplex times at most $\eps$. On each compact subset of the domain this uniformly converges to $0$ as $\eps\to 0$. Hence, the function converges uniformly on compact subsets of the interior of $D$. The pointwise statement follows immediately. Note that the domain of $f_\eps$ is the realization of the simplicial complex $T$. This belongs to $D$ by convexity of $D$, but may be a proper subset. Nevertheless these domains converge to $D$ by the same reasoning above. \begin{comment} %For the converse of the first statement, if $f$ is not weakly quasiconcave, then we %claim we can %choose a set $\Lambda$ satisfying the given properties for some sufficiently %small $\eps>0$, such that one of the superlevel sets of the resulting function %$f_\eps$ is not even %weakly convex, and hence $f_\eps$ is not even weakly quasiconcave. To see %this, we simply note that by uniform convergence on compacta of the $f_\eps$ to $f$, compact subsets of the level sets of $f_\eps$ Hausdorff-converge\footnote{That is, the %Hausdorff distance should tend to $0$. The Hausdorff distance between sets $A$ and $B$ is defined to be the infimum of the $r>0$ such that the $r$-neighborhood of $A$ ( %$\cup_{x\in A}B(x,r)$) contains $B$ and the $r$-neighborhood of $B$ contains $A$.} to those of $f$. Now consider a line segment connecting two points in the interior of a %closed superlevel set $f^{-1}([c,\infty))$ which leaves the super level set, necessarily on at least one open segment of the line. For small enough $\eps$, the same line %segment must similarly connect two points in the interior of $f_\eps^{-1}([c,\infty))$, and yet leave it as well. Hence $f_\eps$ cannot be quasiconcave. \end{comment} Lastly we note that for any $x$ where $f$ is continuous, then $\lim_{\eps\to 0}f_\eps(x)=f(x)$ regardless of the choice of $f_\eps$, since the simplices containing $x$ will eventually have vertices in $\Lambda$ sufficiently near $x$, and thus their values also converge. As in Lemma \ref{lem:feps}�s proof, the set of discontinuous points has measure $0$. For continuous $f$ the difference of the values of vertices of a simplex in $T$ will depend uniformly on $\eps$ on compacta, by uniform continuity of $f$ there. Hence $f_\eps$ converges uniformly on compacta to $f$ in this case as $\eps\to 0$. In particular, it approaches $f$ in any norm which relies only on pointwise differences (as opposed to derivatives, for instance). This includes any $L^p$ norm for $p\in[1,\infty]$. \end{proof} Proposition \ref{prop:rectify} is nice for practical purposes since Theorem \ref{thm:metric}'s potentially arduous testing is unnecessary, nor even the more convenient testing of Theorem \ref{thm:manifold}, provided one is willing to perturb the initial quasiconcave function as prescribed by Definition \ref{def:PL_approx}. Note, too, that in this proposition we have finally extended the idea of concavification to discontinuous functions. If we start with a general weakly quasiconcave function and first apply Lemma \ref{lem:feps} followed by the above proposition, then we immediately obtain the following corollary. \begin{corollary} Suppose $f$ is any weakly quasiconcave function (possibly discontinuous). There exists a sequence of continuous strictly quasiconcave and concavifiable functions $f_\eps$ which converge to $f$ as $\eps\to 0$ pointwise almost everywhere, and uniformly on compacta if $f$ is continuous. \end{corollary} %-------------------------------------------------------------------- \section{Concluding Remarks} We have tried in this article to clarify the relationship between concavity and quasiconcavity at two levels. The first level is the intuitive one, where we have explored when continuous strictly quasiconcave functions, whether differentiable or not, are functions that can be monotonically blown up into strictly concave functions. The second level is the rigorous one, where we have shown that the intuition holds true for arbitrary geodesic metric spaces of any dimension, but subject to caveats that apply even in $\R^1$, caveats involving the Lipschitz continuity of the function and the amount of variation in its derivatives. We also show that these caveats become much simpler to check in the case of twice-differentiable functions with compact level sets, when all that is required is that the gradient of the function not vanish. To mediate between the intuitive and the rigorous we have provided numerous examples of quasiconcave functions that can and cannot be concavified. In economics, the maximands most commonly encountered are utility functions, profit functions, and the payoff functions of principals and agents. Since calculus is our most powerful tool for maximization, we would like for these functions to be twice differentiable and concave. It would be nice if our results in this paper implied that whenever an objective function is quasiconcave, the modeller can transform it one-to-one to a twice-differentiable concave function. Alas, that is not true. We have shown that even if the quasiconcave objective function is nondifferentiable it can be transformed to a concave function, but that concave function is not necessarily differentiable, although it often can be made so. On the other hand, even nondifferentiable concave functions are always Lipschitz-continuous. This means that certain numerical optimization techniques are available which could not be used with the original, non-concave, objective function (``convex minimization'' techniques--- see Wikipedia [2011] and Boyd \& Vandenberghe [2004]). Note, too, that the $f_\epsilon$ approximation that makes weakly quasiconcave functions strict can be chosen to not alter the size or place of the maximum and hence would be a suitable first step for numerical optimization. Whether the combination of monotonic and approximation transformations with convex minimization techniques would be useful in practical applications we do not know. However, we also have provided (in Theorem 4) an explicit function that concavifies, to a twice-differentiable $g(f(\cdot))$, any twice-differentiable strictly quasiconcave function $f$ on bounded domains in $\R^n$ whose gradient does not vanish apart from the maximum. %--------------------------------------------------------------- \bigskip \section*{References} %\bibliographystyle{myalpha} %\bibliography{allbib} Afriat, S. N. (1967) ``The Construction of Utility Functions from Expenditure Data,'' {\it International Economic Review}, 8: 67--77. Arrow, Kenneth J. \& Alain C. Enthoven (1961) ``Quasiconcave Programming,'' {\it Econometrica}, 29: 779--800. Aubin, Thierry (1982) {\it Nonlinear Analysis on Manifolds. Monge-Ampre equations}. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 252, Berlin, New York: Springer-Verlag (1982). Aumann, Robert (1975) ``Values of Markets with a Continuum of Traders,'' {\it Econometrica}, 43: 611--646. Boyd, Stephen \& Lieven Vandenberghe (2004) {\it Convex Optimization}. Cambridge University Press, free access at \url{http://www.stanford.edu/~boyd/cvxbook/}. Chavel, Isaac (1993) {\it Riemannian Geometry--- A Modern Introduction}, Cambridge Tracts in Mathematics, vol. 108, Cambridge University Press, Cambridge (1993). DeFinetti, B. (1949) ``Sulle Stratificazioni Convesse," {\it Annali di Matematica}, 30: 173--183. Fenchel, W. (1953) ``Convex Cones, Sets, and Functions,'' mimeo book, Princeton Mathematics Department, Princeton, New Jersey. Posted on the web with free access by Abros Press, \url{http://rasmusen.org/x/abros/fenchel.pdf}. Folland, G. B. (1984) {\it Real Analysis. Modern Techniques and Their Applications}, Pure and Applied Mathematics Series, New York: John Wiley \& Sons Inc. Ginsberg, W. (1973) ``Concavity and Quasiconcavity in Economics,'' {\it Journal of Economic Theory}, 6: 596--605. Green, Jerry R., Andreu Mas-Colell \& Michael D. Whinston (1995) {\it Microeconomic Theory}, Oxford University Press (1995). Guerraggio, Angelo \& Elena Molho (2004) ``The Origins of Quasiconcavity: A Development between Mathematics and Economics,'' {\it Historia Mathematica}, 31: 62--75. Hjertstrand, Per (2011) ``A Generalized Afriat's Theorem,'' working paper, Department of Economics, Lund University, (February 2011). Kannai, Yakar (1977) ``Concavifiability and Constructions of Concave Utility Functions,'' {\it Journal of Mathematical Economics}, 4: l--56. Kannai, Yakar (1981) ``Concave Utility Functions--- Existence, Construction, and Cardinality,'' pp. 543-612 of {\it Generalized Concavity in Optimization and Economics,} ed. by Siegried Schaible and William T. Ziemba, New York: Academic Press, 1981. Kannai, Yakar (2005) ``Remarks Concerning Concave Utility Functions on Finite Sets,'' {\it Journal of Economic Theory} 26: 333--344. Kreps, David (1990) {\it A Course in Microeconomic Theory}, Princeton: Princeton University Press (1990). Matzkin, Rosa L. \& Marcel K. Richter (1991) ``Testing Strictly Concave Rationality,'' {\it Journal of Economic Theory}, 53: 287--303. Osborne, Martin (undated, untitled) U. of Toronto Economics Department notes, \url{http://www.economics.utoronto.ca/osborne/MathTutorial/QCC.HTM}. Papadopoulos, Athanase (2005) {\it Metric Spaces, Convexity and Nonpositive Curvature}, IRMA Lectures in Mathematics and Theoretical Physics, vol.~6, European Mathematical Society (EMS), Z\"urich (2005). Pogany, Peter (1999) ``An Overview of Quasiconcavity and Its Applications in Economics,'' Office of Economics working paper, U.S. International Trade Commission, \url{http://www.usitc.gov/publications/docs/pubs/research_working_papers/ec9904a.pdf}, (April 1999). Rapcsak, T. (2005) ``Survey of the Fenchel Problem of Level Sets,'' in {\it Variational Analysis and Applications,} F. Giannessi and A. Maugeri (eds), pp. 935--956, Dordrecht, Holland: Kluwer Academic Publishers (2005). Reny, Philip J. (2010) ``A Simple Proof of the Nonconcavifiability of Functions with Linear Not-All-Parallel Contour Sets,'' working paper, Department of Economics, University of Chicago (October 2010). Richter, Marcel K. \& K.-C. Kam-Chau Wong (2004) ``Concave Utility on Finite Sets,'' {\it Journal of Economic Theory,} 115: 341--357. Takayama, Akira (1985) {\it Mathematical Economics}, 2nd edition (1st edition 1974), Cambridge: Cambridge University Press (1985). Varian, Hal R. (1982) ``The Nonparametric Approach to Demand Analysis,''{\it Econometrica}, 50: 945--973. Wikipedia (2011) ``Convex Optimization,'' \url{http://en.wikipedia.org/wiki/Convex_optimization} or \url{http://rasmusen.org/papers/quasi/Convex_optimization.pdf} (May 24, 2011). Wikipedia (2011) ``Sobolev Inequality,'' \url{http://en.wikipedia.org/wiki/Sobolev_inequality.htm} or \url{http://rasmusen.org/papers/quasi/Sobolev_inequality.htm} (June 18, 2009). Wilson, Charles (2009) ``Convex Sets, Concave and Quasiconcave Functions,'' New York University notes, \url{http://homepages.nyu.edu/~caw1/ } (April 1, 2009). Ziemer, William (1989) {\it Weakly Differentiable Functions}. Graduate Texts in Mathematics, New York: Springer-Verlag (1989). \end{document}~~