hubungan program kuadrat dan program linier

Question

Pertimbangkan masalah pemrograman kuadrat berikut

$$ \min\limits_{x \in S} f(x) = c^{\text{T}}x + \frac{1}{2}x^{\text{T}}Qx, $$ dimana $S \subseteq \mathbb{R}^n$ adalah satu set kompak cembung, $Q$ adalah $n \times n$ matriks simetris dan $c \in \mathbb{R}^n$. Seharusnya$x^*$adalah solusi global dari masalah di atas. Saya telah menemukan tanpa bukti itu$x^*$ juga optimal untuk program linier $\min\limits_{x \in S} \nabla f(x^*)^{\text{T}}x$? Bisakah seseorang memberikan bukti? Apa intuisi di balik hasil ini?

Answer 1

Saya akan menggunakan teorema berikut :

$P$: $\min f(x)$ tunduk pada $x \in S$

Teorema 1.1 Jika $\bar{x}$ adalah solusi lokal untuk masalah tersebut $P$, kemudian $f'(\bar{x};d)\leq 0$ untuk semua arah yang memungkinkan $d$ untuk $S$ di $\bar{x}$ untuk itu $f'(\bar{x};d)$ ada.

Jika $x^*$ optimal untuk masalah kuadrat, lalu $(c + Q x^*)^Td \leq 0$ untuk semua arah yang memungkinkan $d$ di $x^*$. Untuk masalah linier, solusinya$\bar{x}$ optimal jika $(c + Q x^*)^Td \leq 0$ untuk semua arah yang memungkinkan $d$ di $\bar{x}$, dan jelas itu $\bar{x}=x^*$ memenuhi kondisi ini.