ilişki ikinci dereceden program ve doğrusal program

Question

Aşağıdaki ikinci dereceden programlama problemini düşünün

$$ \min\limits_{x \in S} f(x) = c^{\text{T}}x + \frac{1}{2}x^{\text{T}}Qx, $$ nerede $S \subseteq \mathbb{R}^n$ dışbükey kompakt bir settir, $Q$ bir $n \times n$ simetik matris ve $c \in \mathbb{R}^n$. Varsayalım$x^*$yukarıdaki sorunun küresel çözümüdür. Kanıt olmadan buldum$x^*$ doğrusal program için de idealdir $\min\limits_{x \in S} \nabla f(x^*)^{\text{T}}x$? Birisi lütfen bir kanıt sunabilir mi? Bu sonucun arkasındaki sezgi nedir?

Answer 1

Aşağıdaki teoremi kullanacağım :

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

Teorem 1.1 Eğer $\bar{x}$ soruna yerel bir çözümdür $P$, sonra $f'(\bar{x};d)\leq 0$ tüm uygulanabilir talimatlar için $d$ için $S$ -de $\bar{x}$ hangisi için $f'(\bar{x};d)$ var.

Eğer $x^*$ ikinci dereceden problem için idealdir, o zaman $(c + Q x^*)^Td \leq 0$ tüm uygulanabilir talimatlar için $d$ -de $x^*$. Doğrusal problem için bir çözüm$\bar{x}$ optimal ise $(c + Q x^*)^Td \leq 0$ tüm uygulanabilir talimatlar için $d$ -de $\bar{x}$ve açık ki $\bar{x}=x^*$ bu koşulu karşılar.