Linear optimization problem: Minimizing a linear function over an affine set.

Question

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.

Answer 1

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.

Answer 2

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