Proving necessity of a condition for minimum of a convex function

Question

Let $f:\mathbb{R}^n \rightarrow \mathbb{R}$ be a convex function and $C \subseteq \mathbb{R}^n$ be a convex set. Consider the problem of minimizing $f(x)$ subject to $x \in C$, and let $x^\star$ denote the solution to this minimization problem. How can I prove that there exist no $g, z \in \mathbb{R}^n$ such that the following equations $$\begin{cases}f(y)\geq f(x^\star)+g^T(y-x^\star),~\forall y \in C\\ g^T(z-x^\star)<0\end{cases}$$ hold together ?

Answer 1

You want to find a contradiction if your assumptions that $x^*$ is a solution and there existed $g,z$ such that your equations held.

Consider $$f(x^*) \geq f(y) + g^T(x^*-y),\quad \forall y \in C \tag{1}$$ and $$g^T(y-x^*) < 0 \tag{2}$$ Then we have $c := g^T(x^*-y) > 0$ so that by $(1)$, we have $$f(x^*) \geq f(y) + c \tag{3} \iff f(x^*) - c \geq f(y)$$ which means that $y$ is a "better" point than $x^*$ because we have $f(y) < f(x^*)$ now.