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

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

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

Έστω *n*, *m* και *p* θετικοί ακέραιοι αριθμοί. Έστω *X* ένα υποσύνολο του *R<sup>n</sup>* (συνήθως ένα περιορισμένο σε πλαίσιο), έστω *f*, *g<sub>i</sub>* και *h<sub>j</sub>* συναρτήσεις πραγματικών τιμών στο *X* για κάθε *i* στο {*1*, ..., *m*} και κάθε *j* στο {*1*, ..., *p*}, με τουλάχιστον μία από τις *f*, *g<sub>i</sub>*, και *h<sub>j</sub>* να είναι μη γραμμική.

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

:
\begin{align}
  \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{align}


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

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

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

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

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

## Εφαρμογή

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

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

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

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

Υπό προϋποθέσεις διαφοροποίησης και περιορισμών, οι **συνθήκες Κάρους-Κουν-Τάκερ (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{align}
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{align}

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

f(\mathbf x) = x_1 + x_2

όπου .

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

\begin{align}
x_1^2 - x_2^2 + x_3^2 &\leq 2 \\
x_1^2 + x_2^2 + x_3^2 &\leq 10
\end{align}

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

f(\mathbf x) = x_1 x_2 + x_2 x_3

όπου .

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

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

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

## Παραπομπές

* 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.
* 
* 
* 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
*.

## Πηγές
* 
* 
* 
* 
* 
* 
* 

Κατηγορία:Στοιχειώδη μαθηματικά
Κατηγορία:Αλγόριθμοι και μέθοδοι βελτιστοποίησης
Κατηγορία:Βελτιστοποίηση
Κατηγορία:Περιοχές των μαθηματικών
Κατηγορία:Θεωρία αριθμών