DOI: https://doi.org/10.1137/23m1555430
تاريخ النشر: 2024-01-22
المؤلف: Lorenzo Baldi وآخرون
الموضوع الرئيسي: أبحاث خوارزميات التحسين المتقدمة
نظرة عامة
تتناول الورقة البحثية التقدم في Positivstellensätze الفعالة لـ Putinar وSchmüdgen، والتي تثبت أن أي متعدد حدود \( f \) يكون موجبًا على مجموعة شبه جبرية مضغوطة يمكن التعبير عنه كمجموع مربعات. التركيز هو على اشتقاق حدود لدرجات هذه المجموعات من المربعات، لا سيما في سياق المكعب الفائق \( B_n = [-1, 1]^n \). يقدم المؤلفون حدًا أعلى للدرجة لتمثيلات من نوع Putinar، تحديدًا من الرتبة \( O\left(\frac{f_{\text{max}}}{f_{\text{min}}}\right) \)، حيث \( f_{\text{max}} \) و \( f_{\text{min}} \) يمثلان القيم القصوى والدنيا لـ \( f \) على \( B_n \)، على التوالي.
تعتبر هذه النتيجة مهمة لأنها توسع النتائج السابقة التي كانت محدودة بتمثيلات من نوع Schmüdgen، مما يمثل تقدمًا ملحوظًا في فهم تمثيلات من نوع Putinar. بالإضافة إلى ذلك، يثبت المؤلفون حدًا أدنى للدرجة قدره \( \Omega\left(\frac{8 f_{\text{max}}}{f_{\text{min}}}\right) \)، وهو الأول من نوعه لتمثيلات من نوع Putinar على مجموعة شبه جبرية ذات داخل غير فارغ محدد بواسطة عدم المساواة القياسية. لهذه النتائج تداعيات مهمة على معدلات التقارب في تسلسل لحظات-SOS في تحسين متعددات الحدود.
مقدمة
تناقش المقدمة التحديات المرتبطة بتحديد ما إذا كان متعدد الحدود \( f \) غير سالب على مجموعة شبه جبرية مغلقة \( S(g) \subseteq \mathbb{R}^n \)، المحددة بواسطة مجموعة من متعددات الحدود \( g = (g_1, g_2, \ldots, g_m) \). المشكلة عمومًا معقدة، ولكن في الحالة غير المقيدة، يمكن تأكيد عدم السلبية من خلال التعبير عن \( f \) كمجموع مربعات من متعددات الحدود. يمتد هذا النهج إلى الحالات المقيدة من خلال الوحدة التربيعية \( Q(g) \) والترتيب المسبق \( T(g) \)، واللذان يقعان كلاهما ضمن مخروط متعددات الحدود غير السالبة على \( S(g) \).
تسلط هذه الفقرة الضوء على نتائج مهمة من Krivine وStengle بشأن تمثيلات متعددات الحدود غير السالبة، لا سيما تحت الشروط التي وضعتها Positivstellensätze لـ Putinar وSchmüdgen. تثبت هذه النظريات أنه بالنسبة للمجموعات شبه الجبرية المضغوطة، تنتمي متعددات الحدود الموجبة بشكل صارم إلى الترتيب المسبق \( T(g) \) و، تحت الشروط الأرخيميدية، إلى الوحدة التربيعية \( Q(g) \). كما تشير المقدمة إلى الاهتمام المتزايد بالإصدارات الفعالة من هذه النظريات، التي تهدف إلى توفير حدود على الحد الأدنى من الدرجة المطلوبة ليتواجد متعدد الحدود الموجب ضمن الوحدة التربيعية المقطوعة أو الترتيب المسبق، مع تداعيات على تقارب تسلسل لحظات-SOS في تحسين متعددات الحدود.
مناقشة
في هذا القسم، يقدم المؤلفون مساهمات مهمة لفهم تمثيلات متعددات الحدود على المكعب الفائق $[-1, 1]^n$. يثبتون أن المكعب الفائق يمكن تعريفه كمجموعة شبه جبرية من خلال عدم المساواة $g_i(x) = 1 – x_i^2 \geq 0$ لـ $i = 1, 2, \ldots, n$. تُظهر الوحدة التربيعية المرتبطة بهذه عدم المساواة، المرموز لها $Q(g)$، أنها أرخيميدية، مما يسمح بتطبيق Positivstellensatz لـ Putinar. يستخرج المؤلفون حدودًا عليا وسفلى على الدرجة المطلوبة لتمثيل متعددات الحدود الموجبة على المكعب الفائق كعناصر من $Q(g)$. على وجه التحديد، يوفر النظرية 3 حدًا أعلى يشير إلى أنه بالنسبة لمتعدد الحدود $f \in P_{>0}([-1, 1]^n)$ من الدرجة $d$، يوجد ثابت $c > 0$ بحيث $f \in Q(1 – x_1^2, \ldots, 1 – x_n^2)_r$ كلما كان $r \geq 4c \cdot d^2 (\log n) \cdot f_{\max} f_{\min} + O(f_{\max} f_{\min}^{1/2})$. بالمقابل، تؤسس النظرية 4 حدًا أدنى، حيث تنص على أنه لأي $\epsilon > 0$، إذا كان $(1 – x_1^2)(1 – x_2^2) + \epsilon \in Q(1 – x_1^2, \ldots, 1 – x_n^2)_r$، فإن $r = \Omega(1/\sqrt{\epsilon})$.
كما يضع المؤلفون نتائجهم في سياق الأدبيات الموجودة حول Positivstellensätze الأرخيميدية الفعالة وتحسين متعددات الحدود، مشيرين إلى أهمية نتائجهم للتطبيقات العملية. يلاحظون أنه بينما قدمت الأعمال السابقة حدودًا للدرجات لمجموعات شبه جبرية متنوعة، فإن تحليلهم يتناول بشكل خاص المكعب الفائق، مما يملأ فجوة ملحوظة في الأدبيات. تم هيكلة الورقة لمراجعة الأدبيات ذات الصلة أولاً، تليها إثباتات مفصلة للحدود العليا والسفلى، وتختتم بمناقشات حول اتجاهات البحث المستقبلية والتطبيقات لمشكلات تحسين متعددات الحدود.
DOI: https://doi.org/10.1137/23m1555430
Publication Date: 2024-01-22
Author(s): Lorenzo Baldi et al.
Primary Topic: Advanced Optimization Algorithms Research
Overview
The research paper discusses advancements in the effective Positivstellensätze of Putinar and Schmüdgen, which establish that any polynomial \( f \) that is positive on a compact semialgebraic set can be expressed as a sum of squares. The focus is on deriving bounds for the degrees of these sums of squares, particularly in the context of the hypercube \( B_n = [-1, 1]^n \). The authors present an upper degree bound for Putinar-type representations, specifically of the order \( O\left(\frac{f_{\text{max}}}{f_{\text{min}}}\right) \), where \( f_{\text{max}} \) and \( f_{\text{min}} \) denote the maximum and minimum values of \( f \) on \( B_n \), respectively.
This finding is significant as it extends previous results that were limited to Schmüdgen-type representations, marking a notable advancement in the understanding of Putinar-type representations. Additionally, the authors establish a lower degree bound of \( \Omega\left(\frac{8 f_{\text{max}}}{f_{\text{min}}}\right) \), which is the first of its kind for Putinar-type representations on a semialgebraic set with a nonempty interior defined by standard inequalities. These results have important implications for the convergence rates of the moment-SOS hierarchy in polynomial optimization.
Introduction
The introduction discusses the challenges associated with determining whether a polynomial \( f \) is nonnegative on a closed semialgebraic set \( S(g) \subseteq \mathbb{R}^n \), defined by a tuple of polynomials \( g = (g_1, g_2, \ldots, g_m) \). The problem is generally complex, but in the unconstrained case, nonnegativity can be certified by expressing \( f \) as a sum of squares of polynomials. This approach extends to constrained cases through the quadratic module \( Q(g) \) and the preordering \( T(g) \), which are both contained within the cone of nonnegative polynomials on \( S(g) \).
The section highlights significant results from Krivine and Stengle regarding representations of nonnegative polynomials, particularly under the conditions set by Putinar’s and Schmüdgen’s Positivstellensätze. These theorems establish that for compact semialgebraic sets, strictly positive polynomials belong to the preordering \( T(g) \) and, under Archimedean conditions, to the quadratic module \( Q(g) \). The introduction also notes the growing interest in effective versions of these theorems, which aim to provide bounds on the minimum degree required for a positive polynomial to lie within the truncated quadratic module or preordering, with implications for the convergence of the moment-SOS hierarchy in polynomial optimization.
Discussion
In this section, the authors present significant contributions to the understanding of polynomial representations on the hypercube $[-1, 1]^n$. They establish that the hypercube can be defined as a semialgebraic set through the inequalities $g_i(x) = 1 – x_i^2 \geq 0$ for $i = 1, 2, \ldots, n$. The quadratic module associated with these inequalities, denoted $Q(g)$, is shown to be Archimedean, allowing the application of Putinar’s Positivstellensatz. The authors derive both upper and lower bounds on the degree required for representing positive polynomials on the hypercube as elements of $Q(g)$. Specifically, Theorem 3 provides an upper bound indicating that for a polynomial $f \in P_{>0}([-1, 1]^n)$ of degree $d$, there exists a constant $c > 0$ such that $f \in Q(1 – x_1^2, \ldots, 1 – x_n^2)_r$ whenever $r \geq 4c \cdot d^2 (\log n) \cdot f_{\max} f_{\min} + O(f_{\max} f_{\min}^{1/2})$. Conversely, Theorem 4 establishes a lower bound, stating that for any $\epsilon > 0$, if $(1 – x_1^2)(1 – x_2^2) + \epsilon \in Q(1 – x_1^2, \ldots, 1 – x_n^2)_r$, then $r = \Omega(1/\sqrt{\epsilon})$.
The authors also contextualize their findings within the existing literature on effective Archimedean Positivstellensätze and polynomial optimization, highlighting the significance of their results for practical applications. They note that while previous works have provided degree bounds for various semialgebraic sets, their analysis specifically addresses the hypercube, filling a notable gap in the literature. The paper is structured to first review relevant literature, followed by detailed proofs of the upper and lower bounds, and concludes with discussions on future research directions and applications to polynomial optimization problems.