Nonlinear programming — תכנות לא-לינארי

תכנות לא-לינארי (NLP) — הוא ענף של תכנות מתמטי וחקר פעולות, העוסק בבעיות אופטימיזציה שבהן הפונקציה המטרה ו/או לפחות אחד מהאילוצים הם פונקציות לא-לינאריות של משתני ההחלטה.

NLP הוא הכללה של תכנות לינארי ומאפשר לדגם מחלקה רחבה יותר של מערכות ותהליכים ממשיים, שבהם התלויות בין המשתנים אינן פרופורציונליות בהכרח (כלומר, מתוארות על ידי עקומות ולא על ידי קווים ישרים).

נושא ומטרה

תכנות לא-לינארי משמש למציאת פתרונות אופטימליים במצבים שבהם:

• התלות של מדד המטרה (רווח, עלויות, יעילות וכדומה) בפרמטרים הנשלטים היא לא-לינארית (לדוגמה, תשואה פוחתת לגודל, עלויות ריבועיות).
• האילוצים על משאבים או על תהליכים טכנולוגיים מתוארים על ידי יחסים לא-לינאריים (לדוגמה, תגובות כימיות, חוקים פיזיקליים, תלויות כלכליות).

בעיות NLP מתעוררות בתחומים רבים:

• תכנון הנדסי (אופטימיזציה של מבנים ותהליכים).
• כלכלה ופיננסים (אופטימיזציה של תיק השקעות תוך התחשבות בסיכון, מודלינג של שוק).
• טכנולוגיה כימית (אופטימיזציה של משטרי כורים).
• Machine Learning (אימון רשתות נוירונים, שיטת וקטורי תמיכה).
• ניהול תהליכי ייצור. לוגיסטיקה (תוך התחשבות בעלויות לא-לינאריות).

הגדרה מתמטית של בעיית NLP

בעיית התכנות הלא-לינארי הכללית מנוסחת כדלקמן:

נדרש למצוא קבוצת ערכים של משתני ההחלטה המקסימה או הממזערת פונקציה מטרה לא-לינארית. כאשר ערכי המשתנים חייבים לקיים מערכת אילוצים, שניתן לבטאם הן בצורת אי-שוויונות (לדוגמה, "גודל A חייב להיות קטן מ-B או שווה לו") והן בצורת שוויונות (לדוגמה, "גודל C חייב להיות שווה בדיוק ל-D"). חשוב שלפחות אחת מהפונקציות המתארות את המטרה או את האילוצים תהיה לא-לינארית. לעיתים קרובות מתווספים תנאי אי-שליליות של המשתנים, כלומר הדרישה שערכיהם יהיו גדולים מאפס או שווים לו.

קבוצת כל קבוצות ערכי המשתנים המקיימים את האילוצים מהווה את תחום הפתרונות הישימים (TPY).

הבדלים מתכנות לינארי

תכנות לא-לינארי שונה באופן מהותי מתכנות לינארי (LP):

• אי-לינאריות: הפונקציה המטרה או האילוצים (או שניהם) מכילים תלויות לא-לינאריות.
• מאפייני תחום הפתרונות: תחום הפתרונות הישימים ב-NLP עשוי להיות לא-קמור (בניגוד ל-LP, שבו תחום הפתרונות הישימים הוא תמיד פוליטופ קמור).
• מאפייני האופטימום: הפתרון האופטימלי ב-NLP אינו חייב להימצא בקודקוד תחום הפתרונות, הוא יכול להיות על הגבול או בפנים התחום. ב-NLP עשויים להתקיים אופטימומים מקומיים שאינם גלובליים.
• מורכבות הפתרון: בעיות NLP הן, ככלל, קשות הרבה יותר לפתרון מבעיות LP. אין אלגוריתם אוניברסלי יחיד, הדומה לשיטת הסימפלקס, לכל בעיות NLP.

קשיים ואתגרים עיקריים של NLP

פתרון בעיות תכנות לא-לינארי כרוך בשורה של קשיים:

• קיום אקסטרמות מקומיות: רוב שיטות NLP מבטיחות מציאת אופטימום מקומי בלבד (פתרון הטוב ביותר בסביבה מסוימת). מציאת האופטימום הגלובלי (הפתרון הטוב ביותר בכל תחום הפתרונות) היא משימה קשה, במיוחד עבור בעיות לא-קמורות.
• אי-קמירות: אם הבעיה אינה קמורה (הפונקציה המטרה או תחום הפתרונות אינם קמורים), עלולים להתקיים אופטימומים מקומיים רבים, ושיטות גרדיאנט סטנדרטיות עשויות "להיתקע" באחד מהם.
• מורכבות חישובית: אלגוריתמים לפתרון NLP דורשים לעיתים קרובות משאבי חישוב גדולים בהרבה בהשוואה ל-LP.

מחלקות חשובות של בעיות NLP

למרות המורכבות הכללית, קיימות תתי-מחלקות חשובות של בעיות NLP שעבורן פותחו שיטות פתרון יעילות:

• תכנות קמור: בעיית מינימיזציה של פונקציה קמורה על קבוצה קמורה של פתרונות ישימים (או מקסימיזציה של פונקציה קעורה). תכונה מרכזית: כל מינימום מקומי הוא גם מינימום גלובלי. דבר זה מפשט באופן משמעותי את החיפוש אחר הפתרון האופטימלי.
• תכנות ריבועי: הפונקציה המטרה היא ריבועית וכל האילוצים הם לינאריים.
• תכנות ספרבילי: הפונקציה המטרה והאילוצים ניתנים לייצוג כסכומים של פונקציות, שכל אחת מהן תלויה במשתנה אחד בלבד.

שיטות לפתרון בעיות NLP

שיטות לפתרון בעיות תכנות לא-לינארי (NLP)

I. שיטות אופטימיזציה ללא אילוצים:

• שיטות גרדיאנט (שיטת הירידה התלולה ביותר, שיטת גרדיאנטים צמודים);
• שיטת ניוטון ושיטות קוואזי-ניוטון (לדוגמה, BFGS);
• שיטות המשתמשות בקירוב ההסיאן.

II. שיטות אופטימיזציה עם אילוצים:

• שיטות טרנספורמציה:
  • שיטת פונקציות עונשין (penalty methods);
  • שיטת פונקציות מחסום (barrier methods).
• שיטות חיפוש כיוון ישיר:
  • שיטת הכיוונים הישימים.
• שיטות המבוססות על תנאי אופטימליות:
  • שיטות Karush-Kuhn-Tucker (תנאי KKT);
  • שיטת מכפילי לגרנז'.
• שיטות איטרטיביות:
  • תכנות ריבועי סדרתי (SQP);
  • שיטות נקודות פנימיות.

III. שיטות אופטימיזציה גלובלית:

• שיטות היוריסטיות ומטא-היוריסטיות:
  • אלגוריתמים גנטיים;
  • סימולציה של שיפור אטי (simulated annealing);
  • חיפוש עם טבו (tabu search).
• שיטות דטרמיניסטיות:
  • ענפים וחסמים (branch and bound);
  • אלגוריתמים לאופטימיזציה גלובלית לבעיות בעלות מבנה מיוחד.

ספרות

• Bazaraa, M., Shetty, C. Nonlinear Programming: Theory and Algorithms. — ניו יורק: Wiley, 1979.
• Fiacco, A., McCormick, G. Nonlinear Programming: Sequential Unconstrained Minimization Techniques. — SIAM, 1990.
• Himmelblau, D. Applied Nonlinear Programming. — McGraw-Hill, 1972.
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. — Springer, 2006. (2nd ed.)

ראו גם

• חקר פעולות
• אופטימיזציה
• תכנות לינארי
• תכנות קמור
• פונקציה מטרה
• אילוצים
• תחום פתרונות ישימים