# Minimize $c^Tx$ subject to $Ax=b$

I am studying linear optimization and want to understand the basic general forms. Consider this problem for $$A \in \mathbb{R}^{n \times m}$$:

$$\begin{array}{ll}\min\limits_{{x:\,Ax=b}} c^Tx.\end{array}$$

From linear algebra I know there are three cases to solve $$Ax=b$$:

1. if $$\mathrm{rank}(A)<\mathrm{rank}([A\quad b])$$, which is like putting to many equations that cannot be solved simultaneously, thus in this case no solution.

$$\begin{array}{ll}\min\limits_{{x:\,Ax=b}} c^Tx=+\infty.\end{array}$$

1. if $$\mathrm{rank}(A)=\mathrm{rank}([A\quad b])=m$$, which means the number of variables is equal to number of equations and this equations are independent, thus there exists only one unique $$x=(A^*A)^{-1}A^*b$$.

$$\begin{array}{ll}\min\limits_{{x:\,Ax=b}} c^Tx=c^T(A^*A)^{-1}A^*b.\end{array}$$

1. if $$\mathrm{rank}(A)=\mathrm{rank}([A\quad b]), which means the number of variables is greater then number of equations, thus we have a freedom to choose many variations of $$x$$ to solve $$Ax=b$$. Many solutions $$x$$ exists.

Now, among these $$x$$, I need to find the one that minimizes $$c^Tx$$. I remember from linear algebra class, that among these $$x$$, there is one that minimizes $$||x||_2^2$$ is $$x=A^*(AA^*)^{-1}b$$. Is it the one that I need to minimize $$c^Tx$$? How I can show it?

• I am quite scared of your notation $A \in \mathbb{F}^{n \times m}$, what does this mean? I do not think this notation should be in a linear program as you are defining. – Michael Sep 20 '19 at 4:37
• @Michael maybe I better change it to real numbers – Lee Sep 20 '19 at 4:39
• Unless I am missing something, case 1 and case 3 are defined by the same condition. – Arin Chaudhuri Sep 20 '19 at 4:40
• One way to think about it is that $Ax=b$ has general solution $x=x^*+My$ where $x^*$ is a particular solution (assuming one exists) and $M$ is a matrix with columns that form a basis for $Null(A)$, $y$ is any vector in $\mathbb{R}^k$ (where $k$ is the dimension of $Null(A)$). – Michael Sep 20 '19 at 4:45
• @ArinChaudhuri thanks, I did mistake there – Lee Sep 20 '19 at 4:45

If $$Ax = b$$ has multiple solutions then let $$x_0$$ be any solution.
A general solution is given by $$x = x_0 + n$$ where is $$n$$ is an arbitrary vector in the null space of $$A$$.
If there is a vector $$n$$ in the null space of $$A$$ such that $$c^T n \neq 0$$, assuming without loss of generality $$c^T n > 0$$, then $$x_0 - t n_0$$ is a solution of $$Ax = b$$ for every real $$t > 0$$ and letting $$t \to \infty$$ we see that the value of the objective function tends to $$-\infty$$ , and so the minimum is clearly not attained.
In case $$c^T n = 0$$ for every $$n$$ in the null space of $$A$$ (in this case $$c$$ is in the row space of $$A$$) then clearly objective function takes only one value over the permissible set of values which will be the minimum.
• one question, if we change $Ax=b$ to $Ax\leq b$, the above still must hold since for the convex problem, the optimal $x$ is in the boundary of the constraint, i.e. $Ax=b$. Is it correct? – Lee Sep 20 '19 at 5:42