Approximation mit Hilfe einer stückweise linearen Funktion

Question

Es geht um folgendes:

In einem linearen Gleichungssystem soll der Ausdruck x² durch eine stückweise lineare Funktion über f-1 Intervalle zwischen 0 und z approximiert werden.

Die Approximation an sich verstehe ich schon.

Es werden zusätzliche Variablen (y1 bis yf) eingeführt, der Ausdruck x² wird durch (z/(f-1))² y₂ + (2z/(f-1))² *y₃ + ... + z² *y_f in der Zielfunktion ersetzt.

Stammt von:  ( (0*z) / (f-1) )²*y₁ + ( (1*z) / (f-1) )²*y₂ + ... + ( ((f-1) *z) / (f-1) )² *y_f

Außerdem benötigt zusätzliche Nebenbedingungen ( y₁+y₂+....+y_f = 1 und x = (z/(f-1))*y₁ + (2z/(f-1))*y₂ + ... +z*y_f ) . Normalerweise benötigt man auch noch binäre Variablen und zwei zusätzliche Nebenbedingungen.
Allerdings habe ich ein Paper zu diesem Thema in dem steht, dass -(x)² fallend und konvex ist und man deshalb keine binärvariablen benötigt.

Nun ist soweit ich weiß -(x)² nicht konvex und selbst wenn es konvex wäre, verstehe ich nicht warum man deshalb die zusätzlichen Nebenbedingungen weglassen kann.

Comments

(z/f-1)² y₂ + (2z/f-1)² *y₃ + ... + z² *y_f

Erst mal eine Frage: Wie genau kommst du am Schluss auf z² y_f ?

Du hast in den Summanden vorher immer noch  -1 gerechnet vor dem Quadrieren. Wegen Punkt- vor Strichrechnung hast du immer nur f im Nenner angegeben! War das überhaupt so gemeint?

---

Ja da hat sich mir ein kleiner Fehler eingeschlichen, es sollte natürlich (f-1) im Nenner heißen. 

 

 ( (0*z) / (f-1) )²*y₁ + ( (1*z) / (f-1) )²*y₂ + ... + ( ((f-1) *z) / (f-1) )² *y_f 

---

Ich habe oben Klammern eingesetzt; auch noch in einer Zeile weiter unten.

Gemäss üblicher Definition von konvex und konkav ist f(x) = -(x)^2=  -x^2 konkav und g(x) = (-x)^2 konvex.

https://de.wikipedia.org/wiki/Konvexe_und_konkave_Funktionen

---

Ja genau. 

Ich kann ja mal das Paper zitieren:

'Normally, piecewise linear approximations require the introduction of integer variables. However, because  -(x)² is nonincreasing and convex on the interval of interest and we are maximizing, the integer variables are not needed. Thus we can solve the approximation as a linear program. '

Und in dieser Aussage liegt auch mein Problem. Wie kann -(x)² nicht-steigend und konvex sein?

---

Schau mal, wie/ob im Paper convex definiert ist. Das ist teilweise individuell…

Ich zweifle etwas an der mathematischen Strenge des Papers, wenn ich -(x)^2 sehe ohne f(x) = und mit einer Klammer um x.

---

Es wird leider keine Definition bezüglich Konvexität gegeben.
Danke für deine Hilfe.

Answer 1

Antwort mit KI erzeugt

Approximation mit Hilfe einer stückweise linearen Funktion

Die Aufgabe beschäftigt sich mit der Approximation des quadratischen Ausdrucks $x^2$ mittels stückweiser linearer Funktionen, um dieses in einem linearen Gleichungssystem handhabbar zu machen. Durch Einführung weiterer Variablen ($y_1$ bis $y_f$) und Nutzung einer Summe von gewichteten Termen wird versucht, die quadratische Funktion anzunähern.

Form der Annäherung

Ausgehend von der Information, dass die Approximation durch die Summe der Terme

$\left( \frac{0 \cdot z}{f-1} \right)^2 y_1 + \left( \frac{1 \cdot z}{f-1} \right)^2 y_2 + \ldots + \left( \frac{(f-1) \cdot z}{f-1} \right)^2 y_f$

erfolgt, erkennen wir, dass dies eine Methode ist, um $x^2$ in einem bestimmten Bereich (zwischen 0 und $z$) durch stückweise Linearisierung anzunähern. Jeder Term der Summe entspricht einem Segment dieser stückweisen Annäherung. Die Koeffizienten (das sind die Quadrate von Brüchen, die mit $z$ multipliziert werden) geben das Gewicht jedes $y_i$ Terms an, der die Steigung in jedem linearen Segment repräsentiert.

Zwei wichtige zusätzliche Nebenbedingungen sind:

1. $y_1 + y_2 + \ldots + y_f = 1$: Diese Bedingung stellt sicher, dass die Summe der Anteile der Approximation 1 ergibt, was bedeutet, dass $x$ vollständig durch diese Kombination der $y_i$ dargestellt wird.

2. $x = \frac{z}{f-1}y_1 + \frac{2z}{f-1}y_2 + \ldots + zy_f$: Dies gewährleistet eine korrekte Relation zwischen $x$ und den $y_i$, angepasst an die Größe der Intervalle und deren Repräsentation durch $y_i$.

Frage zur Konvexität und den binären Variablen

Sie merkten an, dass in einem Paper erwähnt wird, $-x^2$ sei fallend und konvex und folglich keine binären Variablen erforderlich seien. Hierbei scheint ein Missverständnis vorzuliegen: Die Funktion $-x^2$ ist tatsächlich streng monoton fallend und konkav, nicht konvex. Konvexe Funktionen würden nach unten öffnen (wie $x^2$), während konkave Funktionen (wie $-x^2$) nach oben öffnen.

In Optimierungsproblemen, speziell in der gemischten ganzzahligen linearen Programmierung, werden häufig binäre Variablen eingesetzt, um Entscheidungen (wie das Ein- oder Ausschalten bestimmter Terme) zu modellieren. Wenn eine Funktion konvex ist, ermöglicht ihre Struktur oftmals eine einfachere Formulierung des Optimierungsproblems, da keine lokalen Minima außer dem globalen Minimum existieren. Die Annahme, dass keine binären Variablen nötig sind, weil die Funktion konvex sei, kann also nicht direkt auf $-x^2$ angewendet werden, da diese gerade nicht konvex ist.

Möglicherweise bezieht sich die Aussage im Paper auf eine andere Eigenschaft oder einen spezifischen Kontext innerhalb der untersuchten Problematik, die hier nicht vollständig dargelegt wurde. In Optimierungsproblemen, speziell wenn Nichtlinearitäten oder mehrteilige Funktionen ins Spiel kommen, können die Eigenschaften der Funktion (konkav vs. konvex) und die Gestaltung des Problems (z.B. Verfügbarkeit einer konvexen Hülle) beeinflussen, ob binäre Variablen oder spezielle Lösungsansätze benötigt werden.