Μη γραμμικός προγραμματισμός

Στα μαθηματικά, ο μη γραμμικός προγραμματισμός (NLP) είναι η διαδικασία επίλυσης ενός προβλήματος βελτιστοποίησης όπου ορισμένοι από τους περιορισμούς δεν αποτελούν γραμμικές ισότητες ή η αντικειμενική συνάρτηση δεν είναι γραμμική συνάρτηση. Ένα πρόβλημα βελτιστοποίησης είναι ο υπολογισμός των ακρότατων σημείων (μέγιστα, ελάχιστα ή στάσιμα σημεία) μιας συνάρτησης απώλειας σε ένα σύνολο άγνωστων πραγματικών μεταβλητών και υπό την προϋπόθεση της ικανοποίησης ενός συστήματος ισότητας και ανισότητας, που συλλογικά ονομάζονται περιορισμοί. Είναι το υποπεδίο της μαθηματικής βελτιστοποίησης που ασχολείται με προβλήματα που δεν είναι γραμμικά.

Ορισμός και παρουσίαση

Έστω n, m και p θετικοί ακέραιοι αριθμοί. Έστω X ένα υποσύνολο του Rⁿ (συνήθως ένα περιορισμένο σε πλαίσιο), έστω f, g_i και h_j συναρτήσεις πραγματικών τιμών στο X για κάθε i στο {1, ..., m} και κάθε j στο {1, ..., p}, με τουλάχιστον μία από τις f, g_i, και h_j να είναι μη γραμμική.

Ένα πρόβλημα μη γραμμικού προγραμματισμού είναι ένα πρόβλημα βελτιστοποίησης της μορφής

${\begin{aligned}{\text{minimize }}&f(x)\\{\text{subject to }}&g_{i}(x)\leq 0{\text{ for each }}i\in \{1,\dotsc ,m\}\\&h_{j}(x)=0{\text{ for each }}j\in \{1,\dotsc ,p\}\\&x\in X.\end{aligned}}$

Ανάλογα με το σύνολο των περιορισμών, υπάρχουν διάφορες δυνατότητες:

• Εφικτό πρόβλημα είναι εκείνο για το οποίο υπάρχει τουλάχιστον ένα σύνολο τιμών για τις μεταβλητές επιλογής που ικανοποιεί όλους τους περιορισμούς.
• Ένα ανέφικτο πρόβλημα είναι ένα πρόβλημα για το οποίο κανένα σύνολο τιμών για τις μεταβλητές επιλογής δεν ικανοποιεί όλους τους περιορισμούς. Δηλαδή, οι περιορισμοί είναι αμοιβαία αντιφατικοί και δεν υπάρχει λύση- το εφικτό σύνολο είναι το κενό σύνολο.
• Ένα μη φραγμένο πρόβλημα είναι ένα εφικτό πρόβλημα για το οποίο η αντικειμενική συνάρτηση μπορεί να γίνει καλύτερη από οποιαδήποτε δεδομένη πεπερασμένη τιμή. Συνεπώς, δεν υπάρχει βέλτιστη λύση, διότι υπάρχει πάντα μια εφικτή λύση που δίνει καλύτερη τιμή αντικειμενικής συνάρτησης από οποιαδήποτε δεδομένη προτεινόμενη λύση.

Οι περισσότερες ρεαλιστικές εφαρμογές παρουσιάζουν εφικτά προβλήματα, ενώ τα μη φραγμένα ή απεριόριστα προβλήματα θεωρούνται αποτυχία ενός υποκείμενου μοντέλου. Σε ορισμένες περιπτώσεις, τα μη εφικτά προβλήματα αντιμετωπίζονται με την ελαχιστοποίηση ενός αθροίσματος παραβιάσεων εφικτότητας.

Ορισμένες ειδικές περιπτώσεις μη γραμμικού προγραμματισμού έχουν εξειδικευμένες μεθόδους επίλυσης:

• Αν η αντικειμενική συνάρτηση είναι κοίλη (πρόβλημα μεγιστοποίησης), ή κυρτή (πρόβλημα ελαχιστοποίησης) και το σύνολο των περιορισμών είναι κυρτό, τότε το πρόγραμμα ονομάζεται κυρτό και οι γενικές μέθοδοι από τη βελτιστοποίηση κυρτών προβλημάτων μπορούν να χρησιμοποιηθούν στις περισσότερες περιπτώσεις.
• Εάν η αντικειμενική συνάρτηση είναι τετραγωνική και οι περιορισμοί είναι γραμμικοί, χρησιμοποιούνται τεχνικές τετραγωνικού προγραμματισμού.
• Αν η αντικειμενική συνάρτηση είναι λόγος μιας κοίλης και μιας κυρτής συνάρτησης (στην περίπτωση μεγιστοποίησης) και οι περιορισμοί είναι κυρτοί, τότε το πρόβλημα μπορεί να μετατραπεί σε πρόβλημα κυρτής βελτιστοποίησης με τη χρήση τεχνικών κλασματικού προγραμματισμού.

Εφαρμογή

Ένα τυπικό μη κυρτό πρόβλημα είναι αυτό της βελτιστοποίησης του κόστους μεταφοράς με επιλογή από ένα σύνολο μεθόδων μεταφοράς, μία ή περισσότερες από τις οποίες παρουσιάζουν οικονομίες κλίμακας, με διάφορες συνδεσιμότητες και περιορισμούς χωρητικότητας. Ένα παράδειγμα θα ήταν η μεταφορά προϊόντων πετρελαίου, δεδομένης της επιλογής ή του συνδυασμού αγωγού, σιδηροδρομικού βυτιοφόρου, οδικού βυτιοφόρου, ποτάμιας φορτηγίδας ή παράκτιου δεξαμενόπλοιου. Λόγω του οικονομικού μεγέθους της παρτίδας, οι συναρτήσεις κόστους μπορεί να έχουν ασυνέχειες εκτός από ομαλές μεταβολές.

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

Μέθοδοι επίλυσης ενός γενικού μη γραμμικού προγράμματος

Αναλυτικές μέθοδοι

Υπό προϋποθέσεις διαφοροποίησης και περιορισμών, οι συνθήκες Κάρους-Κουν-Τάκερ (KKT) παρέχουν τις αναγκαίες συνθήκες για να είναι μια λύση βέλτιστη. Εάν ορισμένες από τις συναρτήσεις είναι μη διαφορίσιμες, υπάρχουν υποδιαφορικές εκδοχές των συνθηκών Κάρους-Κουν-Τάκερ (KKT).

Υπό συνθήκες κυρτότητας, οι συνθήκες KKT είναι επαρκείς για ένα παγκόσμιο βέλτιστο. Χωρίς κυρτότητα, οι συνθήκες αυτές είναι επαρκείς μόνο για ένα τοπικό βέλτιστο. Σε ορισμένες περιπτώσεις, ο αριθμός των τοπικών βέλτιστων είναι μικρός και μπορεί κανείς να τα βρει όλα αναλυτικά και να βρει εκείνο για το οποίο η αντικειμενική τιμή είναι η μικρότερη.

Αριθμητικές μέθοδοι

Στις περισσότερες ρεαλιστικές περιπτώσεις, είναι πολύ δύσκολο να επιλυθούν οι συνθήκες KKT αναλυτικά, και έτσι τα προβλήματα επιλύονται με τη χρήση αριθμητικών μεθόδων. Αυτές οι μέθοδοι είναι επαναληπτικές: ξεκινούν με ένα αρχικό σημείο και στη συνέχεια προχωρούν σε σημεία που υποτίθεται ότι είναι πιο κοντά στο βέλτιστο σημείο, χρησιμοποιώντας κάποιον κανόνα ενημέρωσης. Υπάρχουν τρία είδη κανόνων ενημέρωσης:

• Ρουτίνες μηδενικής τάξης - χρησιμοποιούν μόνο τις τιμές της αντικειμενικής συνάρτησης και των συναρτήσεων περιορισμών στο τρέχον σημείο,
• Ρουτίνες πρώτης τάξης - χρησιμοποιούν επίσης τις τιμές των κλίσεων αυτών των συναρτήσεων,
• Ρουτίνες δεύτερης τάξης - χρησιμοποιούν επίσης τις τιμές των Χάσιαν αυτών των συναρτήσεων.

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

Διακλάδωση και οριοθέτηση

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

Εφαρμογές

Υπάρχουν πολυάριθμοι επιλυτές μη γραμμικού προγραμματισμού, συμπεριλαμβανομένου του ελεύθερου υλικού:

• ALGLIB (C++, C#, Java, Python API) υλοποιεί διάφορους επιλύτες μη γραμμικού προγραμματισμού πρώτης τάξης και χωρίς παράγωγα
• NLopt (C/C++ υλοποίηση, με πολυάριθμες διεπαφές, συμπεριλαμβανομένων των Julia, Python, R, MATLAB/Octave), περιλαμβάνει διάφορους επιλύτες μη γραμμικού προγραμματισμού
• SciPy (de facto πρότυπο για την επιστημονική Python) διαθέτει τον επιλύτη scipy.optimize, ο οποίος περιλαμβάνει διάφορους αλγορίθμους μη γραμμικού προγραμματισμού (μηδενικής, πρώτης και δεύτερης τάξης).

• 

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

  IPOPT (υλοποίηση σε C++, με πολυάριθμες διεπαφές, συμπεριλαμβανομένων των C, Φορτράν, Java, AMPL, R, Python κ.λπ.) είναι ένας επιλύτης μεθόδου εσωτερικού σημείου (μηδενικής τάξης και προαιρετικά παραγώγων πρώτης και δεύτερης τάξης).

Αριθμητικά παραδείγματα

2-διάστατο παράδειγμα

Ένα απλό πρόβλημα (που φαίνεται στο διάγραμμα) μπορεί να οριστεί από τους περιορισμούς

${\begin{aligned}x_{1}&\geq 0\\x_{2}&\geq 0\\x_{1}^{2}+x_{2}^{2}&\geq 1\\x_{1}^{2}+x_{2}^{2}&\leq 2\end{aligned}}$

με μια αντικειμενική συνάρτηση προς μεγιστοποίηση

$f(\mathbf {x} )=x_{1}+x_{2}$

όπου x = (x₁, x₂).

Η εφαπτομένη της άνω επιφάνειας με τον περιορισμένο χώρο στο κέντρο αντιπροσωπεύει τη λύση.

3-διάστατο παράδειγμα

Ένα άλλο απλό πρόβλημα (βλέπε διάγραμμα) μπορεί να οριστεί από τους περιορισμούς

${\begin{aligned}x_{1}^{2}-x_{2}^{2}+x_{3}^{2}&\leq 2\\x_{1}^{2}+x_{2}^{2}+x_{3}^{2}&\leq 10\end{aligned}}$

με μια αντικειμενική συνάρτηση προς μεγιστοποίηση

$f(\mathbf {x} )=x_{1}x_{2}+x_{2}x_{3}$

όπου x = (x₁, x₂, x₃).

Εξωτερικοί σύνδεσμοι

• English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
• Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
• Ευκλείδεια Γεωμετρία - Πανελλήνιο Σχολικό Δίκτυο
• Θεωρία ομάδων και Λι αλγεβρών -Εθνικό Αρχείο Διδακτορικών Διατριβών
• Θεωρία Αριθμών και Εφαρμογές
• Υπολογιστική Θεωρία Αριθμών
• Καμπυλότητες και γεωμετρία του Riemann σε διαφορίσιμες πολλαπλότητες Εθνικό Αρχείο Διδακτορικών Διατριβών

Δείτε επίσης

• Θεωρία αριθμών
• Αλγεβρική θεωρία αριθμών
• Φυσικός αριθμός
• Αλγεβρική θεωρία αριθμών
• Μοδιακή αριθμητική
• Θεωρία αναπαραστάσεων
• Μη ευκλείδειες γεωμετρίες
• Άρτιοι και περιττοί αριθμοί
• Ευκλείδειος χώρος
• Πυθαγόρειοι φιλόσοφοι
• Πολλαπλάσιο (μαθηματικά)
• Συνάρτηση μάζας πιθανότητας
• Κατανομή πιθανότητας
• Διακριτός μετασχηματισμός Φουριέ
• Θεμελιώδες θεώρημα αριθμητικής
• Αλγεβρική γεωμετρία
• Στατιστικός πληθυσμός
• Ευκλείδειος χώρος

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

• Luenberger, David G.· Ye, Yinyu (20 Ιουνίου 2008). Linear and Nonlinear Programming. Springer Science & Business Media. ISBN 978-0-387-74503-9. 
• Cottle, Richard· Lemke, Carlton E. (1976). Nonlinear Programming. American Mathematical Soc. ISBN 978-0-8218-1329-4. 
• Luenberger, David G.· Ye, Yinyu (7 Ιουλίου 2008). Linear and Nonlinear Programming. Springer Science & Business Media. ISBN 978-0-387-74502-2. 
• Yuan, Ya-xiang (1 Δεκεμβρίου 2013). Advances in Nonlinear Programming: Proceedings of the 96 International Conference on Nonlinear Programming. Springer Science & Business Media. ISBN 978-1-4613-3335-7. 
• Zörnig, Peter (22 Αυγούστου 2014). Nonlinear Programming: An Introduction. Walter de Gruyter GmbH & Co KG. ISBN 978-3-11-037251-9. 
• Mangasarian, Olvi L. (1 Ιανουαρίου 1994). Nonlinear Programming. SIAM. ISBN 978-0-89871-341-1. 
• Mangasarian, Olvi L.· Meyer, Robert R. (10 Μαΐου 2014). Nonlinear Programming 4: Proceedings of the Nonlinear Programming Symposium 4 Conducted by the Computer Sciences Department at the University of Wisconsin–Madison, July 14-16, 1980. Academic Press. ISBN 978-1-4832-6017-4. 
• Nakayama, Keiko (2024). Eigenvalue Problem and Nonlinear Programming Problem: For Economic Studies. Springer Nature. ISBN 978-981-99-2943-6. 

Παραπομπές

• Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. {ISBN 0-486-43227-0.
• Bazaraa, Mokhtar S. and Shetty, C. M. (1979). Nonlinear programming. Theory and algorithms. John Wiley & Sons. ISBN 0-471-78610-1.
• Bonnans, J. Frédéric· Gilbert, J. Charles· Lemaréchal, Claude· Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects. Universitext (Second revised ed. of translation of 1997 French έκδοση). Berlin: Springer-Verlag. σελίδες xiv+490. doi:10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. MR 2265882. 
• Luenberger, David G.· Ye, Yinyu (2008). Linear and nonlinear programming. International Series in Operations Research & Management Science. 116 (Third έκδοση). New York: Springer. σελίδες xiv+546. ISBN 978-0-387-74502-2. MR 2423726. 
• Nocedal, Jorge and Wright, Stephen J. (1999). Numerical Optimization. Springer. ISBN 0-387-98793-2.
• Jan Brinkhuis and Vladimir Tikhomirov, Optimization: Insights and Applications, 2005, Princeton University Press
• Luiz, Atílio; Richter, Bruce (2014), «Remarks on a conjecture of Barát and Tóth», Electronic Journal of Combinatorics 21 (1): P1.57, doi:10.37236/3396, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p57 .

Πηγές

• Apostol, Thomas M. (1976), Introduction to Analytic Number Theory, New York: Springer, ISBN 0-387-90163-9, https://archive.org/details/introductiontoan00apos_0 
• Conway, John Horton; Guy, Richard K. (1996), The Book of Numbers, New York: Copernicus, ISBN 978-0-387-97993-9 
• Crandall, Richard; Pomerance, Carl (2005), Prime Numbers: A Computational Perspective (2nd έκδοση), Berlin, New York: Springer-Verlag, ISBN 978-0-387-25282-7 
• Singer, I. M.· Thorpe, J. A. (28 Μαΐου 2015). Lecture Notes on Elementary Topology and Geometry. Springer. ISBN 978-1-4615-7347-0. 
• Apostol, Tom M. (29 Ιουνίου 2013). Introduction to Analytic Number Theory. Springer Science & Business Media. ISBN 978-1-4757-5579-4. 
• Miller, P. D. (2006), Applied Asymptotic Analysis, American Mathematical Society, ISBN 9780821840788, https://books.google.com/books?id=KQvqBwAAQBAJ 
• Apostol, Thomas M. (1976), Introduction to Analytic Number Theory, New York: Springer, ISBN 0-387-90163-9, https://archive.org/details/introductiontoan00apos_0