Suppose we have the following equality-constrained maximization problem in $x \in\mathbb{R}^n$
$$\begin{array}{ll} \text{maximize} & f(x) := c^Tx\\ \text{subject to} & Ax = b\end{array}$$
where $A \in \mathbb{R}^{m \times n}$, $b \in \mathbb{R}^m$ and $c \in\mathbb{R}^n$. Prove that the following are equivalent:
- The maximum feasible value of $f$ is finite;
- All feasible $x$ are optimal solutions;
- $c$ is a linear combination of the rows of $A$;
So far I have proven implications $3 \implies 2$ and $2 \implies 1$. Also I have some idea how to prove $2 \implies 3$. But I have no idea how to prove either $1 \implies 3$ or $1 \implies 2$.
Let's prove that $(1)$ implies $(3)$.
If the maximum feasible value $f$ is finite, then by strong duality, the dual is feasible and attain the same value.
Consider the dual:
$$\min b^Ty$$
s.t $$y^TA=c^T$$
Hence from the dual constraint, we can see that $c^T$ is linear combination of the rows of $A$.
Remark:
If you have no concept of duality, then suppose on the contrary that $c^T$ is not a linear combination of the rows of $A$. Let's decompose $c^T$ as $c_1^T+c_2^T$ where, $c_2 \ne 0$, $Ac_2=0$, $c_1^T$ is linear combianation of the rows of $A$..
Let $x^*$ be the optimal solultion. then $x^*+kc_2$ remains feasible but we can let $c^T(x^*+kc_2)=c^Tx^*+k\|c_2\|^2$, we can let $k\to \infty$ which contradicts optimality of $x^*$.