Predavanje RAG.3: Newtonov politop

1.4. Newtonov politop

Za lažji zapis bomo uporabljali multiindeksne oznake. Torej za \bar\alpha\in{\mathbb N}_0^n , \bar\alpha=(\alpha_1,\ldots,\alpha_n) , pišemo \bar X^{\bar\alpha}:=X_1^{\alpha_1}\cdots X_n^{\alpha_n} . Hkrati |\bar\alpha|=\sum_{i=1}^n \alpha_i . Tako lahko vsak polinom f\in{\mathbb R}[\bar X] zapišemo kot

\displaystyle f=\sum_{\bar\alpha}f_{\bar\alpha}\bar X^{\bar\alpha},

kjer f_{\bar\alpha}\in{\mathbb R} .

Definicija Naj bo f\in{\mathbb R}[\bar X] .

  1. Množica vseh eksponentov \bar\alpha , katerih pripadajoči koeficient f_{\bar\alpha} polinoma f je neničeln, imenujemo nosilec polinoma f in ga označimo {\rm supp}(f) . Torej:

    \displaystyle {\rm supp}(f)=\{\bar\alpha\in{\mathbb N}_0^n\mid f_{\bar\alpha}\neq 0\}.

  2. Konveksna ogrinjača {\rm supp}(f) je Newtonov politop {\rm New}(f) prirejen f :

    \displaystyle {\rm New}(f)={\rm co}({\rm supp}(f)).

Zgled 1 Za p=2-X_1^2X_2^2+X_1^4X_2^2+X_1^2X_2^4\in{\mathbb R}[X_1,X_2] velja {\rm supp}(f)=\{ (0,0), (2,2), (4,2), (2,4) \} , {\rm New}(f) pa je trikotnik v ravnini {\mathbb R}^2 napet na točke (0,0) , (2,4) in (4,2) .

Izrek 2 (Reznick) Naj bo f\in{\mathbb R}[\bar X]_{\leq 2d} . Potem velja

\displaystyle f\in\sum{\mathbb R}[\bar X]^2 \quad \Leftrightarrow \quad \exists G\succeq 0: \, f=V^tGV,

kjer je V vektor monomov, ki pripadajo točkam iz \frac 12 {\rm New}(f) .

Ekvivalentno: če je f=\sum_i g_i^2 , potem za vsak i velja {\rm New}(g_i)\subseteq \frac 12 {\rm New}(f) .

Zgled 3 Naj bo p=1+X_1^2X_2^2+X_2^2X_3^2+X_3^2X_1^2-4X_1X_2X_3\in{\mathbb R}[X_1,X_2,X_3] .

  1. Velja p|_{{\mathbb R}^3}\geq 0 , saj iz sredine med aritmetično in geometrijsko sredino sledi

    \displaystyle  \frac{1+x_1^2x_2^2+x_2^2x_3^2+x_3^2x_1^2}4\geq \sqrt[4]{1\cdot x_1^2x_2^2\cdot x_2^2x_3^2\cdot x_3^2x_1^2}=|x_1|\, |x_2|\, |x_3|.

    za vsa realna števila x_1,x_2,x_3 .

  2. p\not\in\sum{\mathbb R}[X_1,X_2,X_3]^2 . Poiščimo {\rm supp}(p)=\{(0,0,0),(2,2,0),(0,2,2),(2,0,2),(1,1,1)\} in {\rm New}(p)={\rm co}(\{(0,0,0),(1,1,0),(0,1,1),(1,0,1),(\frac 12,\frac 12, \frac 12)\})= {\rm co}(\{(0,0,0),(1,1,0),(0,1,1),(1,0,1)\}) . Celoštevilske točke te konveksne množice so ravno \{(0,0,0),(1,1,0),(0,1,1),(1,0,1)\} . Vektor V iz Reznickovega izreka je torej V=\begin{bmatrix} 1\\ X_1X_2 \\ X_1X_3 \\ X_2X_3\end{bmatrix} . Sedaj pa ne obstaja matrika G , za katero bi veljalo p=V^tGV , saj npr. monoma X_1X_2X_3 ni mogoče dobiti kot produkt dveh monomov iz V . V posebnem tudi pozitivno semidefinitna matrika G s to lastnostjo ne obstaja. Iz Reznickovega izreka sklepamo p\not\in\sum{\mathbb R}[X_1,X_2,X_3]^2 .

1.5. Linearno programiranje

Linearni program je problem minimiziranja linearne funkcije po politopu. Natančneje, naj bo b\in{\mathbb R}^m , c\in{\mathbb R}^n in A\in{\mathbb R}^{m\times n} . Dopustna rešitev je vsak x\in{\mathbb R}^n_{\geq 0} , za katerega velja Ax\leq b (po komponentah), tj.,

\displaystyle  \begin{array}{ccllcc} a_{11}x_1 & +\cdots+ & a_{1n}x_n & \leq & b_1 \\ \vdots & \ddots & \vdots & & \vdots \\ a_{m1}x_1 & +\cdots+ & a_{mn}x_n & \leq & b_m \end{array}.

Cilj je poiskati med vsemi dopustnimi x takšnega, ki minimizira (ali maksimizira) linearno funkcijo c^tx=c_1x_1+\cdots+c_nx_n . Na kratko lahko pišemo

\displaystyle \min \{ c^tx \mid Ax\leq b, \, x\geq 0\}.

Opomba 4

  1. Če ne predpostavimo, da so naše spremenljivke x nenegativne, lahko x zamenjamo z x=y-z in predpostavimo, da so y,z nenegativne.
  2. Neenakost Ax\geq b je ekvivalentna (-A)x\leq -b .
  3. \max c^t x=- \min (-c)^t x .
  4. Neenakost Ax\leq b lahko zapišemo tudi na sledeč način: Ax+y=b , y\geq 0 .

This entry was posted in Pedagoško delo, Realna algebraična geometrija (FMF), Slovenščina. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s