Nykursetningar - yfirlit

Frumvandamli, P, er:

\begin{eqnarray*}
\textrm{min}_{\mathbf{x} \in X} & & f(\mathbf{x}) \\
\textrm{...
...bf{0} \\
\textrm{og} & & \mathbf{g}(\mathbf{x})\leq \mathbf{0},
\end{eqnarray*}


ar sem

$f, g_1, \ldots, g_r, h_1, \ldots, h_m:\mathbf{R}^n \rightarrow
\mathbf{R}$ og $X \subseteq \mathbf{R}^n$.

Nykurvandamli, D, er:

\begin{eqnarray*}
\textrm{max}_{\boldsymbol{\lambda},\boldsymbol{\mu}} & & q(\bo...
...l{\mu}) \\
\textrm{m.t.t.} & & \boldsymbol{\mu} \geq \mathbf{0}
\end{eqnarray*}


ar sem $q(\boldsymbol{\lambda},\boldsymbol{\mu}) := inf \{ f(\mathbf{x})+ \boldsymbol{\...
...hbf{h}(\mathbf{x})+\boldsymbol{\mu}'\mathbf{g}(\mathbf{x}): \mathbf{x} \in X \}$. Falli q er alltaf hvelft (concave).

  1. veika nykursetningin: Ef x er gjaldgengur (feasible) P og $(\boldsymbol{\lambda},\boldsymbol{\mu})$ er gjaldgengt D, er $f(\mathbf{x}) \geq q(\boldsymbol{\lambda},\boldsymbol{\mu})$. Srlagi gildir a ef vi skrifum


    \begin{displaymath}
f^{*}
:=
\textrm{inf}
\{
f(\mathbf{x}) : h(\mathbf{x})=\...
...\mathbf{g}(\mathbf{x})\leq \mathbf{0}, \mathbf{x} \in X \} \\
\end{displaymath}

    og

    \begin{displaymath}
q^*:=
\textrm{sup} \{ q(\boldsymbol{\lambda},\boldsymbol{\mu...
...\in \mathbf{R}^r \\
\boldsymbol{\lambda} \in \mathbf{R}^m \}
\end{displaymath}

    er


    \begin{displaymath}
f^{*} \geq q^*
\end{displaymath}

  2. Ef $\textrm{sup} \{ q(\boldsymbol{\lambda},\boldsymbol{\mu}) :
\boldsymbol{\mu} \g...
...bol{\mu} \in \mathbf{R}^r
\boldsymbol{\lambda} \in \mathbf{R}^m \} = + \infty $, .e. D er takmarka, er engin lausn P.
  3. Ef $\textrm{inf}
\{
f(\mathbf{x}) : h(\mathbf{x})=\mathbf{0},
\mathbf{g}(\mathbf{x})\leq \mathbf{0}, \mathbf{x} \in X \} = - \infty
$, .e. P er takmarka, er $q(\boldsymbol{\lambda},\boldsymbol{\mu}) = - \infty$ fyrir ll $(\boldsymbol{\lambda},\boldsymbol{\mu})$ me $\boldsymbol{\mu} \geq
\mathbf{0}$
  4. Ef x, $\boldsymbol{\lambda}$ og $\boldsymbol{\mu}$ eru gjaldgeng P og D og $f(\mathbf{x})=q(\boldsymbol{\lambda},\boldsymbol{\mu})$, gildir a x er besta lausn P, $(\boldsymbol{\lambda},\boldsymbol{\mu})$ er besta lausn D og $\mu_i
g_i(\mathbf{x}) =0 \quad \forall i$.
  5. Sterka nykursetningin: Ltum X vera kpt mengi, $f, g_1,
\ldots, g_r$ vera kpt fll og h af gerinni h(x)=Ax-b ar sem A er mxn fylki og b er m-vigur (ea mx1-fylki), sem uppfylla a $\mathbf{0} \in \textrm{int}(X)$, og a $\exists
\hat{\mathbf{x}} \in \mathbf{R}^n$ me $g(\hat{\mathbf{x}}) < 0,
h(\hat{\mathbf{x}})=0$. er f* = q*. Ef a auki gildir a lausnin s endanleg og nst $\mathbf{x}^*, \boldsymbol{\lambda}^*$ og $\boldsymbol{\mu}^*$, er $\boldsymbol{\mu^*} \geq \mathbf{0}$ og $\mu_i
g_i(\mathbf{x}) =0 \quad \forall i$.
  6. Gjaldgengir punktar, $\bar{\mathbf{x}}, \bar{\boldsymbol{\lambda}},
\bar{\boldsymbol{\mu}}$ P og D mynda sulpunkt L, .e.

    \begin{displaymath}
L(\mathbf{\bar{x}},\boldsymbol{\lambda},\boldsymbol{\mu})
\...
...symbol{\mu} \in \mathbf{R}^r, \boldsymbol{\mu}
\geq \mathbf{0}
\end{displaymath}

    og v aeins a $\mathbf{\bar{x}}$ s besta lausn P og $\boldsymbol{\bar{\lambda}},\boldsymbol{\bar{\mu}}$ besta lausn D og lausnin er n nykurgjar, .e. uppfyllir f*=q*.
  7. Ef x* uppfyllir $L(\mathbf{x}^*, \boldsymbol{\lambda}^*,\boldsymbol{\mu^*}) =
\textrm{max}_{\mathbf{x}} L(\mathbf{x}, \boldsymbol{\lambda}^*,\boldsymbol{\mu^*})$, ar sem $\boldsymbol{\lambda}^*,\boldsymbol{\mu^*}$ eru besta lausn D, er x* besta lausn P.
Ofangreint hefur veri ea verur sanna eftir v sem urfa ykir.



Gunnar Stefansson: gunnar@hi.is