رتبة متناظرة واحدة

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

نظريًا، تتقارب سلسلة تقريبات مصفوفة هيسيان الناتجة عن طريقة SR1 إلى مصفوفة هيسيان الحقيقية في ظل شروط معينة؛ عمليًا، تُظهر مصفوفات هيسيان التقريبية الناتجة عن طريقة SR1 تقدمًا أسرع نحو مصفوفة هيسيان الحقيقية مقارنةً بالبدائل الشائعة ( BFGS أو DFP )، وذلك في تجارب عددية أولية. ^{[ 1 ] [ 2 ]} تتميز طريقة SR1 بمزايا حسابية للمسائل المتفرقة أو القابلة للفصل جزئيًا . ^{[ 3 ]}

دالة قابلة للتفاضل مرتين بشكل مستمر${\displaystyle x\mapsto f(x)}$يحتوي على تدرج (${\displaystyle \nabla f}$) ومصفوفة هيسيان${\displaystyle B}$الوظيفة${\displaystyle f}$تتضمن سلسلة تايلور توسعًا في${\displaystyle x_{0}}$والتي يمكن اختصارها

${\displaystyle f(x_{0}+\Delta x)\approx f(x_{0})+\nabla f(x_{0})^{T}\Delta x+{\frac {1}{2}}\Delta x^{T}{B}\Delta x}$؛

يمكن أيضًا تقريب تدرجها باستخدام متسلسلة تايلور.

${\displaystyle \nabla f(x_{0}+\Delta x)\approx \nabla f(x_{0})+B\Delta x}$،

والذي يُستخدم للتحديث${\displaystyle B}$لا يشترط أن يكون للمعادلة القاطعة المذكورة أعلاه حل وحيد ${\displaystyle B}$تحسب صيغة SR1 (عبر تحديث من الرتبة 1) الحل المتناظر الأقرب إلى القيمة التقريبية الحالية ${\displaystyle B_{k}}$:

${\displaystyle B_{k+1}=B_{k}+{\frac {(y_{k}-B_{k}\Delta x_{k})(y_{k}-B_{k}\Delta x_{k})^{T}}{(y_{k}-B_{k}\Delta x_{k})^{T}\Delta x_{k}}}}$،

أين

${\displaystyle y_{k}=\nabla f(x_{k}+\Delta x_{k})-\nabla f(x_{k})}$.

التحديث المقابل لمصفوفة هيسيان العكسية التقريبية${\displaystyle H_{k}=B_{k}^{-1}}$يكون

${\displaystyle H_{k+1}=H_{k}+{\frac {(\Delta x_{k}-H_{k}y_{k})(\Delta x_{k}-H_{k}y_{k})^{T}}{(\Delta x_{k}-H_{k}y_{k})^{T}y_{k}}}}$.

قد يتساءل المرء لماذا لا يتم الحفاظ على خاصية التحديد الإيجابي - ففي النهاية، تحديث من الرتبة 1 على شكل${\displaystyle B_{k+1}=B_{k}+vv^{T}}$تكون موجبة التحديد إذا${\displaystyle B_{k}}$نعم. والتفسير هو أن التحديث قد يكون على شكل${\displaystyle B_{k+1}=B_{k}-vv^{T}}$بدلاً من ذلك، لأن المقام يمكن أن يكون سالباً، وفي هذه الحالة لا توجد ضمانات بشأن التحديد الإيجابي.

أُعيد اكتشاف صيغة SR1 عدة مرات. ونظرًا لأن المقام قد يختفي، فقد اقترح بعض المؤلفين تطبيق التحديث فقط إذا

${\displaystyle |\Delta x_{k}^{T}(y_{k}-B_{k}\Delta x_{k})|\geq r\|\Delta x_{k}\|\cdot \|y_{k}-B_{k}\Delta x_{k}\|}$،

أين${\displaystyle r\in (0,1)}$هو عدد صغير، على سبيل المثال${\displaystyle 10^{-8}}$[ ^{4 ]​}

يُحافظ تحديث SR1 على مصفوفة كثيفة، وهو ما قد يكون مُكلفًا للغاية في المسائل الكبيرة. وعلى غرار طريقة L-BFGS ، توجد أيضًا خوارزمية SR1 محدودة الذاكرة (L-SR1). ^{[ 5 ]} فبدلاً من تخزين تقريب هيسيان الكامل، تخزن طريقة L-SR1 فقط${\displaystyle m}$أحدث الأزواج${\displaystyle \{(s_{i},y_{i})\}_{i=km}^{k-1}}$، أين${\displaystyle \Delta x_{i}:=s_{i}}$و${\displaystyle m}$هو عدد صحيح أصغر بكثير من حجم المشكلة (${\displaystyle m\ll n}$تعتمد المصفوفة ذات الذاكرة المحدودة على تمثيل مصفوفة مضغوطة

$${\displaystyle B_{k}=B_{0}+J_{k}N_{k}^{-1}J_{k}^{T},\quad J_{k}=Y_{k}-B_{0}S_{k},\quad N_{k}=D_{k}+L_{k}+L_{k}^{T}-S_{k}^{T}B_{0}S_{k}}$$

$${\displaystyle S_{k}={\begin{bmatrix}s_{km}&s_{k-m+1}&\ldots &s_{k-1}\end{bmatrix}},}$$$${\displaystyle Y_{k}={\begin{bmatrix}y_{km}&y_{k-m+1}&\ldots &y_{k-1}\end{bmatrix}},}$$

$${\displaystyle {\big (}L_{k}{\big )}_{ij}=s_{i-1}^{T}y_{j-1},\quad (D_{k})_{ii}=s_{i-1}^{T}y_{i-1},\quad km\leq i\leq k-1}$$

بما أن التحديث قد يكون غير محدد، فإن خوارزمية L-SR1 مناسبة لاستراتيجية منطقة الثقة . ونظرًا لمحدودية ذاكرة المصفوفة، فإن خوارزمية منطقة الثقة L-SR1 تتناسب طرديًا مع حجم المشكلة، تمامًا مثل خوارزمية L-BFGS.

• طريقة شبه نيوتن
• طريقة برودن
• طريقة نيوتن في التحسين
• طريقة برودن-فليتشر-جولدفراب-شانو (BFGS)
• طريقة L-BFGS
• تمثيل شبه نيوتن المضغوط