relación programa cuadrático y programa lineal

Question

Considere el siguiente problema de programación cuadrática

$$ \min\limits_{x \in S} f(x) = c^{\text{T}}x + \frac{1}{2}x^{\text{T}}Qx, $$ dónde $S \subseteq \mathbb{R}^n$ es un conjunto compacto convexo, $Q$ es un $n \times n$ matriz simmética y $c \in \mathbb{R}^n$. Suponer$x^*$es la solución global del problema anterior. He encontrado sin prueba que$x^*$ también es óptimo para el programa lineal $\min\limits_{x \in S} \nabla f(x^*)^{\text{T}}x$? ¿Alguien puede proporcionar una prueba? ¿Cuál es la intuición detrás de este resultado?

Answer 1

Usaré el siguiente teorema :

$P$: $\min f(x)$ sujeto a $x \in S$

Teorema 1.1 Si $\bar{x}$ es una solución local al problema $P$, entonces $f'(\bar{x};d)\leq 0$ para todas las direcciones factibles $d$ para $S$ a $\bar{x}$ para cual $f'(\bar{x};d)$ existe.

Si $x^*$ es óptimo para el problema cuadrático, entonces $(c + Q x^*)^Td \leq 0$ para todas las direcciones factibles $d$ a $x^*$. Para el problema lineal, una solución$\bar{x}$ es óptimo si $(c + Q x^*)^Td \leq 0$ para todas las direcciones factibles $d$ a $\bar{x}$, y está claro que $\bar{x}=x^*$ satisface esta condición.