I'm currently studying convex optimization using Boyd & Vandenberghe's textbook. The exercise problem that I'm having trouble with is the exact same as the one here. I'll write it out:
$$\begin{array}{ll} \text{minimize} & c^Tx\\ \text{subject to} & a^Tx \le b\end{array}$$
According to the solution manual, this problem is always feasible and the optimal solution is:
$$p* = \begin{cases}\lambda b\quad (c = a\lambda\quad \text{for some}\ \lambda \le 0) \\ -\infty\quad \text{otherwise} \end{cases}$$
and this is obtained by decomposing vector $c$ into $c = a\lambda + \hat{c}$ where $\hat{c}$ is a vector that is orthogonal to $a$.
I have two question regarding this problem:
How do we know this problem is always feasible? I thought that figuring out the feasibility of an LP was as hard as finding the optimal solution itself?
Why did the author decompose the vector this way? I guess it did lead to the solution but I'm confused about the motivation and intuition behind it.