Direkt zum Inhalt

Lexikon der Mathematik: Kelley, Verfahren von

ein Schnittebenenverfahren zur Lösung allgemeiner konvexer Optimierungsprobleme der Form min cT · x unter den Nebenbedingungen \begin{eqnarray}x\ \epsilon\ M:=\{x|{g}_{i}(x)\le 0,i=1,\mathrm{…},m\}\end{eqnarray} mit konvexen und differenzierbaren Funktionen gi.

Der k-te Schritt des Verfahrens lautet wie folgt: Zunächst finde man ein Polytop Mk mit MMk. Man löse das Problem min cT ·x, xMk und erhalte eine Lösung xk.

Falls xkM, so hat man das Problem gelöst. Andernfalls wähle man eine Nebenbedingunggi mit gi(xk) > 0 aus. Als neue MengeMk+1 betrachte man dann \begin{eqnarray}{M}_{k}\cap \{x\epsilon {{\mathbb{R}}}^{n}|{g}_{i}({x}_{k})+grad{g}_{i}^{T}({x}_{k})\cdot (x-{x}_{k})\le 0\}\end{eqnarray} Die Bedingung MMk+1folgt dabei aus der Konvexität der gi. Die Schnittebene ist also durch die Gleichung \begin{eqnarray}{g}_{i}({x}_{k})+grad{g^{T}_{i}({x}_{k})\cdot (x-{x}_{k})=0\text{}}\end{eqnarray} gegeben. Nun verfahre man analog mit Mk+1.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos