Could someone explain this part of my book for me?

[flyingpig]

I just pulled a paragraph that's giving me a headache atm.

[PLAIN]http://img31.imageshack.us/img31/8697/unledwjt.png

The LOP (Figure 2.1) they refer to is

[PLAIN]http://img600.imageshack.us/img600/9787/unledylv.png

How on Earth did they show that this feasible set is bounded? Yes I know they took a K, but how did they choose "20 to be the smallest"?

How would you even show that it is bounded?

Why would K be the smallest? The inequality |x_j| \leq K obviously says

|x_1| \leq K, |x_2| \leq K

At first I thought they found an K through the contraints, i.e.

3|x_1| +5|x_2| \leq 8K \leq 90

And they took K = \frac{90}{8} = 11.25

I mean they said "a K", so it isn't unique, but this ugly number obviously is not true.

How would you do it if the constraints are NOT in \mathbb{R^2}?

 

[Mark44]

From your picture, what's the largest value of x₁? What's the largest value of x₂?

 

[flyingpig]

From your picture, what's the largest value of x₁? What's the largest value of x₂?

x_2 is no bigger than 10, and x_1 is no bigger than 20. I thought about that at first, but there are two things wrong with this

1) If you can't graph this, you are screwed.

2) Why choose 20 over 15? I am guessing we take K to be a larger number to "cover" over our region?

 

[flyingpig]

Actually why didn't my inequality worked anyways? It didn't seem wrong to me.

 

[Pyrrhus]

Are you familiar with topological concepts, flyingpig?

Basically, a feasible region S is bounded if there exist a epsilon-neighborhood (you could say an open ball) at the origin such that the region is contained within this epsilon neighborhood at the origin.

In your case you probably can find a |x_{j}| \leq K such that it'll contain the constraint set.

 

[flyingpig]

Are you familiar with topological concepts, flyingpig?

Very little, almost none...

Basically, a feasible region S is bounded if there exist a epsilon-neighborhood (you could say an open ball) at the origin such that the region is contained within this epsilon neighborhood at the origin.

In your case you probably can find a |x_{j}| \leq K such that it'll contain the constraint set.

That's the intuition, but how do you do this on paper with variables and numbers?

They say K = 20 is the smallest, but that doesn't make sense seeing it doesn't satisfy the inequality

3(20) + 5(20) = 60 + 100 = 160 \geq 90

See?

 

[flyingpig]

That's the intuition, but how do you do this on paper with variables and numbers?

They say K = 20 is the smallest, but that doesn't make sense seeing it doesn't satisfy the inequality

3(20) + 5(20) = 60 + 100 = 160 \geq 90

See?

This makes no sense. I take everything back. This was only one constraints, it never said all points are in the feasible region, so this makes no sense whatsoever.

From your picture, what's the largest value of x₁? What's the largest value of x₂?

I was thinking about this post again in my sleep last night and here is my deduction

For this problem, I needed to find an |x_j| \leq K

So I needed to find the max value of each x first

3x_1 + 5x_2 \leq 90
9x_1 + 5x_2 \leq 180
x_2 \leq 15

How is that MARK??

Fortunately for us, the problem tells us x_2 \leq 15 already, so that us saves us some work.

Now we must find x_1 which we could see this as 20, but we can do better than this.

3x_1 + 5x_2 \leq 90
9x_1 + 5x_2 \leq 180

Let x_2 = 0


3x_1 \leq 90 \iff x_1 \leq 30
9x_1 \leq 180 \iff x_1 \leq 20

The inequality intersect and hence x_1 \leq 20 (I just did something similar in our proof class today, something about complements of sets)

So therefore we have

x_2 \leq 15
x_1 \leq 20

We are close to getting our K. Now the question comes, how does this say K \geq 20?

Well, in the previous case with x_1 \leq 30 or x_1 \leq 20, it was simple because we were only dealing with x_1, we don't know anything (without a graph) if x_1 \leq x_2 or x_2 \leq x_1.

But we have

x_2 \leq 15
x_1 \leq 20

So the follow is true

x_2 \leq 15 \leq 20, so it follows that x_2 \leq 20

So that concludes

x_2 \leq 20
x_1 \leq 20

Which must mean \forall K \geq 20, the region is bounded.

 

[Mark44]

From your picture, what's the largest value of x₁? What's the largest value of x₂?

x_2 is no bigger than 10, and x_1 is no bigger than 20. I thought about that at first, but there are two things wrong with this

1) If you can't graph this, you are screwed.

2) Why choose 20 over 15? I am guessing we take K to be a larger number to "cover" over our region?

My answer pertained to the question you posted, which included the picture. From this, it's easy to see that the largest value of x₁ (in the feasible region) is 20 and the largest value of x₂ is 15 (not 10, as you said above). So the smallest value of K for which |x_i| <= K, i = 1, 2, is K = 20.

The situation is more complicated in higher dimensions, and I'm not expert enough to know how to find a number K for n = 3 or higher.

Getting back to this problem, K = 20 is the smallest number that is >= both variables. Basically we want to find the smallest square that the feasible region fits into. A square that was 15 X 15 would obviously not be big enough, but one that is 20 X 20 is just the right size.

 

[flyingpig]

My answer pertained to the question you posted, which included the picture. From this, it's easy to see that the largest value of x₁ (in the feasible region) is 20 and the largest value of x₂ is 15 (not 10, as you said above). So the smallest value of K for which |x_i| <= K, i = 1, 2, is K = 20.

The situation is more complicated in higher dimensions, and I'm not expert enough to know how to find a number K for n = 3 or higher.

Getting back to this problem, K = 20 is the smallest number that is >= both variables. Basically we want to find the smallest square that the feasible region fits into. A square that was 15 X 15 would obviously not be big enough, but one that is 20 X 20 is just the right size.

Suppose, just suppose (I know you already said you aren't an expert in this, and I regret a little taking this course...) that the inequality x_2 \leq 15 was never there and somehow you get x_2 \geq 0

DOes that mean a K cannot exist? Because the region is unbounded for x_2 goes off to infinity.

 

[Mark44]

Are we still talking about the problem in the OP? If so, removing the inequality x₂ <= 15 changes the feasible region, but it's still bounded. In fact, the same value of K still works (i.e., K = 20).

 

[flyingpig]

Are we still talking about the problem in the OP? If so, removing the inequality x₂ <= 15 changes the feasible region, but it's still bounded. In fact, the same value of K still works (i.e., K = 20).

Hmmm ummm hmmmmmmmmm

Let's forget about the problem in the OP for a moment and think about this

Suppose x_2 \leq 15 still (but with a different constraints - different equations), but x_1 \geq 0, then this problem is unbounded right?

 

[Pyrrhus]

The general form to test if a region is bounded for a LP (also for a NLP) is to find a number K such that the euclidean distance (or euclidean metric for an open ball at the origin) from the origin (because of the nonnegative constraints) is less than this number K. Mathematically, ||\vec{x}|| \leq K, \forall \vec{x}

flyingpig it depends.

Let me write to you an example

Max x_{1} + x_{2}

st -x_{1} - x_{2} \leq -8

x_{1} \geq 0, x_{2} \geq 0

Can you see why?What about this now

Min x_{1} + x_{2}

st -x_{1} - x_{2} \leq -8

x_{1} \geq 0, x_{2} \geq 0

Is this one bounded? Why?

 

[flyingpig]

The general form to test if a region is bounded for a LP (also for a NLP) is to find a number K such that the euclidean distance (or euclidean metric for an open ball at the origin) from the origin (because of the nonnegative constraints) is less than this number K. Mathematically, ||\vec{x}|| \leq K, \forall \vec{x}

my professor drew a circle like you said (even though it was really ugly and he never said it was at the origin...

flyingpig it depends.

Let me write to you an example

Max x_{1} + x_{2}

st -x_{1} - x_{2} \leq -8

x_{1} \geq 0, x_{2} \geq 0

Can you see why?

Is there a reason why it was written as -x_{1} - x_{2} \leq -8 instead of x_{1} +x_{2} \geq 8

If I let x_1 = 0 (the smallest x_1 could take), then I get that x_2 \geq 8 and respectively x_2 \geq 8

So is the region bounded? No, there is no K such that both x_{1} , x_{2} bounds them. I am not sure how to write this out properly, but that's the explanation I can give.

So is the LOP bounded? No, but how do I show this using math? I know there is no optimum for this LOP, but how do I show that? I could let x_1 = t and x_2 = M for M is some number and maybe take the limit?

What about this now

Min x_{1} + x_{2}

st -x_{1} - x_{2} \leq -8

x_{1} \geq 0, x_{2} \geq 0

Is this one bounded? Why?

The region is still unbounded, that never changes. The LOP is bounded however

There is an optimum, i.e. the point (0,8) or (8,0)

 

[Pyrrhus]

my professor drew a circle like you said (even though it was really ugly and he never said it was at the origin...

Should be at origin, because of what I said about nonnegativity constraints.

Is there a reason why it was written as -x_{1} - x_{2} \leq -8 instead of x_{1} +x_{2} \geq 8

No reason at all. Both are the same.

my professor drew a circle like you said (even though it was really ugly and he never said it was at the origin...

Should be at origin, because of what I said about nonnegativity constraints.

If I let x_1 = 0 (the smallest x_1 could take), then I get that x_2 \geq 8 and respectively x_2 \geq 8

So is the region bounded? No, there is no K such that both x_{1} , x_{2} bounds them. I am not sure how to write this out properly, but that's the explanation I can give.

So is the LOP bounded? No, but how do I show this using math? I know there is no optimum for this LOP, but how do I show that? I could let x_1 = t and x_2 = M for M is some number and maybe take the limit?

I told you how. It requires some topology concepts to show how.