Simplex method (need a clarification of an obvious fact)

Question

We wish to minimize $y^Tb$ subject to $y\ge0$ and $y^TA\ge c^T$.

Why is it true:

if $-c\ge0$ and $b\ge0$, the (obvious) minimizer is $y=0$.

I cannot seem to figure this thing out, albeit the text states that it is obvious. Perhaps I am having one of those days, but I would really appreciate a clarification.

My attempt:

$$y\ge0\land b\ge0\implies y\cdot b\ge0$$ So, if the constraint is met, than the minimum is at $y=0$. Now we must look into the constraint. $$-c\ge0\implies c<0\implies (y=0\implies Ay\ge c)$$

Is this OK?

score 1 · Accepted Answer · answered Sep 05 '18 at 21:19

1

Clearly, $y=0$ satisfies the conditions. Substituting $y=0$ yield $0$ for the objective function. You cannot obtain a negative value for the objective function, as $y\geq 0$ and $b\geq 0$, so their scalar product is also nonnegative.

So $0$ is the best possible minimum you can obtain, and it is indeed attained at $y=0$.

answered Sep 05 '18 at 21:19

A. Pongrácz

7,418

Thank you. I added my attempt to the question, right before you posted. It seems to match. Thank you again. – LeastSquaresWonderer Sep 05 '18 at 21:22
Glad to help. This must have been a blackout. Don't worry, it happens to everybody. – A. Pongrácz Sep 05 '18 at 21:28

Simplex method (need a clarification of an obvious fact)

1 Answers1