Interior-point methods for linear and mixed complementarity problems

Abstract

An infeasible interior-point method with backtracking line search is proposed to solve the linear complementarity and the general mixed complementarity problem. The standard nonlinear complementarity problem is a special case of the latter problem. The algorithm is based on a method for the general nonlinear programming problem. For this algorithm we prove global convergence from any strictly positive staring point, under minor assumptions. Numerical results are reported which demonstrate very good computational performance on large scale linear complementarity problems as well as on a standard set of mixed complementarity problems.In the case of the general nonlinear program, the Karush-Kuhn-Tucker conditions can be stated as a mixed complementarity problem. Computational results are also reported on a large collection of nonlinear programming problems.Finally, the infinite horizon alternating move duopoly method is studied. It is shown that the necessary and sufficient conditions for a symmetric Markov perfect equilibrium of the model can be formulated as a nonlinear complementarity problem. When only necessary conditions are considered, a linear complementarity problem results. The performance of the algorithm when started from different points, is investigated on a specific example of this model. This example is known to have at least two equilibria, one is an Edgeworth cycle and the other is of the kinked demand curve type. Some sensitivity analysis of the solution around these two equilibria is provided.

Προτείνεται ένας μη εφικτός αλγόριθμος εσωτερικού σημείου για την επίλυση γραμμικών και μεικτών προβλημάτων συμπληρωματικότας. Το σύνηθες μη γραμμικό πρόβλημα συμπληρωματικότητας αποτελεί ειδική περίπτωση του μεικτού προβλήματος. Ο αλγόριθμος βασίζεται σε μια μέθοδο για το γενικό πρόβλημα μη γραμμικού προγραμματισμού. Για αυτόν τον αλγόριθμο αποδεικνύουμε την καθολική σύγκλιση από οποιοδήποτε αυστηρά θετικό αρχικό σημείο, κάτω ελάσσονες προϋποθέσεις. Συμπεριλαμβάνονται αριθμητικά αποτελέσματα που καταδεικνύουν πολύ καλές υπολογιστικές επιδόσεις τους προτεινόμενου αλγορίθμου σε μεγάλης κλίμακας γραμμικά προβλήματα συμπληρωματικότητας καθώς και σε ένα τυπικό σύνολο μεικτών προβλημάτων συμπληρωματικότητας.Για την περίπτωση του γενικού μη γραμμικού προβλήματος, οι συνθήκες Karush-Kuhn-Tucker μπορούν να γραφούν σε μορφή ενός μεικτού προβλήματος συμπληρωματικότητας. Η εργασία περιλαμβάνει υπολογιστικά αποτελέσματα εφαρμογής του αλγορίθμους σε μία μεγάλη συλλογή μη γραμμικών προβλημάτων προγραμματισμού.Τέλος, μελετάται το ατέρμονο, εναλλασσόμενης κίνησης μοντέλο δυοπωλίου. Αποδεικνύεται ότι οι αναγκαίες και ικανές συνθήκες για ένα συμμετρικό Markov perfect σημείο ισορροπίας για το μοντέλο αυτό, μπορούν να διατυπωθούν ως ένα μη γραμμικό πρόβλημα συμπληρωματικότητας. Μάλιστα, όταν λαμβάνονται υπόψη μόνο οι αναγκαίες συνθήκες, τότε προκύπτει ένα γραμμικό πρόβλημα συμπληρωματικότητας.Ερευνάται, η απόδοση του αλγορίθμου, από διαφορετικά σημεία εκκίνησης, πάνω σε ένα συγκεκριμένο παράδειγμα δυοπωλίου. Αυτό το παράδειγμα είναι γνωστό ότι έχει τουλάχιστον δύο σημεία ισορροπίας, το ένα είναι ένας κύκλος Edgeworth και το άλλο είναι τύπου μη ομαλής καμπύλης ζήτησης. Τέλος, παρέχεται ανάλυση ευαισθησίας της λύσης γύρω από αυτά τα δύο σημεία ισορροπίας.