Wie berechnet man das maximale Ellipsoid in einem bestimmten Polyeder?

Ich stehe vor dem Problem, das Ellipsoid ( ist eine symmetrische positive definitive Matrix) mit maximalem Volumen innerhalb einer konvexen Menge die als eine Menge linearer Ungleichungen . Ich habe verstanden, wie es als konvexes Optimierungsproblem formalisiert wird wie in "Convex Optimization, Stephen Boyd und Lieven Vandenberghe, Cambridge University Press, 2004" [pdf version] angegeben . Mein Ansatz wäre, Innenpunktmethoden zu verwenden und einen Genauigkeitsparameter t> 0 einzuführen$B$$B$$C$$C=\{x| a_i^T x \leq b_i, i=1,\dots,m\}$

$$\min_{B,d}\quad[\log\det B^{-1}]\\ \mbox{s.t.:}\quad ||Ba_i||_2+a_i^Td\leq b_i, \qquad i=1,\dots, m$$ $t>0$und integrieren Sie die Einschränkungen über eine logarithmische Barrierefunktion in das Ziel, wie in Kapitel 11 des obigen Buches erläutert, und versuchen Sie, das resultierende uneingeschränkte Problem \ min_ {B, d} \ quad \ underbrace {\ left [\ log \ det B ^ zu minimieren {-1} - \ frac {1} {t} \ sum_ {i = 1} ^ m \ log (b_i- || Ba_i || _2-a_i ^ Td) \ right]} _ {= f (B, d )}. $$\min_{B,d}\quad \underbrace{\left[\log\det B^{-1} - \frac{1}{t}\sum_{i=1}^m\log(b_i-||Ba_i||_2-a_i^Td)\right]}_{= f(B,d)}.$$ Daher würde ich partielle Ableitungen von $f$ : $$\frac{\partial f}{\partial B} = B^{-1}+\frac{1}{t}\sum_{i=1}^m\left(\frac{\frac{Ba_ia_i^T}{||Ba_i||}}{b_i-||Ba_i||_2-a_i^Td}\right)$$ ist eine Matrix und $$\frac{\partial f}{\partial d}=\frac{1}{t}\sum_{i=1}^m\left(\frac{a_i}{b_i-||Ba_i||_2-a_i^Td}\right)$$ ist ein Vektor. Und dann ausgehend von einem anfänglichen (machbaren) Punkt $(B^0,d^0)$Ich würde die tatsächliche Lösung (B ^ k, d ^ k) iterativ $(B^k,d^k)$gemäß den negativen partiellen Ableitungen aktualisieren : B ^ {k + 1} = B ^ k - s_B \ frac {\ partielles f (B ^ k, d ^ k) } {\ partielles B} \\ d ^ {k + 1} = d ^ k - s_d \ frac {\ partielles f (B ^ k, d ^ k)} {\ partielles d} $$B^{k+1} = B^k - s_B \frac{\partial f(B^k,d^k)}{\partial B}\\ d^{k+1} = d^k - s_d \frac{\partial f(B^k,d^k)}{\partial d}$$ wobei $s_B>0$ und $s_d>0$sind Schrittgrößenparameter, bis ein vordefiniertes Stoppkriterium erfüllt ist. \ Ich bin nicht sicher, ob dies ein korrekter Weg ist, um das Problem zu lösen? Es scheint mir sehr umständlich und nicht sehr elegant. Ich bin kein Experte für Optimierungstechniken und nicht sicher, ob ich alle Inhaltsstoffe (partielle Ableitungen, Innenpunktmethode, uneingeschränkte Minisierung usw.) richtig zusammengesetzt habe. Ich frage mich, wie ein Experte dieses Problem lösen würde. In dem oben erwähnten Buch wurde diese Aufgabe als Beispiel für ein konvexes Problem gezeigt, aber soweit ich sehen kann, wurde ein so expliziter Algorithmus zur Lösung der Aufgabe angegeben. Ich denke zwar, dass Mr. Boyd irgendwo ein Matlab-Skript auf seinen Seiten hat, um die Aufgabe zu lösen, aber ich möchte zuerst die grundlegenden Techniken verstehen, bevor ich einen "Black-Box" -Algorithmus verwende. Es scheint andere Ansätze in " Innenpunkt-Polynomalgorithmen in der konvexen Programmierung; Yurii Nesterov und Arkadii Nemirovskii, SIAM-Studien in angewandter Mathematik; Vol.13, 1994 "und" Über die Komplexität der Approximation des maximal eingeschriebenen Ellipsoids für ein Polytop, Leonid G. Khachiyan und Michael J. Todd, Mathematical Programming 61 (1993), 137-159 ", aber ich verstehe sie nicht, weil Sie sind für mich technisch geschrieben.

Übrigens: Wie sieht das doppelte Problem des ersten Problems aus? Und wie wird es abgeleitet?

Danke im Voraus

Nun, Sie sind auf dem richtigen Weg. Es ist keine Magie, diese Probleme mit Innenpunktmethoden zu lösen. Sie sind iterativer Natur und basieren auf Linearisierungen usw.

Ein typischer Innenpunktalgorithmus für diese Probleme würde jedoch keinen Schritt in Gradientenrichtung machen, sondern auch Informationen zweiter Ordnung berechnen und somit einen Newton-Schritt machen. Daher wird eine Liniensuche entlang der Newton-Richtung durchgeführt, ein optimaler Schritt wird unternommen und die Prozedur wird wiederholt. Nach der Konvergenz (zu einer angemessen definierten Genauigkeit) wird der Barriereparameter (mit einem geeigneten Faktor) verringert und der Vorgang erneut wiederholt.

Damit es in der Praxis funktioniert, müssen Sie sorgfältig überlegen, wie Sie die Parameteraktualisierungen durchführen. In den meisten Fällen führen Sie alles im Primal-Dual-Bereich durch.

Wenn Sie nach albernsdp googeln, finden Sie eine einfache Implementierung eines SDP-Lösers, der im Wesentlichen Beispiel 11.9 implementiert, in der Boyd & Vandenberghe-Referenz, die Sie lesen. Vielleicht ein Anfang für Inspiration (da semidefinite Programmierung eine Verallgemeinerung eines SOCP ist, den Sie lösen, wobei der logdet-Begriff im Ziel vernachlässigt wird, was die Dinge nicht wirklich kompliziert).