relationship quadratic program and linear program

Question

Consider the following quadratic programming problem

$$ \min\limits_{x \in S} f(x) = c^{\text{T}}x + \frac{1}{2}x^{\text{T}}Qx, $$ where $S \subseteq \mathbb{R}^n$ is a convex compact set, $Q$ is an $n \times n$ symmetic matrix and $c \in \mathbb{R}^n$. Suppose $x^*$ is the global solution of the above problem. I have found without proof that $x^*$ is also optimal for the linear program $\min\limits_{x \in S} \nabla f(x^*)^{\text{T}}x$? Can someone please provide a proof? What is the intuition behind this result?

Answer 1

I will use following theorem:

$P$: $\min f(x)$ subject to $x \in S$

Theorem 1.1 If $\bar{x}$ is a local solution to the problem $P$, then $f'(\bar{x};d)\leq 0$ for all feasible directions $d$ for $S$ at $\bar{x}$ for which $f'(\bar{x};d)$ exists.

If $x^*$ is optimal for the quadratic problem, then $(c + Q x^*)^Td \leq 0$ for all feasible directions $d$ at $x^*$. For the linear problem, a solution $\bar{x}$ is optimal if $(c + Q x^*)^Td \leq 0$ for all feasible directions $d$ at $\bar{x}$, and it is clear that $\bar{x}=x^*$ satisfies this condition.