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$:
- 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}
- 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}
- if $\mathrm{rank}(A)=\mathrm{rank}([A\quad b])<m$, 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?
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.