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

• The see the solution you'll need to scroll all the way down on the first page and hit next ('>'). It's problem 4.8a on the second page. – MRashid Mar 3 '13 at 20:27
• Please don't write "infinite" when you mean "infinitely many". "Infinite solutions" means "solutions each one of which, by itself, is infinite". That's not what is meant here. (I fixed this in the posted question.) – Michael Hardy Mar 3 '13 at 21:29
• @MichaelHardy An amateur mistake on my part. Thanks for pointing it out. – MRashid Mar 3 '13 at 22:07
• @MichaelHardy I noticed that you also changed my solution to the problem. That was not a type and my solution wasn't wrongly copied. That's what I thought that solution should be due to my limited knowledge of matrix theory) – MRashid Mar 3 '13 at 22:59
• @MichaelHardy I noticed that you also changed my solution to the problem. That was not a typo and my solution wasn't wrongly copied. That's what I thought that solution should be (due to my limited knowledge of matrix theory!). I gave the link to the solutions so people could see the actual solution to the problem. I was trying to figure out why my solution was different. – MRashid Mar 3 '13 at 23:01

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.

• Thanks for the explanation. This is how I should've been thinking about the problem in the first place. – MRashid Mar 11 '13 at 0:09

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

• Thanks for the explanation. I'm a bit puzzled as to why this question has been asked before learning Lagrangian multiplier in my class. – MRashid Mar 4 '13 at 0:03
• That's really a question for your instructor rather than this stack exchange group. However, you might reasonably have been expected to learn about Lagrange multipliers in freshman/sophomore calculus. – Brian Borchers Nov 7 '16 at 7:17