Κυρτό σύνολο

Κυρτό (επάνω) και μη κυρτό (κάτω) σύνολο.

Στα μαθηματικά, ένα σύνολο λέγεται κυρτό όταν για οποιαδήποτε δύο σημεία του συνόλου, όλα τα σημεία του ευθύγραμμου τμήματος που τα ενώνει ανήκουν μέσα στο σύνολο.^[1][2][3] Στην αντίθετη περίπτωση, δηλαδή όταν υπάρχουν ζεύγη σημείων των οποίων το ευθύγραμμο τμήμα δεν βρίσκεται ολόκληρο μέσα στο σύνολο, το σύνολο λέγεται μη κυρτό.

Κυρτό είναι το σύνολο της επάνω εικόνας, το οποίο περικλείεται από τη γραμμή. Μη κυρτά είναι η ίδια η γραμμή που περικλείει το κυρτό σύνολο, το εξωτερικό του κυρτού συνόλου, καθώς και το σχήμα της κάτω εικόνας.

Ορισμός

Ένα σύνολο ${\displaystyle S\subseteq \mathbb {R} ^{n}}$ είναι κυρτό αν για κάθε δύο σημεία ${\displaystyle x,y\in S}$, ο κυρτός συνδυασμός τους είναι επίσης στο ${\displaystyle S}$. Ισοδύναμα,

${\displaystyle \forall x,y\in S.\quad \forall \lambda \in [0,1].\quad \lambda \cdot x+(1-\lambda )\cdot y\in S.}$

Παραδείγματα

• Το σύνολο ${\displaystyle \mathbb {R} ^{n}}$ είναι κυρτό.
• Το κενό σύνολο είναι κυρτό.
• Το σύνολο με ένα σημείο είναι κυρτό.
• Κάθε διάστημα ${\displaystyle [a,b]}$ στο ${\displaystyle \mathbb {R} }$ είναι ένα κυρτό σύνολο.

Ιδιότητες

• Η τομή ${\displaystyle n}$ κυρτών συνόλων ${\displaystyle S_{1},\ldots ,S_{n}}$ είναι κυρτό σύνολο.

Απόδειξη

Έστω ${\displaystyle S=S_{1}\cap \ldots \cap S_{n}}$ η τομή των συνόλων. Θεωρούμε ${\displaystyle x,y\in S}$ και ${\displaystyle \lambda \in \mathbb {R} }$. Τότε για κάθε ${\displaystyle 1\leq i\leq n}$, ${\displaystyle x,y\in S_{i}}$ και αφού το ${\displaystyle S_{i}}$ είναι κυρτό έχουμε ότι ${\displaystyle \lambda \cdot x+(1-\lambda )\cdot y\in S_{i}}$, και επομένως, ${\displaystyle \lambda \cdot x+(1-\lambda )\cdot y\in S_{1}\cap \ldots \cap S_{n}=S}$. Συνεπώς, το σύνολο ${\displaystyle S}$ είναι κυρτό.

• Η ένωση δύο κυρτών συνόλων δεν είναι κατά ανάγκη κυρτό σύνολο.

Απόδειξη

Για παράδειγμα, τα διαστήματα ${\displaystyle [0,1]}$ και ${\displaystyle [2,3]}$ είναι κυρτά στο ${\displaystyle \mathbb {R} }$, αλλά η ένωσή τους ${\displaystyle U=[0,1]\cup [2,3]}$ δεν είναι. Για παράδειγμα αν πάρουμε ${\displaystyle x=0}$ και ${\displaystyle y=3}$, τότε για ${\displaystyle \lambda =0.5}$ έχουμε ότι ${\displaystyle 0.5\cdot x+0.5\cdot y=1.5\notin U}$.

Δείτε επίσης

• Κυρτό πολύγωνο

Παραπομπές

1. Γιαννόπουλος, Απόστολος. «Κυρτή ανάλυση: Εισαγωγή» (PDF). Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών. Ανακτήθηκε στις 10 Ιουλίου 2023. 
2. Papadimitriou, Christos H.· Steiglitz, Kenneth (1982). Combinatorial optimization: algorithms and complexity (6η έκδοση). Englewood Cliffs, N.J: Prentice-Hall. ISBN 9780131524620. 
3. Boyd, Stephen· Vandenberghe, Lieven. «Convex Optimization: Convex Sets» (PDF). Stanford University. Ανακτήθηκε στις 10 Ιουλίου 2023.