Linear optimization problem: Minimizing a linear function over an affine set. The problem is as follows:
Give an explicit solution of the linear optimization problem below.
$$ 
   \text{minimize}\ c^Tx \\
   \text{subject to}\ Ax\ =\ b
$$
No other information is given.
My solution is  basically as follows:
$$
p^*\ = \left\{ 
  \begin{array}{l l}
    \infty & \quad \text{if $Ax=b$ has no solution}\\
    \lambda^\top b & \quad c=A^\top \lambda \text{ for some } \lambda\\
    \ -\infty & \quad \text{if $Ax=b$ has infinitely many solutions (underdetermined)}
  \end{array} \right.
$$


*

*When $Ax=b$ has no solution the problem is infeasible. Therefore the optimal point is $\infty$. 

*When $Ax=b$ has infinitely many solutions, the system in unbounded below and therefore the optimal solution in $-\infty$.


Now the actual solution of this problem is shown here (See problem 4.8 part a):
http://www.docin.com/p-347099771.html
I would like to understand how they got the second solution ($\lambda^Tb$) when A is non-singular and Ax=b has a unique solution. Thanks in advance.
 A: I can tell you why your teacher asked you this before telling you about Lagrange multipliers: it's because you don't need to know about multipliers to answer the question. It's a good example to introduce Lagrange multipliers to the class. You can solve the problem with pure geometrical intuition because there are no inequality constraints.
Here's a picture of the two different cases that may arise (barring the situation where $Ax=b$ has no solution, which you correctly identified):

(I apologize about the poor photo quality. I hope you can make out my scribbles.)
The situation on the left is a special case where the vector $c$ is orthogonal to the hyperplane $Ax=b$, i.e., $c$ is orthogonal to the nullspace of $A$. This may also be expressed as $c = A^T \lambda$ for some vector $\lambda$ since the subspace orthogonal to the nullspace of $A$ is the range space of $A^T$. In this situation, every $x$ satisfying $Ax=b$ solves the problem since you can't move "along" $Ax=b$ and decrease $c^T x$. The optimal objective function value is thus $c^T x = \lambda^T A x = \lambda^T b$.
In the situation on the right, $c$ is no longer orthogonal to the nullspace of $A$ and has a nontrivial projection into that subspace. By following the direction $-\text{Proj}(c)$, the objective $c^T x$ can be decreased to $-\infty$.
This simple example gives the essence of the first-order optimality conditions in optimization. The right way to think about continuous optimization is in terms of geometry.
A: The Lagrangian is $c^\top x-\lambda^\top(Ax-b)=(c-A^\top \lambda)^\top x+\lambda^\top b$. To have a finite solution, we need the $x$ coefficient to be zero. So if $c=A^\top \lambda$ for some $\lambda$, the optimal solution will be $\lambda^\top b$.
