25089: روش‌های عددی بهینه‌سازی
نام درس: روش‌های عددی بهینه‌سازی (Numerical Optimization Methods)
شماره درس: 25089
پیش‌نیاز(ها): -
هم‌نیاز(ها): -
تعداد واحد: 3
مقطع: کارشناسی ارشد
آخرین ویرایش: پاییز 1393

توضیحات:
بسیاری از مسائل مهندسی (از جمله مسائل متعددی که دانشجویان کارشناسی ارشد و دکترا در انجام تزهای خود به آن‌ها برخورد می‌کنند) در نهایت می‌تواند به صورت مینیمم یا ماکزیمم‌کردن یک تابع هزینه تحت قیودی خاص مدل شود. برای انجام این عمل بهینه‌سازی، الگوریتم‌های متعددی (مثل روش‌های steepest descent، نیوتن، Quasi-Newton و ...) وجود دارد. هدف نهایی از این درس آن است که بررسی منسجمی از الگوریتم‌های موجود بهینه‌سازی انجام گیرد و دانشجویان با روش‌های مختلف موجود و شرایط به‌کارگیری آن‌ها آشنا شوند. در این درس خود را به حالت مقید (Convex) محدود نمی‌کنیم و حالت کلی را بیان می‌کنیم. اگرچه کمی هم در مورد مسائل Convex و این که چه طور برخی قضایا در آن حالت ساده‌تر می‌شوند صحبت خواهد شد. البته در مقابل صحبتی هم از روش‌های خاص مسائل Convex نخواهد شد. از این رو ممکن است درس را «بهینه‌سازی غیرمحدب (Non-convex Optimization)» نیز نام‌گذاری کرد؛ در مقابل درس دیگری که تمرکز آن فقط روی مسائل محدب است و می‌توان آن را «بهینه‌سازی محدب (Convex Optimization)» نامید.
 
سرفصل‌ها:
  • مقدمات:
    • مقدمه‌ای بر مفاهیم گوناگون بهینه‌سازی: بهینه‌سازی پیوسته و گسسته، بهینه‌سازی نامقید (unconstrained) و بهینه‌سازی مقید (constrained)، بهینه‌سازی global و local، بهینه‌سازی deterministic و stochastic، مفاهیم convexity و Convex Optimization
    • به عنوان مقدمه، روش‌های Golden Section Search و فیبوناچی برای بهینه‌سازی توابع یک متغیره
    • مقدماتی از آنالیز حقیقی، با تأکید بر آنالیز توابع چندمتغیره، مفاهیم گرادیان و هسین (Hessian)، و سری تیلور توابع چندمتغیره
    • خواص گرادیان و الگوریتم Steepest Descent با اندازه قدم (step-size) ثابت، ایده ad-hoc برای داشتن اندازه قدم متغیر
    • مقدماتی از جبر خطی و فضاهای برداری (فرم درجه ۲ و ماتریس‌های مثبت معین)
  • بهینه‌سازی نامقید (Unconstrained Optimization):
    • تئوری بهینه‌سازی نامقید: قضایای شرایط لازم مرتبه اول، شرایط لازم مرتبه دوم و شرایط کافی مرتبه دوم
    • مفاهیم هم‌گرایی لوکال و گلوبال
    • الگوریتم Steepest Descent با اندازه قدم ایده‌آل
    • الگوریتم نیوتن ایده‌آل (اندازه قدم ۱) و اصلاح لونبرگ-مارکار (Levenberg-Marquardt) بر آن
    • مسائل حداقل مربعات (Least Squares) غیر خطی و الگوریتم‌های لونبرگ-مارکار (LMA) و گوس-نیوتن (GNA) برای حل آن
    • روش‌های Line-Search تقریبی: شروط گلدشتاین (Goldestein) و ولف و قوی ولف (Wolfe and Strong Wolfe)، اثبات هم‌گرایی روش‌های بهینه‌سازی مبتنی بر line-search مبتنی بر شرایط ولف، الگوریتم Backtracking برای line-search، الگوریتم line-search مبتنی بر شرایط ولف
    • اشاره به این که روش Conjugate Gradient در حالتی که تعداد متغیرهای بهینه‌سازی زیاد است کاربرد دارد
    • روش‌های Quasi-Newton: روش DFP، روش BFGS (Broyden, Fletcher, Goldfarb, Shanno)، خانواده Broyden
  • بهینه‌سازی مقید (Constrained Optimization):
    • تئوری بهینه‌سازی مقید: روش ضرایب لاگرانژ برای قیود تساوی و تعمیم آن به قیود نامساوی: شرایط لازم مرتبه اول و قضیه KKT (Karush-Kuhn-Tucker)، مفهوم Constraint Qualification، تعریف لاگرانژین، شرایط کافی مرتبه دوم، شرایط لازم مرتبه دوم، حساسیت و تعبیر ضرایب لاگرانژ، شرایط لازم مرتبه دوم، شرایط کافی مرتبه دوم، روش تابع پنالتی و اثبات قضیه KKT با استفاده از تابع پنالتی، مفهوم اثبات قضیه شرایط کافی با روش Augmented Lagrangian، مباحث تئوری، مفهوم Duality
    • اصول کلی الگوریتم‌های بهینه‌سازی غیر خطی مقید: روش حذف متغیرها، روش Gradient-Projection و اثبات هم‌گرایی آن برای مسائل Convex، روش Barrier، روش استفاده از تابع پنالتی: حداقل‌کردن غیر دقیق و اثبات قضیه مربوطه که برای بیان روش multiplier لازم است. اضافه‌کردن {λk} به قضیه و استخراج الگوریتم multiplier (بر مبنای Augmented Lagrangian) برای حل مسائل بهینه‌سازی مقید
  • خلاصه‌ای از روش‌های evolutionary:
    • الگوریتم‌های ژنتیک، Ant System و Particle Swarm Optimization (PSO)

مراجع:
  • J. Nocedal, S. J. Wright, Numerical Optimization, Springer, 1999
  • R. Fletcher, Practical Methods of Optimization, Wiley, 1989
  • E. K. P. Chong, S. H. Zak, An Introduction to Optimization, Wiley, 2001
  • D. G. Luenberger, Linear and Nonlinear Programming, 1984
  • D. P. Bertsekas, Nonlinear Programming, 1999
آخرین به‌روزرسانی: 17 / 4 / 1403