19.07.11 06:00 Uhr
 12.080
 

Zwanzig Jahre altes mathematisches Problem gelöst

Vor knapp 20 Jahren wurden auf einer Fachkonferenz die sieben wichtigsten mathematische Probleme aus dem Bereich der Optimierung ausgewählt. Einem Team um Professor Pablo Parrilo vom Massachusetts Institute of Technology (MIT) ist es jetzt gelungen, eines dieser bedeutenden Probleme zu lösen.

Es ging dabei um die Konvexität einer beliebigen polynomischen Funktion. Für spezielle Problemstellungen ist es wichtig zu wissen, ob eine Funktion konvex ist. Wenn das der Fall ist, besitzt die Funktion ungeachtet ihrer Variablen ein Minimum, was der optimalen Lösung des jeweiligen Problems entspricht.

Parrilo konnte beweisen, dass die Konvexität einer solchen Funktion nicht effizient bestimmt werden kann, was die Lösung der entsprechenden Probleme erschwert. Für Funktionen mit maximal sechs Variablen kann man jedoch eine andere Eigenschaft heranziehen, die den Zweck ähnlich gut erfüllen kann.


Videoplayer auf dieser Seite ausblenden
WebReporter: alphanova
Rubrik:   Wissenschaft
Schlagworte: Problem, Funktion, Mathe, Optiemierung
Quelle: www.astropage.eu

DAS KÖNNTE DICH AUCH INTERESSIEREN

Islamwissenschaftlerin Lamya Kaddor hält viele Flüchtlinge für frauenfeindlich
Wissenschaftler warnen vor Aussterben der Giraffen
Klimawandel - Touristenattraktionen wie Great Barrier Reef vor dem Aus?

Diese News zu meinen Favoriten hinzufügen Beitrag abgeben

26 User-Kommentare Alle Kommentare öffnen

Kommentar ansehen
19.07.2011 06:00 Uhr von alphanova
 
+31 | -7
 
ANZEIGEN
Beispiele für solche Berechnungen sieht man überall im täglichen Leben, aber meist erst auf den zweiten Blick, zum Beispiel bei der Minimierung des Treibstoffverbrauchs in Abhängigkeit verschiedener anderer Parameter.
Kommentar ansehen
19.07.2011 07:39 Uhr von lina-i
 
+20 | -9
 
ANZEIGEN
Was wurde denn gelöst? Es wurde doch nur erkannt bzw. bewiesen, dass es für das Problem keine Lösung gibt...
Kommentar ansehen
19.07.2011 08:03 Uhr von gugge01
 
+15 | -7
 
ANZEIGEN
Oh Gott nichtlineare Optimierung!! Eines meiner Horrorfächer im Studium. Bei jedem Rechnungsdurchgang mit Stift und Taschenrechner kam immer etwas anderes raus.
Das hatte sich erst gegeben als ich mir einen guten alten Rechenschieber besorgt hatte.

Ach ja wen das MIT behauptet etwas entdeckt oder erfunden zu haben, ist 100% sicher das es irgendwo geklaut wurde.
Kommentar ansehen
19.07.2011 08:06 Uhr von alphanova
 
+20 | -6
 
ANZEIGEN
Problem: kann man einer Funktion vorher "ansehen", ob sie konvex ist oder nicht?
Jetzt wurde bewiesen, dass die Konvexität einer Funktion nicht von vornherein bestimmt werden kann.
Lösung: Nein, man kann einer Funktion nicht vorher ansehen, ob sie konvex ist.

[ nachträglich editiert von alphanova ]
Kommentar ansehen
19.07.2011 08:20 Uhr von dubberle
 
+4 | -0
 
ANZEIGEN
Eine Frage konnte beantwortet werden, aber leider nicht mit der erhofften Antwort. Ähnlich, so fürchte ich, wird unter Informatikern irgendwan P!=NP bewiesen werden.

Trotzdem ist die Antwort hilfreich, denn nun kann man einige Forschung fallen lassen und dafür neue Fragen zu klären versuchen, z.B.: Kann man einer Funktion ansehen, ob man ihre Konvexität bestimmen kann? Wenn das effizient ginge, könnte man wenigstens sagen, ob sich der Aufwand lohnt, es zu versuchen.
Kommentar ansehen
19.07.2011 08:28 Uhr von SClause
 
+4 | -3
 
ANZEIGEN
Gelöst? Wie lina-i schon schreibt: Eigentlich beweist er nur, dass ab 7 Variablen das Problem nicht gelöst werden kann und bis 6 Variablen nur durch eine annähernde Ersatzrechnung.

Also eigentlich ist das Grundproblem damit nicht wirklich gelöst. Da kann man sicher noch nachbessern. (vielleicht in den nächsten 20 Jahren)
Kommentar ansehen
19.07.2011 09:55 Uhr von Ivan Barsukow
 
+10 | -8
 
ANZEIGEN
@lina-i: mal ganz ehrlich: es ist eine news von alphanova. die kann nur richtig sein. er gehört zu den wenigen, bei denen man richtig spaß beim lesen bekommt und das trotz völliger ahnungslosigkeit. und er schafft es sogar das man ohne vorwissen oder große mathematische kenntnisse seine news wirklich versteht.

Mach bitte weiter so Alphanova!
Kommentar ansehen
19.07.2011 10:12 Uhr von Gorli
 
+2 | -0
 
ANZEIGEN
"Also eigentlich ist das Grundproblem damit nicht wirklich gelöst. Da kann man sicher noch nachbessern. (vielleicht in den nächsten 20 Jahren) "


Eine der tollen Eigenschaften der Mathematik ist, dass Beweise absolut und zeitlos sind. Auch in 20 und in 200 Jahren wird man für dieses Problem keine Lösung finden, höchstens eine bessere approximierung für den Fall von weniger als 7 Variabeln.
Kommentar ansehen
19.07.2011 11:20 Uhr von Bassram
 
+1 | -10
 
ANZEIGEN
dafür sollte die regierung mahl 1 miliarde locker machen, so könnten 2 millionen arme Familien eine eigenes haus haben
Kommentar ansehen
19.07.2011 12:24 Uhr von Pommbaerle
 
+1 | -0
 
ANZEIGEN
Was soll das eigentlich ? Ich sehe da Analogie zur Menschheit... es werden Probleme entwickelt die unlösbar sind...
Kommentar ansehen
19.07.2011 13:55 Uhr von puri
 
+1 | -1
 
ANZEIGEN
Das Problem bei den "vermeintlichen" Beweisen aktuell ungelöster Problemstellungen in der Mathematik ist, dass die fünf Leute auf der Welt, die den Beweis verstehen, meistens auch die sind, die ihn verfasst haben...
Kommentar ansehen
19.07.2011 13:59 Uhr von Getirnhumor
 
+6 | -1
 
ANZEIGEN
Die Loesung: hat bestimmt einer beim Putzen an die Tafel gekritzelt.
Kommentar ansehen
19.07.2011 15:09 Uhr von mia_w
 
+3 | -0
 
ANZEIGEN
Ich verstehe kein Wort. Aber für die Schlauen unter uns ist das bestimmt eine lesenswerte News vom alpha. Also +

Gehirntumor: Den hab ich verstanden.lol

[ nachträglich editiert von mia_w ]
Kommentar ansehen
19.07.2011 16:32 Uhr von Gorli
 
+5 | -0
 
ANZEIGEN
@puri: Den Beweis nachzuvollziehen, sprich ihn schwarz auf weiß vor sich zu haben und dann halt zu verstehen ist etwas, was mit etwas Zeit jeder Student kann. Aber es gibt eben nur 5 Leute auf der Welt, die diesen Beweis von sich aus entwickeln können.

Und die Mathehater sollen sich bitte etwas zurückhalten. Nur weil ihr euch nicht für sowas interessiert, ist es nicht weniger bedeutend für die Wissenschaft.
Kommentar ansehen
19.07.2011 19:20 Uhr von lina-i
 
+4 | -3
 
ANZEIGEN
@ Ivan Barsukow: alphanova hat leider öfters schon falsche Informationen bzw. sogar falsche Interpretationen in seine News eingebaut.

Nur verstehen nur die wenigsten seine News und noch weniger hinterfragen sie.
Kommentar ansehen
19.07.2011 19:25 Uhr von cheetah181
 
+2 | -0
 
ANZEIGEN
Endlich mal eine News von alphanova die ich vollständig verstehe! ;)

Also eigentlich wurde bewiesen, dass das Problem genauso schwer ist wie andere Probleme für die man bisher keine effiziente Lösung kennt. (NP-schwere Probleme)

In dem speziellen Fall könnte in 20 oder 200 Jahren also womöglich bewiesen werden, dass P = NP ist und dass das Problem damit doch eine effiziente Lösung hat. Das ist aber eher unwahrscheinlich.

Zum besseren Verständnis der Konvexität: Wäre die Funktion oben nicht konvex, dann könnte es neben dem blauen Minimum noch mindestens ein weiteres geben. Und sowas kann bei der Suche nach dem kleinsten Minimum (kleinster Verbrauch, etc.) stören.

[ nachträglich editiert von cheetah181 ]
Kommentar ansehen
19.07.2011 20:29 Uhr von Floxxor
 
+2 | -0
 
ANZEIGEN
@gugge: "Ach ja wen das MIT behauptet etwas entdeckt oder erfunden zu haben, ist 100% sicher das es irgendwo geklaut wurde. "
Warum? Behauptet dein Prof das, weil er es nie nach da geschafft hat?...Neider, ich hasse sie...
Kommentar ansehen
19.07.2011 21:02 Uhr von Nashira
 
+6 | -2
 
ANZEIGEN
naja lina-i: es fällt aber auch vermutlich nicht nur mir auf, dass du ganz bevorzugt in alphas news angebliche fehler bemängelst und dich dann nicht mehr dazu äußerst, wenn dir andere user beweisen, dass du unrecht hast.^^

abgesehen davon wundert es mich auch, dass bei schrottigen wissenschaftsnews von leerpe oder irving komischerweise nie ein kommentar von dir zu sehen ist, obwohl die von offensichtlichen fehlern oft geradezu strotzen.

it smells...baby.
Kommentar ansehen
19.07.2011 22:11 Uhr von TheRoadrunner
 
+0 | -2
 
ANZEIGEN
Witzig. Es ging nur um polynomische Funktionen.
Natürlich ist die News ohnehin nur populärwissenschaftlich, aber ohne diesen Zusatz ist sie mal vollkommen wertlos.
Und wenn man im letzten Absatz schon noch von dieser "anderen Eigenschaft" spricht, dann sollte man vielleicht auch erwähnen, *was* diese Eigenschaft ist?
Deutlich untertroffen wird das allerdings noch vom (NIcht?)-Checker bei der Wahl der Schlagwörter:
- Mathe ---> Umgangssprache. Das heißt Mathematik!
- OptiEmierung ---> das erste IE tut doch weh!!
Kommentar ansehen
19.07.2011 22:22 Uhr von alphanova
 
+4 | -1
 
ANZEIGEN
@theroadrunner: es steht ja auch in der News, dass es um polynomische Funktionen geht.

mir ging es in der News vorrangig darum, dass man die Konvexität solcher Funktionen nicht von vornherein bestimmen kann. die andere Eigenschaft wird in der Quelle beschrieben.
Kommentar ansehen
19.07.2011 22:33 Uhr von TheRoadrunner
 
+2 | -3
 
ANZEIGEN
tatsächlich. Im zweiten Absatz finde ich im 3. Versuch unter einem Haufen überflüssiger Infos tatsächlich das entscheidende Wort. Und: wenn ich die Quelle lesen muss, um das wesentliche mitzubekommen, ist der Sinn der News verfehlt.
Davon abgesehen ist der zweite Teil des zweiten Absatzes schlicht Unsinn: bei konvexen Funktionen ist das entscheidende nicht, dass sie ein Minimum haben, sondern dass sie an jeder Stelle zu diesem Minimum hin abfallen. Es besteht also insbesondere bei einer Optimierung nicht das Risiko, in ein lokales Minimum zu laufen.
Kommentar ansehen
19.07.2011 23:21 Uhr von mia_w
 
+1 | -0
 
ANZEIGEN
lina-i: Und genau wie die
"Nur verstehen nur die wenigsten seine News"
solltest es du auch halten und nicht hinterfragen. Wenn man auch kein Durchblick hat und von allem keine Ahnung sollte man ganz einfach mal im Kämmerlein bleiben und warten bis es vorbei ist. So unqualifiziertes Gefasel braucht keiner.
Oder glaubst du, dass hier irgendjemand annimmt du hättest das Problem hier oder überhaupt eine News von alpha verstanden? lol

alpha unter mir
Dem kann ich zustimmen.

[ nachträglich editiert von mia_w ]
Kommentar ansehen
19.07.2011 23:22 Uhr von alphanova
 
+2 | -2
 
ANZEIGEN
Den Ottonormalrechnern dürfte es ziemlich egal sein, ob die Funktion an jeder Stelle zum Minimum abfällt. Wichtiger ist (meiner Meinung nach) die Tatsache, dass das Minimum die optimale Lösung eines komplexen Problems darstellt, womit Ottonormalrechner mehr anfangen kann. Ergo kein Unsinn.. darfst aber natürlich bei deiner Meinung bleiben^^
Kommentar ansehen
19.07.2011 23:42 Uhr von cheetah181
 
+2 | -0
 
ANZEIGEN
alphanova: Also das polynomisch ist mir beim ersten Lesen aufgefallen.

Mit der konvexen Funktion muss ich TheRoadrunner aber recht geben: das hätte man besser formulieren können.

Dass es eben NUR dieses eine Minimum gibt ist nämlich schon wichtig (und gleichbedeutend damit, dass die Funktion überall abfällt), da der Ottonormalrechner (hier ist keine Person gemeint oder?^^), wenn er in einem anderen (lokalen) Minimum steckt und alle benachbarten Stellen der Funktion schlechtere Ergebnisse liefern eben nicht wissen kann, ob es die optimale Lösung ist.

http://images.onlinemathe.de/...

[ nachträglich editiert von cheetah181 ]
Kommentar ansehen
20.07.2011 02:29 Uhr von Schwertträger
 
+5 | -1
 
ANZEIGEN
@TheRoadrunner: An genau der Stelle war ich auch gestolpert. Ohne diesen Zusatz bezüglich der konvexen Funktion hätte ich die News nicht verstanden.


@alphanova: SOLCHE Ottonormalverbraucher lesen Deine News nicht bzw. klicken sie gar nicht erst an. Die Bürger, die unter Deiner Leserschaft das Normal stellen, wissen, dass man mit Hilfe von Funktionen und deren Maximalstellen (das muss nicht immer ein Minimum sein) Lösungen für komplexe reale Probleme finden will. Da ist dann die korrekte Definition einer konvexen Funktion schon wichtiger. Das mal am Rande.
(Den Absatz deshalb als Unsinn zu bezeichnen, ist aber seinerseits übertriebener Unsinn).

Refresh |<-- <-   1-25/26   -> -->|
Diese News zu meinen Favoriten hinzufügen Beitrag abgeben


Copyright ©1999-2016 ShortNews GmbH & Co. KG

Die News auf dieser Website werden eigenverantwortlich von Nutzern erstellt. Die Shortnews GmbH & Co. KG nimmt keinen redaktionellen Einfluss auf die Inhalte.

impressum | agb | archiv | usenet | zur mobilen Ansicht
SCHLIESSEN

Willst Du die Seite wirklich verlassen?


DAS KÖNNTE DICH AUCH INTERESSIEREN

USA: Astronaut John Glenn ist tot
Pro Asyl beklagt Kurswechsel der CDU in Flüchtlingspolitik
Jeder zehnte Arbeitnehmer hat nur einen befristeten Job


...oder unseren und keine aktuellen News mehr verpassen?