Inexact Approach for Interior Point Methods for Large Scale Quadratic Optimization

في هذه الورقة، قمنا بتصميم مكيف جديد لطريقة النقاط الداخلية و ذلك من أجل البرامج التربيعية. و قد قمنا بتوسيع المكيفات المستخدمة في البرامج الخطية، لتشمل البرامج التربيعية. صمم المكيف لأنظمة متناظرة غير معرفة و غير مستقرة. هذا المكيف حول عدم الاستقرار من نقطة ضعف في هذه الأنظمة إلى نقطة قوة. في هذه المقالة أول مرة ينظر إلى النظام الخطي من زاوية جديدة، حيث قمنا بتمديد عدم الاستقرار إلى معظم أجزاء النظام و من ثم قمنا بتصميم المكيف. اعتمدنا في هذا التصميم على فكرة المتحولات الأساسية التي تستخدم في طريقة السمبلكس. بحيث دمجنا نوعًا ما بين الطريقتين (طريقة النقاط الداخلية و طريقة السمبلكس). فضلا عما سبق، ُذكرت خواص المكيف الجيد و خلال الورقة قمنا بإثبات أن المكيف المطروح هو مكيف جيد.

Interior point methods are considered the most powerful tools for solving linear, quadratic and nonlinear programming. In each iteration of interior point method (IPM) at least one linear system has to be solved. The main computational effort of IPMs consist in the computational of these linear systems. That drives many researchers to tackle this subject, which make this area of research very active. The issue of finding a preconditioner for this linear system was investigated in many papers. In this paper, we provide a preconditioner for interior point methods for quadratic programming. This preconditioner makes the system easier to be solved comparing with the direct approach. The preconditioner used follows the ideas, which is used for linear approach. An explicit null space representation of linear constraints is constructed by using a non-singular basis matrix identified from an estimate of the optimal partition. This is achieved by means of efficient basis matrix factorisation techniques used in implementations of the revised simplex method.