# Could someone explain this part of my book for me?

1. Sep 28, 2011

### flyingpig

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

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

The LOP (Figure 2.1) they refer to is

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

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}$$?

Last edited by a moderator: May 5, 2017
2. Sep 28, 2011

### Staff: Mentor

From your picture, what's the largest value of x1? What's the largest value of x2?

3. Sep 28, 2011

### flyingpig

$$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?

Last edited: Sep 28, 2011
4. Sep 28, 2011

### flyingpig

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

5. Sep 28, 2011

### 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.

Last edited: Sep 28, 2011
6. Sep 28, 2011

### flyingpig

Very little, almost none...

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?

7. Sep 29, 2011

### flyingpig

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.

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$$

$$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.

8. Sep 29, 2011

### Staff: Mentor

My answer pertained to the question you posted, which included the picture. From this, it's easy to see that the largest value of x1 (in the feasible region) is 20 and the largest value of x2 is 15 (not 10, as you said above). So the smallest value of K for which |xi| <= 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.

9. Sep 29, 2011

### flyingpig

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.

10. Sep 29, 2011

### Staff: Mentor

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

11. Sep 30, 2011

### flyingpig

Hmmm ummm hmmmmmmmmm

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

12. Sep 30, 2011

### 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?

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?

Last edited: Sep 30, 2011
13. Sep 30, 2011

### flyingpig

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

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?

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)

Last edited: Sep 30, 2011
14. Oct 2, 2011

### Pyrrhus

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

No reason at all. Both are the same.

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

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