Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider a function $f$ over $\Re^n$ to $\Re$. Suppose it is true that for every affine subspace with dimension strictly lesser than $n$ the function $f$ is concave. Is the function $f$ concave over $\Re^n$?

To start with, suppose $f: \Re^2 \to \Re$, such that for all $x \in \Re$, $f(x, .)$ is concave and for all $y \in \Re$, $f(., y)$ is concave. Is it possible that $f$ is not concave?

EDIT: Not sure about etiquette here, so I'll leave my original post above. I failed to state the question carefully. Let me give it another try:

Suppose we have real-valued function $f$ on $\Re^n$, and we know the following about the function: Pick a dimension and call it dimension $k$. Next, pick a real number $x$. Now, suppose it is true that $f(., ..., x, ., ...)$ is strictly concave, for any $x$, and for any dimension $k$. Is it true that $f$ is concave?

Theo's response below includes an example $f(x, y), = xy$ that I construe as a counterexample if the qualifier of "strict" were not included.

For what it's worth, this is not a homework question, but instead one born of curiosity.

share|improve this question

3 Answers 3

up vote 7 down vote accepted

The definition of concavity is $f((1-t)x + ty) \geq (1-t)f(x) + tf(y)$ for all $x, y$ and all $0 \leq t \leq 1$. This a condition on line segments (hence only involving points lying in $1$-dimensional affine subspaces), so your first question has the tautological answer yes for $n \geq 2$.

The second question has a negative answer. Consider $f(x,y) = xy$. Then $f(x,\cdot)$ and $f(\cdot,y)$ are linear, hence concave, but the function itself is not concave ($f(x,x) = x^{2}$ is convex and $f(x,-x) = -x^{2}$ is concave).

For $C^{2}$-functions the following are equivalent:

  • $f$ is concave;
  • the Hessian of $f$ is negative semi-definite at each point.

In contrast, the condition that $f(\cdot,y)$ and $f(x,\cdot)$ be concave just says that $f_{xx}(\cdot,y), f_{yy}(x,\cdot) \leq 0$, while concavity also involves the mixed derivatives $f_{xy} = f_{yx}$. In detail, concavity is equivalent to $f_{xx} + f_{yy} \leq 0$ and $f_{xx}f_{yy} - (f_{xy})^{2} \geq 0$ everywhere on $\mathbb{R}^{2}$ (a symmetric matrix is negative definite if and only if its eigenvalues are negative and for $2 \times 2$-matrices this is equivalent to negative trace and positive determinant.)

Edit. To make the example from before strictly concave in the $x$ and $y$-directions, just consider $f(x,y) - e^{x + y}$ or Jonas' example.

share|improve this answer
    
Thanks for your response, Theo. I'm going to edit my first question because I did not ask it correctly. As for your answer to my second question, is there an example when $f(x, .)$ and $f(y, .)$ are strictly concave? Finally, isn't it necessary for $f_{xx}$ and $f_{yy}$ to be non-positive, and not just their sum? –  daegan Feb 3 '11 at 0:30
    
@daegan: I had an inequality sign wrong, this should be ok now. Jonas and I have both added an example for the new question. –  t.b. Feb 3 '11 at 1:02

The function $f(x,y)=-(x^2+1)(y^2+1)$ is a counterexample for the new question, being strictly concave in $x$ for each fixed $y$ and vice versa, but not being concave.

More generally, if $g$ is a twice differentiable, positive, strictly convex function on $\mathbb{R}$ that is not log convex, then $f(x,y)=-g(x)g(y)$ is a counterexample. The log convexity criterion for $g(x)g(y)$ to be convex came up at this other question.

share|improve this answer
    
Thanks for your response and the link to the other question. I like your answer to that interesting question. –  daegan Feb 4 '11 at 7:07

This is very likely to be a homework question. Because of that I won't give you a solution to the homework problem but I will give you a suggestion.

You actually have two questions here, and it isn't clear that solving the simplified version (concave in x and y) will actually help you to solve the full version of the problem. You'll want to be careful about that.

For the simpler version of the problem, recall that a twice continuously differentiable function is concave if the Hessian matrix is negative definitede, concave in x if $f_{xx}$ is negative, and concave in $y$ if $f_{yy}$ is negative. Can you construct a function (perhaps a quadratic function so that the Hessian is very simple) that has a $f_{xx}$ negative and $f_{yy}$ negative but does not have a negative definite Hessian? Can you show that the function you've found is actually nonconvex?

For the full version of the question, you might consider the definition of concavity. How does this definition relate to "every affine subspace"?

share|improve this answer
    
Thanks for your response, Brian. I can assure you it is not a homework problem. –  daegan Feb 3 '11 at 0:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.