Semidefinite Programmierung - Versionsgeschichte

Simonthewriter01: /* growthexperiments-addlink-summary-summary:2|1|0 */

2024-12-21T13:28:02Z

Linkvorschlag-Funktion: 2 Links hinzugefügt.

← Nächstältere Version		Version vom 21. Dezember 2024, 15:28 Uhr
Zeile 4:		Zeile 4:

	== Problemformulierung ==		== Problemformulierung ==
	Gegeben sei der reelle Vektorraum der reellen, symmetrischen <math> n \times n </math> Matrizen <math> S^n </math> versehen mit dem [[Frobenius-Skalarprodukt]]		Gegeben sei der reelle [[Vektorraum]] der reellen, symmetrischen <math> n \times n </math> Matrizen <math> S^n </math> versehen mit dem [[Frobenius-Skalarprodukt]]
	:<math>\langle A, B \rangle_F = \sum_{i=1}^n \sum_{j=1}^n a_{ij} b_{ij}=\operatorname{tr}(A^T B)=\operatorname{tr}(A B^T)</math>.		:<math>\langle A, B \rangle_F = \sum_{i=1}^n \sum_{j=1}^n a_{ij} b_{ij}=\operatorname{tr}(A^T B)=\operatorname{tr}(A B^T)</math>.

Zeile 58:		Zeile 58:

	=== Als konisches Programm ===		=== Als konisches Programm ===
	Semidefinite Programme sind [[Konisches Programm\|konische Programme]] auf dem Vektorraum der symmetrischen reellen Matrizen versehen mit dem Frobenius-Skalarprodukt und unter Verwendung des Kegels der positiv semidefiniten Matrizen. Der lineare Unterraum des <math> S^n </math> wird in der Normalform durch den Kern der Abbildung <math> L: S^n \mapsto \mathbb{R}^m </math>, also durch die Lösungsmenge der Gleichung <math> L(X)=0 </math>, beschreiben. In der Ungleichungsform mit Schlupfvariable wird der Unterraum durch das Bild der Abbildung <math> L^*: \mathbb{R}^m \mapsto S^n </math> beschrieben.		Semidefinite Programme sind [[Konisches Programm\|konische Programme]] auf dem Vektorraum der symmetrischen reellen Matrizen versehen mit dem Frobenius-Skalarprodukt und unter Verwendung des Kegels der positiv semidefiniten Matrizen. Der lineare Unterraum des <math> S^n </math> wird in der Normalform durch den Kern der Abbildung <math> L: S^n \mapsto \mathbb{R}^m </math>, also durch die [[Lösungsmenge]] der Gleichung <math> L(X)=0 </math>, beschreiben. In der Ungleichungsform mit Schlupfvariable wird der Unterraum durch das Bild der Abbildung <math> L^*: \mathbb{R}^m \mapsto S^n </math> beschrieben.

	=== Spezialfall lineare Programme ===		=== Spezialfall lineare Programme ===

Aka: /* Weblinks */ https

2023-04-10T18:50:33Z

Weblinks: https

← Nächstältere Version		Version vom 10. April 2023, 20:50 Uhr
Zeile 139:		Zeile 139:
	== Weblinks ==		== Weblinks ==
	* {{cite web		* {{cite web
	\| url= ~~http~~://www-user.tu-chemnitz.de/~helmberg/semidef.html		\| url= https://www-user.tu-chemnitz.de/~helmberg/semidef.html
	\| title= Seite mit vielen weiterführenden Links		\| title= Seite mit vielen weiterführenden Links
	\| accessdate= 19. Juli 2008		\| accessdate= 19. Juli 2008

2A02:810D:400:5F48:901C:35A2:D2DD:C658: /* Slater-Bedingung */

2021-05-20T16:39:18Z

Slater-Bedingung

← Nächstältere Version		Version vom 20. Mai 2021, 18:39 Uhr
Zeile 128:		Zeile 128:

	=== Slater-Bedingung ===		=== Slater-Bedingung ===
	Die [[Slater-Bedingung]] ist eine Voraussetzung an das primale Problem, die garantiert, dass [[starke Dualität]] gilt. Sie fordert, dass das Problem einen Punkt besitzt, der die Gleichungsnebenbedingungen erfüllt, und alle Ungleichungsnebenbedingungen strikt erfüllt, dass also <math> f(x) \prec_K 0</math> bzw. <math> f(x) \succ_K 0</math> für mindestens einen Punkt <math> x </math> in allen Ungleichungsnebenbedingungen des Problems gleichzeitig gilt. Da aber <math> X \succ_{S^n_+}0 </math> genau dann gilt, wenn <math> X \in \operatorname{Int}(S^n_+) </math> ist, was wiederum äquivalent dazu ist, dass <math> X </math> eine positiv definite Matrix ist, ist die Slater-~~bedingung~~ für SDPs bereits erfüllt, wenn es eine positiv definite Matrix gibt, welche die Gleichungsnebenbedingungen erfüllt.		Die [[Slater-Bedingung]] ist eine Voraussetzung an das primale Problem, die garantiert, dass [[starke Dualität]] gilt. Sie fordert, dass das Problem einen Punkt besitzt, der die Gleichungsnebenbedingungen erfüllt, und alle Ungleichungsnebenbedingungen strikt erfüllt, dass also <math> f(x) \prec_K 0</math> bzw. <math> f(x) \succ_K 0</math> für mindestens einen Punkt <math> x </math> in allen Ungleichungsnebenbedingungen des Problems gleichzeitig gilt. Da aber <math> X \succ_{S^n_+}0 </math> genau dann gilt, wenn <math> X \in \operatorname{Int}(S^n_+) </math> ist, was wiederum äquivalent dazu ist, dass <math> X </math> eine positiv definite Matrix ist, ist die Slater-Bedingung für SDPs bereits erfüllt, wenn es eine positiv definite Matrix gibt, welche die Gleichungsnebenbedingungen erfüllt.

	== Literatur ==		== Literatur ==

Benji: /* Normalform */ Verb fehlte

2021-04-26T10:52:20Z

Normalform: Verb fehlte

← Nächstältere Version		Version vom 26. April 2021, 12:52 Uhr
Zeile 18:		Zeile 18:
	& \langle{A_i},{X}\rangle_F=b_i & \, \text{ für } i=1, \dots, m		& \langle{A_i},{X}\rangle_F=b_i & \, \text{ für } i=1, \dots, m
	\end{align} </math>		\end{align} </math>
	mit <math> C,X,A_i \in S^n </math> ein '''lineares semidefinites Programm''' oder einfach '''semidefinites Programm''' (kurz SDP) in Normalform. Gesucht wird also eine reelle, symmetrische Matrix <math>X </math>, die positiv semidefinit ist, deren Skalarprodukt mit vorgegebenen Matrizen einen bestimmten Wert annimmt und die maximal bezüglich des Frobenius-Skalarprodukts ist. Manchmal werden auch die <math> m </math> Gleichungsnebenbedingungen zusammengefasst durch eine Lineare Funktion <math> L(X): S^n \mapsto \mathbb{R}^m </math>, die durch		mit <math> C,X,A_i \in S^n </math> ist ein '''lineares semidefinites Programm''' oder einfach '''semidefinites Programm''' (kurz SDP) in Normalform. Gesucht wird also eine reelle, symmetrische Matrix <math>X </math>, die positiv semidefinit ist, deren Skalarprodukt mit vorgegebenen Matrizen einen bestimmten Wert annimmt und die maximal bezüglich des Frobenius-Skalarprodukts ist. Manchmal werden auch die <math> m </math> Gleichungsnebenbedingungen zusammengefasst durch eine Lineare Funktion <math> L(X): S^n \mapsto \mathbb{R}^m </math>, die durch
	:<math> L(X):=		:<math> L(X):=
	\begin{pmatrix}		\begin{pmatrix}

HilberTraum: fmt

2020-07-05T18:08:59Z

fmt

← Nächstältere Version		Version vom 5. Juli 2020, 20:08 Uhr
Zeile 75:		Zeile 75:
	:<math> \begin{align}		:<math> \begin{align}
	\text{Minimiere } & s(X)=\langle{C},{X}\rangle_F &\\		\text{Minimiere } & s(X)=\langle{C},{X}\rangle_F &\\
	\text{unter den Nebenbedingungen } & X \succcurlyeq_{S^n_+} 0 &\, \text{(~~positiv~~ ~~semidefinitheit~~)}\\		\text{unter den Nebenbedingungen } & X \succcurlyeq_{S^n_+} 0 &\, \text{(positive Semidefinitheit)}\\
	& \langle{A_i},{X}\rangle_F=b_i & \, \text{für } i=1, \dots, m		& \langle{A_i},{X}\rangle_F=b_i & \, \text{für } i=1, \dots, m
	\end{align} </math>,		\end{align} </math>,
Zeile 81:		Zeile 81:
	so lässt sich das duale Problem bezüglich der [[Lagrange-Dualität]] wie folgt formulieren. Man formuliert die Gleichungsnebenbedingungen um zu <math> -\langle{A_i},{X}\rangle_F+b_i=0 </math>. Damit erhält man als Lagrange-Funktion		so lässt sich das duale Problem bezüglich der [[Lagrange-Dualität]] wie folgt formulieren. Man formuliert die Gleichungsnebenbedingungen um zu <math> -\langle{A_i},{X}\rangle_F+b_i=0 </math>. Damit erhält man als Lagrange-Funktion
	:<math> L(X,\Lambda, \mu)=\langle{C},{X}\rangle_F + \langle{-X},{\Lambda}\rangle_F +\sum_{i=1}^m \mu_i(-\langle{A_i},{X}\rangle_F+b_i)</math>.		:<math> L(X,\Lambda, \mu)=\langle{C},{X}\rangle_F + \langle{-X},{\Lambda}\rangle_F +\sum_{i=1}^m \mu_i(-\langle{A_i},{X}\rangle_F+b_i)</math>.
	und unter Ausnutzung der [[Selbstdualer Kegel\|Selbstdualität]] des ~~Semidefiniten~~ Kegels das duale Problem		und unter Ausnutzung der [[Selbstdualer Kegel\|Selbstdualität]] des semidefiniten Kegels das duale Problem
	:<math> \begin{align}		:<math> \begin{align}
	\text{Maximiere } & \mu^Tb \\		\text{Maximiere } & \mu^Tb \\

HilberTraum: /* Lagrange-Dualität */ Formulierung

2020-07-05T17:57:46Z

Lagrange-Dualität: Formulierung

← Nächstältere Version		Version vom 5. Juli 2020, 19:57 Uhr
Zeile 79:		Zeile 79:
	\end{align} </math>,		\end{align} </math>,

	so lässt sich das duale Problem bezüglich der [[Lagrange-Dualität]] ~~auf~~ wie folgt formulieren. Man formuliert die Gleichungsnebenbedingungen um ~~als~~ <math> -\langle{A_i},{X}\rangle_F+b_i=0 </math>. Damit erhält man als Lagrange-Funktion		so lässt sich das duale Problem bezüglich der [[Lagrange-Dualität]] wie folgt formulieren. Man formuliert die Gleichungsnebenbedingungen um zu <math> -\langle{A_i},{X}\rangle_F+b_i=0 </math>. Damit erhält man als Lagrange-Funktion
	:<math> L(X,\Lambda, \mu)=\langle{C},{X}\rangle_F + \langle{-X},{\Lambda}\rangle_F +\sum_{i=1}^m \mu_i(-\langle{A_i},{X}\rangle_F+b_i)</math>.		:<math> L(X,\Lambda, \mu)=\langle{C},{X}\rangle_F + \langle{-X},{\Lambda}\rangle_F +\sum_{i=1}^m \mu_i(-\langle{A_i},{X}\rangle_F+b_i)</math>.
	und unter Ausnutzung der [[Selbstdualer Kegel\|Selbstdualität]] des Semidefiniten Kegels das duale Problem		und unter Ausnutzung der [[Selbstdualer Kegel\|Selbstdualität]] des Semidefiniten Kegels das duale Problem

80.108.186.5: /* Lagrange-Dualität */

2020-07-05T09:25:26Z

Lagrange-Dualität

← Nächstältere Version		Version vom 5. Juli 2020, 11:25 Uhr
Zeile 81:		Zeile 81:
	so lässt sich das duale Problem bezüglich der [[Lagrange-Dualität]] auf wie folgt formulieren. Man formuliert die Gleichungsnebenbedingungen um als <math> -\langle{A_i},{X}\rangle_F+b_i=0 </math>. Damit erhält man als Lagrange-Funktion		so lässt sich das duale Problem bezüglich der [[Lagrange-Dualität]] auf wie folgt formulieren. Man formuliert die Gleichungsnebenbedingungen um als <math> -\langle{A_i},{X}\rangle_F+b_i=0 </math>. Damit erhält man als Lagrange-Funktion
	:<math> L(X,\Lambda, \mu)=\langle{C},{X}\rangle_F + \langle{-X},{\Lambda}\rangle_F +\sum_{i=1}^m \mu_i(-\langle{A_i},{X}\rangle_F+b_i)</math>.		:<math> L(X,\Lambda, \mu)=\langle{C},{X}\rangle_F + \langle{-X},{\Lambda}\rangle_F +\sum_{i=1}^m \mu_i(-\langle{A_i},{X}\rangle_F+b_i)</math>.
	und unter Ausnutzung der [[Selbstdualer Kegel\|~~selbstdualität~~]] des Semidefiniten Kegels das duale Problem		und unter Ausnutzung der [[Selbstdualer Kegel\|Selbstdualität]] des Semidefiniten Kegels das duale Problem
	:<math> \begin{align}		:<math> \begin{align}
	\text{Maximiere } & \mu^Tb \\		\text{Maximiere } & \mu^Tb \\

80.108.186.5: /* Lagrange-Dualität */

2020-07-05T09:24:30Z

Lagrange-Dualität

← Nächstältere Version		Version vom 5. Juli 2020, 11:24 Uhr
Zeile 79:		Zeile 79:
	\end{align} </math>,		\end{align} </math>,

	so lässt sich das duale Problem bezüglich der [[Lagrange-Dualität]] auf wie folgt ~~Formulieren~~. Man formuliert die Gleichungsnebenbedingungen um als <math> -\langle{A_i},{X}\rangle_F+b_i=0 </math>. Damit erhält man als Lagrange-Funktion		so lässt sich das duale Problem bezüglich der [[Lagrange-Dualität]] auf wie folgt formulieren. Man formuliert die Gleichungsnebenbedingungen um als <math> -\langle{A_i},{X}\rangle_F+b_i=0 </math>. Damit erhält man als Lagrange-Funktion
	:<math> L(X,\Lambda, \mu)=\langle{C},{X}\rangle_F + \langle{-X},{\Lambda}\rangle_F +\sum_{i=1}^m \mu_i(-\langle{A_i},{X}\rangle_F+b_i)</math>.		:<math> L(X,\Lambda, \mu)=\langle{C},{X}\rangle_F + \langle{-X},{\Lambda}\rangle_F +\sum_{i=1}^m \mu_i(-\langle{A_i},{X}\rangle_F+b_i)</math>.
	und unter Ausnutzung der [[Selbstdualer Kegel\|selbstdualität]] des Semidefiniten Kegels das duale Problem		und unter Ausnutzung der [[Selbstdualer Kegel\|selbstdualität]] des Semidefiniten Kegels das duale Problem

Maxeto0910 am 26. November 2019 um 19:57 Uhr

2019-11-26T19:57:19Z

← Nächstältere Version		Version vom 26. November 2019, 21:57 Uhr
Zeile 1:		Zeile 1:
	In der '''~~Semidefiniten~~ Programmierung''' (SDP, auch '''~~Semidefinite~~ Optimierung''') werden [[Optimierung (Mathematik)\|Optimierungsprobleme]] untersucht, deren Variablen keine Vektoren, sondern [[Symmetrische Matrix\|symmetrische Matrizen]] sind. Als Nebenbedingung wird verlangt, dass diese Matrizen positiv (oder negativ) [[Definitheit\|semidefinit]] sind, woraus sich der Name der Problemstellung ergibt.		In der '''semidefiniten Programmierung''' ('''SDP''', auch '''semidefinite Optimierung''') werden [[Optimierung (Mathematik)\|Optimierungsprobleme]] untersucht, deren Variablen keine Vektoren, sondern [[Symmetrische Matrix\|symmetrische Matrizen]] sind. Als Nebenbedingung wird verlangt, dass diese Matrizen positiv (oder negativ) [[Definitheit\|semidefinit]] sind, woraus sich der Name der Problemstellung ergibt.

	Anwendungen gibt es auf dem Gebiet der [[Approximationstheorie]], der [[Kontrolltheorie]], der [[Kombinatorische Optimierung\|kombinatorischen Optimierung]], der [[Optimal Experimental Design\|optimalen Versuchsplanung]] und in der Technik.		Anwendungen gibt es auf dem Gebiet der [[Approximationstheorie]], der [[Kontrolltheorie]], der [[Kombinatorische Optimierung\|kombinatorischen Optimierung]], der [[Optimal Experimental Design\|optimalen Versuchsplanung]] und in der Technik.

Bejahend: +Kat Normalform

2019-05-17T15:37:06Z

+Kat Normalform

← Nächstältere Version		Version vom 17. Mai 2019, 17:37 Uhr
Zeile 147:		Zeile 147:

	[[Kategorie:Kombinatorische Optimierung]]		[[Kategorie:Kombinatorische Optimierung]]
			[[Kategorie:Normalform]]