relation programme quadratique et programme linéaire

Question

Considérez le problème de programmation quadratique suivant

$$ \min\limits_{x \in S} f(x) = c^{\text{T}}x + \frac{1}{2}x^{\text{T}}Qx, $$ où $S \subseteq \mathbb{R}^n$ est un ensemble compact convexe, $Q$ est un $n \times n$ matrice symétrique et $c \in \mathbb{R}^n$. Supposer$x^*$est la solution globale du problème ci-dessus. J'ai trouvé sans preuve que$x^*$ est également optimal pour le programme linéaire $\min\limits_{x \in S} \nabla f(x^*)^{\text{T}}x$? Quelqu'un peut-il fournir une preuve? Quelle est l'intuition derrière ce résultat?

Answer 1

J'utiliserai le théorème suivant :

$P$: $\min f(x)$ sujet à $x \in S$

Théorème 1.1 Si $\bar{x}$ est une solution locale au problème $P$, puis $f'(\bar{x};d)\leq 0$ pour toutes les directions possibles $d$ pour $S$ à $\bar{x}$ Pour qui $f'(\bar{x};d)$ existe.

Si $x^*$ est optimal pour le problème quadratique, alors $(c + Q x^*)^Td \leq 0$ pour toutes les directions possibles $d$ à $x^*$. Pour le problème linéaire, une solution$\bar{x}$ est optimal si $(c + Q x^*)^Td \leq 0$ pour toutes les directions possibles $d$ à $\bar{x}$, et il est clair que $\bar{x}=x^*$ satisfait à cette condition.