يك الگوريتم كارا براي زير مساله‌ي ناحيه‌ اطمينان توسيع يافته با دو قيد خطي

An Efficient Algorithm for the Extended Trust Region Subproblem with Two Linear Constraints

زير مسالهي ناحيه اطمينان (TRS) كه در واقع مساله ي مينيمم سازي يك تابع درجهي دوم روي يك گوي است، نقش كليدي در حل مسايل بهينه سازي غيرخطي نامقيد ايفا ميكند و علي رغم اين كه لزوماً محدب نيست، الگوريتم هاي كاراي متعددي براي حل آن به ويژه براي حل آن در ابعاد بزرگ ارايه شده است. اخيراً توسيع زير مساله ي ناحيه اطمينان به مساله اي با قيود خطي اضافي مورد توجه بسياري از محققان قرار گرفته است. مطالعات انجام شده نشان ميدهد هنگامي كه قيود خطي مساله ي توسيع يافته درون گوي اشتراك ندارند، جواب بهينه ي مساله را ميتوان از طريق حل يك مسالهي بهينه سازي مخروطي به دست آورد. در هر صورت حل مسايل بهينه سازي مخروطي در ابعاد بزرگ و حتي در ابعاد متوسط عملي نيست. در اين مقاله حل مساله ي ناحيه اطمينان توسيع يافته با دو قيد خطي بدون در نظر گرفتن هيچ شرطي روي قيود آن مورد مطالعه قرار گرفته است. جديدترين الگوريتم هاي موجود براي حل زيرمساله ي ناحيه اطمينان و محاسبه ي مينيمم موضعي غير سراسري آن كه مساله را از طريق حل يك مساله ي مقدار ويژه ي تعميم يافته حل ميكنند براي حل مسالهي توسيع يافته در ابعاد بزرگ توسعه داده ميشود. در پايان كارايي الگوريتم پيشنهادي روي دستهاي از مسايل تصادفي ارزيابي ميشود.

Trust region subproblem (TRS), which is the problem of minimizing a quadratic function over a ball, plays a key role in solving unconstrained nonlinear optimization problems. Though TRS is not necessarily convex, there are efficient algorithms to solve it, particularly in large scale. Recently, extensions of TRS with extra linear constraints have received attention of several researchers. It has been shown that in the case where the linear constraints do not intersect within the ball, the optimal solution of the extended problem can be computed via solving a conic optimization problem. However, solving largescale or even medium scale conic optimization problems are not practicable. In this paper, the extended trust region subproblem with two linear constraints without any assumptions on the constraints is considered. The latest algorithms for solving TRS and computing its local nonglobal minimizer, that solve the problem via a generalized eigenvalue problem, are used to solve the extended trust region subproblem. Finally, the efficiency of the proposed algorithm is evaluated on several randomly generated instances