Linear programming, convex analysis

Question

Hello, I'm having trouble for doing this demonstration, I think that this is true because all the optimal solutions are in the boundary, but I don't know how to proceed. Thanks

Answer 1

Let $\mathbf{x} \in S$ be an optimal solution. Let $d > 0$ be the distance from $\mathbf{x}$ to the boundary of $S$. (This distance is the infimum of the distances from $\mathbf{x}$ to all the points on the boundary. The parenthetical in the problem statement shows that $d> 0$.) By our choice of $d$, the open ball, $U$, of radius $d/2$ centered at $\mathbf{x}$ is also in $S$, $\mathbf{x} \in U \subset S$. Since $\mathbf{c} \neq 0$, $\mathbf{y} = \mathbf{x} + \frac{d}{3} \cdot \frac{\mathbf{c}}{||\mathbf{c}||}$ has $$ \mathbf{c}\mathbf{y} = \mathbf{c}\mathbf{x} + \frac{d}{3} \sqrt{||\mathbf{c}||} > \mathbf{c} \mathbf{x} $$ and $$ |\mathbf{y} - \mathbf{x}| = \left| \frac{d}{3} \cdot \frac{\mathbf{c}}{||\mathbf{c}||} \right| = \frac{d}{3} < \frac{d}{2} \text{,} $$ so $\mathbf{y} \in U \subset{S}$. This contradicts that $\mathbf{x}$ is optimal in $S$. Therefore, no point of $S$ is optimal.