Prove that a function is concave

  • Thread starter Thread starter blaah
  • Start date Start date
  • Tags Tags
    Concave Function
blaah
Messages
2
Reaction score
0

Homework Statement


f:R->R, c'
prove that f is concave iff f(x*)+(x-x*)f'(x*)>=f(x)


Homework Equations


assume the function is only once differentiable


The Attempt at a Solution


i have no idea how to approach this question...:confused:
 
Physics news on Phys.org
blaah said:

Homework Statement


f:R->R, c'
prove that f is concave iff f(x*)+(x-x*)f'(x*)>=f(x)


Homework Equations


assume the function is only once differentiable


The Attempt at a Solution


i have no idea how to approach this question...:confused:
Are x* and x any two values of x? Are there any restrictions on the values of x?

To prove your statement you need to prove two things:
  1. f is concave ==> f(x*) + (x - x*) f'(x*) >= f(x)
  2. f(x*) + (x - x*) f'(x*) >= f(x) ==> f is concave
For the first, what does it mean for a function to be concave?
For the second, one approach would be a proof by contradiction. Suppose that f(x*) + (x - x*) f'(x*) >= f(x) is true and that f is not concave. If you arrive at a contradiction, it means that your original assumption was incorrect, and therefore f must be concave.

Mark
 
for all x, x*

i know that for the function to be concave all the points on the tangent need to be on or below the function...but i doesn't help...i've been staring at the problems for days now, with no result...
 
Looks to me like the mean value theorem would be useful here.
 
Thread 'Use greedy vertex coloring algorithm to prove the upper bound of χ'
Hi! I am struggling with the exercise I mentioned under "Homework statement". The exercise is about a specific "greedy vertex coloring algorithm". One definition (which matches what my book uses) can be found here: https://people.cs.uchicago.edu/~laci/HANDOUTS/greedycoloring.pdf Here is also a screenshot of the relevant parts of the linked PDF, i.e. the def. of the algorithm: Sadly I don't have much to show as far as a solution attempt goes, as I am stuck on how to proceed. I thought...
Back
Top