\documentclass[12pt]{article}
 \input{quasi-preamble.tex}
%that file has the preamble in it.


\begin{document}
\titlepage
\begin{center}

{\large {\bf   Concavifying the  QuasiConcave } }  (Published in  a much shorter form that has mistakes fixed but is much harder to understand in  {\it The  Journal of Convex Analysis}, 24(4): 1239-62 (December 2017).)

August 14,  2014   
\bigskip

Christopher  Connell  and  Eric  B.  Rasmusen

{\it Abstract}
\end{center}

\begin{small}
We revisit a classic question of Fenchel from 1953: Which quasiconcave functions can be concavified by a monotonic transformation? While many authors have given partial answers  under various assumptions, we offer a complete characterization for all quasiconcave functions without a priori assumptions on regularity.   In particular, we show that if and only if  a real-valued function $f$ is strictly quasiconcave, (except possibly for a flat  interval at its maximum) and furthermore belongs to a certain explicitly determined regularity class,  there exists  a strictly  monotonically increasing function $g$ such that $g\smallcircle f$ is  strictly concave. Our primary new contribution is determining this precise minimum regularity class.

We prove this sharp characterization of quasiconcavity for continuous but possibly nondifferentiable  functions whose domain is any Euclidean space or even any arbitrary geodesic metric space. Under the assumption of twice differentiability, we also establish simpler sufficient conditions for concavifiability on arbitrary Riemannian manifolds, which essentially generalizes those given by Kannai in 1977 for the Euclidean case. Lastly we present the approximation result that if a function $f$ is either weakly or strongly quasiconcave then there exists an arbitrarily close strictly concavifiable approximation $h$ to $f$.

\noindent
Christopher  Connell:   Indiana University,  Department of
Mathematics, Rawles Hall,
RH 351,   Bloomington,
Indiana, 47405.     (812) 855-1883. Fax:(812) 855-0046.
\href{mailto:connell@indiana.edu}{connell@indiana.edu}.

\noindent
Eric Rasmusen, Department of Business Economics and Public Policy, Kelley
School of Business, Indiana University. BU 438, 1309 E. 10th Street,
Bloomington, Indiana,
47405-1701. (812) 855-9219. Fax: 812-855-3354.
\href{mailto:erasmuse@indiana.edu}{erasmuse@indiana.edu},
\url{http://rasmusen.org}.

  \noindent
   This paper:
\url{http://rasmusen.org/papers/connell-rasmusen.quasiconcavity.pdf}.\\
 Mathematica and diagram files: \url{http://rasmusen.org/papers/quasi}.

 \noindent
  Keywords: quasiconcavity, quasiconvexity, concavity,
convexity, unique maximum, maximization. JEL Code: C61. 

  We would like to thank  Per Hjertstrand and  participants in the BEPP Brown Bag Lunch
for
comments, and Dan Zhao for research assistance.

\end{small}
%----------------------------------------------------------
\newpage

\section{Introduction}


Quasiconcavity is a property of functions  which,  if strict, guarantees
that a function defined on  a compact set  has a single, global, maximum
and,  if weak,  a convex
set of maxima.  Most economic models involve maximization of a utility,
profit, or social welfare function, and so assumptions which guarantee
strict quasiconcavity
are standard for tractability. Concavity is  easier to understand than
quasiconcavity, and concave functions on compact sets also have a single,
global maximum, but
concavity is a much stronger assumption.

In the rush of first-semester graduate economics, every  economist encounters   concavity
and quasiconcavity  and learns that they both   have something to do with maximization.
Why quasiconcavity has the word ``concavity'' in its name, however,  is left unclear.  He
learns that the concepts are nested--- that all concave functions are quasiconcave--- but
quasiconcave functions can look very different from concave functions. Figure \ref{quasi1} depicts functions that are strictly convex,
strictly concave, and neither convex nor concave.  The  third function has no trace of
the diminishing returns or negative second derivatives that we associate with concavity.
But all three curves have a single maximum and are quasiconcave.

\bigskip

 \begin{figure}[ht!]
 \centering
 \includegraphics[width=5in]{quasifig01-3qc-functions}
\caption{\sc   Three Strictly Quasiconcave Functions} \label{quasi1}
 \end{figure}

 [CHECK FIgure 1: I see some garbage to the left of the first diagram, and it looks too small.]


\bigskip
The purpose of this paper is to analyze a natural way to link concavity to
quasiconcavity: by means of a monotonically increasing transformation. We
will show that to say a sufficiently regular function is strictly quasiconcave is close
to
saying  it can be made concave by a strictly increasing transformation.
Almost any sufficiently regular quasiconcave function can  be concavified this way. Any
function not quasiconcave
cannot be.

The ``almost'' part of the conclusion must be qualified,  but it  can also
be extended. The two qualifications are that after concavifying one
monotonic portion, which
can always be done even if the function is not  differentiable, (i) its rate
of change must not be ``too near'' zero or infinity, and (ii)  it cannot
have  ``too many" changes
of its rate of change. (Both of these conditions will be made
precise below.) An extension is that certain  quasiconcave functions that
are not only
nondifferentiable but discontinuous   can also be characterized this way,
including all monotonic discontinuous functions.

Weakly quasiconcave functions which are not strictly quasiconcave away from the peak
 are never concavifiable. Nevertheless, weakly
and strictly quasiconcave functions, even when not concavifiable, lie arbitrarily close
to concavifiable functions. We show that the concavifiable functions are uniformly
dense in the space of weakly quasiconcave functions.

    Our topic goes back to the origins of the study of quasiconcavity, in
DeFinetti (1949)   and  Fenchel (1953)  (who invented the name, as Guerraggio \&  Molho
(2004) explain in their history).  The approach in our  paper is most related to the
economics literature exploring what sort of preferences can be represented by concave
utility functions.  Both DeFinetti (in
his ``second problem") and Fenchel investigated whether any quasiconcave function could
be transformed into a concave function, which with related problems is surveyed in
Rapcsak  (2005) (see also Section 9 of  Aumann (1975)).  Kannai (1977, and 1981 more elaborately) treats the question in depth
in the context of utility
functions, giving  conditions under which continuous convex preferences
can be represented by concave utility functions.  We will discuss Kannai's
conditions in greater detail in connection with Theorem \ref{thm:manifold}  below.  Richter
\& Wong (2004) and Kannai (2005)s similarly address  preferences over discrete sets.

   The previous  literature  has asked when preference orderings
that can be represented by differentiable functions  can be represented by concave
functions.    We answer the complete problem of when quasiconcave functions can be concavified, whether they be utility, profit, social welfare, payoff, or inverse loss functions.  We 
generalize from the previously analyzed differentiable  functions in Euclidean space to strictly quasiconcave continuous functions on any non-flat manifold, which require  a different approach. We also analyze the undiscussed cases of what may be done with 
weakly quasiconcave  and discontinuous functions.   In this way we
hope to have shed new light on a classic problem in the fundamentals of optimization and to better understand the key concept of what kinds of  functions have a single local maximum.  We hope that this may eventually help by extending the use of convex optimization numerical techniques, though we do not explore them in the present paper. 


We   start the analysis with the easy case of a quasiconcave function defined over a
finite domain of points. Next, we   build up from strictly increasing differentiable
functions $f\suchthat  \R^1 \rightarrow \R$,   to nonmonotonic differentiable functions,
and then to nonmonotonic nondifferentiable  continuous functions. The
interesting necessary and sufficient conditions   arise in the last
two cases. We attain our greatest generality  with functions on geodesic metric spaces
in
general, of which nondifferentiable functions $f\suchthat
\R^n\rightarrow\R$ are a special case. We then backtrack to look at the
interesting special case of twice-differentiable functions on manifolds, where sufficient
conditions for
concavifiability of a much simpler nature can be found.
These latter conditions are closely related to those found in Kannai (1977), although very different in appearance and  under
slightly different assumptions.


Finally, we examine two classes of functions $f$  to which our results do
not apply without significant limitations: discontinuous functions   and
weakly quasiconcave
functions.  Our conclusion that a quasiconcave function is one that can be
concavified does not apply to those two classes of functions generally. It 
  does apply  to a limited class of discontinuous functions, and  a weakly quasiconcave
function  can always be approximated by a concavifiable one.
We completely classify when discontinuous or weakly quasiconcave functions are
concavifiable.

%-------------------------------------------------

\section{Formalization}


Textbook expositions of quasiconcavity can  be found in Kreps (1990 p. 67),
Takayama (1985, p. 113), and Green, Mas-Colell and Whinston (1995, pp. 49,
943). Arrow \& Enthoven (1961) is the classic article applying it to
maximization
Osborne (undated), Pogany (1999), and Wilson (2009)  have useful notes on
the Web. Definition 1 is  one of
  several
  equivalent ways to  define the term (Ginsberg (1973)  and Pogany (1999)
discuss  variant    definitions).

\fboxsep=12pt\begin{boxedminipage}[c]{.9 \linewidth}
\begin{definition}\label{def:qc}
(QUASICONCAVITY)   A  function $f$ defined on a subset $D\subset\R^n$ is {\em weakly
quasiconcave} iff for any two distinct points
 $ x',x''\in D$ and any number $t \in (0,1)$ with $t x'+ (1-t)x''\in D$, we have
 \begin{equation}  \label{e3}
 f(t x'+ (1-t)x'')  \geq  \min\set{f(x'), f(x'')}.
\end{equation}
 Iff the inequality is strict whenever $x'\neq x''$, we say that $f$ is
{\em strictly quasiconcave}.
\end{definition}
\end{boxedminipage}\fboxsep= 3pt


This definition  does not  require $f$ to be differentiable, or even continuous. Often we
assume that the domain $D$
is convex, but we will use this generality for investigating finite domains as well.

An equivalent definition  for weak quasiconcavity   which we will exploit later on says
that $f$ is weakly
quasiconcave if and only if  its super-level sets  are
weakly convex; that is, the sets $S_c\equiv \set{x\in D\,:\, f(x)\geq c}$ are weakly
convex for each $c$ in the range
of $f$  as shown in  Figure \ref{quasi1}. For strict
quasiconcavity, one requires strictly convex super-level sets together with the absence
of horizontal line segments
in
the graph. (Figure \ref{quasifig12-weak}, late in the paper, depicts  a weakly but not strictly
quasiconcave
function.)

 It is frequently plausible in economic applications that a function $f(x)$  being
maximized is quasiconcave, which is convenient because quasiconcavity
guarantees    a unique supremum of $f(x)$ (which we will denote  by
\fbox{$f^*$}).\footnote{We will box definitions and examples where we think this useful for readers
flipping back to find
them.}  Strict quasiconcavity further guarantees   a unique maximum on a closed set,
\fbox{$m$}, where $m \suchthat f^* \equiv f(m)$.  (If  the quasiconcavity is only weak,
there might be several $x$'s such that $f^*=f(x)$, though the set of optimal $x$'s will
at least be convex.)

If $-f$ is strictly  quasiconcave  then $f$ is    {\em strictly  quasiconvex}. If $-f$ is
weakly quasiconcave  then $f$ is    {\em weakly  quasiconvex}.


\fboxsep=12pt\begin{boxedminipage}[c]{.9 \linewidth}
\begin{definition}\label{def:con}
 (CONCAVITY)  A  function $f$ defined on a subset $D\subset \R^n$ is {\em concave} iff
for any two points $ x',x''\in
D$ and any number $t \in (0,1)$ with $t x'+ (1-t)x''\in D$, we have
 \begin{equation} \label{eq:quasi2}
 f(tx'+ (1-t)x'')  \geq  t f(x') + (1-t) f(x'') .
\end{equation}
 Iff  inequality  \eqref{eq:quasi2} is strict, we say that $f$ is strictly
concave; otherwise it is weakly concave or simply ``concave''.
\end{definition}
\end{boxedminipage}\fboxsep= 3pt

Figure \ref{quasi1}(a)  illustrates  this definition, which  says that the secant line
must lie below the function.
Every  concave function is quasiconcave, but not every quasiconcave function is concave.
That is because
$\min(f(x'), f(x'')) \leq t f(x') + (1-t) f(x'')$. Quasiconcavity requires the function
merely not to dip down and
back up between $x'$ and $x''$, but concavity requires  it  to  rise faster than linear
from the lower point to the
upper one.

 \begin{figure}[ !ht]
  \centering
 \includegraphics[width=6in]{quasifig02-concavifying}
\caption{\sc   A Non-Concave Strictly  Quasiconcave Function $f(x)$ that
  Can Be Concavified by a Monotonic  $g(f)$ }
 \label{quasi3}
 \vspace*{24pt}
 \end{figure}


We will be looking at whether  given a quasiconcave $f$ we can always find a strictly
monotonic function $g$ that will transform  $f$ to a strictly concave $g\of f$. Figure
\ref{quasi3} shows an example of a  strictly quasiconcave function $f(x)$ that is not
concave, and a compound function $g(f(x))$ that is both strictly quasiconcave and
strictly
concave.\footnote{For reference,   the following list of weaker (and easier to prove)
relationships between $f$ and $g$ may be useful. (a)  If $f$ is strictly concave and  $g$
is
strictly monotonic, then $g(f(x))$ is not necessarily concave  but it is strictly
quasiconcave. (b) If $f$ is strictly quasiconcave and $g$ is strictly monotonic,
$g(f(x))$ is strictly
quasiconcave.  (c)   If $f$ is strictly quasiconcave and $g$ is weakly monotonic,
$g(f(x))$ is at least weakly    quasiconcave.   (d) If $f$ is weakly  but not strictly
quasiconcave
and $g$ is weakly monotonic, $g(f(x))$ is  at least weakly   quasiconcave. }

In economics, we are interested in concavity and quasiconcavity  because we
usually assume diminishing returns to single activities as a result of
mixtures being better than extremes (e.g., a taste for variety in food) or
some activity levels being fixed (e.g., fixed capital in the short run).
Thus, the set of utilities obtainable from a given budget will be a convex
set, and the utility function will be concave in each good and quasiconcave
over all of them.  Figure \ref{quasi2} is an example in two dimensions  that
shows the  function $f\suchthat \R^2_+ \to  \R$ given by $f(x,y)= 50  \log(x)
\log(y)$, which is  strictly concave on $[e,\infty)^2\subset \R^2_+$ but only
quasiconcave on the larger domain $[1,\infty)^2\subset \R^2_+$ despite the
fact that each slice in any coordinate direction is concave on $[1,\infty]$.
Note also that this function is monotone along all line segments, since the level sets
are themselves line segments,
which can only
intersect any line segment  at one point at most.



 \begin{figure}[ !ht]
  \centering
 \includegraphics[width=4in]{quasifig03-3D-example}
\caption{\sc   A Strictly Quasiconcave  but Not Concave  Function $f(x,y) = 50
\log(x) \log(y)$  Which Is Concave Only for $x$ and $y$ Greater than $e$. }
 \label{quasi2}
 \end{figure}


Most of the difficulties in concavifying quasiconcave functions arise even when the
function's domain is
one-dimensional Euclidean space,  so $\R^1$ will be the focus of the
first half of this article. Even $\R^2$ is much harder to visualize, as may be seen from
  Figure
\ref{quasifig-aumann.jpg}’s example:

\fboxsep=12pt
 \begin{boxedminipage}[c]{.9 \linewidth}
 \begin{small}\label{ex:Aumann}
 {\bf   Figure \ref{quasifig-aumann.jpg}'s example: 
 Fenchel's example.}   Figure \ref{quasifig-aumann.jpg}'s  function $f(x, y)   = y
+\sqrt{x + y^2}$  cannot be concavified. This was first proposed by Fenchel (1953) and
features in Aumann (1975) and Reny (2010).  The function is strictly increasing in both
$x$ and $y$,  and  strictly concave in each variable individually. It is only weakly
quasiconcave, however, because its level sets are straight lines, as shown in the
right-hand side of Figure \ref{quasifig-aumann.jpg}. As a result, $f$ is not
concavifiable, and,
more surprisingly, is not even weakly concavifiable. (continued on the next page)
\end{small}
\end{boxedminipage}
\fboxsep= 3pt


\begin{figure}[ht]
 \centering
 \includegraphics[width=5in]{quasifig04-aumann.jpg}
\caption{\sc   Fenchel's Example:  Nonconcavifiable with Linear Level Sets }
 \label{quasifig-aumann.jpg}
 \end{figure}



\fboxsep=12pt
 \begin{boxedminipage}[c]{.9 \linewidth}
\begin{small}
(Fenchel's Example, continued) Regardless of any postcomposition by a strictly increasing
function $g$, the rate of increase of the function $g\of f$ from point $a$ to $b$ is
greater than   that of the same length segment from $d$ to $e$. More precisely, the
gradient at $a$ is larger than the gradient at $c$. Hence, if we choose the point $b$
sufficiently close to $a$, the level sets with values slightly larger than $g(f(a))$ but
less than $g(f(b))$, must lie under the segment connecting $(c,g(f(c)))$ to $(b,g(f(b))$
near
the point $(c,g(f(c))$. Hence part of the graph of $g\of f$ lies over the line segment
from $(c,g(f(c)))$ to $(b,g(f(b))$. Hence, $g\of f$ could not have been
concave. \\
\hspace*{18pt}A word of caution regarding this intuitive proof: it depends crucially on
the fact that the level sets
are only weakly convex.  If they were strictly convex, even ever so slightly,
then the function $f$ would be concavifiable (see Theorem \ref{thm:manifold}).  In that
case, $g$ could be chosen in
such a way that the gradient would
change rapidly so that that the point $b$ must be chosen very close to $a$ in order for
the linear gradient
approximation to remain valid. However, then the line segment
from $c$ to $b$ would lie mostly to the left of the bent level set on which $a$ and $c$
lie, and thus it would not
cross, near $c$, the other level sets in the domain with values
greater than $g(f(c))$.
\end{small}
\end{boxedminipage}
\fboxsep= 3pt





%--------------------------------------------------------------------

\section{Objective Functions  Defined over a  Finite Number of
Points}

Let us start with the easiest case, where the function $f(x)$ is defined on a set
consisting of a  finite number of
points.   Afriat's  Theorem  says that for any finite set of
consumption data points satisfying the Generalized Axiom of Revealed Preference (GARP),
there exists a continuous,
concave, strictly monotone   utility function that
would generate that data (Afriat [1967]).     Another way to view Afriat's Theorem is
that if a consumer is solving a
maximization problem with a unique solution then he
must be maximizing a   quasiconcave function, and the theorem says that if we also
assume the function is
strictly increasing  then that function can be chosen to
be concave.

  The literature following Afriat's Theorem has generalized it to infinite
sets of consumption data and in other ways (see  Varian (1982), Matzkin \&   Richter
(1991), and Hjertstrand  (2011)). Richter and Wong (2004) give three conditions, they call (C),(G), and (G') on a preference ordering over a finite set of consumption bundles. They show that condition (G) is equivalent to being describable by a weakly concave utility function, and (G') is equivalent to being describable by a strictly concave utility function. In fact, condition (G') is equivalent to strict quasiconcavity and condition (C) to weak quasiconcavity, while condition (G) lies between the two. We will present below a significantly shorter proof of their Theorem 2 in the context of functions rather than preference orderings. 

Note that in this context the notions of differentiability and continuity are vacuous. Quite different problems arise when the space of points is uncountably infinite ( e.g.,  an interval), as we shall see shortly.

\fboxsep=12pt\begin{boxedminipage}[c]{.9 \linewidth}
\begin{Theorem}[Richter and Wong (2004), Theorem 2]\label{thm:finite} Let $f(\cdot)$ be defined on a finite set
of points in $\R^n$. If and only if  $f(x)$ is strictly quasiconcave  there exists  a
strictly increasing function
$g(z)$ such that $g(f(x))$ is  a strictly concave function of
$x$.
\end{Theorem}
\end{boxedminipage}\fboxsep= 3pt



\begin{proof}
{\bf Part 1.} We will start by showing that if $f(x) $ is strictly
quasiconcave we can find a strictly increasing function $g(z)$ such that
$g(f(x))$ is  strictly  concave.

Define $S_1$ to be the set of $x$'s that yield the highest value of $f(x)$,
$S_2$ to be the set of that yields the second-highest value,  $S_3$ to yield
the third highest, and so forth,  so  $S_1 \equiv  \argmax f(x)$ and
$\ds{S_i \equiv  \argmax_{x \not\in \; S_1\cup \cdots \cup S_{i-1}} f(x)}$.


In general, the $S_i$ sets may contain many points, though under our assumption that $f$
is strictly quasiconcave, the convex hull $W_i$ of the super-level sets $\cup_{j\leq
i}S_i$ will always be a weakly convex polytope in the domain such that $W_{i}\subset
W_{i+1}$ for all $i$. We really only need to separate these convex polytopes in height in
a convex way, but it will be simpler in practice to construct an "overkill" g which
convexifies $f$ using pointwise conditions.

To construct our concavified function, we set $g(f(S_1))=0$ and choose appropriate
numbers $\epsilon_i$ inductively such that $g(f(S_{i+1})) \equiv g(f(S_i)) - \epsilon_i $
as follows. Choosing $\epsilon_1=1$, we assume $\epsilon_2,\dot,\epsilon_{i-1}$ have been
chosen by inductive hypothesis. We need to make $g$ have as large a rate of increase as
necessary from points in $S_{i+1}$ to $S_i$ to ensure that the rate of increase is always
diminishing and $g$ is strictly concave. choose the $\epsilon_i$ so that for any $i\geq
2$, and for any $x_{i-1}\in S_{i-1}, x_i\in S_i$ and $x_{i+1}\in S_{i+1}$, we always
have,
\begin{equation} \label{e444}
\frac{g(f(x_{i-1})) - g(f(x_{i })) }{\norm{ x_{i-1} - x_i }} <
\frac{g(f(x_{i})) - g(f(x_{i +1})) }{\norm{ x_{i } - x_{i +1}}}.
\end{equation}
Since $g(f(x_{i-1})) - g(f(x_{i }))=\epsilon_{i-1}$ we can simplify this to choosing
$\epsilon_i$ so that
\begin{equation} \label{e444a}
\epsilon_i > \epsilon_{i-1}\frac{\min_{\substack{x_{i-1}\in S_{i-1} \\ x_i\in S_i}} \norm{x_{i-1} -
x_i} }
{\min_{\substack{x_{i+1}\in S_{i+1} \\ x_i\in S_i}} \norm{ x_{i } - x_{i +1}}}.
\end{equation}

From the definition of concavity on arbitrary domains it follows that the choice of
$\epsilon_i$ in \eqref{e444a} guarantees concavity of $g\of f$.

\bigskip

\noindent
{\bf Part 2. }We now must show that if $f(x)$  is not  strictly quasiconcave
we cannot  find a strictly increasing function $g(z)$ such that $g(f(x))$ is
strictly  concave.

If $f(x)$ is not strictly quasiconcave, then  there exist
points $w,y,z$ such that
  $w<y<z$ and one  of the following three conditions holds:
\vspace{-12pt}
\begin{enumerate}[(i)]
\item $f(y)  < Min (f(w), f(z))$ (if $f(x) $ is not even weakly quasiconcave)

\item $f(y)  = Min (f(w), f(z))$  and $f(w) \neq f(z)$

\item $f(y)  =  f(w)=f(z)$.
\end{enumerate}

In any of these cases,  for any strictly monotonic function $g$,  $ g(f(y))$
will be below a straight line connecting $g(w)$ and $g(z)$ and hence by
Definition 2 is not concave,  because:
\begin{equation} \label{e444b}
g(f(y))  \leq  \left| \frac{w-y}{w-z} \right| g(f(w)) + \left| \frac{
y-z}{w-z} \right| g(f(z))
\end{equation}

In case (i), this is because $g(f(y))$ is less than either  $ g(f(w)) $   or
$ g(f(z)) $, so the inequality in  inequality  \eqref{e444b}  is strict.  In
case  (ii), $g(f(y))$ is equal to one
of the other two $g$'s and less than the other, so \eqref{e444b} is  also
strict. In case (iii), $g(f(y))$ is equal to both the other two $g$'s, so
the inequality becomes an
equality. This completes part 2 of the proof.
\end{proof}

\bigskip

\begin{remark}%REMARK 1
Theorem \ref{thm:finite} applies equally well to functions defined on finite subsets of arbitrary
geodesic metric spaces,  if one
  first   generalizes  our earlier
definitions  of quasiconcavity and concavity to the  natural analogues of the
definitions expanded to entire
geodesic
metric spaces later in this article.
 The same proof   would   apply with the obvious modifications.
\end{remark}

\bigskip

\begin{remark} %REMARK 2
If  $f$ is only  weakly quasiconcave, and so is  flat for some values of $x$,  then if
the maximum is
unique
(that is, if  $\argmax \; f(x)$ is unique) we can find
$w, y, z$ so that case (ii) applies and inequality \eqref{e444b} is strict, so that $g$
is not even weakly
concave.   We will return to this idea of weak  quasiconcavity not being
definable using weak concavity towards the end of
the paper.
\end{remark}

\bigskip
\begin{remark}\label{rem:finite}%REMARK 3
If we replace a finite number of points by a countable set of points then   Theorem 1
fails. To see this,   choose a dense countable set of points, such as the
rationals,
and  apply this to one of our strictly quasiconcave counterexamples (e.g. Example
\ref{ex:X} or \ref{ex:XX}). The transforming function $g$ would necessarily extend
continuously to all of $\R$,  providing a contradiction. On the other hand, the proof
above also works for domains consisting of an infinite countable set of points which is
discrete (so each point is at least a fixed   distance $\epsilon$ from each other point, e.g. the
integers)  save perhaps  for a unique limit point occurring at the unique argmax of the
function $f$.
\end{remark}

\begin{remark}
   Theorem 1 of Richter \& Wong (2004)  shows when a concave utility function can represent a
preference ordering over a finite set of goods
(their condition G or E). Kannai (2005) provides an alternative approach to the same
problem.  Our problem is different because we start with a strictly quasiconcave function rather
than with preferences.  Thus, we give a simpler answer to a simpler problem,    using a  particular
monotonic postcomposition of the range to
 concavify  a given strictly quasiconcave function.

\end{remark}

%------------------------------------------------------------

\section{Continuous Objective Functions on $\R^1$}

Now let the function's domain be a real continuum. Consider a function $f  \suchthat
I\toarrow    \R^1$  defined on an interval $I\subset \R^1$ which is either  open (in
which case it might be unbounded), half open, or closed. For the rest of the paper we
will define \fbox{ $a\equiv \inf(I)$} and \fbox{ $b \equiv \sup(I)$}.  Recall that
\fbox{$f^* \equiv  \sup(f)$.}

The following lemma will allow us to  essentially  restrict our attention to the case
when the postcomposing function $g$ is strictly increasing.

\bigskip
\newpage
\begin{lemma}\label{lem:g}
  Given continuous functions $f\suchthat D\to \R$ with $D\subset \R^1$ connected and $g
\suchthat\op{Range(f)}\to \R$,
for $g\of f$ to be strictly
quasiconcave it is necessary that $f$ and $g$ fall into precisely one of these four
cases:
  \vspace{-16pt}
\begin{enumerate}[(i)]
  \item $f$ is strictly increasing and $g$ is strictly quasiconcave,
  \item $-f$ is strictly increasing and $-g$ is strictly quasiconcave,
  \item $f$ is strictly quasiconcave but not monotone and $g$ is strictly increasing,
or
  \item $-f$ is strictly quasiconcave but not monotone and $-g$ is strictly
increasing.
\end{enumerate}

\end{lemma}


\begin{proof}
The cardinality $\op{card}( (g\of f)^{-1}(t))$ of the level set of  value $t$ for $g\of
f$ is \\
 $\sum_{s\in g^{-1}(t)}
\op{card}(f^{-1}(s))$. In particular, postcomposition
by a function never  reduces a level set's  cardinality. The maximum cardinality of a
level set of the quasiconcave
function $g\of f$ is two. Hence on values where
the level sets of $f$ have cardinality two, $g$ must be one-to-one, and $g$ can only be
two-to-one on values where $f$
has cardinality one. Such continuous functions
are fairly simple to analyze.

If all the level sets of $f$ have cardinality one everywhere then $f$ is monotone by
continuity and we are in  case (i) or (ii). Then $g$ or $-g$ must be quasiconcave since
the
composition of the strictly increasing function $f^{-1}$ (or $(-f)^{-1}$) with the
quasiconcave function $g\of f$ is again quasiconcave.

If the cardinality of $f$'s level sets  is two on a subset $L\subset \op{Range}(f)$, then
consider any $p\in L$. Let $\set{x,y}=f^{-1}(p)$, with $x<y$, and let $\set{U_i}$ be any
sequence of connected open intervals centered at $p$ and strictly decreasing to $p$. By
continuity of $f$, the preimages of each $U_i$ under $f$  are open and contain  both
$x$ and $y$. Since each point has at most two preimages, for some sufficiently large $i$,
the open subintervals $A$ containing $x$ and $B$ containing $y$ in $f^{-1}(U_i)$
must be distinct, and hence disjoint. If $C=f(A)\cap f(B)$, then $f$ must be monotone on
$f^{-1}(C)\cap A$ and $f^{-1}(C)\cap B$. Now $C$, being connected, either has
interior, or else is just $p$. If it is just $p$, some points are  to the right of $x$
and have values less than $p$ and some points are to the left of $y$  and  have values
greater
than $p$. Hence, the intermediate value theorem guarantees, since $D$ is connected,
another point $z\in (x,y)\subset D$ for which $f(z)=f(x)=f(y)=p$, which violates the
cardinality restriction on the level sets. Therefore, we conclude that each point $p\in
L$ contains an interval about it, a priori not necessarily in $L$, on which $f$ is
monotone. Since $f$ is one-to-one off of $L$, $f$ is locally monotone everywhere except
for local extrema. The cardinality rule then implies that $f$ has at most two extrema
and is monotone on each connected segment after removing these points.

Now $g$ preserves the local extreme points of $f$. So if $f$ has more than one local
extreme point, then the values must coincide under $g$, but then there are at least four
preimages of some value near this extreme value for $g\of f$, violating strict
quasiconvexity. So $f$ can have at most one local extremum. It has exactly one because
$f$ is not
monotone and $D$ is connected. In particular, $L$ is connected.

\begin{comment}
%each subinterval. then note that $L$ necessarily excludes any local extrema of $f$, but contains
all of them in its closure. If $L$ is not closed in $\op{Range}(f)$ then
%take a point $p\in
%\overline{L}\backslash L \cap
%\op{Range}(f)$. The unique preimage point $x=f^{-1}(p)$ is a
%we will show that $L$ must be an interval. Note that $L$ necessarily excludes the local extrema of
$f$, but contains all of them in its closure. Since $g$ is necessarily
%one-to-one on $L$, $L$ is connected if and only if $g(L)$ is. However, if $g(L)$ is not connected
then the graph of $g\of f$ must have changed directions at a minimum
%of two points, since $f$ already has one local extrema and hence has more than one local extrema,
violating quasiconvexity. (To see this connect one point close before
%the first extremum to a point close after the second.)
%one of which is the unique point $m$ where the maximum of $g\of f$ occurs, and the other point we
will call $x$. A superlevel set of $g\of f$ at a slightly higher value than
%$g\of f(x)$ must then be disconnected, and hence not convex, violating quasiconcavity.
\end{comment}

Since $L$ is connected,  $g$ is one-to-one on the closure of  $L$, not just on $L$. This
contains all of the local extrema of $f$. Now assume $g$ is strictly increasing on this
closure. If the graph of $g$ changes direction elsewhere, then $g\of f$ has at least two
local extrema, violating quasiconcavity. Hence, $g$ is strictly increasing everywhere.
This then implies that $f$ was strictly quasiconcave since postcomposition by a strictly
increasing function $g^{-1}$ preserves quasiconcavity.

If $g$ was strictly decreasing on the closure of $L$ then similarly it is strictly
decreasing everywhere and $-f$ is strictly quasiconcave.
\end{proof}

\bigskip

\begin{remark}
 Lemma 1 fails for discontinuous $f$ and $g$ or for disconnected $D$. For instance, $f$
can be pathologically
discontinuous and not monotone, and yet
one-to-one  so $g=f^{-1}$ exists and is one-to-one with  the identity function as $g\of
f$.
\end{remark}

\bigskip

\begin{remark}
Surprisingly,  the analogous lemma for weakly quasiconcave compositions is false. If we
replace ``strictly'' everywhere by ``weakly'', however,  and ``strictly increasing'' by
``nondecreasing'',  then the conclusion remains true provided we conclude that $f$ or
$-f$ is weakly quasiconcave only after collapsing regions in the range where $g$ is
constant.
\end{remark}

%----------------------------------------------------------

\subsection{The Case Where the Objective Function on $\R^1$ Is Continuous and
Strictly Monotone}
\bigskip

If the continuous function $f$ is strictly increasing or decreasing, then  $f  \suchthat I\to \R^1$
is invertible. Hence,  we can easily solve the problem of concavifying $f$ by
choosing $g=h\of f^{-1}$ where $h$ is a concave function  and hence $g(f(x))=h(x)$ is
concave.\footnote{This can even be done in the case that $f$ is discontinuous and
strictly increasing or decreasing,  by first repairing the range (see Section \ref{subsec:discont}).
However, note that basic obstructions like those in Example \ref{ex:Aumann}
arise in two or more dimensions regardless of continuity.}

Here, however, we will treat the twice-differentiable case more intrinsically and connect the
definition of concavity more viscerally with the properties of $f$. This will  build a
foundation for the next section, where we treat the noninvertible case.

Thus, let us move to  the special case where  $f$ is twice differentiable and strictly
increasing. We will also for now assume $g$ is twice differentiable and strictly
increasing.
Recall that we are searching for a strictly concave function $g\of f$. The twice
differentiable function $g\of f$ is strictly concave if   the expression
\begin{equation} \label{e100}
 (g \of  f)''(x)=g''(f(x)) \cdot f'(x)^2+g'(f(x))\cdot f''(x),
\end{equation}
  is nonpositive and never vanishes on an entire interval.
Equivalently, this occurs if
\begin{equation} \label{e01}
  \frac{g''(f(x))}{g'(f(x))}\leq -\frac{f''(x)}{ f'(x)^2},
\end{equation}
with equality never holding on any interval. (There are examples of strictly convex functions where
equality holds on a full measure set, however.)

Since we assume that $f$ is strictly increasing, it is invertible. Define  \fbox{$z \equiv f(x)$},
so $x=f^{\scriptscriptstyle -1}(z)$. Note that  $ \frac{1}{f'(x)} = \frac{1}
{f'(f^{\scriptscriptstyle -1}(z))} =\frac{\del}{\del  z} f^{\scriptscriptstyle -1}(z),$ so  the
right-hand side of inequality \eqref{e01}  is
\begin{equation} \label{e02}
 -\frac{f''(x)}{f'(x)^2}=\frac{\del}{\del  x}  \left( \frac{1}{f'(x)}
\right)  =  \frac{\del}{\del  x} \left( \frac{\del}{\del  (z=f(x))}
f^{\scriptscriptstyle -1}(f(x)) \right) =    f^{{\scriptscriptstyle -1}
\prime \prime }  (f(x)) \cdot  f'(x)   .
\end{equation}



Taking another step:
\begin{equation} \label{e03}
 -\frac{f''(x)}{f'(x)^2}=    f^{{\scriptscriptstyle -1} \prime \prime }
(f(x)) \cdot  f'(x)  =  \frac{\del}{\del  x}    \log
f^{{\scriptscriptstyle -1}  \prime }    (f(x))   .
\end{equation}

Similarly (though since we are constructing $g$ we need not invert), the
left hand side of  inequality  \eqref{e01}  is $\frac{\del}{\del   f(x)}
\log g^{   \prime }    (f(x) )   .$
Hence a sufficient criterion    for inequality  \eqref{e100}   to be true, so that we do not have to
even worry about it vanishing on an interval, is that
\begin{equation} \label{e04}
\frac{\del}{\del   z}    \log g^{   \prime }    (z )  < \frac{\del}{\del z}
\log  f^{{\scriptscriptstyle -1}  \prime }    (z)
\end{equation}
  for all $z$ in the range of $f$, provided both sides are well
defined.

 If we choose a number $c>0$ and a function $g$ so that
\begin{equation} \label{e05}
g'(z)=e^{-c z} \cdot  f^{{\scriptscriptstyle -1}\prime}  ( z )
\end{equation}
then
\begin{equation} \label{e05a}
\log g'(z)=  -c z + \log f^{{\scriptscriptstyle -1}\prime}   (z)
\end{equation}
 and
\begin{equation} \label{e05b}
\frac{\del}{\del   z}   \log g'(z)=  -c+  \frac{\del}{\del   z}    \log
f^{{\scriptscriptstyle -1}\prime}(z)   < \frac{\del}{\del   z}    \log
f^{{\scriptscriptstyle -1}\prime}(z)
\end{equation}

Integrating  equation \eqref{e05}'s $g'$  will produce the desired
function.

This approach, using Equation \eqref{e05},    has the advantage of relying
only on first derivative data of $f$ in its construction  (although the
properties requisite for its application do rely on the second derivatives
of $f$.) Later we will make use of a second approach.
To construct $g$,  choose any function $u(z)<f'(f^{\scriptscriptstyle -1}(
z) )
\cdot f^{\scriptscriptstyle -1 \prime \prime}(z) $.   Then set
\begin{equation} \label{e06}
g(z)= \int_0^z  \left( e^{\int_{a}^s u(t)dt} \right) ds
\end{equation}
 for any $a\in\R$ chosen at the top of the domain of  $u(z)$. This yields
a function with $g \of  f$ concave on $(a,d]$.

We note that demanding strict equality in quantities such as \eqref{e04} does not lose us any
generality, provided we are willing to be flexible with $g$. Since if $g\of
f$ is strictly convex, by a modification of $g$ as above we can make its second derivative strictly
negative.

\bigskip


%---------------------------------------------------------
\newpage

\subsection{The  Case When the  Objective Function on $\R^1$ Is Nonmonotonic but Twice
Differentiable}\label{sec:nonmonotonic}
\bigskip

Now suppose the function  $f$ is twice differentiable and strictly quasiconcave but not
monotone. In that case it achieves its maximum at a unique internal point $m\in (a,b)$,
so that $f$ is rising on $(a,m]$ and  falling  on $[m,b)$  as in Figure
\ref{quasi-f1f2.jpg}.

  \begin{figure}[ht!]
   \centering
 \includegraphics[width=5in]{fig-f1f2.pdf}
\caption{\sc   The Construction of   $f_1$ and $f_2$   }
 \label{quasi-f1f2.jpg}
 \end{figure}

For now, we will also require that $f$ have a non-vanishing derivative except at an
internal maximum or
endpoints.



Denote by \fbox{$f_1$}$
\suchthat [0,1)
\toarrow
\R$ the strictly increasing function
$$
f_1(x)= f(a(1-x)+x m)
$$
   and by \fbox{$f_2$}$ \suchthat  [0,1) \toarrow   \R$ the strictly increasing function
$$
f_2(x)=f(b (1-x)+x m).
$$



Figure \ref{quasi-f1f2.jpg} illustrates this construction, which splits $f(x)$ into two
strictly increasing functions on $[0,1]$ to save the bother of using negative  signs and
absolute values of slopes in our analysis. (In Figure \ref{quasi-f1f2.jpg} the $f(x)$ is
not twice differentiable; it is drawn with a kink to illustrate the $f_1$, $f_2$
construction  clearly.)

The new functions $f_1$ and $f_2$ are homeomorphisms onto their images, so
they have inverses $f_1^{\scriptscriptstyle -1}$ and
$f_2^{\scriptscriptstyle -1}$. Hence, by
post-composition we can easily  choose a $g$  such that  either $g \of  f_1$
or $g \of  f_2$ is strictly concave and smooth.  The difficulty is  in
making   $g \of  f$   concave on
its entire domain--- that is, to  use the same function to concavify  both
$f_1$ and $f_2$---  especially when $f$ is nondifferentiable or not defined
over a compact set. We will
treat this general problem in the next section.

Before handling the present case, with $f(x)$ being twice differentiable,  we will
present an example demonstrating why we need the condition that the gradient not vanish
except at the maximum. Note first that since the gradient is continuous, the derivative
is bounded away from zero except perhaps at   the optimum and endpoints.

%-------------------------------------------------------------


\fboxsep=12pt
\begin{boxedminipage}[c]{.9 \linewidth}
\begin{small}
{\bf Figure  \ref{quasi3a}‘s example:  A
zero right-derivative.} A nondifferentiable example   is the simplest way to see the
  problem. 
  Consider the strictly quasiconcave function $f(x)$   in Figure
\ref{quasi3a}, which is defined as follows.
  \begin{equation*} \label{e08b}
 f(x) =
 \begin{cases}
 x & {\rm if }\; x \leq 1\\
  1 + (x-1)^2 & {\rm if }\; 1 \leq x \leq 2\\
  4-x & {\rm if }\; x \geq 2\\
 \end{cases}
 \end{equation*}

  The problem in concavifying $f(x)$ comes  with the $x$ values around 1
and 3.  We have $f(1) = f(3)=1$, so necessarily $g(f(1)) = g(f(3))$. But
$f'_+(1) = 0$ and $f'(3)=-1$, which makes it impossible for $g(f(x))$ to
be concave since either  $g\of f'(1)$ remains $0$ or else $g\of f'(3)$
becomes  infinite.
\end{small}
 
\end{boxedminipage}\fboxsep= 3pt


 \begin{figure}[ht]
  \centering
 \includegraphics[width=4in]{quasifig06-frog}
 \caption{\sc    A Nonconcavifiable Strictly Quasiconcave Function with a Zero
Right-Derivative at $x=1$ }
  \label{quasi3a}
 \end{figure}

xxxx[This figure ahs a strange parallel horizontal line at the bottom. It needs bigger fonts too.]


 \begin{figure}[ht]
  \centering
 \includegraphics[width=3in]{quasifig07-right-derivative}
\caption{\sc    A Nonconcavifiable Strictly Quasiconcave Function with a Zero
Derivative at $x=1$ }
 \label{quasi5}
 \end{figure}




The same kind of problem shows up with  differentiable strictly quasiconcave
functions.

\fboxsep=12pt\begin{boxedminipage}[c]{.9 \linewidth}
\begin{small}
{\bf  Figure   \ref{quasi5}‘s example: An   
inflection point.} 
    Consider the strictly quasiconcave function $f(x) =-x^4+6 x^3-12
x^2+10 x$ in Figure \ref{quasi5}.
 The problem in concavifying $f(x)$ comes  with the $x$ values around 1 and
$3$.  We have $f(1) = f(3)=3$, so necessarily $g(f(1)) = g(f(3))$. But
$f'(1) = 0$ and $f'(3)=-8$,
 which makes it impossible for $g(f(x))$ to be concave since either $(g\of
f)'(1)=0$ or else $(g\of f)'(3)=-\infty$. Thus, the $(g\of f)$ shown in
Figure \ref{quasi5} is not concave.
 \end{small}
\end{boxedminipage}\fboxsep= 3pt

\pagebreak


Since $f$ is twice differentiable with first derivative bounded away from $0$, and  $I$
is compact, the problem becomes easy in light of what we discovered in the previous
section. Simply set

\begin{equation} \label{e06c}
\hspace{-2.0in}\text{(Concavifying function)}\quad g'(z)=e^{\int_0^z u(t)dt}
\cdot  f_1^{{\scriptscriptstyle -1}  \prime } (z) \cdot
f_2^{{\scriptscriptstyle -1}  \prime }(z)
\end{equation}
  for any continuous function $u  \suchthat   \R \toarrow    \R$ satisfying
\begin{equation} \label{e07}
 u(z)< \min\set{0,-    \frac{\del}{\del   z}  \log
 f_1^{{\scriptscriptstyle -1}  \prime } (z) ,-  \frac{\del}{\del   z}  \log
f_2^{{\scriptscriptstyle -1}  \prime } (z) }.
\end{equation}
so that
\begin{equation} \label{e08}
\frac{\del}{\del   z}  \log g' (z) =  \frac{\del}{\del   z}   \log
f_1^{{\scriptscriptstyle -1}  \prime } (z)  + \frac{\del}{\del   z}  \log
f_2^{{\scriptscriptstyle -1}  \prime } (z) +u(z)< \min\set{ \frac{\del}{\del
z}
\log  {f_1^{\scriptscriptstyle -1}}'(z) , \frac{\del}{\del   z}  \log
{f_2^{\scriptscriptstyle -1}}'(z) }.
\end{equation}

Note that we used the   nonvanishing derivative condition  on $f$ simply to
guarantee the existence of $u$ in that the right-hand side of \eqref{e07} is
bounded from below.  Thus we can solve for
$g$, yielding $g\of f$ concave.
 

We have saved what we consider to be the most beautiful example of this paper for last.
It demonstrates the most
subtle type of obstruction to concavifiability that can   arise.
\pagebreak

\fboxsep=12pt\begin{boxedminipage}[c]{.95 \linewidth}
\begin{small}
 {\bf Figure  \ref{quasi3b}’s example: A
positive log-derivative with unbounded variation.}
   Consider the strictly quasiconcave
function $f(x)$ on $[-1,4]$
shown in Figure
\ref{quasi3b}, which is defined as follows.
\begin{equation*} \label{e09b}
f(x)=\begin{cases}
  q(x) & -1\leq   x<1 \\
  q(1)-\frac{1}{2} (x-3) (x-1) q'(1) & \phantom{-}1\leq x\leq 4
\end{cases}
\end{equation*}
where
$$
 q(x)=\int_{-1}^x e^{t \sin \left(\frac{1}{t}\right)+1}\, dt
  $$

From the formula we can readily verify that the first derivative,
$$
f'(x)=
 \begin{cases}
  e^{x\sin(1/x)+1} & -1\leq x<1 \text{ and } x\neq0\\ e & x=0 \\
e^{1+\sin(1)}(2-x) & \phantom{-}1\leq x \leq4
  \end{cases},
$$
is a $C^1$ function with derivative bounded away from $0$, except at the peak of
$f$ at $x=2$, and is strictly concave on $[1,4]$.   Nevertheless, on
the interval $(-1,1)$, we have $\log f'(x)=x\sin(\frac1x)+1$ which is a classic example
of a function with unbounded variation. It is not obvious at this point, but later in the paper,
Theorem \ref{thm:1-d}  will prove that such an $f$ cannot be concavified by any
postcomposition.
\end{small}
 \end{boxedminipage}\fboxsep= 3pt

\begin{figure}[ht]
  \centering
 \includegraphics[width=4in]{quasifig08-sinewave.pdf}
\caption{\sc Most Subtle of All---  Nonconcavifiable Strictly Quasiconcave Function with Strictly Positive Derivatives but  Unbounded Variation  }
 \label{quasi3b}
 \end{figure}
\pagebreak

The problem in  Figure 8’s example is  that the log of the first derivative has infinite
variation over a finite interval, is imperceptible to the naked eye when examining the
graph. In trying to concavify this, it becomes impossible to adjust the slope to be
decreasing at a certain height on one side of the maximum without creating a vertical or
horizontal tangency at the same height on the other side. We will show this formally
later, as  part of Theorem \ref{thm:1-d}. Note that if $f$ is monotonic--- as it would be
if
$f$ were restricted to the range $[-1,2]$--- then unbounded variation does not hinder
concavifiability
 








%--------------------------------------------------------------------


\bigskip
\subsection{The  Case When the Function  on $\R^1$ Is Nondifferentiable and Nonmonotonic but
Continuous}
\bigskip

What is most difficult is when $f$ is nondifferentiable and nonmonotonic. If after we postcompose
$f_2$ with $f_1^{-1}$, the new function becomes smooth except at the
endpoints of the domain, then we are simply in the case handled by the previous section. This will
generally not hold true, however.



 We will begin by showing that  the most obvious   avenues of approach to
constructing a concavifying function $g$ fail.

If  we could arrange for $g$ to smooth $f$ before it concavifies $f$,
$f$'s nondifferentiability wouldn't matter.
Example X  shows that this approach won't  work.

\fboxsep=12pt
\begin{boxedminipage}[c]{.9 \linewidth}
\begin{small}
 {\bf Example X:   You can't always smooth.}
 
One cannot always smooth a non-differentiable quasiconcave $f$
by postcomposition with a  $g \suchthat   \R \toarrow \R$, except by one which is
constant on the range of $f$. First, choose a smooth function $q_1 \suchthat [0,1)
\toarrow    \R$ with strictly positive derivative (e.g. $q(x)=x$) and a continuous
strictly increasing function $q_2 \suchthat [0,1) \toarrow    \R$ with the same range as
$q_1$ but nondifferentiable at a countable dense set of points in $[0,1]$.\addtocounter{footnote}{1}
\footnotemark[\value{footnote}]
 Now, form the strictly quasiconcave
$f\suchthat (-1,1)\toarrow\R$ with $m=0$, $f_1=q_1$ and $f_2=q_2$. For any $g \suchthat
\R \toarrow\R$, if $g \of  f$ restricted to $(-1,0]$ is smooth then $g$ is smooth on the
entire range of $f$. Consequently $g \of f$ is not differentiable on a dense subset of
$(0,1)$.
\end{small}
 \end{boxedminipage}
\fboxsep= 3pt

\footnotetext[\value{footnote}]{ One can build such a $q_2$ by repeatedly modifying a
Cantor staircase function, for example. (See \url{http://rasmusenorg/papers/dense.pdf}.
}

[dense.pdf is not up on the web---put it there or remove the link.]




\bigskip

 A second consideration is that  in our search for a suitable $g$ we cannot
expect   $g$ to always be concave, even to concavify a single strictly increasing
function, or $g'$ to be even locally Lipschitz--- that is, to be such that on each compact subset of the
 domain $D$, 
$\ds{\sup_{\substack{x,y\in D \\ y\neq
x}}   \frac{\abs{g’(y)-g’(x)}}{\abs{y-x}}<C}$ for some $C>0$. 
Example Y  below  shows this
using the fact that concave functions are differentiable except at a countable
 number of points (in fact,  for  strictly increasing concave functions  the left-
and right-hand derivatives exist everywhere  and are both nonincreasing.)
In particular, concave
 functions are locally Lipschitz, so  their slopes are bounded.

\bigskip

\fboxsep=12pt
\begin{boxedminipage}[c]{.9 \linewidth}

\begin{small}
{\bf Example Y:  
 Concavifiers of Lipschitz $f$ need not be Lipschitz.} Suppose $f\suchthat [a,b] \toarrow
\R$ is a strictly increasing function which is differentiable except possibly at
$c\in(a,b)$ and which has a horizontal tangent at $c$, i.e. $\lim_{t
\toarrow c^-}f'(x)=0$. A Lipschitz example is $f(x)=x^3$ confined to [-1,1],
for which $f'(0) = 0$.
This implies that $f^{\scriptscriptstyle -1}$ has the opposite corner with
$\lim_{t \toarrow a^-} f^{{\scriptscriptstyle -1}\prime} (x)=\infty$, and in
particular that
$f^{\scriptscriptstyle -1}$ is not Lipschitz. Any concavifying $g$ can be
written as $f^{\scriptscriptstyle -1}$ followed by a locally Lipschitz
concave function. Since
$f^{\scriptscriptstyle -1}$ is not Lipschitz any $g$ concavifying $f$ cannot
be locally Lipschitz, and thus cannot be concave, unless $g$ is constant on
an interval
containing  $[f(c),f(b)]$.\ \ 
     Similarly, if there is an interior point $w\in(a,b)$  for which there is
a vertical tangent, $\lim_{t \toarrow    w^+}f'(x)=\infty$, then
$f^{\scriptscriptstyle -1}$ has a
horizontal tangent at $f(w)$. Hence,  any concavifying $g$ cannot itself be
concave unless it is constant on $[f(a),f(w)]$.
\end{small}
 \end{boxedminipage}\fboxsep= 3pt



In the case of a nondifferentiable $f$,  we would like, following equation
\eqref{e06c},  to form
\begin{equation}\label{e08a}
 g'(z)=e^{\int_0^z u(t)dt} {f_1^{\scriptscriptstyle -1}}'(z) \cdot
{f_2^{\scriptscriptstyle -1}}'  (z)
\end{equation}
in a distributional sense, since we can only rely on weak derivatives.\footnote{A weak
derivative is a generalization of the concept of the derivative to nondifferentiable
functions.  See expression \eqref{e26} and surrounding text.} For this we consider the
Sobolev space $W^{k,p}$, the space of functions whose weak $k$-th derivatives
belong to $L^p$. Since $f_1^{\scriptscriptstyle -1}$ and $f_2^{\scriptscriptstyle -1}$
are strictly increasing, they are absolutely continuous and live in $W^{1,1}$. However,
$W^{1,1}$ does not form an algebra, since it is not closed under multiplication of
functions, and this creates the problem shown in Figure  \ref{bi-cubic}’s example. 

\fboxsep=12pt\begin{boxedminipage}[c]{.9 \linewidth}
%\refstepcounter{examplecounter}
\begin{small}
{\bf Figure  \ref{bi-cubic}’s example: 
  No simple concavifier.} Suppose our quasiconcave function $f(x)$ was  such that $f_1(x)=f_2(x)=x^3$,
as in Figure \ref{bi-cubic}.
The strictly increasing function $f_1^{-1}(x)=f_2^{-1}(x)=x^{\frac13}$ belong to $W^{1,1} $ on
$[-1,1]$.  This has derivative ${f_1^{-1}}'(x)=\frac13 x^{-\frac23}\in L^1$,  but the product we
would have for our construction in equation \eqref{e08a} is ${f_1^{\scriptscriptstyle -1}}'(z) \cdot
{f_2^{\scriptscriptstyle -1}}'  (z)=\frac19 x^{-\frac43}$, which is not in $ L^1$, and integrating
it to get $g$ yields   $-\frac13 x^{-\frac13}$,  which is not even increasing on all of $[-1,1]$. On
the other hand, this $f$ is easily concavified by $g(y)=-y^{2/3}.$
\end{small}
\end{boxedminipage}\fboxsep= 3pt


\begin{figure}%[ht]
 \centering
 \includegraphics[width=3in]{bi-cubic.pdf}
\caption{\sc A Function Made from Back-to-Back Cubic Functions  }
 \label{bi-cubic}
 \end{figure}


Figure  \ref{bi-cubic}’s example  shows that simply taking the product
$f_1^{{\scriptscriptstyle -1} \prime} (z) \cdot f_2^{{\scriptscriptstyle -1}
\prime} (z)$ for
$g'(z)$ will not always work. If we assumed that each derivative  was in
$W^{1,p}$ for $p\geq 2$, then the product would be in $W^{1,1}$.  If we want
to use
arbitrary products, though,    we would be forced to work in $W^{1,\infty}$,
and this is a stronger assumption than we need, since $W^{1,\infty}$
coincides with the
space of Lipschitz functions  and we know that there are non-Lipschitz
quasiconcave functions that can be concavified.\footnote{Consider $f(x) =
x^\frac13$, which
has an unbounded first derivative, $f'(x) =\frac13 x^{-\frac23}$.}

Conversely, if we wanted to work directly on weak second derivatives to guarantee that $
\frac{\del}{\del   z}
\log
g' (z)<\min\set{\frac{\del}{\del z} \log
f_1^{{\scriptscriptstyle -1} \prime} (z), \frac{\del}{\del   z}  \log
f_2^{{\scriptscriptstyle -1} \prime} (z)} $ for
equation \eqref{e08},  we would need to work in
$W^{2,1}$. By the Sobolev embedding theorem,
however, $W^{2,1}\subset W^{1,\infty}$ for one-dimensional functions.\footnote{For the
general Sobolev Embedding Theorem, see Wikipedia (2011) or Chapter 2 of Aubin (1982). For $W^{2,1}
(\R)\subset
W^{1,\infty}(\R)$, see Exercise 2.18 in Ziemer (1989).} Thus we gain nothing over working
with Lipschitz functions.

\bigskip

In view of these problems, let us consider the following upper and lower derivatives
$\overline{D}f,\underline{D}f\suchthat    \R  \toarrow
[-\infty,\infty]$   (not to be confused with ``weak
derivatives''). Given a function $f$ define
\begin{equation} \label{e09}
 \overline{D}f(x)=\limsup_{h \toarrow     0}
\frac{f(x+h)-f(x)}{h}\quad\text{and}\quad  \underline{D}
f(x)=\liminf_{h \toarrow    0}
\frac{f(x+h)-f(x)}{h}.
\end{equation}

These quantities always exist, if we allow for values of $-\infty$ and $\infty$, and $ \overline{D}
f(x)\geq
\underline{D} f(x)$ with equality occurring if and only if the derivative of
$f$ exists at $x$, in
which case both quantities coincide with $f'(x)$.

Note that if $w<x<y$ then the slope of the secant line between $(w,f(w))$ and $(y,f(y))$
lies between the values of the slopes of the secant lines from $(w,f(w)))$ to $(x,f(x))$
and $(x,f(x))$ to $(y,f(y)))$. Hence we have,
\begin{equation} \label{e10}
 \overline{D}f(x)=\limsup_{\substack{\abs{y-w}\to 0 \\ w\leq x <
y}}\frac{f(y)-f(w)}{y-w}\quad\text{and}\quad
\underline{D}f(x)=\liminf_{\substack{\abs{y-w}\to 0 \\ w\leq x <
y}}\frac{f(y)-f(w)}{y-w}.
\end{equation}

In other words, these quantities reflect the lower and upper limit of the slopes of all secant lines
between points before and after $x$, not just those with an endpoint
at $x$. Also, we cannot dispense with the ordering $w\leq x <y$ in the above limits, since the
continuous extension of the function $x^2 \sin(\frac1{x^2})$ has
derivative $0$ at $0$ and yet admits secant lines of unboundedly positive and negative slope whose
endpoints are arbitrarily close to $0$.

We now begin to explore analogues of conditions for concavity of $C^2$ functions using the above
objects that are available to us for arbitrary continuous functions.
For what follows let $\ell(x,y)$ represent the secant line between $(x,f(x))$ and $(y,f(y))$, and
let $s(x,y)$ represent the slope of $\ell(x,y)$. In the next three lemmas,
we will explore the relationship between concavity and conditions on $\overline{D}f$. (Analogous
statements invoking $\underline{D}(f)$ could also naturally be
formulated.)

\begin{lemma}\label{lemma1}
A continuous function $f:I\to \R$ is strictly concave
 if and only if for all $x\in  I$, and all
$w<x$, $\overline{D}f(x) < s(w,x)$.
\end{lemma}

\begin{proof}
If $f$ is concave, then for any $y>w$ in $I$ we have $s(x,y)<s(x,w)$ and hence taking the $\limsup$
as ${y\to x}$ we obtain the forward implication. Conversely,  if
$f$ is not convex then   there exist points $r<s<t$ in $I$ such that $f(s)$ lies below the secant
line $\ell(r,t)$. By continuity, one may trace the graph in both
directions from $(s,f(s))$ until it runs into the segment $\ell(r,t)$ showing that there is some
open interval $(w,x)\subset (s,t)$ such that the entire graph of $f$ over
 $(w,x)$ lies strictly below the secant line $\ell(w,x)$. For all $z\in(w,x)$, we then have $s(z,x)>
s(w,x)$ and therefore $\overline{D}f(x)\geq s(w,x)$ contradicting our hypothesis.
\end{proof}

\bigskip

\begin{lemma}\label{lem:2}
A continuous function $f:I\to \R$ is strictly concave if and only if $\overline{D}f$ is a strictly
decreasing function.
\end{lemma}

\begin{proof}
If $f$ is concave, then for any three points $w<x<y$ in $I$ we have $s(w,x)>s(w,y)$ and $s(w,y)>
\overline{D}f(y)$ by  Lemma \ref{lemma1}. Taking the $\limsup$ as
$w$ approaches $x$ from below we see that $\overline{D}f(x)\geq s(w,y)> \overline{D}f(y)$, as
desired.

Conversely, if $f$ is not convex we can find, as in Lemma \ref{lemma1}’s proof, points $w<x$
for which the entire graph of $f$ over $(w,x)$ lies strictly below the
secant line $\ell(w,x)$. After possibly shrinking this neighborhood we may assume the graph of $f$
changes sides of the secant line $\ell(x,w)$ at both $w$ and $x$.
Then for any point $z$ sufficiently near $w$, and any point $y$ sufficiently near $x$, we have
$s(z,w)<s(w,x)<s(x,y)$. Taking limsup's as $z$ approaches $w$ and $y$
approaches $x$, we obtain $\overline{D}f(w)\leq \overline{D}f(x)$, contradicting our hypothesis.
\end{proof}

Combining Lemma \ref{lem:2}  with  Figure 6’s example,   we obtain  the following necessary criterion for strict
quasiconcavity  of   $f$. First recall that  $a$ was defined as the lower bound of $f$’s support and
$m$    as its argmax in
  Section \ref{sec:nonmonotonic}. We will use the following notation in the next proof and the
remainder of the paper: \fbox{
   $\rest{f} {(a,m]}$}  denotes the restriction of the function $f$ to the
interval $(a,m]$.

\bigskip

\begin{lemma}\label{lem:concavif-noncont}
Given a strictly quasiconcave function $f\suchthat    (a,b)
\toarrow \R$, there is a $g  \suchthat   \R \toarrow   \R$ such that $g \of
f$  is strictly concave
only if there is a function $h\suchthat  \R \toarrow   \R$ such that $h \of
f$ satisfies,
\begin{equation} \label{e11}
\begin{cases}
\phantom{\infty}0<\underline{D}(h \of  f)(x)\leq\overline{D}(h \of
f)(x)<\infty & {\rm for }\; x\in(a,m)\\
\\
-\infty<\underline{D}(h \of  f)(x)\leq\overline{D}(h \of  f)(x)<0 & {\rm for
}\; x\in(m,b).
\end{cases}
\end{equation}
 In particular, $h \of  f$ must be (locally) Lipschitz except at $m$.
 \end{lemma}


\begin{proof}
Suppose there is no such $h$.      We can compose $f$ by the function $h=\rest{f}
{(a,m]}^{\scriptscriptstyle
-1}$ so that $h \of  f$ is still strictly quasiconcave, but $(h \of  f)_1$ is linear. By
hypothesis, $(h
\of f)_2$ either admits a vertical tangency on the pre-image of the range of $(h \of f)_1$,
or else $\underline{D} (h
\of  f)_2(x)=0$ for some $x\in (0,1)$. In the latter case, if we had instead chosen $h=
-\rest{f} {[m,b)}^{\scriptscriptstyle -1}$ then $(h \of f)_2$ would be linear and $(h \of  f)_1$
would admit a vertical tangency, and so we are back in the first case after
switching ``1''and ``2''. Hence, without loss of generality we may assume that there is a point
$x\in (0,1)$ with $\overline{D}(h \of f)_2(x)=\infty.$ (Recall here that $(h \of
f)_2$ is increasing, see Figure \ref{quasi-f1f2.jpg}.)

Since $(h \of  f)_1$ is the identity, any  strictly  concavifying $g$ for $h
\of  f$ must be concave and strictly increasing, and hence with
$\underline{D}(g)(z)>0$ for any $z$ in the
interior of the range of $(h \of  f)_1$. Then, however,  it could not have
concavified $(h \of f)_2$.
\end{proof}


The function $h$ in Lemma \ref{lem:concavif-noncont} can also be taken to be the inverse of the
restriction to the strictly increasing side, so $h=
 \rest{f} {[m,b)}^{\scriptscriptstyle -1}$.

\begin{remark}
In fact, we shall see that the necessary conditions in Lemma \ref{lem:concavif-noncont} turn out to
not be sufficient for concavifiability. A significantly more subtle
problem arises.
\end{remark}

 We will need terminology to be able to discuss the problem of rapidly changing derivatives.

\fbox{ The
``variation'' of a function} $f\suchthat    [a,b] \toarrow    \R$ is defined
as
\begin{equation} \label{e12}
  \fbox{$ \op{Var}(f)$} \equiv \sup\set{\sum_{i=1}^{n} \abs{f(x_{i})-
f(x_{i-1})}  \suchthat  n\in \N
 \;\; {\rm and} \;\; a\leq x_0<x_1<x_2<\cdots<x_n\leq b }.
\end{equation}


Denote the  ``functions of bounded variation'' on the closed interval
$[a,b]
$  by
\begin{equation} \label{e13}
  \fbox{$ \op{BV}([a,b])$ }    \equiv \set{f  \suchthat [a,b] \toarrow   \R
\suchthat \op{Var}(f)<\infty}.
\end{equation}




For a general interval $I\subset \R$,   denote by \fbox{$\op{BV}_{loc}(I)$}
the set of {\em locally} bounded variation functions, i.e. those which
belong to $\op{BV}([a,b])$ for
every compact interval $[a,b]\subset I$.

In Theorem \ref{thm:1-d} below, without loss of generality, we will assume that our function  $f
\suchthat (a,b)\to \R$ has the property that if either $f$ or $-f$ is
quasiconcave, then $\op{Range}(\rest{f}{(a,m]})=\op{Range}(f)$ where $m$
represents the unique extremal point. \footnote{If this is not the case, we
simply replace $f(x)$ by its reflection about $\frac{b+a}{2}$, namely
$f(b+a-x)$. Then the very same resulting function $g$ will concavify the original $f$.}

Thus armed with notation, we can state our second theorem. Recall that we earlier explained that for
monotonic functions it is very easy to show that the function being strictly quasiconcave is
equivalent to it being concavifiable.  For nonmonotonic functions we need to add two more conditions
whose importance is considerably less clear.

\fboxsep=12pt\begin{boxedminipage}[c]{.9 \linewidth}
\begin{Theorem}\label{thm:1-d}
For any continuous nonmonotonic function $f\suchthat  (a,b) \toarrow \R$, there is a function $g
\suchthat   \op{Range(f)} \toarrow   \R$ such that $g \of f$ is strictly concave if and
only if
\begin{enumerate}[(i)]
\item
 $f$ or $-f$ is strictly  quasiconcave, with argmax $m$. 
\item
 for $h \equiv \rest{f} {(a,m]}^{\scriptscriptstyle -1}$,  the function $h
\of  \rest{f} {(m,b)}$  and its inverse are locally Lipschitz.
\item 
$\log \abs{\overline{D}(h \of f)}\in\op{BV}_{loc}((m,b))$.
\end{enumerate}
Moreover, when $g$ exists it is strictly monotone.
\end{Theorem}
\end{boxedminipage}\fboxsep= 3pt

\begin{proof}
 We will first explain the necessity of (i), strict quasiconcavity. Apply exactly
the same proof as Part 2 of Theorem \ref{thm:finite}’s proof  (the
theorem for functions
 defined over a finite number of points).  Here, $f$
is defined over a continuum, but we can still apply the proof method of
choosing three points
 from the continuum to test for concavity.  Lemma  \ref{lem:concavif-noncont} demonstrates
the necessity of condition (ii) on the upper derivatives.  
Condition (iii) will be explained at the end of the proof.

 The sufficiency of the conditions is a bit more difficult to prove. Without loss of
generality we can assume $f$ is strictly 
quasiconcave. The existence of $g$ implies that it is continuous,  since
$f$ and $g\of f$ are. Moreover, $\overline{D}(h \of  f)$ is nonpositive on $(m,b)$ since
$f$ is strictly decreasing there and $h$ is strictly increasing on its domain. (This
accounts for taking the absolute value in condition (iii),  which is unnecessary in the
case
when $-f$ is quasiconcave.) Since $\log \abs{\overline{D}(h \of
f)}\in\op{BV}_{loc}((m,b))$,  it is a standard fact, e.g. see Folland (1984), that $\log
\abs{\overline{D}(h \of  f)}$ is the difference of two strictly increasing
functions. Also,  $\log \abs{\overline{D}(h \of  f)}$  is continuous except at a
countable set of points such
 that the sizes of the jumps at the discontinuities on any compact interval
are summable. Now $\log \abs{(h \of  f)'}$ agrees with this function wherever it
is defined, which
 is a-priori almost everywhere. [xxx Eric is confused by this last clause]By the D’Arboux  [xxx Chris check spelling]  Theorem (Folland (1984)), and
since a full
measure set is dense, $\log \abs{(h \of f)'}$ then agrees with $\log
\abs{\overline{D}(h \of  f)}$ at each
 point where $\log \abs{\overline{D}(h \of  f)}$ is continuous. Since $-\log \abs{(h \of
f)'(x)}=\log \abs{((h \of f)^{\scriptscriptstyle -1})'(h \of f(x))}$, it also
agrees with $\log \abs{\overline{D}(h \of
 f)^{\scriptscriptstyle -1} \of h \of  f}$ except at a countable number of
points where  $\log \abs{\overline{D}(h \of f)^{\scriptscriptstyle -1} \of h \of
f}$ has discontinuities with
 summable gaps. Thus, since precomposition does not affect the $\op{BV}$
property, except for the domain over which it applies, $\log \abs{\overline{D}(h
\of  f)
 ^{\scriptscriptstyle -1}}\in \op{BV}_{loc}\(\(h(f(m)), h(f(b))\)\).$

Let $h_1 \equiv h_0 \of  h$,  where $h_0$ is a smooth strictly increasing concave
function on $(-\infty,f(m)]$ with $\lim_{x \toarrow    m} \overline{D}(h_0 \of f)(x)=0$.
This
can always be done by using an $h_0$ that increases sufficiently slowly near $f(m)$.

From now on in the proof,  we will  write $f$ for $\rest{f} {[m,b)}$ to avoid distraction
from the subscript. Since the derivative of $h_0$ is bounded away from $0$ and
$\infty$ and is strictly decreasing on any compact subinterval of $\(f(b),f(m)\)$, the
function  $\log \abs{\overline{D}((h_1 \of f)^{\scriptscriptstyle -1})}$ still lies in
$\op{BV}_{loc}((h_1(f(b)),h_1(f(m))))$ and $h_1 \of  f$ is concave on $(a,m]$.

Now choose $z_0\in \(h_1(f(b)),h_1(f(m))\)$. Since $\log \abs{\overline{D}((h_1
\of f)^{\scriptscriptstyle -1})}\in\op{BV}_{loc}\(\(h_1(f(b)),h_1(f(m))\)\)$,
there is a representative
\begin{align}\label{eq:q}
q\in L^1_{loc}\(\(h_1(f(b)),h_1(f(m))\)\)
\end{align}
 of the almost everywhere defined function $\left(\log \abs{\overline{D}((h_1 \of
f) ^{\scriptscriptstyle -1})}\right)'$ such that $\log\abs{\overline{D}((h_1 \of f)
^{\scriptscriptstyle -1}) (z)}=\log\abs{\overline{D}((h_1 \of f)^{\scriptscriptstyle
-1})(z_0)}+\int_{z_0}^z q(t) \,dt$. Since $\lim_{z
\toarrow m}\overline{D}(h_0 \of f)(z)=0$, the negative part of $q$, defined by
\begin{align}\label{eq:q-}
q^-(x)\equiv \begin{cases} q(x) & q(x)<0 \\ 0 & q(x)\geq 0\end{cases},
\end{align}
belongs to $L^1([h_1(f(c)),h_1(f(m))])$ for any $c<b$. By integrating, we can find a twice-
differentiable (though not necessarily in $C^2$) function $g
\suchthat \(h_1(f(b)),h_1(f(m))\)\to \R$ such that
\begin{equation} \label{e14}
 g'(z)=e^{\int_{h_1(f(m))}^z (-1+q^-(t))\,dt}.
\end{equation}

Consequently,  $g'(z)> 0$, $g''(z)<0$ and $(\log g')'<q^-(z)$ for each
$z\in\(h_1(f(b)),h_1(f(m))\).$ Since by construction $(\log g')'(z) < (\log
\abs{((h_1
\of  f)^{\scriptscriptstyle -1})'})'(z)$ for almost every
$z\in\(h_1(f(b)),h_1(f(m))\)$, it follows that $\overline{D}(g \of h_1 \of f)$ is
strictly decreasing on $(a,b)$ and so $g \of  h_1 \of  f$ is concave, which is what we
needed to
prove.

All that remains to be proved is the necessity of condition (iii). If $\log
\overline{D} (h \of f)\not\in\op{BV}_{loc}((m,b))$,  then no such function
$q\in L^1$ can be
found: there exists no $g$ for which $\log g'$ grows slower than $\log (h_1
\of  f)'$  since   $\log g'(z)$ would necessarily become unbounded before
$z$ reached $h_1(f(b))$.
\end{proof}

 
 Theorem \ref{thm:1-d}'s condition (ii) is, strictly speaking, superfluous  in that it only serves to
establish the existence of the function in   condition (iii), where its
existence is   implicit. In particular, we need $\log \abs{\overline{D}(h\of f)}$ to exist  almost
everywhere  in order to make sense of it being in $\op{BV}_{loc}$. Once
it belongs to $\op{BV}_{loc}$ we can conclude that $h\of f$ on $(m,b)$, and its inverse, are locally
Lipschitz. Moreover, whenever the hypotheses of the Theorem
\ref{thm:1-d} hold, $g$ will always be strictly monotone. 


This theorem shows that quasiconcavity is not quite equivalent to concavifiability.
Besides quasiconcavity we need condition (ii), which roughly says that after straightening
out one side, the other side has no horizontal or vertical tangencies. Beyond that, one
still needs the yet more subtle condition (iii) governing the oscillation of the
derivative on the unstraightened side. In economic terms, the marginal utility or profit
cannot be oscillating too wildly. Note that even after straightening one side to linear,
$f$ can have a horizontal or vertical tangency at $m$ or $b$ on the unstraightened side
and still be concavifiable, as in Figure \ref{fig:linear-cusp}. Also, any pathology is
permitted on  one side so long as it is mirrored on the other side, as with Figure
\ref{bi-cubic}'s symmetric zero slopes at inflection points.


 \begin{figure}[ht]
  \centering
 \includegraphics[width=3in]{linear-cusp}
\caption{\sc After straightening one side, certain pathologies can exist on the other side and still
be
concavifiable.}
\label{fig:linear-cusp}
 \end{figure}

\bigskip

\begin{remark}\label{rem:1-d}
  The statement for functions of the form  $f  \suchthat (a,b] \toarrow
\R$ (that is,
    where the domain is $(a,b]$, not  $(a,b)$),  is identical, except that $h \of
\rest{f} {(m,b]}$ should be
locally
Lipschitz and $\log \overline{D}(h
\of  f)\in\op{BV}_{loc}((m,b])$.
For the remaining two cases of possible interval domains, $f\suchthat   [a,b)
\toarrow   \R$ and $f\suchthat   [a,b] \toarrow   \R$, the statement is
identical  to the original or the modification except that $h$ becomes $h=\left(\rest{f}
{[a,m]}\right)
^{\scriptscriptstyle -1}$. The necessary modifications of Theorem \ref{thm:1-d}'s proof
for these three
cases are straightforward. The only nontrivial point is to observe that $(h \of  f)'\in
\op{BV}_{loc}((m,b]) $
implies that $g'$ can be chosen to be finite at $f(b)$.

%The function $h
%\of \rest{f} {(m,b)}$ is locally Lipschitz and $\log \overline{D} (h \of
%f)\in\op{BV}_{loc}((m,b))$.


%
%   Note that if the conditions on $f$ in Theorem \ref{thm:metric}  are not met on some
%   subinterval of the domain, one can still find a $g$ such that $g \of  f$ is
%   weakly concave by having $g$ collapse the smallest interval which contains
%   the image under $f$ of the offending interval, and the minimum value for
%   $f$.
%
%\noindent
%$\bullet$
% If we set $\overline{\abs{D}}(f)(x)=\max{\overline{D}(f)
%(x),-\underline{D}(f)(x)}$, then we can write the condition as one on all of
%$f$. Namely, $f$ can be concavified if and only if there is some $f$ such that
%$\log \overline{\abs{D}}(f)$ is bounded above away from $a,b$, and
%bounded away from $-\infty$ away from $m$ with the negative part of the
%derivative of this function satisfying $[(\log\overline{\abs{D}}(f)))']^-\in
%L^1_{\loc}((a,b))$. (Recall here $f^-(x)=\begin{cases}-f(x) & f(x)<0 \\ 0  &
%f(x)\geq 0 \end{cases}.$) We have also used the fact that if $g\in L^1([a,b])$
%then $G(x)=\int_a^x g(t)dt$ is absolutely continuous and in $\op{BV}([a,b])$.

\end{remark}

\bigskip


%\refstepcounter{remarkcounter}
\begin{remark}\label{rem:1-d-2}  %REMARK 8
   We could have written   Theorem \ref{thm:1-d}'s  conditions (ii) and (iii)
differently.  For instance, $f$ can be concavified if and only if after
postcomposition by a function
   $h
\suchthat [f(m),\infty) \toarrow    \R$, $\log \overline{D}(h \of f) _1(x)$
and $\log \overline{D}(h \of  f) _2(x)$ are bounded above on $[0,t]$ for any $t<1$, and
bounded from below
on $[s,t]$ for any $0<s<t<1$ and  if the negative part of the resulting upper derivatives
satisfy
$[\overline{D}(\log
\overline{D}(h \of  f) _i)]^-\in L^1_{loc}([0,1))$ for $i=1,2$. (Recall here
that
$f^-(x)=  f(x)$  for   $f(x)<0$  and $f^-(x)=  0$ for   $f(x) \geq 0 $.)
We
have also used the fact that if $g\in L^1([a,b])$ then $G(x)=\int_a^x
g(t)dt$ is
absolutely continuous and in $\op{BV}([a,b])$.
\end{remark}


%   There are two direct ways analyzing the weak derivative. The
%first is to consider the following upper derivative. Given a
%function $F$ define
%\begin{equation} \label{e15}
% D_+F(x)=\limsup_{h \toarrow
%0} \frac{f(x+h)- f(x)}{h}.
%\end{equation}
%
%Note that by the triangle inequality we have
%\begin{equation} \label{e16} D_+F(x)=
%\limsup_{h_1\neq h_2 \toarrow    0} \frac{f(x+h_1)-f(x+h_2)}
%{h_1+h_2}.
%\end{equation}
%The upper derivative clearly equals the derivative where defined, and the
%above expression shows that $D_+F$ is an upper- semicontinuous function.
%Moreover, for any positive upper-semicontinuous function $h$ which is infinite
%only on a measure zero set, we can find an $g$ such that $D_+g=h$.
%\comment{reference or else drop}.  The other method for dealing with
%
\bigskip

%\refstepcounter{remarkcounter}


\bigskip

\begin{remark}\label{rem:1-d-3}
The necessity part   of  Theorem \ref{thm:1-d}'s proof can also be done
using approximate derivatives.  For each $\eps>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<s<t<1$,  and
%\item[(ii)]
%  $[\overline{D}(\log
%\overline{D}(f))]^-\in L^1_{loc} ([0,1))$.
%\end{enumerate}
\end{comment}

 \begin{comment}
%
%   bounded above away from $0,1$, and bounded away from
%$-\infty$ away from the minimum point $m\in[0,1]$ with the
%negative part of the derivative of this function satisfying
%$\op{Var}(q^-)<C$ where $q=\overline{D}
%(\log\overline{\abs{D}}(f))$. (Note that $q^-$ this is an
%explicitly defined $L^1$ representative of $(\log \abs{f'})'$.)
%
 \end{comment}


\bigskip

\fboxsep=12pt
\begin{boxedminipage}[c]{.9 \linewidth}
\begin{Theorem}\label{thm:metric}
Let $X$ be any geodesic metric space.
For any continuous function $f\suchthat   X\toarrow  \R$
there is a function $g  \suchthat  \op{Range(f)}\toarrow  \R$  such that $g
\of  f$ is strictly concave if and only if:

\begin{enumerate}
\item[(i)]
 Either $f$ or $-f$ is strictly quasiconcave;

\item[(ii)] $h\of f$ is locally Lipschitz on $X-\set{m}$ where $h=(f\of\ga_o)^{-1}$
for some geodesic $\ga_o$ in
$X$ ending at $m$ such that $\op{Range}(f\of \ga_o)=\op{Range}(f)$. Moreover
$\overline{D}(h\of f \of \ga)$ does not vanish on any geodesic segment $\ga\suchthat
(0,1)\to X$ for which $h\of f\of \ga$ is strictly increasing.

\item[(iii)] The total variation of $\log \overline{D} (h\of f)$ along all geodesics
$\ga\suchthat [0,1]\to X$
for
which $h\of f\of \ga$ is strictly increasing is uniformly bounded away from the
extrema of $h\of f$,  or in
other words,
\begin{equation} \label{e17}
\inf_{\ga}\set{[\overline{D}(\log \overline{D}(h\of f\of \ga)^{-1})]^- }\in
L^1_{loc}(R).
\end{equation}
(Here $R$ is the interior of the range of $f$ and the infimum is taken over all
geodesic segments $\ga\suchthat [0,1]\to X$ for which $h\of f\of \ga$ is strictly
increasing.)
\end{enumerate}
\end{Theorem}
\end{boxedminipage}\fboxsep= 3pt


\begin{proof}
Suppose first that the conditions are met. Let $q=\inf_{\ga}\set{[\overline{D}(\log
\overline{D}(h\of f\of
\ga)^{-1})]^- }$. From   Theorem {\ref{thm:1-d}}\,'s proof, any function $g_0$ such that
$(\log g_0')'<q$
will concavify $h \of  f  \of  \gamma$ for
each such $\gamma$. Choose $g_0$ such that $(\log g_0')'= -1+q$. (Note that we can extend
$g_o$ to a function at the
endpoints of $R$ as well.)

Observe that every segment $\gamma \suchthat [0,1]\toarrow  X$ contains a subsegment
$[s,1]$ where $h \of  f \of
\gamma$ is strictly increasing on $[s,1]$. Moreover, $h \of  f \of  \gamma(1-t)$ is also
strictly increasing for $t\in [1-s,1]$. We now
note that a quasiconcave function that is concave on both its strictly increasing and
strictly decreasing part separately  is concave. Hence, the function $g_0$ concavifies
$h
\of f \of
\gamma$ for every geodesic $\gamma$, and so $g_0 \of  h \of  f$ is concave. (This applies
even to geodesics through $m$ since $g_0\of h\of f$ is concave on every
subinterval on either side of $m$.) Taking $g=g_0 \of h$ finishes this direction of the
proof.

Conversely, suppose that there is a function $g$ such that $g\of f$ is concave. Since $h$
is invertible, we may write $g\of f=g\of h^{-1}\of h\of f$, and set $g_o=g\of h^{-1}$.
By concavity of $g\of f$ along $\ga_o$, we have that $g_o=g\of f\of \ga_o$ is convex. In
particular it $C^1$ with $\log (g_o)'$ Lipschitz with derivative belonging to
$L^1_{loc}(R)$.    Moreover, for any geodesic $\ga\suchthat [0,1]\to X$, with $f\of \ga$
strictly increasing, we have $(\log (g_o)')'\leq q_\ga$ where
$q_\ga=[\overline{D}(\log
\overline{D}(h\of f\of \ga)^{-1})]^-$,  the comparison holding almost everywhere. Taking
infima over all such $\ga$ implies $(\log (g_o)')'\leq q$ as desired.

\begin{comment}
%
%By the final hypothesis of Theorem \ref{thm:1-d}, we have $\log g_o'$ If the conditions of the
theorem are not satisfied, then for any
%$h  \suchthat \R^1\toarrow  \R$ as in the statement, there is a geodesic $\ga:[0,1]\to X$ for which
$h\of f\of \ga$ is increasing, but
%either $\log\abs{\overline{D}(h \of  f \of  \gamma)}$ is unbounded at an interior point of
$\gamma$, or there is   a geodesic along which the restriction
%of $h \of  f$
%cannot be concavified by Theorem \ref{thm:metric} . In the second case we
%are done, and in the first case we may assume that the geodesic does not
%pass through the
%global maximum of $f$ since we can always choose an $h$ which increases so
%slowly at $f(m)$ that after possibly postcomposing $h$ with another $h_1$,
%we may
%assume that the entire differential of $h \of  f$ vanishes at $m$, i.e.
%$d_m(h \of  f)=0$. If the function $h \of  f \of \gamma$ does not have
%bounded upper derivative at
%its maximum point, however,  then it is not concave. Thus, if this property
%does not apply to    all $\gamma$ simultaneously,   $f$ is not
%concavifiable.
\end{comment}

\end{proof}
\bigskip

Put crudely, Theorem \ref{thm:metric} says that in any geodesic metric space, including infinite-
dimensional ones, the function $f$ being   strictly concavifiable
by a strictly increasing $g$ is equivalent to three conditions on $f$. First, $f$ must be strictly
quasiconcave. Second, after being straightened to linear along one
geodesic spanning the whole range, the resulting function must not be too flat or too steep in any
direction. Lastly, condition (iii) requires that the total variation of
the log of the derivative along all geodesic segments must be bounded uniformly, away from the
endpoints.

\bigskip

\begin{remark}
Even in this most  general of our theorems,  the  proof is  still constructive. The
function $g$ which
concavifies $f$ can be explicitly constructed following the proof, using only data
provided by the hypotheses.
Additionally, if $X$ is a proper metric space, then one can postcompose again to flatten
the peak of the function as
was done in constructing the $g$ from Theorem \ref{thm:1-d}, if one so desires.
\end{remark}

\bigskip

\begin{remark}
Once again, condition (ii)  is unnecessary, strictly speaking,  in that it follows from
the satisfaction of condition
(iii), since otherwise $\log \overline{D}(h\of f\of \ga)$ would not be defined as a
function.  We include  it for
parallelism with the other theorems, and because otherwise the condition might appear
hidden in condition (iii).
\end{remark}

\bigskip
\begin{remark} % Remark 12
There are two reasons   a function may not be in $L^1_{loc}$: (a)  it is  not
measurable; or (b)   it   does not have
bounded integral on some compacta. We only need
   condition (iii)   to rule out problem (b). Even though the composition of measurable
functions is not always
measurable, problem (a) cannot  arise  here
since the following operations always result in a measurable function: the composition of
measurable functions by
continuous functions, the real limit of measurable
functions (e.g., the $\overline{D}$ operator),  taking the supremum of measurable
functions, and taking the negative
part of a measurable function. Note that $h\of f\of
\gamma$ is continuous and hence measurable, and therefore the function
$\sup_{\ga}\set{[\overline{D}(\log
\overline{D}(h\of f\of
\ga))]^- }$ is automatically measurable.
\end{remark}



  Theorem \ref{thm:metric} applies quite generally, but   its  conditions,
though sharp, are not always easy to verify.
In the case of a Riemannian manifold $M$, however,  we can search for
conditions that take advantage of the global smooth structure on $M$.  In
the next section we
will examine a relatively simple set of necessary and sufficient conditions
which allow for much easier verification. In particular, they avoid the
potentially difficult task of deciding whether
or not the restriction of the function to each geodesic lies in the required
function space. The price to be paid for this  simplification is the
limitation to twice-differentiable functions, for both the original function
and the concavifier.

%---------------------------------------------------

\subsection{Differentiable Functions  on the Manifold $M$ (including $\R^n$)
as a Special Case}

Here  we consider a $C^2$  Riemannian manifold $M$ with its Riemannian connection
$\nabla$ (the
natural Riemannian extension of the Euclidean gradient differential
operator).  We will make the assumption that the quasiconcave function
$f\suchthat M\to \R$ is  twice differentiable. Later, for our last
theorem, we will weaken this to functions belonging only to the Sobolev
space $W^{2,1}$ (i.e. possessing weak second derivatives).


 Let $f  \suchthat   M\toarrow  \R$ be strictly  quasiconcave. Suppose $\grad f$
exists and does not vanish at a point $x$. In a neighborhood of $x$,
choose an orthonormal basis $\set{e_i(x)}$ such that (i) $e_1= \frac{\grad f}{\norm{\grad f}} $, and
(ii)  $e_2,\dots,e_n$, tangent to the level set of $f$ through $x$,
are a diagonal basis for the second fundamental form\footnote{This is the symmetric form describing
the shape operator of relative curvatures of the embedded
manifold.} of the level set $f^{\scriptscriptstyle -1}(f(x))$.

The Hessian  of a function $f$ on an arbitrary Riemannian manifold is the $(0,2)$
tensor\footnote{A $(0,q)$-tensor
is,
roughly speaking, a multilinear map that eats
$q$ distinct vectors and spits out a scalar. For $q=2$, an example is the dot product in $\R^n$.}
$\op{Hess} (f)=\nabla df$.
Given a basis, $e_1,\dots,e_n$ at a point $p$,  the
corresponding matrix of the Hessian at $p$ has entries
\begin{equation} \label{e18}
 f_{ij}=\inner{\nabla_{e_i}(\nabla
f),e_j}=\nabla_{e_i}\inner{\grad f,e_j}-\inner{\grad
f,\nabla_{e_i}e_j}
\end{equation}

This  matrix depends on the metric, and not just on the smooth structure
(except at critical points of the function $f$, where $\nabla df=d^2f$).
Note, too, that $\op{Hess}(f)$ is symmetric, which can be seen easily by
extending the basis $\set{e_i}$ to a coordinate basis so that
\begin{equation} \label{e19}
f_{ij}-f_{ji}=e_i(df(e_j))-e_j(df(e_i))-df(\nabla_{e_i}
e_j-\nabla_{e_j}e_i)=[e_i,e_j](f)-df([e_i,e_j])=0.
\end{equation}

Thus equipped,  we  can present a necessary and sufficient condition for concavifiability of a
twice-differentiable quasiconcave function $f$ by postcomposing with a
twice-differentiable function $g$. (Recall that   $q$ its negative part $q^{-}$ is the negative part  of $q$, as 
defined as in Equation \eqref{eq:q-}.) Our theorem will apply to $C^2$ Riemannian manifolds; that is,   manifolds
admitting $C^2$ charts for which the metric tensor coefficients are also $C^2$ functions. It will depend on the principal curvatures of the level sets of $f$, which are the   eigenvalues of the second fundamental form of a
submanifold. These   values (which  are positive for a quasi-concave function) indicate the bending
of the submanifold relative to the ambient manifold's curvature.  For an  $\R^2$ example to illustrate the theorem, look ahead to Figure 11’s example  after the proof. 
 

\fboxsep=12pt
\begin{boxedminipage}[c]{.9 \linewidth}
%\fbox{\parbox{5.5in}{
\begin{Theorem}\label{thm:manifold}
%\refstepcounter{theoremcounter} \label{thm:c2}
Let $M$ be a $C^2$ Riemannian manifold.  For
any twice-differentiable function $f\suchthat X\toarrow
\R$ there is a strictly increasing twice-differentiable $g
\suchthat  \R \toarrow  \R$  such that $g \of  f$ is strictly concave if and only if:
\begin{enumerate}
\item[(i)]
 $f$ is strictly quasiconcave;

 \item[(ii)]
  $\grad f$ does not vanish except possibly at the maximum point of
$f$, HOW ABOUT A HALF-DERIVATIVE AT AN EDGE OF THE RANGE e .g. $f(x) = x^2$ on [0,1]? And

WHERE IN THE PROOF DOES IT COME IN THAT IT’S OK FOR THE GRADIENT TO DISAPPEAR AT A MAXIMUM?

 \item[(iii)]
  The function $q^{-}$ belongs to $L^1_{loc}(R)$, where $R$ is the interior of the range of $f$ and
$q$ is defined by
\begin{equation} \label{e20}
q(t)=\inf
\frac{1}{\norm{\nabla f}^2} \left(-f_{11}-\sum_{j=2}^n
\frac{f_{1j}^2}{\lambda_j\norm{\nabla f}}\right)
\end{equation}
   where the infimum is taken over points  on the level set $f^{\scriptscriptstyle -1}(t)$ and where
$\lambda_2,\dots,\lambda_n$ denote the principal
curvatures    of the
level sets of $f$.
\end{enumerate}

 A suitable $g$ is 
\begin{equation} \label{g-function}
 g(z)=\int_{f(m)}^z e^{\int_{f(m)}^s (-1+q_o(t))\,dt}\,ds, 
\end{equation}  
with $q_o$   a continuous function almost everywhere less than $q^{-}$. 
\end{Theorem}
%}}
\end{boxedminipage}\fboxsep= 3pt








\begin{proof}
Consider $f$ in a neighborhood of  a point $p\in M$. We
assumed $\grad_p f\neq 0$ which allows us to choose an
orthonormal basis of $T_xM$\footnote{Here, $T_xM$ is the vector space of all tangent
vectors to $M$ at $x$.} for $x$
in a
neighborhood of $p$ as before,  so that $e_1(x)=\frac{\grad_x f}{\norm{\grad_x f}}
$ and $e_2(x),\dots,e_n(x)$ is a basis of $e_1^\perp$ which
diagonalizes the second fundamental form of the level set
$f^{\scriptscriptstyle -1}(f(p))$ at the point $p$. We will denote the
eigenvalues, the principal curvatures
for this symmetric bilinear form,  by $\lambda_2,\dots,
\lambda_n$, where $n=\dim(M)$. By quasiconcavity of $f$ (condition (i)), these are all strictly
positive. In terms of our basis we
have $\lambda_j=-\inner{\nabla_{e_j}e_1,e_j}$ (see e.g. Chavel (1993)).

For any twice-differentiable function $g  \suchthat  \R\toarrow  \R$, the
Hessian of $g \of  f$
is given by $\grad^2 (g \of  f)=(g'' \of  f)df \tensor df + g' \of  f
\op{Hess}(f)$. We need to show that this is negative definite under the hypotheses.

Recall that in the above frame we computed the $(i,j)$-entry of the Hessian to be
$f_{ij}=\inner{\nabla_{e_i}(\nabla
f),e_j}= \nabla_{e_i}\inner{\grad f,e_j}-\inner{\grad f,\nabla_{e_i}
e_j}$. By our choice of frame,  for $j>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}

