Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » LGS Berechnung einer Lösung mit nur positiven Einträgen
Druckversion
Druckversion
Autor
Kein bestimmter Bereich J LGS Berechnung einer Lösung mit nur positiven Einträgen
DrRuhe
Junior Letzter Besuch: im letzten Monat
Dabei seit: 20.03.2020
Mitteilungen: 6
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-03-20


Lange Version (TLDR unten):
Ich versuche für ein Projekt einen Generator für Workouts zu bauen. Dabei soll die Anzahl der verschiedenen Übungen berechnet werden und vorher eine Präferenz angelegt werden (das generierte Workout soll z.b. 5 Einheiten Bauch und 4 Einheiten Beine trainieren.).

Dazu sei $M$ die Matrix, die für alle Übungen die Intensitäten der jeweiligen Übungen auf den verschiedenen Bereichen kodiert. Sei $b$ der Vektor der definiert, welche Muskelgruppen wie sehr beantsprucht werden sollen.

Gesucht ist nun der Vektor $x$, welcher (wenn berechnet) aussagt, wie häufig jede Übung vorkommen soll.

Meine erste Idee war nun, da $Mx=b$ evtl garkeine Lösung hat, per Normalengleichung die bestmögliche Lösung zu generieren ($M^TMx = M^Tb$). Jedoch könnte dabei $x$ auch negative Werte enthalten, was für den Kontext eines Workouts keinen Sinn macht.

Sei $f(x)=|Mx-b|$ dazu die "Abstandsfunktion" wie weit die Übungskombination $x$ von dem Wunschworkout entfernt ist.

Nun stellt sich mir die Frage, wie kann ich ein $x$ finden, dass nur positive Einträge enthält, und $f$ minimiert?

Für den Kontext der Anwendung würde auch nur eine Lösung ausreichen. Es muss nicht der Gesamte Lösungsraum berechnet werden. Von daher würde das Problem  auch bestimmt mithilfe von Optimierung mit Nebenbedingung lösbar sein.

Gibt es eine Möglichkeit, mit einer "Einfachen Rechnung" ein solches $x$ zu berechnen, oder benötigt man doch ein Optimierungsverfahren?

Ich bedanke mich schonmal im Vorraus für jegliche Hilfe und Denkanstöße.

TLDR:
Sei $M$ eine $n\times m$ Matrix und $b$ ein Vektor wobei $M$ und $b$ nur positive Einträge haben.

Gesucht sei der Vektor $x$ nur mit positiven Einträgen, wobei $|Mx-b|$ möglichst minimal sein soll.

Wie kann ich an $x$ herankommen?




  Profil  Quote  Link auf diesen Beitrag Link
querin
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.01.2018
Mitteilungen: 327
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-03-21


Hallo,

wie würde ein konkretes Zahlenbeispiel aussehen (ohne Interpretation der Übungsarten)?

Es geht um die typische Größe von M, untere und obere Schranken von x und sonstige implizite Bedingungen (wie sie bei einer praktischen Anwendung sicherlich auftreten werden).



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5862
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2020-03-21


Hallo DrRuhe,

en paar Rückfragen.

Die Einträge von x und b haben nur positive Einträge. Oder meinst du nicht-negativ, also darf auch 0 als Eintrag vorkommen? Sind die Einträge von x und b ganzzahlig? Wie sieht es mit den Einträgen von M aus?

Wie ist der Abstand definiert?
\(|a|=\sqrt{\sum a_i^2}\) oder \(|a|=\sum|a_i|\) oder \(|a|=\max\{|a_i|\}\)?



  Profil  Quote  Link auf diesen Beitrag Link
DrRuhe
Junior Letzter Besuch: im letzten Monat
Dabei seit: 20.03.2020
Mitteilungen: 6
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2020-03-21


Hi,
danke ersteinmal für die Rückmeldungen!

2020-03-21 13:31 - querin in Beitrag No. 1 schreibt:
wie würde ein konkretes Zahlenbeispiel aussehen (ohne Interpretation der Übungsarten)?
Es geht um die typische Größe von M, untere und obere Schranken von x und sonstige implizite Bedingungen (wie sie bei einer praktischen Anwendung sicherlich auftreten werden).

In erster Linie werden in M und b Verhältnisse festgehalten. Sprich welche Zahlen nun in M stehen ist an sich unwichtig, jedoch sind die Größenverhältnisse entscheidend (Es können durch M aussagen getroffen werden, wie: Ein Liegestütz ist etwas weniger Bauchintensiv als ein Plank).

2020-03-21 14:01 - StrgAltEntf in Beitrag No. 2 schreibt:

Die Einträge von x und b haben nur positive Einträge. Oder meinst du nicht-negativ, also darf auch 0 als Eintrag vorkommen?


Ich meine nicht-negativ. Es kann natürlich sein, dass eine Übung 0 mal im Workout vorkommt. Genauso sind die Einträge aus M auch nicht-negativ.

2020-03-21 14:01 - StrgAltEntf in Beitrag No. 2 schreibt:

Sind die Einträge von x und b ganzzahlig? Wie sieht es mit den Einträgen von M aus?

Die Einträge von x und b müssen nicht zwingend ganzzahlig sein. Für das resultierende Workout könnte man auch x runden (das sollte in der Anwendung nur minimal schlechten Nebenwirkungen haben. Wenn man allerdings ein Optimierungsverfahren wählt, so wäre es natürlich sinnvoll, wenn x in jedem Iterationsschritt nur aus Natürliche Zahlen besteht).

2020-03-21 14:01 - StrgAltEntf in Beitrag No. 2 schreibt:
Wie ist der Abstand definiert?
\(|a|=\sqrt{\sum a_i^2}\) oder \(|a|=\sum|a_i|\) oder \(|a|=\max\{|a_i|\}\)?

Ich denke \(|a|=\sqrt{\sum a_i^2}\) würde für den Kontext am meisten Sinn machen.

 

Um ein Konkretes Beispiel zu geben:
fed-Code einblenden






  Profil  Quote  Link auf diesen Beitrag Link
querin
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.01.2018
Mitteilungen: 327
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-03-21


Für dieses Beispiel gibt es auch exakte Lösungen

$x=\left( \begin{array}{}
2 \\ 4 \\ 3 \\ 0 \\
\end{array}\right)$, $\left( \begin{array}{}
2 \\ 2 \\ 3 \\ 1 \\
\end{array}\right)$ oder $\left( \begin{array}{}
2 \\ 0 \\ 3 \\ 2 \\
\end{array}\right)$.

Mit Größe von M meinte ich die Dimension. Wenn das nur im Bereich einer $10x10$ Matrix bleibt und die Werte von b unter 100 liegen, findet ein einfacher Algorihmus mit Zufallssuche problemlos die optimalen Lösungen (halt ohne "schönen" mathematischen Formalismun).






  Profil  Quote  Link auf diesen Beitrag Link
DrRuhe
Junior Letzter Besuch: im letzten Monat
Dabei seit: 20.03.2020
Mitteilungen: 6
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2020-03-21


Das ist jetzt keine Genaue Aussage, allerdings gibt es ja ca. 30 Muskelgruppen die für Workouts relevant sind und es gibt bestimmt an die 200 verschiedene Übungen. Von daher würde sich wahrscheinlich kein zufälliges Raten anbieten.
Besonders wenn man bedenkt dass es von mobilen Endgeräten berechnet werden soll.



  Profil  Quote  Link auf diesen Beitrag Link
querin
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.01.2018
Mitteilungen: 327
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-03-21


Es ist natürlich kein blindes Raten, sondern eine schrittweise Verbesserung durch lokale Suche, die zu einem lokalen Minimum der Fehlerfunktion führt.

Wenn es ca. 30 Muskelgruppen und 200 Übungen gibt, handelt es sich um ein massiv unterbestimmtes Gleichungssystem von dem nur (irgend)eine Lösung gesucht ist.

Ich würde so vorgehen:
In einem ersten Schritt könnte das Programm (oder der Benutzer) maximal 30 Übungen auswählen. Die restlichen Variablen werden Null gesetzt. Für das reduzierte Gleichungssystem wird eine Näherungslösung (lokales Minimum) bestimmt. Ist das Ergbnis zu schlecht, kann der Vorgang mit einer anderen Übungsauswahl wiederholt werden.




  Profil  Quote  Link auf diesen Beitrag Link
DrRuhe
Junior Letzter Besuch: im letzten Monat
Dabei seit: 20.03.2020
Mitteilungen: 6
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2020-03-21


Gut, dann läuft es wohl auf eine Optimierung hinaus.
Wüsstest du, welches Optimierungsverfahren hier am geeignetsten wäre, oder sollte ich mich an das Optimierungsforum wenden?
Ich würde vermuten ein Gradientenabstiegsverfahren, jedoch kenne ich mich mit Optimierung nur Oberflächlich aus.



  Profil  Quote  Link auf diesen Beitrag Link
querin
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.01.2018
Mitteilungen: 327
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2020-03-22


Aus $M\cdot x=b$ mit nichtnegativen x ergeben sich die oberen Schranken
\[x_k\le \left(\max_j \frac{M_{j,k}}{b_j}\right)^{-1}\] Damit wird der Suchraum eingeschränkt.

Passende Suchbegriffe für dein Problem sind "quadratic programming" bzw. "quadratische Optimierung". In Matlab gibt es die Funktion MINQ zur Lösung solcher Probleme, aber damit kenne ich mich nicht aus. Fragen zu MINQ könntest du im Unterforum Matlab stellen.



  Profil  Quote  Link auf diesen Beitrag Link
DrRuhe
Junior Letzter Besuch: im letzten Monat
Dabei seit: 20.03.2020
Mitteilungen: 6
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2020-03-22


Danke, werde ich mir anschauen.



  Profil  Quote  Link auf diesen Beitrag Link
DrRuhe hat die Antworten auf ihre/seine Frage gesehen.
DrRuhe hat selbst das Ok-Häkchen gesetzt.
DrRuhe wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]