relacionamento programa quadrático e programa linear

Question

Considere o seguinte problema de programação quadrática

$$ \min\limits_{x \in S} f(x) = c^{\text{T}}x + \frac{1}{2}x^{\text{T}}Qx, $$ Onde $S \subseteq \mathbb{R}^n$ é um conjunto compacto convexo, $Q$ é um $n \times n$ matriz simética e $c \in \mathbb{R}^n$. Suponha$x^*$é a solução global do problema acima. Eu encontrei sem prova que$x^*$ também é ideal para o programa linear $\min\limits_{x \in S} \nabla f(x^*)^{\text{T}}x$? Alguém pode fornecer uma prova? Qual é a intuição por trás desse resultado?

Answer 1

Vou usar o seguinte teorema :

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

Teorema 1.1 Se $\bar{x}$ é uma solução local para o problema $P$, então $f'(\bar{x};d)\leq 0$ para todas as direções possíveis $d$ para $S$ em $\bar{x}$ para qual $f'(\bar{x};d)$ existe.

E se $x^*$ é ideal para o problema quadrático, então $(c + Q x^*)^Td \leq 0$ para todas as direções possíveis $d$ em $x^*$. Para o problema linear, uma solução$\bar{x}$ é ótimo se $(c + Q x^*)^Td \leq 0$ para todas as direções possíveis $d$ em $\bar{x}$, e é claro que $\bar{x}=x^*$ satisfaz esta condição.