Prove that set is convex

In summary: The easiest way to deal with questions like the one you asked is to proceed in small steps: (1) prove that a half-space a_1 x_1 + a_2 x_2 + \cdots + a_n x_n \leq b is a convex set in (x_1, x_2, \ldots, x_n)-\text{space} (where the a_i, b are constants); then prove (2): the intersection of convex sets is convex. With hardly any work at all you then can ...
  • #1
Dostre
26
0
Let [itex]\alpha[/itex]>0 and [itex]\gamma[/itex]>0 and [itex]\beta[/itex]>0 be real numbers. Let M={x∈R[itex]^{2}_{+}[/itex] ∶[itex]\alpha[/itex]x[itex]_{1}[/itex]+[itex]\gamma[/itex]x[itex]_{2}[/itex][itex]\leq[/itex][itex]\beta[/itex]}. Prove M is a convex set. Prove that M is bounded. What does this set resemble (in economics)?

I have a little idea of how to show that this set is convex, although, I know the condition for a convex set (ax1+(1-a)x2, 0<a<1). It is clear to me that this set resembles PPF, so can you just show me how to prove that it is convex, please.
 
Last edited:
Physics news on Phys.org
  • #2
pick any two points in your set, x=(x1,x2), y=(y1,y2), prove that a*x+(1-a)*y is also in that set for any 0<a<1.
 
  • #3
sunjin09 said:
pick any two points in your set, x=(x1,x2), y=(y1,y2), prove that a*x+(1-a)*y is also in that set for any 0<a<1.

And how do I prove these arbitrary point s are in the set? Should I make some kind of inequality?
 
  • #4
You know that (x1,x2) and (y1,y2) satisfy the inequality that defines M. Write down those conditions. Then write down the inequality that the convex combination of these points has to satisfy, and prove that this inequality is true by using the two inequalities that you know are true.

The proof is basically three lines, if you write everything down and try some algebra and it doesn't work post what you've done and we can help you
 
  • #5
Office_Shredder said:
You know that (x1,x2) and (y1,y2) satisfy the inequality that defines M. Write down those conditions. Then write down the inequality that the convex combination of these points has to satisfy, and prove that this inequality is true by using the two inequalities that you know are true.

The proof is basically three lines, if you write everything down and try some algebra and it doesn't work post what you've done and we can help you

I wrote that proof, but I am unable to make this inequality work out. Thats what I got:
u=(u[itex]_{1}[/itex],u[itex]_{2}[/itex]), f(u)=[itex]\alpha[/itex]u[itex]_{1}[/itex]+[itex]\gamma[/itex]u[itex]_{2}[/itex]-[itex]\beta[/itex]

v=(v[itex]_{1}[/itex],v[itex]_{2}[/itex]), f(v)=[itex]\alpha[/itex]v[itex]_{1}[/itex]+[itex]\gamma[/itex]v[itex]_{2}[/itex]-[itex]\beta[/itex]

Inequality that the convex function has to satisfy is:

[itex]\lambda[/itex]f(u)+(1-[itex]\lambda[/itex])f(v)[itex]\geq[/itex]f[[itex]\lambda[/itex]u+(1-[itex]\lambda[/itex])v]

or

[itex]\lambda[/itex]([itex]\alpha[/itex]u[itex]_{1}[/itex]+[itex]\gamma[/itex]u[itex]_{2}[/itex]-[itex]\beta[/itex])+(1-[itex]\lambda[/itex])([itex]\alpha[/itex]v[itex]_{1}[/itex]+[itex]\gamma[/itex]v[itex]_{2}[/itex]-[itex]\beta[/itex])[itex]\geq[/itex][itex]\alpha[/itex]([itex]\lambda[/itex]u[itex]_{1}[/itex]+(1-[itex]\lambda)[/itex]v[itex]_{1}[/itex])+[itex]\gamma[/itex]([itex]\lambda[/itex]u[itex]_{2}[/itex]+(1-[itex]\lambda[/itex])v[itex]_{2}[/itex])-[itex]\beta[/itex]

So I cannot make this inequality work out. What I get is that 0[itex]\geq[/itex]0. Does it mean that the inequality is satisfied since it is bigger or EQUAL?
 
Last edited:
  • #6
I don't understand why you are introducing convex functions to the problem. Set convexity and function convexity are related but distinct concepts.

If [itex] (x_1,x_2)\ , (y_1,y_2) \in M[/itex] we get
[tex] \alpha x_1 + \gamma x_2 \leq \beta [/tex]
[tex] \alpha y_1 + \gamma y_2 \leq \beta[/tex]

Now for any 0<a<1 we want to prove
[tex] \alpha( a x_1 + (1-a) y_1)) + \gamma ( a x_2 + (1-a) y_2 ) \leq \beta [/tex]
There are two things that you should do: understand why this is what we need to prove, and then prove it using the first two inequalities that I posted
 
  • #7
Oh I did not actually realize these are two different concepts.

Alright, I got the solution. To prove this inequality I first expanded the LHS and rearranged the terms:(instead of [itex]\alpha[/itex] I will use [itex]\lambda[/itex] to avoid confusion)

[tex] \lambda ( a x_1 + (1-a)y_1) + \gamma( ax_2+(1-a)y_2) =
\lambda ax_1 + \gamma ax_2 + \lambda( 1-a) y_1 + \gamma( 1-a) y_2\ =
a(\lambda x_1+\gamma x_2) + (1-a)(\lambda y_1 + \gamma y_2)[/tex]

Now I need to show that the last expression above is less than β. To do that I used the two inequalities that I know are true.

[tex] \alpha x_1 + \gamma x_2 \leq \beta [/tex]
[tex] \alpha y_1 + \gamma y_2 \leq \beta[/tex]

Multiply the first one by a and we get:
[tex] a(\alpha x_1 + \gamma x_2) \leq a\beta [/tex]

Multiply the second one by (1-a) and we get:
[tex] (1-a)(\alpha y_1 + \gamma y_2) \leq (1-a) \beta[/tex]

Add them up and we get:
[tex]a(\lambda x_1+\gamma x_2) + (1-a)(\lambda y_1 + \gamma y_2) \leq a\beta + (1-a) \beta [/tex]

The LHS looks exactly like the LHS of the inequality we need to prove.
So now If we expand the RHS we get β and the inequality looks like:
[tex]a(\lambda x_1+\gamma x_2) + (1-a)(\lambda y_1 + \gamma y_2) \leq \beta[/tex]

Exactly like the inequality we need to prove and did so. Since we know that the two inequalities with points (x1,x2) and (y1,y2) are true adding them up will be also true and after we added them up the resultant inequality looks exactly like the one we needed to prove after we rearranged terms.
 
Last edited:
  • #8
This set resembles a budget constraint (not PPF) and is bounded by:
at x[itex]_{2}[/itex]=0, x[itex]_{1}\leq[/itex][itex]\frac{\beta}{\alpha}[/itex]
at x[itex]_{1}[/itex]=0, x[itex]_{2}\leq[/itex][itex]\frac{\beta}{\gamma}[/itex]
 
  • #9
Dostre said:
This set resembles a budget constraint (not PPF) and is bounded by:
at x[itex]_{2}[/itex]=0, x[itex]_{1}\leq[/itex][itex]\frac{\beta}{\alpha}[/itex]
at x[itex]_{1}[/itex]=0, x[itex]_{2}\leq[/itex][itex]\frac{\beta}{\gamma}[/itex]

By far, the easiest way to deal with questions like the one you asked is to proceed in small steps: (1) prove that a half-space [itex] a_1 x_1 + a_2 x_2 + \cdots + a_n x_n \leq b[/itex] is a convex set in [itex] (x_1, x_2, \ldots, x_n)-\text{space}[/itex] (where the [itex] a_i, b[/itex] are constants); then prove (2): the intersection of convex sets is convex. With hardly any work at all you then can say that the set of [itex](x_1,x_2,\ldots,x_n)[/itex] that satisfy the equalities and inequalities
[tex]\begin{array}{l}
a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n \leq b_1,\\
a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n \leq b_2, \\
\vdots\\
a_{r1} x_1 + a_{r2} x_2 + \cdots + a_{rn} x_n \leq b_r,\\
c_{11} x_1 + c_{12} x_2 + \cdots + c_{1n} x_n = d_1, \\
\vdots\\
c_{s1} x_1 + c_{s2} x_2 + \cdots + c_{sn} x_n = d_s
\end{array}
[/tex]
is convex if it is not empty.

RGV
 

1. What is a convex set?

A convex set is a set of points in a space where, for any two points in the set, the line segment connecting the two points lies entirely within the set. In other words, a convex set is a set that is "bent outwards" and does not have any indentations or holes.

2. How do you prove that a set is convex?

To prove that a set is convex, you must show that for any two points in the set, the line segment connecting the two points lies entirely within the set. This can be done by using the definition of convexity and mathematical proofs such as induction or contradiction.

3. Can a set be both convex and concave?

No, a set cannot be both convex and concave. A set is either convex or concave, depending on whether it has an outward or inward curvature. A set that has both inward and outward curvature is considered neither convex nor concave.

4. Are all polygons convex?

No, not all polygons are convex. A polygon is convex if and only if all its interior angles are less than 180 degrees. If a polygon has one or more interior angles that are greater than 180 degrees, it is considered concave.

5. Why is it important to prove that a set is convex?

It is important to prove that a set is convex because convexity is a fundamental concept in mathematics and has many applications in fields such as optimization, geometry, and economics. By proving that a set is convex, we can use various mathematical tools and techniques to analyze and solve problems related to the set.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
956
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
996
  • Calculus and Beyond Homework Help
Replies
20
Views
2K
  • Calculus and Beyond Homework Help
Replies
8
Views
2K
  • Calculus and Beyond Homework Help
Replies
14
Views
519
  • Calculus and Beyond Homework Help
Replies
18
Views
2K
Back
Top