Κυρτές Συναρτήσεις και Κυρτά Σύνολα

Μια κυρτή συνάρτηση $f(x)$ σε ένα διάστημα $I$ είναι τέτοια ώστε για κάθε $x_1, x_2 \in I$ και για όλους τους μη αρνητικούς συντελεστές $w_1, w_2$ με άθροισμα $1$, ισχύει: $$w_1 f(x_1) + w_2 f(x_2) \geq f(w_1 x_1 + w_2 x_2)$$ 

Γεωμετρικά αυτό σημαίνει ότι το γράφημα της $f$ ανάμεσα στα $(x_1, f(x_1))$ και $(x_2, f(x_2))$ βρίσκεται κάτω από την τέμνουσα των στα σημεία αυτά. 

Δύο χρήσιμα στοιχεία: 

1. Μια συνεχής συνάρτηση που ικανοποιεί την παραπάνω ανισότητα για $w_1 = w_2 = 1/2$ είναι κυρτή.  
2. Μια δύο φορές παραγωγίσιμη συνάρτηση $f$ είναι κυρτή αν και μόνο αν $f''(x) \geq 0$ σε όλο το εξεταζόμενο διάστημα. 
3. Η γραφική παράσταση μιας παραγωγίσιμης κυρτής συνάρτησης βρίσκεται πάνω από τις εφαπτομένες της. 

Κυρτό σύνολο

Ένα υποσύνολο $S$ είναι κυρτό αν, για κάθε ζεύγος σημείων $P, Q \in S$, όλα τα σημεία του ευθύγραμμου τμήματος που ενώνει τα $P$ και $Q$ ανήκουν επίσης στο $S$.