20303

۲۰۳۰۳

روش فوق تخفيف و كاربرد آن در مسائل برنامه ريزي درجه دوم

كارشناسي ‌ارشد

رياضي كاربردي - آناليز عددي

۱۳۹۵

۱۳۹۷/۱۰/۲۵

دكتر تورج نيك آزاد

دكتر مرتضي گرشاسبي

رياضي

در اين پايان نامه، ابتدا به معرفي مسئله مكمل خطي و بيان پيشينه و خواص آن مي پردازيم و سپس مسئله برنامه ريزي درجه دوم را كه نوعي از برنامه ريزي غير خطي مي باشد را معرفي مي كنيم. سپس ثابت مي كنيم كه مسئله برنامه ريزي درجه دوم با محدوديت نامنفي، تحت شرايطي با مسئله مكمل خطي معادل است. از طرفي خواهيم ديد كه مسئله كمترين مربعات نامنفي را مي توانيم به صورت يك مسئله برنامه ريزي درجه دوم و در نتيجه يك مسئله مكمل خطي بنويسيم. روش هاي مختلفي براي حل مسئله مكمل خطي وجود دارد. در اين پايان نامه روشي براي حل آن ارائه مي شود كه كاربردي از روش فوق تخفيف است و سپس به اثبات همگرايي اين روش مي پردازيم و در آخر نيز مقادير بهينه پارامتر تخفيف و نتايج عددي را مورد بررسي قرار مي دهيم .

1398/01/25

The solution of a quadratic programming problem using overrelaxation

4/14/2019 12:00:00 AM

In this thesis, first we describe the linear complementarity problem and its properties and history, then we discuss the quadratic programming problem which is a kind of nonlinear programming. We prove that the quadratic programming problem with nonnegative constraint and the linear complementarity problem are equivalent with some conditions. On the other hand we can describe the nonnegative least squares problem in the form of the quadratic programming problem as a result in the form of the linear complementarity problem. Many methods are exist to solve the linear complementarity problem. In this thesis we describe an algorithm which is an application of SOR method and then we prove its convergance. Finally we evaluate optimum relaxation parameter and numerical results of our algorithm.