Convex subset

C

cooltafel

New member
Joined
May 1, 2020
Messages
11
Hello,

I got an assignment I have to prove, but I am a bit stuck on how to continue.

The assignment:
A function [MATH]f: F \to \mathbb{R} [/MATH] is convex if and only if its sublevel set {x∈S|f(x)≤c} is a convex set for any c.

Convex theorem:
[MATH]f((1-\alpha)x_1 + \alpha x_2) \le (1-\alpha)f(x_1) + \alpha f(x_2)\\ for \\alpha \in [0,1]\\ x_1, x_2 \in S[/MATH]
My try:
[MATH]f(x) \le c\\ x = (1-\alpha)x_1 + \alpha x_2\\ f(x) = f((1-\alpha)x_1 + \alpha x_2)\\ f(x) \le (1-\alpha)f(x_1) + \alpha f(x_2)\\ f(x) \le (1-\alpha)c + \alpha c\\ f(x) = c [/MATH]

Am I missing something?
Could someone give me a clear explanation of the steps, since I don't fully understand it all.

Thank you in advance!
 
I'm not sure I understand what you are asking. Is "the assignment" a definition you were given, or a fact you are to prove? Does "convex theorem" assume that f is a convex function? Is it something you were given, or what you are to prove? And what is S?
 
Dr.Peterson said:
I'm not sure I understand what you are asking. Is "the assignment" a definition you were given, or a fact you are to prove? Does "convex theorem" assume that f is a convex function? Is it something you were given, or what you are to prove? And what is S?
Click to expand...

Thank you for your reply!

I am sorry, perhaps I haven't been clear.
So the assignment is to give proof that this fact is right:
A function f: F→R is convex if and only if its sublevel set {x∈S|f(x)≤c} is a convex set for any c.

I already know that it is right, since it was given in the lecture. However, the assignment is now to prove it.

S is the Universal set.

I found the same question on stack exhange, but I don't understand the explanation. Perhaps it helps to understand the question better.
 
cooltafel said:
Thank you for your reply!

I am sorry, perhaps I haven't been clear.
So the assignment is to give proof that this fact is right:
A function f: F→R is convex if and only if its sublevel set {x∈S|f(x)≤c} is a convex set for any c.

I already know that it is right, since it was given in the lecture. However, the assignment is now to prove it.

S is the Universal set.

I found the same question on stack exhange, but I don't understand the explanation. Perhaps it helps to understand the question better.
Click to expand...

Are F and S supposed to be the same set (called X in the Stack Exchange question)? That's what I was asking about S.

The Stack Exchange problem, of course, is only half of yours (since yours has "if and only if"), but it's a start.

One thing missing in your attempted proof is words to explain each step; theirs could have more words, but has enough to follow if you read carefully. Can you tell us where you don't follow it? What you wrote is essentially the same thing. (Did you just copy it and leave out the words, which are really the most important part?)

Here it is:
1591303958396.png

They are given that f is convex, and their alpha is your c. They want to show that the sublevel set is convex. What does that mean? What is the definition of a convex set?

Note that the conclusion is not that [MATH]f(x) = c[/MATH], but that [MATH]f(x)\le c[/MATH]. Do you see why? Do you see why that accomplishes the goal?
 
Dr.Peterson said:
Are F and S supposed to be the same set (called X in the Stack Exchange question)? That's what I was asking about S.

The Stack Exchange problem, of course, is only half of yours (since yours has "if and only if"), but it's a start.

One thing missing in your attempted proof is words to explain each step; theirs could have more words, but has enough to follow if you read carefully. Can you tell us where you don't follow it? What you wrote is essentially the same thing. (Did you just copy it and leave out the words, which are really the most important part?)

Here it is:
View attachment 19508

They are given that f is convex, and their alpha is your c. They want to show that the sublevel set is convex. What does that mean? What is the definition of a convex set?

Note that the conclusion is not that [MATH]f(x) = c[/MATH], but that [MATH]f(x)\le c[/MATH]. Do you see why? Do you see why that accomplishes the goal?
Click to expand...

Thank you again for your reply!

First of all, I found the stack exchange problem after I posted the problem here.

Secondly, I tried to solve it with what I called the "convex theorem".
I looked at the stack exchange problem, but I don't fully understand the 'epi' part.
In my solution, I just did what I though is possible.

A set S is convex if for all [MATH] x_1 \enspace and \enspace x_2 \in S[/MATH], the line segment between u and v is in S.

I don't fully understand what you mean by "Note that the conclusion is not that [MATH]f(x) = c[/MATH], but that [MATH]f(x)\le c[/MATH]."

I don't understand the epigraph, we haven't had seen this in the lecture.

Could you please explain it?

Thanks in advance!
 
I'm not familiar with the term "epigraph" either; so I had to look it up! https://en.wikipedia.org/wiki/Epigraph_(mathematics)

As I expected, it's a simple concept I didn't know by that name. (Actually, the same is true of "sublevel set".)

The comment about "= c" was because in your work you ended with "[MATH]f(x)=c[/MATH]", which is not necessarily true. Comparing with the Stack Exchange work, their last line is "[MATH]= \alpha[/MATH]", but that's a continuation of a string of comparisons "[MATH]f(x) = \dots\le\dots\le\dots = \alpha[/MATH]", whose conclusion is "[MATH]f(x)\le \alpha[/MATH]". That was why I was wondering if you might have copied your work from them and misread that line.

If I were teaching this, I would explain considerably more than that author did. I would start by describing what you need to prove: To show that the sublevel set (which I'll call S' since you've used S for the universe) is convex, you need to show, as you've stated, that for any elements [MATH]x_1, x_2\in S'[/MATH], any element between them is in S', that is, for any [MATH]\lambda\in[0,1][/MATH], [MATH]x = (1-\lambda)x_1 + \lambda x_2\in S'[/MATH]. The steps you show, and they show, apply f to this element x, then apply your "convex theorem" (which I would have called the definition of a convex function). Then, where they say they are using the "epigraph definition", they simply use the fact that [MATH]f(x_1)\le \alpha[/MATH] and [MATH]f(x_2)\le \alpha[/MATH] from the definition of S', because [MATH]x_1, x_2\in S'[/MATH]. A little algebra leads to the conclusion.

They conclude by saying that the epigraph of f is convex, which is their way of defining a convex function. You would close with reference to your definition.
 
I assume you are paraphrasing the proof that if S' is convex, then f is convex (since that's the last line of what you wrote), and not proving the converse (which you also have to do). But it's not clear which you are actually doing.

I am not happy with "we can rewrite any x ..."; you need to choose [MATH]x_1[/MATH] and [MATH]x_2[/MATH] first, not x.

And if you are trying to prove f is convex, you can't apply the definition of a convex function to it.

Whichever fact you are proving, you need to improve your style (which takes time to get used to). Clarity is as important in a proof as in a persuasive essay (which is really what a proof is).
 
You must log in or register to reply here.
Top