کتاب Mathematics of Convex and Linear Optimization

کتاب Mathematics of Convex and Linear Optimization یا ریاضیات بهینه‌سازی محدب و خطی، یک منبع بسیار عالی برای یادگیری ریاضیات خطی و بهینه‌سازی ریاضیاتی می‌باشد. این کتاب در 15 فصل به آموزش مقدماتی تا بیان نکات پیشرفته ریاضیات خطی خواهد پرداخت.

در ادامه مقدمه‌ای از کتاب Mathematics of Convex and Linear Optimization را از زبان نویسنده شرح خواهیم داد.

مقدمه‌ای بر کتاب Mathematics of Convex and Linear Optimization:

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

با این حال، در سه دهه گذشته الگوریتم‌های جدید و بسیاری از برنامه های کاربردی جدید علاقه به بهینه‌سازی محدب را افزایش داده اند. مانند برنامه نویسی خطی، مشکلات کاربردی بزرگ اکنون می‌توانند به طور مؤثر و قابل اعتماد حل شوند. از نظر مفهومی، برنامه‌ریزی محدب با برنامه‌ریزی خطی بهتر از برنامه‌ریزی غیرخطی عمومی تناسب دارد.

این نوع بهینه‌سازی‌ها برای این کتاب نیز مناسب هستند، زیرا دارای یک نظریه واضح و یکپارچه‌کننده اصول ریاضی هستند که بسیاری از آن‌ها را شامل می‌شود. رویکرد اتخاذ شده دارای سه تأکید است.

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

یک رویکرد ریاضی برای برقراری ارتباط به شیوه‌ای مختصر و یکپارچه استفاده می‌شود. نشانه‌گذاری ماتریسی در اوایل معرفی شده و به طور گسترده استفاده می‌شود. سؤالات صحت محو نمی‌شوند. مسائل ریاضی تشریح شده و در جایی که سطح مناسب باشد، شواهد ارائه می‌شود. ارتباط با برخی موضوعات دیگر در ریاضیات مقطع کارشناسی ایجاد شده است. این رویکرد در نتیجه 30 سال تدریس من این موضوعات به دانشجویان ریاضی در مقطع کارشناسی شکل گرفت.

بیشتر بخوانید: کتاب Essential Mathematics for Quantum Computing

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

بسیاری از کتاب‌های درسی تحقیق در عملیات مقدماتی بر مدل‌ها و الگوریتم‌ها بدون توجیه و بدون استفاده از زبان ریاضی تأکید دارند. چنین کتاب‌هایی برای دانش‌آموزان ریاضی مناسب نیستند. از سوی دیگر، متونی که به صورت ریاضی بیشتر به موضوع می‌پردازند، بیش از حد پیشرفته و جزئی می‌شوند و هزینه‌های کاربردی را از بین می‌برند. کتاب Mathematics of Convex and Linear Optimization به دنبال یک راه میانه است.

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

با توجه به این مخاطب، تعداد انواع مختلف مسئله و الگوریتم‌ها به حداقل می‌رسد و در عوض بر رویکردهای یکپارچه و مشکلات کلی‌تر تأکید می‌شود. به طور خاص، الگوریتم‌های اکتشافی تنها به طور خلاصه ذکر شده است. آن‌ها برای مسائل سخت استفاده می‌شوند و از رویکردهای مختلف زیادی استفاده می‌کنند، در حالی که کتاب Mathematics of Convex and Linear Optimization روی مسائلی تمرکز دارد که الگوریتم‌های کارآمد یا حداقل رویکردهای یکپارچه دارند.

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

کتاب Mathematics of Convex and Linear Optimization همچنین به طور خاص برای مربیانی نوشته شده است که از نظر ریاضی آموزش دیده اند، نه برای یک متخصص در تحقیق در عملیات و بهینه‌سازی. درمان دقیق تفکر الگوریتمی و آشنایی با پیچیدگی الگوریتم‌ها برای کمک به این مربیان در نظر گرفته شده است. سبک ریاضی در سراسر کتاب باید بیشتر با اساتید ریاضی سازگار باشد.

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

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

فصل‌های 1 تا 4 کتاب Mathematics of Convex and Linear Optimization به معرفی بهینه‌سازی و مدل سازی بهینه‌سازی اختصاص داده شده است. مدل‌های محدب بعداً با مواد دیگر در بهینه‌سازی محدب ظاهر می‌شوند. بر اساس تجربه من در تدریس به دانش‌آموزان ریاضی، آن‌ها مدل سازی را چالش برانگیز می‌دانند.

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

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

فصل‌های 5 تا 8 کتاب Mathematics of Convex and Linear Optimization، الگوریتم‌های تکراری را مورد بحث قرار می‌دهند، مثال‌هایی را که به راحتی توضیح داده می‌شوند از بهینه‌سازی گسسته، و پیش‌زمینه نظری برنامه‌ریزی خطی ارائه می‌کنند. این شامل کمی پیچیدگی محاسباتی، تحدب و مطالعه چند وجهی، شرایط بهینه برای برنامه‌ریزی خطی، و نظریه دوگانگی برای برنامه‌ریزی خطی است. پوشش همه این‌ها قبل از معرفی روش سیمپلکس غیر متعارف است.

با این حال، از نظر مفهومی، این موضوعات با هم تناسب دارند و به روش سیمپلکس بستگی ندارند. کنار هم قرار دادن آن‌ها بر این واقعیت تأکید می‌کند. فصل 8 در مورد دوگانگی مستقل از فصل 9 در روش سیمپلکس است، به طوری که می‌توان آن‌ها را به هر ترتیب پوشش داد. من معمولاً از مباحث بخش‌های 5.3، 7.5، 8.4 و 8.5 صرف نظر می‌کنم تا به روش سیمپلکس در حدود وسط ترم برسم.

فصل‌های 9 تا 11 کتاب Mathematics of Convex and Linear Optimization، روش سیمپلکس، از جمله تحلیل حساسیت، و سایر الگوریتم‌های برنامه‌ریزی خطی را ارائه می‌کنند. یک رویکرد توسعه ای برای ارائه روش سیمپلکس در نظر گرفته شده است. با استدلال هندسی در مورد اینکه چرا کار می‌کند، ابتدا به شکل “ساده‌لوح” ارائه می‌شود، جایی که به اصطلاح ماتریس مبنا معکوس از ابتدا در هر تکرار محاسبه می‌شود. در حالی که این فرم از نظر محاسباتی ناکارآمد است، توضیح آن برای یک دانشجوی ریاضی، هم برای محاسبه و هم برای توجیه کارکرد الگوریتم، بسیار آسان است. هنگام کار کردن با مثال‌ها، می‌توان از فناوری برای معکوس کردن و ضرب ماتریس‌ها استفاده کرد.

پس از تکمیل تصویر چرایی کارکرد روش (انحطاط، سیمپلکس دو فازی)، بخش 9.4 موضوع کارآمدتر کردن روش سیمپلکس، از جمله فرم تابلو و روش سیمپلکس تجدیدنظر شده را مطرح می‌کند. مربیانی که می‌خواهند با تابلو شروع کنند می‌توانند از مطالب موجود در اینجا استفاده کنند. فصل 10 کتاب Mathematics of Convex and Linear Optimization در مورد تجزیه و تحلیل حساسیت، که به فصل 8 بستگی دارد، می‌تواند بدون از دست دادن تداوم نادیده گرفته شود. با این حال، تفسیر متغیرهای دوگانه به عنوان قیمت‌های سایه و مشتقات جزئی، حتی در عصری که تجزیه و تحلیل حساسیت را می‌توان با حل برنامه‌های خطی اصلاح شده به سرعت انجام داد، غنی می‌شود.

تفسیری از دوگانگی قوی از نظر هزینه‌های متوسط ​​نیز در بخش 10.3 ارائه شده است. فصل 11 کتاب Mathematics of Convex and Linear Optimization، سه الگوریتم دیگر را برای برنامه‌ریزی خطی ارائه می‌کند که همگی بر دوگانگی متکی هستند: سیمپلکس دوگانه، سیمپلکس حمل‌ونقل، و روش نقطه داخلی دوگانه اولیه یا دنباله‌روی مسیر. روش سیمپلکس حمل و نقل ابتدا به عنوان یک مسئله جریان حداقل هزینه ارائه شده است، سپس به مشکلات حمل و نقل اختصاص یافته است.

در فصل‌های 12 و 13 کتاب Mathematics of Convex and Linear Optimization الگوریتم‌های برنامه‌ریزی اعداد صحیح ارائه شده است. این‌ها به دلیل اهمیت برنامه‌ریزی خطی برای ایجاد مرزها هنگام حل یک برنامه عدد صحیح، به مطالب قبلی مربوط می‌شوند. برنامه‌نویسی اعداد صحیح همچنین قدرت مدل‌سازی بیشتری دارد، همانطور که با کاربردهای فراوان در فصل 14 نشان داده شده است.

فصل‌های قبلی کتاب Mathematics of Convex and Linear Optimization برای آماده کردن خواننده برای درک آسان‌تر برنامه‌نویسی محدب طراحی شده‌اند. شرایط بهینه KKT و قضایای دوگانگی تعمیم دوگانگی لاگرانژی هستند (بخش 8.4). شرایط لازم و کافی برای یک بهینه جهانی از تئوری تحدب که قبلاً برای برنامه‌های خطی در فصل 6 اعمال شده است، پیروی می‌کند.

فصل 15 کتاب Mathematics of Convex and Linear Optimization به روش نقطه داخلی اولیه-دوگانه، که برای برنامه‌های خطی در بخش 11.3 ارائه شد، ختم می‌شود. برنامه‌نویسی درجه دوم نیز معرفی شده است و ارتباط بین روش نقطه داخلی اولیه-دوگانه و برنامه‌ریزی درجه دوم متوالی ایجاد می‌شود.

مطالب تکمیلی در وب سایت www.gordon.edu⁄michaelveatch/optimization برای کتاب موجود خواهد بود. راهنمای کامل راه حل در دسترس مربیان قرار خواهد گرفت.

کتاب Mathematics of Convex and Linear Optimization حاوی مقدار مطالبی است که در یک رشته معمولی دو ترم از کلاس‌های کارشناسی پوشش داده شده است. یک دوره ترم با تمرکز بر برنامه‌ریزی خطی می‌تواند فصل‌های 1، 2، بخش‌های 3.1-3.2، 5، 6، بخش‌های 7.1-7.4 و 8.1-8.3، 9، 10 به علاوه برخی موضوعات دیگر از این فصل‌ها و فصل 11 را پوشش دهد.

و برنامه‌نویسی عدد صحیح می‌تواند فصل‌های 1، 2، بخش‌های 3.1-3.2، 4، 5، 6، بخش‌های 7.1-7.4 و 8.1-8.3، 9، 12، و 13 کتاب Mathematics of Convex and Linear Optimization را پوشش دهد. 1-3، 5-7.4، 8، 9، بخش‌های 11.1-11.13، 14، و 15.

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

بخش 5.3 کتاب Mathematics of Convex and Linear Optimization، در مورد پیچیدگی محاسباتی، اگرچه دشوار نیست، فقط گاهی در فصل‌های بعدی ذکر می‌شود.

بخش 7.5 کتاب Mathematics of Convex and Linear Optimization، شرایط بهینه مورد نیاز برای حل برنامه‌های خطی را به چندوجهی عمومی گسترش می‌دهد.

بخش 8.4 کتاب Mathematics of Convex and Linear Optimization، دوگانگی لاگرانژی را برای برنامه‌های خطی معرفی می‌کند و نشان می‌دهد که معادل دوگانه معمولی است. تنها زمانی مورد نیاز است که برنامه‌نویسی محدب (فصل 14) پوشش داده شود.

لم فارکاس در بخش 8.5 کتاب Mathematics of Convex and Linear Optimization ارائه شده است و رویکرد دیگری به قضایای دوگانگی ارائه می‌کند. استراتژی‌های محاسباتی در بخش 9.4 برای روش سیمپلکس مهم هستند اما در ادامه استفاده نمی‌شوند. الگوریتم نقطه داخلی در بخش 11.4 از نظر محاسباتی بیشتر درگیر است. ارتباط نزدیکی با بخش 15.5 دارد.

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

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

مایکل اچ. ویچ

Wenham، MA
مارس، 2020

سرفصل‌های کتاب Mathematics of Convex and Linear Optimization:

• Preface
• About the Companion Website
• 1 Introduction to Optimization Modeling
• 2 Linear Programming Models
• 3 Linear Programming Formulations
• 4 Integer Programming Models
• 5 Iterative Search Algorithms
• 6 Convexity
• 7 Geometry and Algebra of LPs
• 8 Duality Theory
• 9 Simplex Method
• 10 Sensitivity Analysis
• 11 Algorithmic Applications of Duality
• 12 Integer Programming Theory
• 13 Integer Programming Algorithms
• 14 Convex Programming: Optimality Conditions
• 15 Convex Programming: Algorithms
• A Linear Algebra and Calculus Review
• Bibliography
• Index

فایل کتاب Mathematics of Convex and Linear Optimization را می‌توانید پس از پرداخت، دریافت کنید.