1

Let $A$ be a given $m$ x $n$ matrix, and $c\in R^n$ and $b\in R^m$ be given vectors. Use LP duality theory to show that if the problem $$\min\{x^Tx: Ax=b, x\geq0\}$$ has a finite optimal solution, then the following problem $$\min\{c^Tx: Ax=u, x\geq 0\} $$ cannot be unbounded, no matter what value $u$ might take.

When it says that it has a finite optimal solution, does that mean the problem is infeasible? I am guessing it doesn't so if the first one has an optimal solution then that means the second one has an optimal solution.

If the first one is unbounded then the second cant be unbounded right? But how do I prove that the first one is unbounded? If it even is..

snowman
  • 3,733
  • 8
  • 42
  • 73
  • "unbounded" means that you can not find values for x satisfying Ax=u such that c^T x becomes arbitrarily large. – wonce Feb 13 '15 at 01:22
  • The second problem is "unbounded" when $\inf { c^T x \mid Ax = u, x \geq 0 } = -\infty$. – littleO Feb 16 '15 at 19:43
  • I have edited the question. – snowman Feb 16 '15 at 19:47
  • This problem is wrong, since its conclusion is false. Take $A$ as the all-zero matrix and take $b$ and $u$ as the all-zero vectors, and take $c=(-1,0,0,\ldots,0)$. Then clearly $x=0$ is the (finite) optimal solution to the first problem, and clearly $x=(M,0,0,\ldots,0)$ (for any positive $M$) satisfies the constraints of the second with objective value $-M$, which can be arbitrarily large as $M\rightarrow\infty$. – Michael Feb 22 '15 at 05:58
  • In your first equation, $x^T x = ||x||^2$ the norm of the vector. So you ask for the point of minimum norm across a certain affine subspace. Then you can generalize the point-to-line distance formula. – cactus314 Feb 23 '15 at 18:57

0 Answers0