الگوریتمهای پروگزیمال
مقدمه و کلیات
الگوریتمهای پروگزیمال خانوادهای از روشهای بهینهسازی هستند که برای حل مسائل غیرصاف، مقید و بزرگمقیاس بهکار میروند. این روشها بهویژه زمانی اهمیت پیدا میکنند که تابع هدف مشتقپذیر نباشد یا شامل قیود سخت باشد.
مفاهیم پایه
نگاشت پروگزیمال (Proximal Mapping)
تعریف ریاضی
نگاشت پروگزیمال یک تابع ( f : H \to (-\infty,+\infty] ) به صورت زیر تعریف میشود:
[ \text{Prox}_f(v) := \arg\min \left{ f(x) + \frac{1}{2} | x - v |^2 : x \in H \right}. ]
در این تعریف:
- ( v \in H ) نقطه مرجع است،
- جمله ( \frac{1}{2} | x - v |^2 ) نقش منظمسازی و تضمین یکتایی جواب را دارد.
مثال: تابع قدر مطلق
اگر:
[ f(x) = |x| ]
آنگاه نگاشت پروگزیمال به صورت زیر محاسبه میشود:
[
\text{Prox}_{\lambda |x|}(v)
=
\begin{cases}
v - \lambda & v > \lambda,
0 & |v| \le \lambda,
v + \lambda & v < -\lambda.
\end{cases}
]
این عملگر همان Soft Thresholding است.
فضای هیلبرت
فضای هیلبرت ( H ) فضایی برداری با ضرب داخلی است که نسبت به نرم القاشده کامل میباشد. این فضا بستر طبیعی تحلیل الگوریتمهای پروگزیمال است، زیرا:
- تصویر پروژکشن روی مجموعههای محدب بسته در آن یکتا است،
- تابع ( x \mapsto |x|^2 ) اکیداً محدب است،
- قضیه نمایش رایز برقرار است.
الگوریتم نقطه پروگزیمال
فرض کنید ( x_0 \in H ) داده شده باشد. الگوریتم نقطه پروگزیمال دنباله ( {x_n} ) را بهصورت زیر تعریف میکند:
[ x_n \in \arg\min \left{ f(x) + \frac{1}{2\lambda} | x - x_{n-1} |^2 : x \in H \right}. ]
همگرایی (قضیه مارتینه)
اگر:
[ \arg\min f \neq \emptyset ]
آنگاه دنباله ( {x_n} ) بهطور ضعیف به یکی از نقاط کمینه تابع ( f ) همگرا میشود.
نمایش با نگاشت پروگزیمال
الگوریتم بالا را میتوان به صورت زیر نوشت:
[ x_n = \text{Prox}{\lambda f}(x{n-1}). ]
روش گرادیان پروگزیمال
صورت مسئله
[ \min \left{ g(x) + h(x) : x \in H \right} ]
که در آن:
- ( g ) تابعی صاف و مشتقپذیر است،
- ( h ) تابعی غیرصاف با نگاشت پروگزیمال قابل محاسبه است.
گام بهروزرسانی
[ x^{+} = \text{Prox}_{t h} \left( x - t \nabla g(x) \right). ]
مثال: رگرسیون با جریمه ( L^1 )
تابع هدف:
[ \min \left{ \frac{1}{2} \sum_{i=1}^n (a x_i + b - y_i)^2 + \lambda |a| : (a,b) \in \mathbb{R}^2 \right}. ]
گام پروگزیمال برای پارامتر ( a ):
[ a^{(k+1)} = \mathrm{sign}(a^{\text{temp}})\max \left( |a^{\text{temp}}| - t\lambda , 0 \right). ]
جمعبندی
الگوریتمهای پروگزیمال چارچوبی منسجم برای حل مسائل بهینهسازی غیرصاف فراهم میکنند و پایه روشهایی مانند ISTA، FISTA و ADMM هستند.