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.