Διακριτή l1 προσέγγιση υπό αύξουσες αποδόσεις και εφαρμογές σε οικονομικά δεδομένα

Abstract

The problem of convexity runs deeply in economic theory and practice. For example, increasing returns or upward slopes, which provide convexity, and diminishing returns or downward slopes, which provide concavity, of certain supply, demand, production and utility relations are often assumed in economics. Quite frequently, however, the observations have lost convexity or concavity due to errors of the measuring process, occasionally few of them being outliers. We address the question of smoothing the data by minimizing the sum of the moduli of the errors subject to the condition that the second divided differences of the smoothed data are nonnegative, that is, by assuming non-decreasing returns of the changed data. It follows that the best piecewise linear interpolant to the smoothed data is a convex curve, while in short, we address the problem of calculating a best L1 convex fit to the data. This is a linear inequality constrained optimization problem, which can be expressed as a linear programming calculation. In this dissertation we establish optimality conditions for the characterization of the best L1 convex fit, in terms, both of certain parameters that resemble the Karush-Kuhn-Tucker multipliers, when the objective function is replaced by a differentiable one, and of certain parameters that depend on the interpolation points and the KKT-like parameters. Also, we develop an efficient descent algorithm that is much faster than general linear programming procedures. Its efficiency is due to the banded matrices that occur during the iterations. Intensive numerical results illustrate the computation and present the efficacy of the method in small, medium and large data sets with errors that range from few outliers to a full corruption of the data. Certain applications are presented in order to illustrate the convexity assumption of real economic time series. The results are analyzed and the interpretation capability of the method is presented, due to its rich inherent structure, the values of the KKT-like parameters and the values of the parameters at the interpolation points.

Η παρούσα διατριβή εντάσσεται στη θεματική περιοχή της θεωρίας προσεγγίσεων και της βελτιστοποίησης και στόχος της είναι η θεωρητική ανάλυση, θεμελίωση και ανάπτυξη αλγορίθμων για L1 προσεγγίσεις διακριτών δεδομένων που περιέχουν σφάλματα, ενίοτε δε οφειλόμενα σε έκτοπα σημεία, υπό μη αρνητικές δεύτερες διηρημένες διαφορές. Οι αλγόριθμοι είναι ανθεκτικοί, δηλαδή μη ευαίσθητοι στην κατανομή των καταλοίπων.Η κύρια δυσκολία του υπολογιστικού προβλήματος της εύρεσης της άριστης L1 κυρτής προσέγγισης σε μονοδιάστατα διακριτά δεδομένα έγκειται στο ότι στην L1 βελτιστοποίηση δεν ισχύουν οι συνθήκες Karush-Kuhn-Tucker, διότι εμπλέκονται μη παραγωγίσιμες μορφές. Η διερεύνηση, επομένως, του προβλήματος απαίτησε βασική έρευνα στο χαρακτηρισμό της L1 προσέγγισης, όπου δόθηκαν αναγκαίες και ικανές συνθήκες, οι οποίες έχουν την ενδιαφέρουσα ιδιότητα να εκφράζονται σε όρους που θυμίζουν τις συνθήκες Karush-Kuhn-Tucker παρά το γεγονός ότι η αντικειμενική συνάρτηση του προβλήματος είναι μη διαφορίσιμη. Το αποτέλεσμα αυτό αποτελεί τη σημαντικότερη συμβολή της παρούσας διδακτορικής διατριβής στην ανάπτυξη νέας γνώσης.Δεδομένου ότι οι περιορισμοί είναι γραμμικές ανισότητες το πρόβλημα μπορεί να αναχθεί σε πρόβλημα γραμμικού προγραμματισμού για το οποίο υπάρχουν γενικοί αλγόριθμοι επίλυσης. Επειδή, όμως οι περιορισμοί μας εμφανίζουν δομή και επειδή πολλές χιλιάδες δεδομένα μπορεί να υπεισέλθουν στον υπολογισμό αναπτύξαμε έναν ειδικό αλγόριθμο που είναι αποτελεσματικότερος ενός γενικού αλγόριθμου. Με βάση το θεώρημα χαρακτηρισμού προτείνουμε μία κατηφορική μέθοδο και αναπτύσσουμε έναν πεπερασμένο αλγόριθμο που υπολογίζει την άριστη L1 προσέγγιση. Ο αλγόριθμος αυτός είναι αποτελεσματικός διότι λαμβάνει υπόψη την ειδική δομή των περιορισμών που ορίζονται από τις συνθήκες κυρτότητας. Θεμελιώθηκε με ισχυρά θεωρητικά επιχειρήματα, απαίτησε πρωτογενές προγραμματιστικό έργο και υπολογισμούς υψηλής κλίμακας, και υλοποιήθηκε σε γλώσσα Matlab. Δοκιμάσθηκε σε δεδομένα από προσομοίωση με βασικά κριτήρια αποτελεσματικότητας τον υπολογιστικό χρόνο που απαιτείται για τη λήψη της άριστης κυρτής προσέγγισης καθώς και τη σχετική ακρίβεια αυτής. Εφαρμόστηκε σε διάφορα σύνολα πραγματικών δεδομένων από οικονομικές εφαρμογές που ακολουθούν κυρτή ή κοίλη τάση και συνήθως η τάση αυτή υποστηρίζεται από κατάλληλη και σχετική προς τα δεδομένα θεωρία. Πρέπει να σημειωθεί ότι η μέθοδός μας μπορεί να βρει γενικότερες εφαρμογές στην επιστήμη, την ιατρική, την τεχνολογία και τη στατιστική.