You are not allowed to perform this action

بهینه‌سازی محدب

Convex Optimization

شماره درس: ۴۰۸۳۷ تعداد واحد: ۳
مقطع: کارشناسی ارشد نوع درس: نظری
پیش‌نیاز: – هم‌نیاز: –

اهداف درس

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

ریز مواد

  1. مجموعه‌های محدب (Convex Set)
    • مجموعه‌های محدب و آفین (Affine and Convex Sets)
    • عملیاتی که تحدب را حفظ می‌کند
  2. توابع محدب
    • خواص مقدماتی
    • عمیاتی که تحدب را حفظ می‌کنند
    • توابع مزدوج (Conjugate Functions)
    • توابع شبه‌محدب (Quasiconvex Functions)
  3. مسایل بهینه‌سازی محدب
    • مسایل بهینه‌سازی در حالت کلی
    • بهینه‌سازی محدب
    • مسایل بهینه‌سازی خطی
    • مسایل بهینه‌سازی درجه دوم
  4. دوگانگی (Duality)
    • تابع دوگان لاگرانژ
    • مسئله دوگان لاگرانژ
    • تعبیر هندسی و تعبیر نقطه زینی (Geometric and Saddle-point Interpretations)
    • شرایط بهینگی (Optimality Conditions and KKT conditions)
    • اختلال و تحلیل حساسیت (Perturbation and Sensitivity Analysis)
  5. الگوریتم‌های بهینه‌سازی نامقید
    • مسایل بهینه‌سازی نامقید
    • الگوریتم‌های کاهشی (Descent Algorithms)
    • الگوریتم کاهشی گرادیان (Gradient Descent Algorithm)
    • الگوریتم کاهش با تندترین شیب (Steepest Descent Algorithm)
    • الگوریتم نیوتون (Newton’s Method)
  6. الگوریتم‌های بهینه‌سازی با قیود تساوی
    • مسایل بهینه‌سازی با قیود تساوی
    • روش نیوتون با قیود تساوی
  7. الگوریتم‌های بهینه‌سازی با قیود نامساوی (روش‌های نقطه درونی، Interior-point Methods)
    • مسایل بهینه‌سازی با قیود نامساوی
    • تابع سد لگاریتمی و مسیر مرکزی (Logarithmic Barrier Function and Central Path)
    • روش سد (Barrier Method)
    • امکان‌پذیری و روش‌های فاز یک (Feasibility and Phase I Methods)
    • روش‌های نقطه درونی اولیه-دوگان (Primal-Dual Interior-point Methods)
  8. کاربردها (Applications)
    • رگرسیون خطی، رگرسیون لجستیکی
    • ماشین بردار پشتیبان
    • مسایل بهینه‌سازی رنک-پایین ((low-rank optimization problems (e.g., Netflix, video security)
    • اینترنت به عنوان یک مسئله بهینه‌سازی محدب
  9. بهینه‌سازی تصادفی (Stochastic Optimization)
    • تعریف کلی یک مساله‌ی بهینه‌سازی تصادفی
    • انواع قیود در بهینه‌سازی تصادفی
    • مسایل بهینه‌سازی تصادفی نوع یک و دو (Type I & Type II Stochastic Optimization Problems)
    • الگوریتم کاهشی گرادیان تصادفی (Stochastic Gradient Descent Algorithm)
    • الگوریتم‌های بهینه‌سازی تصادفی موازی و توزیع‌شده (Parallel and Distributed Stochastic Optimization Algorithms)

ارزیابی

  1. تمرین: ۲۰ درصد
  2. میان‌ترم: ۳۰ درصد
  3. پایان‌ترم: ۵۰ درصد

مراجع

  1. Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
  2. Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Series in Operations Research and Financial Engineering, 2nd edition, 2006.
  3. Convex Optimization taught by Ryan Tibshirani at CMU from 2013 to 2019.