Nonlinear programming — Μη Γραμμικός Προγραμματισμός

Μη Γραμμικός Προγραμματισμός (ΜΓΠ) — είναι κλάδος του μαθηματικού προγραμματισμού και της επιχειρησιακής έρευνας, ο οποίος ασχολείται με προβλήματα βελτιστοποίησης όπου η αντικειμενική συνάρτηση και/ή τουλάχιστον ένας από τους περιορισμούς είναι μη γραμμικές συναρτήσεις των μεταβλητών απόφασης.

Ο ΜΓΠ αποτελεί γενίκευση του γραμμικού προγραμματισμού και επιτρέπει τη μοντελοποίηση ευρύτερης κατηγορίας πραγματικών συστημάτων και διεργασιών, όπου οι εξαρτήσεις μεταξύ των μεταβλητών δεν είναι αυστηρά αναλογικές (δηλαδή περιγράφονται από καμπύλες και όχι από ευθείες γραμμές).

Αντικείμενο και σκοπός

Ο Μη Γραμμικός Προγραμματισμός χρησιμοποιείται για την εύρεση βέλτιστων λύσεων σε καταστάσεις όπου:

• Η εξάρτηση του στόχου (κέρδους, κόστους, αποδοτικότητας κ.λπ.) από τις ελεγχόμενες παραμέτρους είναι μη γραμμική (π.χ. φθίνουσες αποδόσεις κλίμακας, τετραγωνικά κόστη).
• Οι περιορισμοί στους πόρους ή στις τεχνολογικές διεργασίες περιγράφονται από μη γραμμικές σχέσεις (π.χ. χημικές αντιδράσεις, φυσικοί νόμοι, οικονομικές εξαρτήσεις).

Προβλήματα ΜΓΠ εμφανίζονται σε πολλούς τομείς:

• Μηχανολογικός σχεδιασμός (βελτιστοποίηση κατασκευών, διεργασιών).
• Οικονομία και χρηματοοικονομικά (βελτιστοποίηση χαρτοφυλακίου με εκτίμηση κινδύνου, μοντελοποίηση αγοράς).
• Χημική τεχνολογία (βελτιστοποίηση λειτουργικών συνθηκών αντιδραστήρων).
• Machine Learning (εκπαίδευση νευρωνικών δικτύων, μέθοδος διανυσμάτων υποστήριξης).
• Διαχείριση παραγωγικών διεργασιών. Logistics (με εκτίμηση μη γραμμικών κοστών).

Μαθηματική διατύπωση του προβλήματος ΜΓΠ

Το γενικό πρόβλημα μη γραμμικού προγραμματισμού διατυπώνεται ως εξής:

Ζητείται να βρεθεί σύνολο τιμών μεταβλητών απόφασης, το οποίο μεγιστοποιεί ή ελαχιστοποιεί μια μη γραμμική αντικειμενική συνάρτηση. Οι τιμές των μεταβλητών πρέπει να ικανοποιούν σύστημα περιορισμών, οι οποίοι μπορούν να εκφραστούν είτε ως ανισότητες (π.χ. «το μέγεθος Α πρέπει να είναι μικρότερο ή ίσο με το Β»), είτε ως ισότητες (π.χ. «το μέγεθος Γ πρέπει να ισούται ακριβώς με το Δ»). Σημαντικό είναι ότι τουλάχιστον μία από τις συναρτήσεις που περιγράφουν τον στόχο ή τους περιορισμούς είναι μη γραμμική. Συχνά προστίθενται συνθήκες μη αρνητικότητας των μεταβλητών, δηλαδή απαίτηση οι τιμές τους να είναι μεγαλύτερες ή ίσες του μηδενός.

Το σύνολο όλων των συνδυασμών τιμών μεταβλητών που ικανοποιούν τους περιορισμούς αποτελεί την περιοχή εφικτών λύσεων (ΠΕΛ).

Διαφορές από τον γραμμικό προγραμματισμό

Ο Μη Γραμμικός Προγραμματισμός διαφέρει ουσιαστικά από τον Γραμμικό Προγραμματισμό (ΓΠ):

• Μη γραμμικότητα: Η αντικειμενική συνάρτηση ή οι περιορισμοί (ή και τα δύο) περιέχουν μη γραμμικές εξαρτήσεις.
• Ιδιότητες ΠΕΛ: Η περιοχή εφικτών λύσεων στον ΜΓΠ μπορεί να είναι μη κυρτή (σε αντίθεση με τον ΓΠ, όπου η ΠΕΛ είναι πάντα κυρτό πολύεδρο).
• Ιδιότητες βέλτιστου: Η βέλτιστη λύση στον ΜΓΠ δεν βρίσκεται απαραίτητα σε κορυφή της ΠΕΛ· μπορεί να βρίσκεται στο σύνορο ή στο εσωτερικό της περιοχής. Στον ΜΓΠ μπορούν να υπάρχουν τοπικά βέλτιστα που δεν είναι ολικά.
• Πολυπλοκότητα επίλυσης: Τα προβλήματα ΜΓΠ είναι κατά κανόνα σημαντικά δυσκολότερα στην επίλυση από τα προβλήματα ΓΠ. Δεν υπάρχει ενιαίος καθολικός αλγόριθμος, ανάλογος της simplex μεθόδου, για όλα τα προβλήματα ΜΓΠ.

Κύριες δυσκολίες και προκλήσεις του ΜΓΠ

Η επίλυση προβλημάτων μη γραμμικού προγραμματισμού συνοδεύεται από σειρά δυσκολιών:

• Ύπαρξη τοπικών ακρότατων: Οι περισσότερες μέθοδοι ΜΓΠ εγγυώνται μόνο την εύρεση τοπικού βέλτιστου (λύσης που είναι η καλύτερη σε κάποια γειτονιά). Η εύρεση ολικού βέλτιστου (της καλύτερης λύσης σε όλη την ΠΕΛ) αποτελεί δύσκολο πρόβλημα, ιδίως για μη κυρτά προβλήματα.
• Μη κυρτότητα: Εάν το πρόβλημα δεν είναι κυρτό (η αντικειμενική συνάρτηση ή η ΠΕΛ είναι μη κυρτές), μπορεί να υπάρχουν πολλαπλά τοπικά βέλτιστα και οι τυπικές μέθοδοι κλίσης ενδέχεται να «παγιδευτούν» σε ένα από αυτά.
• Υπολογιστική πολυπλοκότητα: Οι αλγόριθμοι επίλυσης ΜΓΠ απαιτούν συχνά σημαντικά μεγαλύτερους υπολογιστικούς πόρους σε σύγκριση με τον ΓΠ.

Σημαντικές κατηγορίες προβλημάτων ΜΓΠ

Παρά τη γενική πολυπλοκότητα, υπάρχουν σημαντικές υποκατηγορίες προβλημάτων ΜΓΠ για τις οποίες έχουν αναπτυχθεί αποδοτικές μέθοδοι επίλυσης:

• Κυρτός προγραμματισμός: Πρόβλημα ελαχιστοποίησης κυρτής συνάρτησης σε κυρτό σύνολο εφικτών λύσεων (ή μεγιστοποίησης κοίλης συνάρτησης). Βασική ιδιότητα: κάθε τοπικό ελάχιστο είναι επίσης και ολικό ελάχιστο. Αυτό απλοποιεί σημαντικά την αναζήτηση βέλτιστης λύσης.
• Τετραγωνικός προγραμματισμός: Η αντικειμενική συνάρτηση είναι τετραγωνική και όλοι οι περιορισμοί είναι γραμμικοί.
• Διαχωρίσιμος προγραμματισμός: Η αντικειμενική συνάρτηση και οι περιορισμοί μπορούν να αναπαρασταθούν ως αθροίσματα συναρτήσεων, καθεμία από τις οποίες εξαρτάται μόνο από μία μεταβλητή.

Μέθοδοι επίλυσης προβλημάτων ΜΓΠ

Μέθοδοι επίλυσης προβλημάτων μη γραμμικού προγραμματισμού (ΜΓΠ)

Ι. Μέθοδοι βελτιστοποίησης χωρίς περιορισμούς:

• Μέθοδοι κλίσης (μέθοδος απότομης καθόδου, μέθοδος συζυγών κλίσεων);
• Μέθοδος Newton και οιονεί-Newtonian μέθοδοι (π.χ. BFGS);
• Μέθοδοι με χρήση προσέγγισης του Hessian.

ΙΙ. Μέθοδοι βελτιστοποίησης με περιορισμούς:

• Μέθοδοι μετασχηματισμού:
  • Μέθοδος συναρτήσεων ποινής (penalty methods);
  • Μέθοδος συναρτήσεων φραγμού (barrier methods).
• Μέθοδοι άμεσης αναζήτησης κατεύθυνσης:
  • Μέθοδος εφικτών κατευθύνσεων.
• Μέθοδοι βασισμένες σε συνθήκες βελτιστότητας:
  • Μέθοδοι Karush-Kuhn-Tucker (KKT-συνθήκες);
  • Μέθοδος πολλαπλασιαστών Lagrange.
• Επαναληπτικές μέθοδοι:
  • Διαδοχικός τετραγωνικός προγραμματισμός (SQP);
  • Μέθοδοι εσωτερικών σημείων.

ΙΙΙ. Μέθοδοι ολικής βελτιστοποίησης:

• Ευρετικές και μετα-ευρετικές μέθοδοι:
  • Γενετικοί αλγόριθμοι;
  • Προσομοίωση ανόπτησης;
  • Αναζήτηση με απαγορεύσεις (tabu search).
• Ντετερμινιστικές μέθοδοι:
  • Διακλάδωση και φράγματα (branch and bound);
  • Αλγόριθμοι ολικής βελτιστοποίησης για προβλήματα με ειδική δομή.

Βιβλιογραφία

• Bazaraa M., Shetty C. Μη Γραμμικός Προγραμματισμός. Θεωρία και αλγόριθμοι. — Μ.: Mir, 1982.
• Fiacco A., McCormick G. Μη Γραμμικός Προγραμματισμός. Μέθοδοι διαδοχικής άνευ περιορισμών ελαχιστοποίησης. — Μ.: Mir, 1972.
• Himmelblau D. Εφαρμοσμένος μη γραμμικός προγραμματισμός. — Μ.: Mir, 1975.
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. — Springer, 2006. (2nd ed.)

Δείτε επίσης

• Επιχειρησιακή έρευνα
• Βελτιστοποίηση
• Γραμμικός προγραμματισμός
• Κυρτός προγραμματισμός
• Αντικειμενική συνάρτηση
• Περιορισμοί
• Περιοχή εφικτών λύσεων