programma quadratico di relazione e programma lineare

Question

Considera il seguente problema di programmazione quadratica

$$ \min\limits_{x \in S} f(x) = c^{\text{T}}x + \frac{1}{2}x^{\text{T}}Qx, $$ dove $S \subseteq \mathbb{R}^n$ è un insieme compatto convesso, $Q$ è un $n \times n$ matrice simmetrica e $c \in \mathbb{R}^n$. Supponiamo$x^*$è la soluzione globale del problema di cui sopra. L'ho trovato senza prove$x^*$ è ottimale anche per il programma lineare $\min\limits_{x \in S} \nabla f(x^*)^{\text{T}}x$? Qualcuno può fornire una prova? Qual è l'intuizione alla base di questo risultato?

Answer 1

Userò il seguente teorema :

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

Teorema 1.1 Se $\bar{x}$ è una soluzione locale al problema $P$, poi $f'(\bar{x};d)\leq 0$ per tutte le direzioni possibili $d$ per $S$ a $\bar{x}$ per cui $f'(\bar{x};d)$ esiste.

Se $x^*$ è quindi ottimale per il problema quadratico $(c + Q x^*)^Td \leq 0$ per tutte le direzioni possibili $d$ a $x^*$. Per il problema lineare, una soluzione$\bar{x}$ è ottimale se $(c + Q x^*)^Td \leq 0$ per tutte le direzioni possibili $d$ a $\bar{x}$, ed è chiaro che $\bar{x}=x^*$ soddisfa questa condizione.