program kwadratowy relacji i program liniowy

Question

Rozważmy następujący problem programowania kwadratowego

$$ \min\limits_{x \in S} f(x) = c^{\text{T}}x + \frac{1}{2}x^{\text{T}}Qx, $$ gdzie $S \subseteq \mathbb{R}^n$ to zestaw wypukły kompaktowy, $Q$ jest $n \times n$ macierz symetryczna i $c \in \mathbb{R}^n$. Przypuszczać$x^*$jest globalnym rozwiązaniem powyższego problemu. Odkryłem bez dowodu$x^*$ jest również optymalny dla programu liniowego $\min\limits_{x \in S} \nabla f(x^*)^{\text{T}}x$? Czy ktoś może przedstawić dowód? Jaka jest intuicja kryjąca się za tym wynikiem?

Answer 1

Użyję następujące twierdzenie :

$P$: $\min f(x)$ z zastrzeżeniem $x \in S$

Twierdzenie 1.1 Jeśli $\bar{x}$ to lokalne rozwiązanie problemu $P$, następnie $f'(\bar{x};d)\leq 0$ dla wszystkich wykonalnych kierunków $d$ dla $S$ w $\bar{x}$ dla którego $f'(\bar{x};d)$ istnieje.

Jeśli $x^*$ jest więc optymalna dla problemu kwadratowego $(c + Q x^*)^Td \leq 0$ dla wszystkich wykonalnych kierunków $d$ w $x^*$. Rozwiązanie problemu liniowego$\bar{x}$ jest optymalny, jeśli $(c + Q x^*)^Td \leq 0$ dla wszystkich wykonalnych kierunków $d$ w $\bar{x}$i jest to jasne $\bar{x}=x^*$ spełnia ten warunek.