25587

همگرايي روش هاي بلوكي كاهش مؤلفه

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

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

1396

1399/12/6

تورج نيك آزاد

رضا احمدي

رياضي

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

1400/09/12

ON THE CONVERGENCE OF BLOCK COORDINATE DESCENT TYPE METHODS

2/25/2022 12:00:00 AM

In this paper we study smooth convex programming problems where the decision variables vector is split into several blocks of variables. We analyze the block coordinate gradient projection method in which each iteration consists of performing a gradient projection step with respect to a certain block taken in a cyclic order. Global sublinear rate of convergence of this method is established and it is shown that it can be accelerated when the problem is unconstrained. In the unconstrained setting we also prove a sublinear rate of convergence result for the so-called alternating minimization method when the number of blocks is two. When the objective function is also assumed to be strongly convex, linear rate of convergence is established.

رو شهاي بلوكي كاهشي، مينيمم سازي متناوب، مرتبه همگرايي، بهينه سازي محدب

block descent methods, alternating minimization, rate of convergence, convex optimization