روش گرادیان

روش گرادیان یک روش بهینه سازی است که برای یافتن کمینه یا بیشینه محلی یک تابع استفاده می شود. این روش بر اساس این اصل است که هر نقطه در فضای جستجو دارای یک گرادیان است که جهت افزایش سریعترین تابع را نشان می دهد. با حرکت به سمت مخالف گرادیان، به سمت کمینه یا بیشینه محلی حرکت می کنیم.

روش گرادیان در حل مسائل چندهدفه به گفرین (Geoffrion) منتسب است. این روش قادر به حل مسائل بهینه سازی خطی و غیرخطی است به شرطی که خبره بتواند تابع مطلوبیت کلی خود را از اهداف مسئله مشخص نماید.

روش گرادیان یک روش ساده و موثر است که برای طیف گسترده ای از مسائل بهینه سازی استفاده می شود. با این حال، ممکن است در مواردی که تابع دارای چندین کمینه یا بیشینه محلی باشد، کارآمد نباشد.

---

انواع الگوریتم‌های گرادیان

اگرچه مفهوم اصلی روش گرادیان ساده است، اما در طول سال‌ها انواع مختلفی از این الگوریتم‌ها برای رفع محدودیت‌های پایه‌ای توسعه یافته‌اند. در ادامه به مهم‌ترین انواع اشاره می‌کنیم:

1. گرادیان نزولی ساده (Batch Gradient Descent)

در این نسخه، در هر تکرار تمام نمونه‌های داده‌ها برای محاسبهٔ گرادیان استفاده می‌شوند. مزیت اصلی آن دقت بالا است، اما هزینه محاسباتی زیاد و زمان اجرا طولانی می‌شود؛ به‌ویژه برای دیتاست‌های بزرگ.

2. گرادیان نزولی تصادفی (Stochastic Gradient Descent – SGD)

در این روش، در هر گام تنها یک نمونه (یا یک مینی‌بچ کوچک) برای محاسبهٔ گرادیان استفاده می‌شود. این کار باعث می‌شود که روش گرادیان به‌سرعت به‌روز شود و به مینیمم‌های محلی فرار کند؛ اما نوسان بیشتری در مسیر همگرایی دارد.

3. گرادیان نزولی مینی‑بچ (Mini‑Batch Gradient Descent)

این الگوریتم ترکیبی از دو روش قبلی است؛ در هر گام یک مینی‌بچ (مثلاً ۲۴‑۱۲۸ نمونه) استفاده می‌شود. این ترکیب تعادل خوبی بین سرعت محاسبه و پایداری مسیر همگرایی فراهم می‌کند و در اکثر کتابخانه‌های یادگیری عمیق به‌کار می‌رود.

4. بهینه‌سازهای پیشرفته (Adam, RMSProp, Adagrad)

این بهینه‌سازها با استفاده از تخمین‌های لحظه‌ای از میانگین و واریانس گرادیان، گام یادگیری را به‌صورت خودکار تنظیم می‌کنند. به‌ویژه روش گرادیان مبتنی بر Adam در شبکه‌های عصبی عمیق به‌عنوان استاندارد de‑facto شناخته می‌شود.

هر یک از این الگوریتم‌ها مزایا و معایب خاص خود را دارند؛ انتخاب مناسب بستگی به ویژگی‌های مسئله (ابعاد، حجم داده، ساختار تابع هزینه) دارد.

---

مراحل روش گرادیان

گام های روش گرادیان به شرح زیر است:

انتخاب نقطه اولیه

ابتدا باید یک نقطه اولیه در فضای جستجو انتخاب کنیم. این نقطه می تواند هر نقطه ای باشد که به نظر می رسد نزدیک به کمینه یا بیشینه محلی باشد. انتخاب نقطه اولیه یک مرحله مهم در روش گرادیان است. اگر نقطه اولیه بیش از حد دور از کمینه یا بیشینه محلی باشد، ممکن است روش گرادیان به آن نقطه نرسد.

در برخی از موارد، می توان از روش های مختلفی برای انتخاب نقطه اولیه استفاده کرد. به عنوان مثال، می توان از روش های زیر استفاده کرد:

• انتخاب نقطه ای به صورت تصادفی
• انتخاب نقطه ای در وسط فضای جستجو
• انتخاب نقطه ای که گرادیان آن صفر باشد

محاسبه گرادیان

در مرحله بعدی، باید گرادیان تابع را در نقطه فعلی محاسبه کنیم. گرادیان یک بردار است که جهت افزایش سریعترین تابع را نشان می دهد. محاسبه گرادیان یک تابع می تواند دشوار باشد. با این حال، برای بسیاری از توابع، می توان گرادیان را به صورت تحلیلی محاسبه کرد. در برخی از موارد، نیز می توان از روش های عددی برای محاسبه گرادیان استفاده کرد.

حرکت در جهت مخالف گرادیان

در مرحله سوم، باید در جهت مخالف گرادیان، یک قدم کوچک برداریم. این قدم کوچک به ما کمک می کند تا به سمت کمینه یا بیشینه محلی حرکت کنیم. اندازه قدم برداشته شده در جهت مخالف گرادیان، یک عامل مهم در روش گرادیان است.

اگر اندازه قدم بیش از حد بزرگ باشد، ممکن است روش گرادیان از کمینه یا بیشینه محلی خارج شود. اگر اندازه قدم بیش از حد کوچک باشد، ممکن است روش گرادیان به کندی به سمت کمینه یا بیشینه محلی حرکت کند.

در روش گرادیان ساده، اندازه قدم معمولا ثابت است. در روش گرادیان کاهش وزن، اندازه قدم به تدریج کاهش می یابد. این به جلوگیری از پرش از کمینه یا بیشینه محلی کمک می کند.

تکرار مراحل 2 و 3

آخرین مرحله، تکرار مراحل 2 و 3 است. این تکرارها تا زمانی ادامه می یابد که معیار پایانی تحقق یابد. معیار پایانی ممکن است شامل موارد زیر باشد:

• رسیدن به مقدار مشخصی از دقت: اگر مقدار تابع در نقطه فعلی، کمتر از یک مقدار مشخص باشد، می توان گفت که روش گرادیان به کمینه محلی رسیده است.
• رسیدن به تعداد مشخصی از تکرار: اگر تعداد تکرارهای روش گرادیان به یک مقدار مشخص برسد، می توان گفت که روش گرادیان به نقطه ای رسیده است که دیگر نمی تواند بهبود یابد.
• رسیدن به نقطه ای که گرادیان آن صفر باشد: اگر گرادیان تابع در نقطه فعلی صفر باشد، می توان گفت که روش گرادیان به نقطه ای رسیده است که دیگر نمی تواند حرکت کند.

در پایان باید توجه داشته باشید که روش گرادیان ممکن است در مواردی که تابع دارای چندین کمینه یا بیشینه محلی باشد، کارآمد نباشد. در این موارد، ممکن است لازم باشد از روش های بهینه سازی دیگری استفاده شود.

الگوریتم های حل روش گرادیان

روش گرادیان را می توان با استفاده از انواع مختلف الگوریتم ها پیاده سازی کرد. برخی از الگوریتم های رایج عبارتند از:

• روش گرادیان ساده: روش گرادیان ساده ساده ترین الگوریتم است. در این الگوریتم، اندازه قدم برداشته شده در هر تکرار ثابت است.
• روش گرادیان کاهش وزن: روش گرادیان کاهش وزن یک الگوریتم بهبود یافته است. در این الگوریتم، اندازه قدم برداشته شده در هر تکرار به تدریج کاهش می یابد. این به جلوگیری از پرش از کمینه یا بیشینه محلی کمک می کند.
• روش گرادیان تصادفی: روش گرادیان تصادفی یک الگوریتم ابتکاری است. در این الگوریتم، در هر تکرار، علاوه بر حرکت در جهت مخالف گرادیان، یک حرکت تصادفی نیز انجام می شود. این به یافتن کمینه یا بیشینه محلی بهتر کمک می کند.

---

روش گرادیان ساده

روش گرادیان ساده ساده ترین الگوریتم است. در این الگوریتم، اندازه قدم برداشته شده در هر تکرار ثابت است.

الگوریتم حل گرادیان ساده

الگوریتم گرادیان در قالب روش فرانک- ولف مطرح شده است. در روش فرانک- ولف حرکت از یک نقطه شدنی ( Xⁱ ) شروع می شود و از آن جا به منظور دسترسی به یک جهت بهینه حرکت (d_i) به نقطه جدید (yⁱ) می رسد به طوری که خواهیم داشت: ( d_i = (yⁱ –  Xⁱ سپس باید مقدار بهینه حرکت (λⁱ) تعیین شود.

برای یافتن مقدار بهینه حرکت مسئله بهینه سازی زیر باید حل شود:

بهینه کنید: f (Xⁱ + λⁱ d_i )

s.to:  λⁱ  ≥ 0

برای یافتن نقطه مقصد مدل زیر باید حل شود:

برای اطلاعات بیشتر آموزش جامع کدنویسی در GAMS را مطالعه کنید.

مدل گرادیان برای حل یک مسئله K هدفه

max: U {f₁ (x), f₂ (x), …. f_k (x)} = U (F)

s.t: x ∈ S   ;   s = {x | g_i(x) ≤ 0 ; i = 1, 2, …, m }

در این مدل توابع (f(x و (g(x به طور عینی معلوم است اما تابع مطلوبیت (U(F به طور ضمنی مد نظر است.

مفروضات استفاده از شرایط فرانک- ولف

• مجموعه متشکل از محدودیت ها محدب و بسته (مرزدار) باشد
• (U(F (تابع مطلوبیت توابع هدف) بر روی X مشتق پذیر و مقعر باشد
• هر یک از توابع هدف مقعر باشد
• مشتق جزئی تابع مطلوبیت نسبت به تابع هدف اول مثبت باشد که در نتیجه این تابع هدف به عنوان هدف مرجع تلقی می گردد

الگوریتم روش گرادیان یک مسئله K هدفه

قدم یکم: نقطه شروع xⁱ ∈ S را انتخاب نموده و قرار دهید i=1

قدم دوم: راه حل بهینه yⁱ را به منظور جهت یابی برای حرکت بهبودبخش از مسئله زیر بیابید:

max: ∇_x U = (f₁ (xⁱ), f₂ (xⁱ), …. f_k (xⁱ)) .  yⁱ

s.t : yⁱ ∈ S

بخش اساسی تعامل با خبره در همین جا است زیرا (U(F به طور عینی مشخص نیست و نیاز به کمک خبره دارد. فرض بر آن است که خبره قادر است تعدیل بین هر دو هدف از اهداف مسئله را به ازای یک راه حل مشخص برآورد کند. این نرخ حاشیه ای جایگزینی بین اهداف را می توان برای برآورد گرادیان از (U(F به کار برد. اثبات ریاضی این موضوع در ادامه ارائه شده است.

مدل بهینه سازی با تقسیم بر یک عدد ثابت تغییری نمی کند به این دلیل تابع هدف مذکور را بر (U∂/∂Fⁱ1)   تقسیم می کنیم.

اوزان منعکس کننده تعدیل خبره بین اهداف است زیرا:

حال در ادامه جهت  بدست آوردن اوزان wⁱ_j باید نرخ حاشیه ای جایگزینی بین اهداف اول و jام را به کمک خبره ارزیابی نمود بدین صورت که تعدیل بی تفاوتی خبره از تغییر بسیار کوچک در هدف اول Δf₁ در مقابل تغییر لازم برای هدف jام را جویا شویم. یعنی تغییر در هدف اول به میزان Δf₁ با ثابت نگه داشتن بقیه اهداف به استثنای هدف jام چه اندازه از این هدف را جبران خواهد نمود. این برآورد به صورت زیر است:

wⁱ_j = Δf₁/Δf_j

قدم سوم: مقدار بهینه λⁱ را از مدل روبرو محاسبه نمائید:

max: U {  F (Xⁱ + λⁱ d_i ) }

s.to: 0 ≤ λⁱ ≤ 1

برای انجام این برآورد باید از نظرات خبره استفاده کرد. برای این کار به دو طریق می توان عمل نمود:

1. رسم نمودار
2. رسم جدول

روش گرادیان روش گرادیان روش گرادیان روش گرادیان روش گرادیان

قدم چهارم: اختتام الگوریتم

از نظر تئوری پایان الگوریتم زمانی است که دو راه حل متوالی با یکدیگر یکسان شوند ولی این ایده آل به ندرت اتفاق می افتد. به همین دلیل نسبتی را به نام نسبت بهبودی تعریف می کنیم که یک معیار عملی برای پایان الگوریتم است:

به منظور شفاف سازی حل روش گرادیان، در ادامه مثالی ذکر شده است.

مثال روش گرادیان

مساله روبرو ر با 3 تابع هدف و 4 محدودیت در نظر بگیرید. با استفاده از روش گرادیان نقاط بهینه تابع را بدست آورید.

Max  f1(x)= – x1 – 2 x2 – 3 x3

       f2(x) = – x1 – 2 x2 – x3

       f3(x) = -2×1 – x2 –x3

S . to :

        2×1 + 5×2 + 3 x3 ≥ 30

        x1 + x2 + x3 ≥ 18

        10×1 + 8×2 + 4 x3 ≥40

        3×1+2×2 ≥20

         x1 , x2 , x3 ≥ 0

انتقال یکم :

گام اول) تعیین نقطه عملی

  x’ ∈ S    ->   x¹= (2, 9, 7)   , i=1 ,  ε =0.15

مفروضات مسئله:

 F⁰ = {F¹(x¹), F²(x¹), F³(x¹)}   ->  F⁰ = { (-41, -27, -20)

گام دوم) راه حل بهینه

قدم دوم : (f1 در مقابل  f2)

 {(-41-20 )   ,   ( -27 + 2 )    , ( -20 )} = > w¹₂=-(2/-20) = 0.1

قدم دوم : (f2 در مقابل  f3)

 {(-41)  ,   ( -27 + 2 )    , ( -20- 10 )}= > w¹₃=-(2/-10) = 0.2    ->  w₁=(0.1 , 1, 0.2)

محاسبه (Y₁, d₁ )= 0.1(-1  ,  -2    ,  -3 ) Y₁  +1( -1  ,  -2  ,  -1) Y₁ +  0.2 ( -2  , -1  , -1 ) Y₁ 

Y₁={Y1₁ , Y2₁ , Y3₁ }

Max: 0.1f1(Y1) + 1f2(Y1)+ 0.2 f3(Y1)

S.to Y1 ∈ S

S فضای حاصل از محدودیتهای مسئله: 

Y₁ = {0, 0, 10}    d₁= = {(0 – 2), (0 – 9),  (10 – 7)} = {-2, – 9, 3}

گام سوم ) تعیین نمودن نقطه بهینه

برای f1  داریم ( محاسبات برای 0.2= λو  0.4= λو 0.6= λو 0.8= λ و اگر 1= λ) :

-1 ( 2 + .2 ( -2 )) -2 ( 9 + .2 ( -9 ))-3( 7 + .2 ( 3 )) =-38.8

-1 ( 2 + .4 ( -2 )) -2 ( 9 + .4 ( -9 ))-3( 7 + .4 ( 3 )) =- 36.7

-1 ( 2 + .6 ( -2 )) -2 ( 9 + .6 ( -9 ))-3( 7 + .6 ( 3 )) =-34.4

-1 ( 2 + .8 ( -2 )) -2 ( 9 + .8 ( -9 ))-3( 7 + .8 ( 3 )) =-32.1

-1 ( 2 + 1 ( -2 )) -2 ( 9 + 1 ( -9 ))-3( 7 + 1 ( 3 )) =-30

برای f2  داریم:

-1 ( 2 + .2 ( -2 )) -2 ( 9 + .2 ( -9 ))- ( 7 + .2 ( 3 )) =-23.6

-1 ( 2 + .4 ( -2 )) -2 ( 9 + .4 ( -9 ))- ( 7 + .4 ( 3 )) =- 20.2

-1 ( 2 + .6 ( -2 )) -2 ( 9 + .6 ( -9 ))- ( 7 + .6 ( 3 )) =-16.8

-1 ( 2 + .8 ( -2 )) -2 ( 9 + .8 ( -9 ))- ( 7 + .8 ( 3 )) =-13.4

-1 ( 2 + 1 ( -2 )) -2 ( 9 + 1 ( -9 ))- ( 7 + 1 ( 3 )) =-10

و برای f3   داریم :

-2 ( 2 + .2 ( -2 )) -1 ( 9 + .2 ( -9 ))- ( 7 + .2 ( 3 )) =-18

-2 ( 2 + .4 ( -2 )) -1 ( 9 + .4 ( -9 ))- ( 7 + .4 ( 3 )) =- 16

-2 ( 2 + .6 ( -2 )) -1 ( 9 + .6 ( -9 ))- ( 7 + .6 ( 3 )) =-13.8

-2 ( 2 + .8 ( -2 )) -1 ( 9 + .8 ( -9 ))- ( 7 + .8 ( 3 )) =-12

-2 ( 2 + 1 ( -2 )) -1 ( 9 + 1 ( -9 ))- ( 7 + 1 ( 3 )) =-10

1=λ1	0.8=λ1	0.6=λ1	0.4=λ1	0.2=λ1	0=λ1
-30	-32.1	-34.4	-36.7	-38.8	-41	F1
-10	-13.4	-16.8	-20.2	-23.6	-27	F2
-10	-12	-13.8	-16	-18	-20	F3

در صورتی که 0.4=λ مورد نظر خبره باشد: ( -36.7  ,   –  20.2   ,   -16   )

 به منظور انتقال به مرحله دوم باید محاسبه شود :

x²= ( X¹ + λ1 d1)

x²= 2+ 0.4  -2=1.2

x²= 9+ 0.4  -9=5.4

x²= 7+ 0.4  3=8.2

x²= ( 1.2  ,   5.4   ,   8.78  ) ->  F ={ (-38.34)  , (  -20.78  )  ,  ( -16.58 ) }

قدم چهارم: کلیه گام ها مانند قبل تکرار می شود و مقدار ( -47.636   , -19.032     ,   -17.422   ) = F2  بدست می آید. حال شرط خاتمه بررسی می شود که در صورت تصدیق میزان بهینگی الگوریتم از حرکت باز می ایستد.

از ε =0.15 کمتر است پس در همین تکرار متوقف می شود.

---

نتیجه‌گیری

روش گرادیان به‌عنوان یکی از پایه‌ای‌ترین و پرکاربردترین تکنیک‌های بهینه‌سازی عددی، امکان یافتن نقاط بهینه توابع پیچیده را با استفاده از اطلاعات محلی (گرادیان) فراهم می‌کند. در این مقاله، مفاهیم اساسی، انواع الگوریتم‌های گرادیان (Batch, Stochastic, Mini‑Batch و بهینه‌سازهای پیشرفته مانند Adam)، پیاده‌سازی ساده در پایتون و نکات کلیدی برای تنظیم گام یادگیری و جلوگیری از گیر کردن در مینیمم‌های محلی بررسی شد.

از مزایای اصلی روش گرادیان می‌توان به سادگی پیاده‌سازی، عدم نیاز به محاسبهٔ هسین (ماتریس دوم مشتق) و قابلیت مقیاس‌پذیری به ابعاد بسیار بالا اشاره کرد. در عین حال، محدودیت‌هایی همچون حساسیت به مقدار اولیه، نیاز به تنظیم دقیق گام یادگیری و احتمال همگرایی به مینیمم محلی وجود دارد؛ بنابراین، ترکیب این روش با تکنیک‌های پیشرفته (مانند Adam یا RMSProp) و استفاده از استراتژی‌های توقف زودرس (early stopping) می‌تواند عملکرد را به‌طور چشمگیری بهبود بخشد.

در حوزه‌های مختلف از جمله یادگیری عمیق، بهینه‌سازی ترکیبی، پردازش سیگنال و مهندسی کنترل، روش گرادیان به‌عنوان ابزار اصلی بهینه‌سازی شناخته می‌شود و با توسعه‌های اخیر (به‌کارگیری یادگیری تقویتی برای تنظیم خودکار پارامترها، ترکیب با برنامه‌ریزی فازی برای مدیریت عدم قطعیت) همچنان در حال پیشرفت است.

در نهایت، تسلط بر اصول و جزئیات روش گرادیان برای دانشجویان، پژوهشگران و مهندسانی که با مسائل بهینه‌سازی سروکار دارند، گامی اساسی در جهت حل مؤثر و کارآمد مشکلات واقعی محسوب می‌شود.

---