lineare Ungleichungen aus Menge

Question

Aufgabe:

Begründen Sie, weshalb die gegebenen Mengen nicht durch lineare Ungeleichungen beschrieben sind und machen Sie dies anschließend!

$$P = \{x\in \R^n: |x_i| \leq 1 , i=1,...,n \} \\ Q = \{x\in \R^n: \sum \limits_{i=1}^{n}|x_i| \leq 1 \}$$

Problem/Ansatz:

Kann mir jemand erklären, warum diese Mengen nicht schon lineare Ungl. sind?

Darf bei linearen Ungleichungen etwa kein Betragszeichen verwendet werden, oder was ist der Grund?

Answer 1

Lineare Ungleichung sind dadurch gekennzeichnet, dass sie eine lineare Funktion enthalten. Die Betragsfunktion ist bekanntlich nicht linear. Deine Beobachtung ist also korrekt.

Die linearen Ungleichungen bekommst du aber, indem du eine Fallunterscheidung machst. Für \(n=2\) betrachte etwa \(x\leq 1\), \(y\leq 1\), \(x\geq -1\) und \(y\geq -1\).

Comments

Danke! Bei zweiten tue ich mich noch ein bisschen schwer. Für n=2 hätten wir zB:

|x| + |y| ≤ 1

Könnte man da mit Quadieren von beiden Seiten vielleicht weiterkommen?

(|x| + |y|)^2 ≤ 1^2

⇔ x^2 + |x||y| + y^2 ≤ 1

⇔ |x||y| ≤ 1 - x^2 - y^2

und dann

xy ≤ 1 - x^2 - y^2

xy ≥ -1 + x^2 + y^2

Würde das stimmen für das zweite im Fall n = 2?

---

Das ist dann wieder nicht linear, weil du quadratische Terme hast.

---

Hast Recht...

viel einfacher ist

x+y ≤ 1

-x-y ≤ 1

-x+y ≤ 1

x-y ≤ 1

Meine Frage wäre jetzt hier nur noch, wie man das allgemein aufschreiben könnte für n beliebig. Beim ersten war es leicht, es zu verallgemeinern, immer zwei Ungl. pro x_i.

---

Arbeite zum Beispiel mit einem Vektor, der die Vorzeichen codiert und rechne dann \(c^Tx\), wobei \(c\in \{-1,1\}^n\).