---
layout: persian
classes: wide rtl-layout
dir: rtl
title: "الگوریتمهای پروگزیمال"
permalink: /teaching/toolkit/ProximalMapping111/
author_profile: true
sidebar:
nav: "toolkit"
header:
overlay_image: "/assets/images/background.jpg"
overlay_filter: 0.3
overlay_color: "#5e616c"
caption: "Photo credit: [**Unsplash**](https://unsplash.com)"
---
الگوریتمهای پروگزیمال یک دسته قدرتمند از روشهای بهینهسازی هستند که در سطح انتزاع بالاتری نسبت به الگوریتمهای کلاسیک مانند روش نیوتن قرار میگیرند. در حالی که روش نیوتن یک ابزار استاندارد برای حل مسائل بهینهسازی نرم (smooth) بدون قید با اندازه متوسط است، الگوریتمهای پروگزیمال را میتوان ابزاری مشابه برای معادلات ناهموار، مقید، بزرگمقیاس و نسخههای توزیعشده دانست.
پروگزیمال یک روش ریاضی است برای اینکه وقتی یک مسئلهٔ بهینهسازی «سخت» یا «غیرقابل مشتق» داریم، آن را به یک مسئلهٔ سادهتر و قابلحل تبدیل کنیم.
فرض کنید میخواهید یک تابع را کمینه کنید، اما:
در این حالت، Proximal Mapping میگوید: بهجای اینکه مستقیم سراغ تابع سخت برویم، یک نقطهٔ فعلی را میگیریم و نزدیکترین نقطهای را پیدا میکنیم که هم به آن نقطه نزدیک باشد و هم مقدار تابع را کوچک کند.
برای یک تابع ( f(x) ):
[ \text{prox}_{f}(v) = \arg\min_x \left( f(x) + \frac{1}{2}|x - v|^2 \right) ]
توضیح اجزا:
v : نقطهی فعلیvاگر: [ f(x) = |x| ] آنگاه پروگزیمال مپ برابر است با Soft Thresholding:
[
\text{prox}_{\lambda |x|}(v) =
\begin{cases}
v - \lambda & v > \lambda
0 & |v| \le \lambda
v + \lambda & v < -\lambda
\end{cases}
]
تفسیر:
فضای هیلبرت یک فضای برداری است که دو ویژگی کلیدی دارد:
روش نقطۀ پروکسیمال بر اساس منظمسازی مسئلۀ اصلی بنا شده است. به این معنی که به جای حل مستقیم مسئلۀ کمینهسازی برای تابع محدب ( f )، توجه خود را معطوف میکنیم به دنبالهای از مسائل کمینهسازی که حاصلِ اغتشاش تابع هدف اصلی با یک تابع نرمی از فضای ( H ) هستند.
فرض کنید ( x_0 \in H ) نقطه شروع باشد. اگر ( x_{n-1} ) داده شده باشد و ( \lambda > 0 )، آنگاه ( x_n ) را به عنوان جواب مسئلۀ کمینهسازی زیر تعریف میکنیم:
[ \min_{x \in H} \left{ f(x) + \frac{1}{2\lambda} | x - x_{n-1} |^2 \right} \tag{1.3} ]
مارتینه ثابت کرد که اگر: [ \arg\min f \neq \emptyset ] یعنی تابع ( f ) حداقل یک نقطۀ کمینه داشته باشد، آنگاه دنبالۀ ( {x_n} ) تولیدشده توسط رابطهی (۱.۳) همگرای ضعیف به یک نقطۀ کمینهی تابع ( f ) خواهد بود.
با استفاده از نگاشت پروگزیمال، الگوریتم مارتینه به صورت فشرده زیر قابل بازنویسی است:
[ x_n = \text{Prox}{\lambda f} (x{n-1}). ]
به این ترتیب، هر گام الگوریتم تنها یک ارزیابی پروکسیمال است که نقطۀ قبلی را به نقطۀ بعدی نگاشت میکند.
میخواهیم مسألهای از این جنس را حل کنیم:
[ \min_{x \in H} \left{ g(x) + h(x)\right} ]
که در آن:
الگوریتم میگوید:
[ x^+ = \text{prox}_{th} ( x - t \nabla g(x) ) ]
وقتی ( h(x) = 0 ): [ \text{prox}_{t0}(u) = u ] پس الگوریتم میشود همان گرادیاندسنت معمولی.
**وقتی ( h(x) = |x|1 )** (LASSO / sparse recovery):
prox این تابع، soft-thresholding است. برای هر مؤلفه:
[
\text{prox}{th}(u)_i =
\begin{cases}
u_i - t & \text{if } u_i > t
0 & \text{if } |u_i| \le t
u_i + t & \text{if } u_i < -t
\end{cases}
]
دادهها: [ D={(x_i,y_i)}_{i=1}^n ]
مدل خطی: [ y \approx ax + b ]
تابع هدف: [ \min_{a,b}\; g(a,b)+h(a,b) ] که در آن: [ g(a,b)=\frac12\sum_{i=1}^n (ax_i+b-y_i)^2 ] [ h(a,b)=\lambda |a| ]
گام گرادیانی: [ a^{temp}=a^{(k)}-t\sum_{i=1}^n (ax_i+b-y_i)x_i ] [ b^{(k+1)}=b^{(k)}-t\sum_{i=1}^n (ax_i+b-y_i) ]
گام Proximal (فقط روی (a)): [ a^{(k+1)}=\text{sign}(a^{temp}) \max(|a^{temp}|-t\lambda,0) ]
نتیجه: مدل sparse و پایدارتر
طبق تعریف: [ \begin{aligned} \text{prox}_{\lambda |x|}(v) &= \arg\min_x \left( \lambda |x| + \frac{1}{2}(x - v)^2 \right) \end{aligned} ]
حالت ( x > 0 ): [ x = v - \lambda \quad \text{به شرط } v > \lambda ]
حالت ( x < 0 ): [ x = v + \lambda \quad \text{به شرط } v < -\lambda ]
حالت ( x = 0 ): [ x = 0 \quad \text{به شرط } |v| \le \lambda ]
[
\text{prox}_{\lambda |x|}(v) =
\begin{cases}
v - \lambda & v > \lambda
0 & |v| \le \lambda
v + \lambda & v < -\lambda
\end{cases}
]
[ \begin{aligned} \text{prox}_{\lambda |x|}(v) &= \mathrm{sign}(v) \cdot \max\bigl(|v| - \lambda, 0\bigr) \end{aligned} ] —
الگوریتمهای پروگزیمال نه جادو هستند و نه ترفند؛ فقط استفادهای دقیق از هندسهی محدبها و ساختارهای فضایی مناسب برای حل مسائل بهینهسازی مدرن میباشند.