|
|
|
Wie löse ich am besten ein lineares Optimierungsproblem? |
|
| clustering_n00b |
Forum-Century
|
 |
Beiträge: 129
|
|
|
|
Anmeldedatum: 05.09.11
|
|
|
|
Wohnort: ---
|
|
|
|
Version: R2011a, R2012b
|
|
|
|
 |
|
Verfasst am: 25.11.2012, 11:13
Titel: Wie löse ich am besten ein lineares Optimierungsproblem?
|
 |
| |
 |
 |
Hi zusammen! 
Ich beschäftige mich gerade mit einer einfachen Aufgabe im Bereich lineare Optimierung.
Nehmen wir an, dass sich eine Bildmatrix I aufspalten lässt in das Produkt zweier Matrizen A und B.
Nun sieht man schon, dass es mehrere mögliche Lösungen für A und B gibt, denn A' = k*A und B' = B/k ergeben das genau gleiche Bild I, wobei k eine skalare Konstante ist.
Die Problemstellung lautet folgendermassen:
| Zitat: |
Jetzt habe ich ein A', B', A und B gegeben und möchte A' und B' so nahe an A und B haben wie möglich.
Es ergeben sich also folgende zwei Probleme:
Finde k, so dass
 |
Dabei soll k ungleich 1 sein (triviale Lösung)
Jetzt habe ich mal ein bisschen angefangen hier auszuprobieren.
Ich habe A' und A genommen (beide 222x267x3 Matrizen) und daraus eine Funktion definiert.
Zuerst wollte ich das Minimum grafisch überprüfen. Das hat aber einen Error verursacht:
| Zitat: |
fplot(rfunc, [-10, 10])
Subscripted assignment dimension mismatch.
Error in fplot (line 105)
x = xmin+minstep; y(2, = feval(fun,x,args{4:end});
|
Dann bin ich zum eigentlichen Optimierungsproblem übergegangen, der wieder einen Error ausgegeben hat:
| Zitat: |
[kopt ropt] = fmincon(rfunc, 0, [], [], [], [], 1, inf)
Error using fmincon (line 704)
User supplied objective function must return a scalar value. |
Jetzt habe ich die folgenden Fragen:
1) Welche Visualisierung würdet ihr hier empfehlen (fplot, ezcontour, ezsurf, etc.)?
2) Welche Minimimierungsfunktion eigenet sich hier am besten (fmincon, fminsearch, least-squares Methode, etc.) und wie kann man die Einschränkung 'k ~= 1' einbauen?
Freue mich auf Antworten!
EDIT: Ich habe hier noch ein interessantes LSQ Skript gefunden, mit dem man Lösungspunkte auch grafisch anzeigen kann.
Macht es Sinn, in meiner Aufgabe ein A\b (LSQ) zu lösen?
|
|
|
|
|
|
| MaFam |
Forum-Meister
|
|
Beiträge: 799
|
|
|
|
Anmeldedatum: 02.05.12
|
|
|
|
Wohnort: ---
|
|
|
|
Version: R2009b
|
|
|
|
|
|
|
Verfasst am: 25.11.2012, 13:44
Titel:
|
|
Hallo,
so macht das gesamte Vorgehen erstmal keinen Sinn. Worin liegt überhaupt die Motivation I in ein Produkt aus A und B zu zerlegen. Warum nicht I=A+B?
Grüße, Marc
|
|
|
|
| clustering_n00b |
Themenstarter
Forum-Century
|
|
Beiträge: 129
|
|
|
|
Anmeldedatum: 05.09.11
|
|
|
|
Wohnort: ---
|
|
|
|
Version: R2011a, R2012b
|
|
|
|
|
|
|
Verfasst am: 25.11.2012, 14:13
Titel:
|
|
Hi MaFam!
Naja, das ist schon gegeben - da kann man nix machen.
Ist ja nicht wichtig, wie die Zerlegung stattfindet. Es geht einfach drum ein Gleichungssystem zu lösen.
Zuletzt bearbeitet von clustering_n00b am 25.11.2012, 14:21, insgesamt einmal bearbeitet
|
|
|
|
| MaFam |
Forum-Meister
|
|
Beiträge: 799
|
|
|
|
Anmeldedatum: 02.05.12
|
|
|
|
Wohnort: ---
|
|
|
|
Version: R2009b
|
|
|
|
|
|
|
Verfasst am: 25.11.2012, 14:18
Titel:
|
|
|
Es ist entscheidend, wie die Zerlegung gestaltet werden soll! Kommt A' = k*A und B' = B/k von dir, oder ist das Teil einer Aufgabenstellung? Damit diese Bedingung überhaupt gelten kann, muss A und B bereits gegeben sein und I=A*B erfüllen. Ist das der Fall?
|
|
|
|
| clustering_n00b |
Themenstarter
Forum-Century
|
|
Beiträge: 129
|
|
|
|
Anmeldedatum: 05.09.11
|
|
|
|
Wohnort: ---
|
|
|
|
Version: R2011a, R2012b
|
|
|
|
|
|
|
Verfasst am: 25.11.2012, 14:22
Titel:
|
|
| MaFam hat Folgendes geschrieben: |
| Es ist entscheidend, wie die Zerlegung gestaltet werden soll! Kommt A' = k*A und B' = B/k von dir, oder ist das Teil einer Aufgabenstellung? Damit diese Bedingung überhaupt gelten kann, muss A und B bereits gegeben sein und I=A*B erfüllen. Ist das der Fall? |
Ja, natürlich ist es für die Rechnung entscheidend, aber wie das Bild I aufgebaut ist, kann ich nicht beeinflussen.
Ja, I = A*B ist erfüllt und alle 3 Grössen, sowie A' und B' sind gegeben.
|
|
|
|
| MaFam |
Forum-Meister
|
|
Beiträge: 799
|
|
|
|
Anmeldedatum: 02.05.12
|
|
|
|
Wohnort: ---
|
|
|
|
Version: R2009b
|
|
|
|
|
|
|
Verfasst am: 25.11.2012, 14:35
Titel:
|
|
Gut, dann gilt es jetzt zu klären, was A-A' -> min überhaupt heißen soll. Wie definierst du den Abstand zwischen zwei Matrizen, wobei wir dann auch bei der Fehlermeldung sind: "User supplied objective function must return a scalar value."
Eine Norm würde A-A' auf einen Skalar abbilden. Das muss also zunächst geklärt werden.
|
|
|
|
| clustering_n00b |
Themenstarter
Forum-Century
|
|
Beiträge: 129
|
|
|
|
Anmeldedatum: 05.09.11
|
|
|
|
Wohnort: ---
|
|
|
|
Version: R2011a, R2012b
|
|
|
|
|
|
|
Verfasst am: 25.11.2012, 14:43
Titel:
|
|
| MaFam hat Folgendes geschrieben: |
Gut, dann gilt es jetzt zu klären, was A-A' -> min überhaupt heißen soll. Wie definierst du den Abstand zwischen zwei Matrizen, wobei wir dann auch bei der Fehlermeldung sind: "User supplied objective function must return a scalar value."
Eine Norm würde A-A' auf einen Skalar abbilden. Das muss also zunächst geklärt werden. |
Wie wäre es z.B. mit der Frobeniusnorm? Diese Variante scheint mir am naheliegendsten zu sein.
|
|
|
|
| MaFam |
Forum-Meister
|
|
Beiträge: 799
|
|
|
|
Anmeldedatum: 02.05.12
|
|
|
|
Wohnort: ---
|
|
|
|
Version: R2009b
|
|
|
|
|
|
|
Verfasst am: 26.11.2012, 08:45
Titel:
|
|
|
Ja, diese Norm könnte man verwenden. Sodann würde ich die Zielfunktion aufstellen. Hier böte sich f(k)=norm(A-A')+norm(B-B') an. Mit der Frobeniusnorm wäre allerdings f quadratisch in k und hätte somit ein globales Minimum. Das ist nur interessant, wenn auf einem Gebiet optimiert wird. Daher würde ich die Spektralnorm oder die Maximumsnorm verwenden, wenn auf ganz IR ohne die 0 natürlich optimiert werden soll.
|
|
|
|
| clustering_n00b |
Themenstarter
Forum-Century
|
|
Beiträge: 129
|
|
|
|
Anmeldedatum: 05.09.11
|
|
|
|
Wohnort: ---
|
|
|
|
Version: R2011a, R2012b
|
|
|
|
|
|
|
Verfasst am: 26.11.2012, 09:46
Titel:
|
|
Hi nochmals!
Deine Antwort sein ganz interessant zu sein. Da möchte ich folgendes dazu sagen:
1) Wenn ich norm(X) in MATLAB eingebe, dann wird automatisch die Spektralnorm verwendet, oder (siehe Referenz; Ctrl + F für 'Spektralnorm')? Das scheint der Default zu sein.
Für die Frobeniunorm müsste ich n = norm(X,'fro') eingeben.
2) Ich würde eigentlich noch gerne 2 Gleichungssystem aufstellen, deren Optimalwerte k und k' berechnen, die beiden Funktionen plotten und danach grafisch vergleichen.
3) Wieso meinst du dass die Funktion quadratisch wird?
4) Die Definitionsmenge von k ist eigentlich das ganze Gebiet der reellen Zahlen IR ohne die triviale Lösung k = k' = 1.
|
|
|
|
| MaFam |
Forum-Meister
|
|
Beiträge: 799
|
|
|
|
Anmeldedatum: 02.05.12
|
|
|
|
Wohnort: ---
|
|
|
|
Version: R2009b
|
|
|
|
|
|
|
Verfasst am: 26.11.2012, 10:08
Titel:
|
|
| |
|
|
| clustering_n00b hat Folgendes geschrieben: |
1) Wenn ich norm(X) in MATLAB eingebe, dann wird automatisch die Spektralnorm verwendet, oder (siehe Referenz; Ctrl + F für 'Spektralnorm')? Das scheint der Default zu sein.
Für die Frobeniunorm müsste ich n = norm(X,'fro') eingeben.
|
Ja, die Spektralnorm ist default (gibt's da eigentlich ein gutes deutsches Wort für?).
| clustering_n00b hat Folgendes geschrieben: |
2) Ich würde eigentlich noch gerne 2 Gleichungssystem aufstellen, deren Optimalwerte k und k' berechnen, die beiden Funktionen plotten und danach grafisch vergleichen.
|
Gut, ich hatte das so verstanden, dass k sowohl A-A', als auch B-B' minimieren soll. Das muss im Grund auch gelten, wenn später A'*B' wieder I ergeben soll. Daher verknüpfte ich beide Bedingungen.
| clustering_n00b hat Folgendes geschrieben: |
3) Wieso meinst du dass die Funktion quadratisch wird?
|
Schau' dir die Frobeniusnorm doch mal an. Es ist in der Tat nur lokal quadratisch, aber die Funktion besitzt nur ein globales Minimum. Da 1 eine Lösung ist, wird es keine weiteren Lösungen mehr geben.
| clustering_n00b hat Folgendes geschrieben: |
4) Die Definitionsmenge von k ist eigentlich das ganze Gebiet der reellen Zahlen IR ohne die triviale Lösung k = k' = 1.
|
Die Null muss auch raus, wegen 1/k. Es darf ruhig ganz IR ohne die Null verwendet werden. Auch darf die 1 entfernt werden. Dann führt Optimierung bei Verwendung der Frobeniusnorm allerdings immer betragsmäßig an den Wert, der am nächsten an der 1 liegt. Das führt dann zu zwei Lösungen auf dem Rand der Exklusion (das entfernte Intervall).
|
|
|
|
| clustering_n00b |
Themenstarter
Forum-Century
|
|
Beiträge: 129
|
|
|
|
Anmeldedatum: 05.09.11
|
|
|
|
Wohnort: ---
|
|
|
|
Version: R2011a, R2012b
|
|
|
|
|
|
|
Verfasst am: 26.11.2012, 12:48
Titel:
|
|
| MaFam hat Folgendes geschrieben: |
Gut, ich hatte das so verstanden, dass k sowohl A-A', als auch B-B' minimieren soll. Das muss im Grund auch gelten, wenn später A'*B' wieder I ergeben soll. Daher verknüpfte ich beide Bedingungen.
|
Das soll auch so sein. Ich wollte aber die beiden Lösungsmengen selber vergleichen.
| MaFam hat Folgendes geschrieben: |
Die Null muss auch raus, wegen 1/k. Es darf ruhig ganz IR ohne die Null verwendet werden. Auch darf die 1 entfernt werden. Dann führt Optimierung bei Verwendung der Frobeniusnorm allerdings immer betragsmäßig an den Wert, der am nächsten an der 1 liegt. Das führt dann zu zwei Lösungen auf dem Rand der Exklusion (das entfernte Intervall). |
Achso, da bin ich gespannt auf welches Minimum ich komme und wie die entsprechen Matrizen dann aussehen.
Jetzt noch zur eigentlichen Optimierung:
Etwa so?
|
|
|
|
| MaFam |
Forum-Meister
|
|
Beiträge: 799
|
|
|
|
Anmeldedatum: 02.05.12
|
|
|
|
Wohnort: ---
|
|
|
|
Version: R2009b
|
|
|
|
|
|
|
Verfasst am: 26.11.2012, 16:07
Titel:
|
|
Ich weiß jetzt nicht, warum du k*norm(B-B') schreibst. Das k ist doch schon in B' enthalten?!
Was die Nebenbedingungen betrifft, würde ich mit (...'lb',lb,'ub',ub,...) arbeiten.
|
|
|
|
| clustering_n00b |
Themenstarter
Forum-Century
|
|
Beiträge: 129
|
|
|
|
Anmeldedatum: 05.09.11
|
|
|
|
Wohnort: ---
|
|
|
|
Version: R2011a, R2012b
|
|
|
|
|
|
|
Verfasst am: 26.11.2012, 17:21
Titel:
|
|
| MaFam hat Folgendes geschrieben: |
Ich weiß jetzt nicht, warum du k*norm(B-B') schreibst. Das k ist doch schon in B' enthalten?!
Was die Nebenbedingungen betrifft, würde ich mit (...'lb',lb,'ub',ub,...) arbeiten. |
Nein, das k ist nicht in B' enthalten! Mit dem k wollen wir B' so nahe am B wie möglich bringen. Analog für A.
Ich habe gerade folgendes überlegt:
min 1/2 || k * A' - A ||
min 1/2 || k * B - B' ||
Also ist das neue Problem:
min 1/2 || k * (A' + B) - (A + B') ||
Dies lässt sich in MATLAB mit lsqlin folgendermassen lösen:
Das k, das ich aber bekommen habe, erscheint mir falsch, denn wenn ich die Bilder A, A' und A'*k anschaue, dann hat das k das Bild A' eher verschlechter, als näher am A gebracht.
Gleiches gilt für B.
Wieso funktioniert hier Least-Squares nicht?
|
|
|
|
| clustering_n00b |
Themenstarter
Forum-Century
|
|
Beiträge: 129
|
|
|
|
Anmeldedatum: 05.09.11
|
|
|
|
Wohnort: ---
|
|
|
|
Version: R2011a, R2012b
|
|
|
|
|
|
|
Verfasst am: 26.11.2012, 18:22
Titel:
|
|
| |
|
|
Jetzt habe ich einen neuen Versuch gestartet mit fmincon.
Die Bilder A'*kopt und B'/kopt scheinen nun viel näher an A und B zu sein!
Ich bekomme jedoch einen ganz Haufen an Warnungen, mit denen ich nichts zu anfangen weiss:
Ich habe nun einen neuen Versuch gestartet, und zwar mit fmincon.
| Zitat: |
Warning: To use the default trust-region-reflective algorithm you
must supply the gradient in the objective function and set the
GradObj option to 'on'. FMINCON will use the active-set algorithm
instead. For information on applicable algorithms, see Choosing the
Algorithm in the documentation.
> In fmincon at 516
Warning: Your current settings will run a different algorithm
(interior-point) in a future release.
> In fmincon at 521
Local minimum possible. Constraints satisfied.
fmincon stopped because the predicted change in the objective function
is less than the default value of the function tolerance and constraints
are satisfied to within the default value of the constraint tolerance.
<stopping criteria details>
|
|
|
|
|
| clustering_n00b |
Themenstarter
Forum-Century
|
|
Beiträge: 129
|
|
|
|
Anmeldedatum: 05.09.11
|
|
|
|
Wohnort: ---
|
|
|
|
Version: R2011a, R2012b
|
|
|
|
|
|
|
Verfasst am: 28.11.2012, 10:44
Titel:
|
|
Ich habe dieses Problem nun anders behoben, und zwar habe ich wieder neu angefangen und Old-School-style durchgemacht.
Falls es jemanden interessiert:
Zielfunktion
f(k) = min sum((B_i - 1/k B_i'^2), i)
Nun leiten wir f(k) nach k ab. Das ergibt schlussendlich:
k = sum(B_i'^2, i)/sum(B_i' * B, i)
In MATLAB sieht das folgendermassen aus:
Gruss,
clustering_n00b
|
|
|
|
|
Gehe zu Seite 1, 2 Weiter
|
|
Einstellungen und Berechtigungen
|
|
Du kannst Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
Du kannst Dateien in diesem Forum posten
Du kannst Dateien in diesem Forum herunterladen
|
|
Impressum
| Nutzungsbedingungen
| Datenschutz
| FAQ
|  RSS
Hosted by:
Copyright © 2007 - 2024
goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
|
|
