Ο τετραγωνικός προγραμματισμός είναι μια μέθοδος που χρησιμοποιείται για τη βελτιστοποίηση μιας πολυμεταβλητής τετραγωνικής συνάρτησης που μπορεί ή όχι να είναι γραμμικά περιορισμένη. Πολλά προβλήματα του πραγματικού κόσμου, όπως η βελτιστοποίηση του χαρτοφυλακίου μιας εταιρείας ή η μείωση του κόστους ενός κατασκευαστή, μπορούν να περιγραφούν χρησιμοποιώντας ένα τετραγωνικό πρόγραμμα. Εάν η αντικειμενική συνάρτηση είναι κυρτή, τότε μπορεί να υπάρχει μια εφικτή λύση και μπορεί να επιλυθεί με γνωστούς αλγόριθμους όπως ο αλγόριθμος διευρυμένου απλού. Υπάρχουν μέθοδοι για την επίλυση ορισμένων μη κυρτών τετραγωνικών συναρτήσεων, αλλά είναι πολύπλοκες και δεν είναι άμεσα διαθέσιμες.
Οι τεχνικές μαθηματικής βελτιστοποίησης χρησιμοποιούνται στον τετραγωνικό προγραμματισμό για την ελαχιστοποίηση μιας αντικειμενικής συνάρτησης. Η αντικειμενική συνάρτηση αποτελείται από έναν αριθμό μεταβλητών απόφασης που μπορεί ή όχι να οριοθετούνται. Οι μεταβλητές απόφασης έχουν δυνάμεις 0, 1 ή 2. Η αντικειμενική συνάρτηση μπορεί να υπόκειται σε έναν αριθμό γραμμικών περιορισμών ισότητας και ανισότητας σχετικά με τις μεταβλητές απόφασης. Ένα παράδειγμα τετραγωνικού προγραμματισμού είναι: ελαχιστοποίηση f(x,y) = x2 + 3y2 – 12y + 12 όπου x + y = 6 και x > 0 και y ≥ 0.
Είναι συχνά ενδιαφέρον να χρησιμοποιούμε πολυμεταβλητές τετραγωνικές συναρτήσεις για να περιγράψουμε προβλήματα του πραγματικού κόσμου. Για παράδειγμα, χρησιμοποιώντας τη σύγχρονη θεωρία χαρτοφυλακίου, ένας χρηματοοικονομικός αναλυτής θα προσπαθήσει να βελτιστοποιήσει το χαρτοφυλάκιο μιας εταιρείας επιλέγοντας το ποσοστό των περιουσιακών στοιχείων που ελαχιστοποιούν τον κίνδυνο που σχετίζεται με μια δεδομένη αναμενόμενη απόδοση. Μια τετραγωνική εξίσωση που αποτελείται από βάρη περιουσιακών στοιχείων και τη συσχέτιση μεταξύ των περιουσιακών στοιχείων περιγράφει τη διακύμανση του χαρτοφυλακίου που μπορεί να ελαχιστοποιηθεί χρησιμοποιώντας τετραγωνικό προγραμματισμό. Ένα άλλο παράδειγμα μπορεί να είναι ένας κατασκευαστής που χρησιμοποιεί μια τετραγωνική εξίσωση για να περιγράψει τη σχέση μεταξύ των διαφορετικών ποιοτικών στοιχείων και του κόστους ενός προϊόντος. Ο κατασκευαστής μπορεί να ελαχιστοποιήσει το κόστος διατηρώντας παράλληλα ορισμένα πρότυπα προσθέτοντας γραμμικούς περιορισμούς στο τετραγωνικό πρόγραμμα.
Μία από τις πιο σημαντικές προϋποθέσεις για την επίλυση ενός τετραγωνικού προγράμματος είναι η κυρτότητα της αντικειμενικής εξίσωσης. Η κυρτότητα μιας τετραγωνικής συνάρτησης καθορίζεται από την Έσσια ή τον πίνακα των δεύτερων παραγώγων της. Η συνάρτηση ονομάζεται κυρτή εάν ο πίνακας της Έσσης είναι είτε θετικός οριστικός είτε θετικός ημι-ορισμένος, δηλαδή εάν όλες οι ιδιοτιμές είναι θετικές ή μη αρνητικές αντίστοιχα. Εάν το Hessian είναι θετικό και υπάρχει μια εφικτή λύση, τότε αυτό το τοπικό ελάχιστο είναι μοναδικό και είναι ένα παγκόσμιο ελάχιστο. Εάν το Hessian είναι ημι-θετικό, μια εφικτή λύση μπορεί να μην είναι μοναδική. Οι μη κυρτές τετραγωνικές συναρτήσεις μπορεί να έχουν τοπικά ή καθολικά ελάχιστα, αλλά είναι πιο δύσκολο να προσδιοριστούν.
Υπάρχουν πολλές προσεγγίσεις για την επίλυση μιας κυρτής τετραγωνικής συνάρτησης χρησιμοποιώντας τετραγωνικό προγραμματισμό. Η πιο κοινή προσέγγιση είναι η επέκταση του απλού αλγορίθμου. Ορισμένες άλλες μέθοδοι περιλαμβάνουν τη μέθοδο εσωτερικού σημείου ή φραγμού, τη μέθοδο ενεργού συνόλου και τη μέθοδο συζυγούς κλίσης. Αυτές οι μέθοδοι είναι ενσωματωμένες σε ορισμένα προγράμματα όπως το Mathematica® και το Matlab® και είναι διαθέσιμες σε βιβλιοθήκες για πολλές γλώσσες προγραμματισμού.