Beziehung quadratisches Programm und lineares Programm

Question

Betrachten Sie das folgende quadratische Programmierproblem

$$ \min\limits_{x \in S} f(x) = c^{\text{T}}x + \frac{1}{2}x^{\text{T}}Qx, $$ wo $S \subseteq \mathbb{R}^n$ ist ein konvexes kompaktes Set, $Q$ ist ein $n \times n$ symmetische Matrix und $c \in \mathbb{R}^n$. Annehmen$x^*$ist die globale Lösung des oben genannten Problems. Ich habe das ohne Beweis gefunden$x^*$ ist auch optimal für das lineare Programm $\min\limits_{x \in S} \nabla f(x^*)^{\text{T}}x$? Kann jemand bitte einen Beweis vorlegen? Was ist die Intuition hinter diesem Ergebnis?

Answer 1

Ich werde folgenden Satz verwenden :

$P$:: $\min f(x)$ vorbehaltlich $x \in S$

Satz 1.1 Wenn $\bar{x}$ ist eine lokale Lösung für das Problem $P$, dann $f'(\bar{x};d)\leq 0$ für alle möglichen Richtungen $d$ zum $S$ beim $\bar{x}$ für welche $f'(\bar{x};d)$ existiert.

Wenn $x^*$ ist also optimal für das quadratische Problem $(c + Q x^*)^Td \leq 0$ für alle möglichen Richtungen $d$ beim $x^*$. Für das lineare Problem eine Lösung$\bar{x}$ ist optimal wenn $(c + Q x^*)^Td \leq 0$ für alle möglichen Richtungen $d$ beim $\bar{x}$und es ist klar, dass $\bar{x}=x^*$ erfüllt diese Bedingung.