Prove inequality of a convex function

AI Thread Summary
The discussion revolves around proving an inequality involving a convex function, specifically the relationship between values at points x1, x2, and x3 where x1 < x2 < x3. The original approach incorrectly linked monotonicity to convexity, leading to a flawed conclusion. Instead, it was suggested to use the definition of convexity, which states that for any points x, y, and z, the inequality f(y) ≤ (z-y)/(z-x)f(x) + (y-x)/(z-x)f(z) holds. By expressing x2 as a convex combination of x1 and x3, the correct inequality can be derived using the properties of convex functions. The conversation highlights the importance of understanding the definitions and properties of convex functions in proving inequalities.
Lambda96
Messages
233
Reaction score
77
Homework Statement
Proof that the following inequality holds ##\frac{f(x_2)-f(x_1)}{x_2-x_1} \leq \frac{f(x_3)-f(x_1)}{x_3-x_1 } \leq \frac{f(x_3)-f(x_2)}{x_3-x_2}##
Relevant Equations
none
Hi,

I have problem to prove that the following inequality holds

Bildschirmfoto 2024-05-01 um 21.21.01.png

I thought of the following, since it is a convex function and ##x_1 < x_2 <x_3## applies, I started from the following inequality ##f(x_2) \leq f(x_3)## and transformed it further

$$f(x_2) \leq f(x_3)$$
$$f(x_2)-f(x_1) \leq f(x_3)-f(x_1)$$
$$\frac{f(x_2)-f(x_1)}{x_2- x_1} \leq \frac{f(x_3)-f(x_1)}{x_2 - x_1}$$

Since the following applies ##x_2 - x_1 \leq x_3 - x_1## it follows ##\frac{f(x_3)-f(x_1)}{x_3- x_1} \leq \frac{f(x_3)-f(x_1)}{x_2 - x_1}## then follows ##\frac{f(x_2)-f(x_1)}{x_2- x_1} \leq \frac{f(x_3)-f(x_1)}{x_3 - x_1}## i.e. the first part of the inequality

Is my approach correct, or does anyone have a better idea of how I can prove the inequality?
 
Physics news on Phys.org
##f(x_2)\leq f(x_3)## sounds like a condition about increasing functions, not convex functions. What is the definition of a convex function?

Also note your last step is wrong, you basically wrote down ##a<b## and ##c< b## and concluded ##a<c##
 
  • Like
Likes Lambda96 and FactChecker
## f ## is convex if and only if
<br /> \frac{f(y)-f(x)}{y-x} \leqslant \frac{f(z)-f(x)}{z-x}<br />
for all ## a < x < y < z < b ##. You have arrived to the right conclusion, but it does not stem from monotonicity (##x^2## is convex but not monotone, for instance) nor the suspect step in between. Consider instead
<br /> f(y) \leqslant \frac{z-y}{z-x}f(x)+\frac{y-x}{z-x}f(z).<br />
  1. Why is this inequality true? (substitute ## y=(1-\lambda)x + \lambda z ##)
  2. Check that it is equivalent to the first inequality.
 
Last edited:
Thank you Office_Shredder and nuuskur for your help 👍👍

Since it is a convex function and ##x_2## lies between ##x_1## and ##x_3##, I can represent ##x_2## as follows ##x_2=(1- \lambda)x_1 + \lambda x_3## with ##\lambda \in (0,1)##

I then inserted this expression into the first part of the inequality ##\frac{f(x_2)-f(x_1)}{x_2-x_1} \leq \frac{f(x_3)-f(x_1)}{x_3-x_1 }##

In order to get the required inequality, I applied the following, since it is a convex function ##f((1- \lambda)x_1 + \lambda x_3) \le (1-\lambda)f(x_1) + \lambda f(x_3)##
 
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