Метод невизначених множників Лагранжа

З курсу математичного аналізу відомі методи вирішення нескладних оптимізаційних задач, в яких задано аналітичний вираз критерію оптимальності – цільової функції від керуючих впливів, при цьому цільова функція є безперервною або гладкою. Завдяки цьому можна знайти аналітичні вирази для їх перших похідних, а для гладких функцій і других похідних, а потім, використовуючи різні ознаки досліджувати "підозрілі" на екстремум точки. При перевірці відкидають ті точки, які не можуть визначати екстремальні значення критерію, а серед решти вибирають ті, які можуть задовольняти найбільшому або найменшим значенням критерію оптимальності залежно від постановки задачі.

Оскільки система рівнянь, що отримується в результаті прирівнювання нулю перших похідних функцій, забезпечує лише необхідні умови оптимальності, то її рішення в подальшому перевіряють за допомогою достатніх умов (критерій Сильвестра) з метою виявити тип екстремуму.

Ці методи дослідження дозволяють знаходити екстремум в так званих задачах безумовної оптимізації. При наявності обмежень на область зміни незалежних змінних, тобто в задачах умовної оптимізації, згадані методи використовують тільки для знаходження екстремальних значень всередині області. Крім того, проводять аналіз значень цільової функції на кордоні області зміни, де може перебувати екстремум функції, який може виявитися досить складним, особливо для задач з великим числом змінних.

При вирішенні класичної задачі на умовний екстремум, що містить обмеження типу рівностей, використовують метод невизначених множників Лагранжа, який дозволяє звести задачу умовної оптимізації до вирішення більш простої задачі безумовної оптимізації, хоча і більш високої розмірності. Використовуються зазначені вище методи дослідження екстремуму функції класичного аналізу, при цьому порядок системи рівнянь, розв'язуваної для знаходження екстремумів, відповідно підвищується на число обмежень, що мали місце. Цей метод часто використовується як допоміжний при вирішенні іншими методами різних задач оптимізації, в яких містяться обмеження типу рівностей, наприклад в варіаційному численні і динамічному програмуванні.

Лінійне програмування

Лінійне програмування – це математичний апарат, що дозволяє вирішувати задачі оптимізації, в яких критерій оптимальності є лінійною функцією кількох змінних, а область їх зміни визначається сукупністю лінійних виразів.

Кожній задачі лінійного програмування може бути поставлена у відповідність двоїста їй задача. Центральним фактом в лінійному програмуванні є теорема подвійності, що встановлює рівність оптимальних значень цільових функцій прямої та двоїстої задач. Зазначимо, що кожній задачі лінійного програмування відповідає інша задача, яка називається двоїстою по відношенню до вихідної. Рішення двоїстої задачі може виявитися легше рішення вихідної задачі і бути корисним при вирішенні прямої задачі, а також може бути використано при розробці різних алгоритмів.

Багато задач лінійного програмування можуть бути вирішені за допомогою практично універсального алгоритму – симплексного методу, який дозволяє за скінченне число кроків знаходити оптимальне рішення. При цьому наявність у вихідній постановці різних комбінацій обмежень (рівності або нерівностей) і їх числа не позначається на можливостях застосування алгоритму, оскільки можливі еквівалентні перетворення, що дозволяють звести вихідну задачу до потрібного вигляду.

На відміну від інших методів додаткові перевірки на оптимальність одержуваних тут рішень не потрібні. В задачах лінійного програмування допустиму множину рішень можна представити у вигляді опуклого багатогранника, при цьому шукане рішення знаходиться в вершині багатогранника, а іноді на його ребрі або межі. Симплекс-метод дозволяє, почавши з будь-якої вершини, далі рухатися в такому напрямку, перебираючи вершини, при якому значення цільової функції зростає (зменшується). У багатограннику кожній вершині відповідає своя система рівнянь, що обирається спеціальним чином з системи нерівностей обмежень і умов задачі. Таким чином, обчислювальна процедура симплекс-методу полягає в послідовному вирішенні систем лінійних алгебраїчних рівнянь, тобто перебором вершин опуклого багатогранника в багатовимірному просторі.

Нелінійне програмування

Під нелінійним програмуванням розуміється велика група числових методів, які іноді називають також "прямими методами" рішення оптимізаційних завдань. З їх допомогою вирішуються задачі з нелінійними цільовими функціями, в яких на шукані змінні можуть бути накладені нелінійні обмеження, які мають вигляд рівності або нерівностей. По суті методи нелінійного програмування використовують, якщо жоден з методів інших розділів математичного програмування не дозволяє скільки-небудь просунутися у вирішенні оптимізаційної задачі.

Методи одновимірної оптимізації: сканування, половинного ділення, золотого перетину, чисел Фібоначчі, ДСК-Пауела мають як самостійне значення, так і часто використовуються в якості допоміжних (наприклад, під час спуску по напрямку) в багатовимірних методах оптимізації. При використанні цих методів задають інтервал пошуку зміни змінної і точність визначення оптимального значення цієї змінної. Більшість методів (за винятком методу сканування) застосовуються для унiмодальних функцій.

Серед методів безумовної багатовимірної оптимізації виділяють методи нульового, першого і другого порядків. У методах нульового порядку на кожному кроці при пошуку екстремуму цільової функції використовується інформація про значеннях цієї функції на попередніх кроках, в методах першого порядку, крім цього, використовується інформація про похідні, а в методах другого порядку – також і других похідних функції в цих точках.

До методів безумовної багатовимірної оптимізації нульового порядку відносять методи сканування, покоординатного спуску, багатогранника, що деформується; першого порядку – методи релаксації, найшвидшого спуску; другого порядку – ньютонівські і квазіньютонівські методи. Заслуговує також згадка про методи випадкового пошуку безумовного екстремуму цільової функції. Для вирішення задач умовної оптимізації з обмеженнями типу нерівностей і рівностей використовують методи прямого пошуку з поверненням, проекціювання вектора градієнта, штрафних функцій. Особливу роль нелінійне програмування грає на окремих етапах вирішення завдань оптимізації іншими методами, наприклад за допомогою динамічного програмування, принципу максимуму і ін.

Опукле програмування

Розглядаються методи вирішення задач мінімізації опуклих функцій на опуклих множинах, що задаються системами нерівностей і рівностей. Існує закінчена теорія опуклого програмування і розроблені числові методи вирішення задач. Центральним фактом опуклого програмування є теорема Куна-Такера про сідлову точку, яка дає необхідну і достатню умову існування оптимального рішення задачі. При деяких додаткових умовах це дозволяє отримати ефективні алгоритми вирішення, пов'язані з пошуком сідлової точки. Інший підхід до вирішення задачі пов'язаний з пошуком можливих напрямків, які не виводять з множини допустимих точок і вздовж яких цільова функція зменшується. На кожній ітерації такого методу обчислюється можливий напрямок, що виходить з чергової точки, після чого проводиться зрушення у цьому напрямі. Використовуються методи, засновані на зведенні задач опуклого програмування до безумовної оптимізації (методи штрафів) та послідовної їх апроксимації за допомогою лінійного програмування.

Квадратичне програмування

Розглядаються методи вирішення задач мінімізації опуклих квадратичних функцій на множинах, що задаються системами лінійних нерівностей і рівностей. Розроблено закінчену теорію і числові методи вирішення задач, в тому числі типу симплексного методу, що призводять до вирішення за скінченне число кроків (ітерацій). Ці задачі часто виникають як допоміжні при вирішенні різних задач математичного програмування.

Дискретне програмування

Дискретне програмування займається дослідженням вирішення задач оптимізації на скінченних множинах і, зокрема рішення цілочислових задач. Розглядаються задачі, які називають нетривіальними, в яких виділяють додаткові умови: число елементів на розглянутих скінченних множинах дуже велике, настільки, щоб не можна було вирішити задачу вручну шляхом перебору і порівняння значень цільової функції або на ЕОМ; задача не є регулярною. Універсальних ефективних методів вирішення задач дискретного програмування не створено головним чином через труднощі їх вирішення, обумовлених великим числом локальних екстремумів. Існують досить відомі методи – метод гілок і меж і його різні модифікації, які є методами спрямованого перебору. Їх ефективно застосовують для вирішення спеціалізованих задач, проте серед них можна підібрати такі задачі, для яких згадані методи спрямованого перебору незначно відрізняються від повного перебору. Іншим джерелом труднощів вирішення задач дискретного програмування є те, що допустима множина часто задається в неявній формі. Наприклад, у цілочисловому лінійному програмуванні його визначають у вигляді цілочислових рішень системи лінійних нерівностей. Таке і складніше задання множин допустимих рішень робить нетривіальною не тільки саму задачу перерахування елементів множини, а й вказівки навіть одного елемента. Основні результати дискретного програмування отримані для більш вузьких класів задач – транспортної задачі, задачі про комівояжера і кількох комівояжерах, лінійного цілочислового програмування, задачі про розклади, екстремальні задачі на графах та ін. У даний час розвиваються наближені методи для вирішення практичних задач великої розмірності, які принципово мало відрізняються від методів пошуку екстремумів безперервних функцій і функціоналів, алгоритмів локальної оптимізації, випадкового пошуку.

Геометричне програмування

За допомогою методів геометричного програмування вирішується один спеціальний клас задач математичного програмування, в яких цільові функції і обмеження задають у вигляді позитивних поліномів, тобто сум добутків степеневих функцій від незалежних змінних. Подібні задачі часто зустрічаються при проектуванні. В окремих випадках ряд задач нелінійного програмування за допомогою апроксимації цільових функцій і обмежень доцільно звести до задачі геометричного програмування. В основі алгоритму розв'язання задачі геометричного програмування лежить відома нерівність між середньоарифметичним і середньогеометричним. Саме воно дало назву цим методам і саме завдяки йому будується двоїста функція і формулюється двоїста задача, вирішення якої в багатьох випадках набагато простіше, ніж рішення вихідної задачі. Між рішенням прямої і двоїстої задач існує певний взаємозв'язок.

Стохастичне програмування

За допомогою методів стохастичного програмування вирішуються задачі умовної оптимізації при неповній інформації про параметри умов задачі, які (всі або деякі) можуть виявитися невизначеними або випадковими. В одному випадку можливо встановити ті чи інші імовірнісні характеристики параметрів умов задачі, в іншому – ні. У першому випадку описується ситуація, пов'язана з ризиком, у другому – ситуація, пов'язана з невизначеністю. В окремих задачах стохастичного програмування замінюють випадкові параметри їх середніми значеннями і вирішують детерміновану задачу. Існують постановки задач, в яких обмеження повинні задовольнятися при всіх реалізаціях випадкових параметрів, які називаються жорсткими постановками. Іноді в задачах необхідно, щоб забезпечувалася вірогідність попадання рішення в допустиму область не нижче заданої, такі задачі називаються задачами з ймовірними обмеженнями. Цільовою функцією цих моделей є зазвичай математичне очікування реалізацій показника якості рішення задачі оптимізації або ймовірність перевищення випадковим значенням показника якості деякого фіксованого порога.

Динамічне програмування

У динамічному програмуванні досліджуються задачі оптимізації дискретних багатостадійних (багатокрокових) процесів, в яких критерій оптимальності задається у вигляді адитивної або мультиплікативної функцій критеріїв оптимальності окремих стадій. Відповідно до принципу оптимальності Беллмана, кожній точці оптимальної стратегії притаманна властивість. Відрізок траєкторії, що починається з цієї точки, теж оптимальний. Іншими словами, оптимальна поведінка має ту властивість, що якою б не була початкова поведінка процесу, наступні рішення повинні бути оптимальними щодо вже реалізованого стану. Застосування цього принципу дозволяє вивести функціональні рівняння Беллмана, що лежать в основі алгоритмів розв'язання задач динамічного програмування. По суті цей метод дає можливість послідовно визначати оптимальні стратегії управління на всіх стадіях процесу, починаючи з останньої. При цьому управління на кожній стадії знаходять, вирішуючи за допомогою методів нелінійного програмування окремі задачі оптимізації, значно менш складні, ніж вихідна задача оптимізації. Завдяки цьому досягається серйозний виграш у часі вирішення задачі. Обмеження на змінні враховуються при вирішенні окремих задач оптимізації, причому обмеження типу рівностей дозволяють зменшувати розмірність цих задач за допомогою методу множників Лагранжа.