Навигация по сайту

Популярные статьи

Увлекательный поход по Крыму

Мы предлагаем вам увлекательный поход по живописным местам горного Крыма, полюбоваться красотами каньонов и горных водопадов, послушать журчание горных рек и пение птиц, насладиться экзотическими пейзажами

Отдых в Карпатах

Активный отдых - это очень важная часть жизни абсолютно любого человека, который способен обогащать и закалять человека как напрямую физически, улучшая форму, так и духовно, психологически, морально,

Моделювання в електроенергетиці - Оптимізаційні задачі. Загальні відомості

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

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

Умова пошуку екстремуму цільової функції записується в наступному вигляді:

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

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

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

де змінна де змінна   - це збільшення вектора керованих параметрів - це збільшення вектора керованих параметрів. Залежно від умови пошуку (пошук максимального або мінімального значення цільової функції) використовується або знак «+», або знак «-».

Приріст вектора керованих параметрів в більшості випадках обчислюється за формулою:

Приріст вектора керованих параметрів в більшості випадках обчислюється за формулою:

В даному вираженні В даному вираженні   - значення вектора керованих параметрів на k-му кроці,   - крок розрахунку, а   - напрямок пошуку екстремуму функції - значення вектора керованих параметрів на k-му кроці, - крок розрахунку, а - напрямок пошуку екстремуму функції.

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

крок розрахунку

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

Іншими словами, величина кроку розрахунку обчислюється при вирішенні наступного виразу:

В результаті вирішення даного рівняння ми отримаємо, що крок розрахунку в символьному вигляді визначається наступним чином:

де де   - значення аргументу функції на k-му кроці ітерації; - значення аргументу функції на k-му кроці ітерації;

n - кількість невідомих змінних, які визначаються в результаті виконання завдання;

L - деяка константа, яка визначається з визначника наступної матриці:

В результаті для визначення оптимального кроку розрахунку потрібно виконати великий обсяг обчислень цільової функції. Для зниження числа операцій на практиці використовують інший підхід: підбирають такі значення кроку розрахунку В результаті для визначення оптимального кроку розрахунку потрібно виконати великий обсяг обчислень цільової функції , Щоб вони задовольняли будь-якого з представлених нижче умові.

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

Критерій вибору кроку розрахунку за правилом Арміхо

Методика визначення кроку розрахунку оптимізаційної задачі відповідно до правила Арміхо полягає в наступному:

1.Задать коефіцієнт 1 в діапазоні від 0 до 1.

2.Задать початкове значення кроку 2 .

Процедура пошуку (перевірка виконання умови за правилом Арміхо)

3. У разі якщо умова за правилом Арміхо не виконується, тоді необхідно скорегувати крок розрахунку 3 , Де змінна може приймати будь-яке значення від 0 до 1, за замовчуванням приймемо, що змінна , а - поточний крок пошуку.

4. У разі якщо умова за правилом Арміхо виконується, тоді як крок розрахунку можна прийняти 4 , А процедура пошуку завершується.

Дане правило вимагає одноразового обчислення градієнта, після чого невелику кількість ітерацій витрачається на підбір відповідного кроку. Кожна з таких вкладених ітерацій, в свою чергу, вимагає обчислення значення цільової функції без градієнта, тобто проводяться випробування щодо легковагі. Слід зазначити, що дана умова задовольняється для всіх досить малих Дане правило вимагає одноразового обчислення градієнта, після чого невелику кількість ітерацій витрачається на підбір відповідного кроку . Правило Арміхо можна розширити на багатокритерійний випадок: нерівність 3.19 слід розуміти покомпонентно.

  • Друга умова (Правило Вольфа-Пауелла - Wolfe. P) є модифікованим критерієм, дозволяє вибрати крок розрахунку в разі виконання двох умов:

- функція - функція   не повинна перевищувати значення деякої спадної лінійної функції, яка дорівнює   в нулі: не повинна перевищувати значення деякої спадної лінійної функції, яка дорівнює в нулі:

- величина швидкості зміни функція в заданому напрямку - величина швидкості зміни функція в заданому напрямку   була в   раз більше, ніж швидкість зміни функції в початковій точці була в раз більше, ніж швидкість зміни функції в початковій точці

Критерій вибору кроку розрахунку за правилом Вольфа-Пауелла

Методика визначення кроку розрахунку оптимізаційної задачі відповідно до правила Вольфа-Пауелла полягає в наступному:

1. Поставити коефіцієнт 1 і в діапазоні від 0 до 1 .

2. Задати початкове значення кроку 2 , Прийняти коефіцієнт і

Процедура пошуку (перевірка виконання умови за правилом Вольфа-Пауелла)

3. У разі якщо перша умова по правилу Вольфа-Пауелла не виконується, тоді прийняти коефіцієнт 3 . Перейти до пункту №5.

4. У разі якщо друга умова за правилом Вольфа-Пауелла не виконується, тоді прийняти коефіцієнт 4 :

- у разі якщо - у разі якщо   , То перейти до пункту №5; , То перейти до пункту №5;

- у разі якщо - у разі якщо   виконати екстраполяцію, поклавши   , Де r - коефіцієнт екстраполяції виконати екстраполяцію, поклавши , Де r - коефіцієнт екстраполяції . Перейти до пункту №3.

5. Виконати поточний розрахунок кроку по формулі

де де   - коефіцієнт інтерполяції, який визначається в наступному діапазоні - коефіцієнт інтерполяції, який визначається в наступному діапазоні

Перейти до пункту №3.

6. У разі якщо виконуються обидві умови правилом Вольфа-Пауелла, тоді як крок розрахунку можна прийняти 6 , А процедура пошуку завершується.

  • Третя умова (правило Голдстейн-армій) дозволяє вибрати крок розрахунку, розглядаючи наступне нерівність:

Третя умова (правило Голдстейн-армій) дозволяє вибрати крок розрахунку, розглядаючи наступне нерівність:

Методика визначення кроку розрахунку оптимізаційної задачі відповідно до правила Голдстейн-армій полягає в наступному:

1.Задать коефіцієнт 1 і в діапазоні від 0 до 1 .

2. Задати початкове значення кроку 2

3. У разі якщо умова за правилом Голдстейн-армій не виконується, тоді необхідно скорегувати крок розрахунку 3 , Де змінна може приймати будь-яке значення від 0 до 1, за замовчуванням приймемо, що змінна , а - поточний крок пошуку.

4. У разі якщо умова за правилом Голдстейн-армій виконується, тоді як крок розрахунку можна прийняти 4 , А процедура пошуку завершується.

Критерії зупинки оптимізаційного процесу

Пошук оптимального рішення завершується в разі, коли на ітераційне кроці розрахунку виконується один (або декілька) критеріїв:

- траєкторія пошуку залишається в малій околиці поточної точки пошуку:

- приріст цільової функції не змінюється:

- градієнт цільової функції в точці локального мінімуму звертається в нуль:

Класифікація методів оптимізації.

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

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

Методи безумовної оптимізації

Класична задача безумовної оптимізації формулюється в такий спосіб: потрібно знайти вектор змінних Класична задача безумовної оптимізації формулюється в такий спосіб: потрібно знайти вектор змінних   , При якому цільова функція приймає екстремальне (максимальне або мінімальне значення) значення , При якому цільова функція приймає екстремальне (максимальне або мінімальне значення) значення

Екстремальне значення цільової функції відповідає оптимальному управлінню. У графічному вигляді постановка задачі виглядає наступним чином:

Завдання безумовної оптимізації для функції двох змінних

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

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

Найбільш популярними (з точки зору навчання у вищій школі) є такі методи вирішення оптимізаційних задач нульового порядку:

Методи одновимірного пошуку:

- Метод дихотомічного поділу і метод золотого перерізу - це методи одновимірної оптимізації, засновані на розподілі відрізка, на якому шукається екстремум, навпіл або в пропорціях золотого перетину (0,382 / 0,618), відповідно.

- Метод полиномиальной апроксимації (метод квадратичної інтерполяції) - це метод одновимірної оптимізації, відповідно до якого цільова функція апроксимується квадратичним поліномом.

Методи багатовимірного пошуку:

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

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

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

  • Методи першого порядку (градієнтні методи пошуку) для пошуку екстремуму вимагають обчислення значень функції в точках простору оптимізації, а також визначення аналітичного виду похідних першого порядку по керованим параметрам. Методи першого порядку називають також градієнтними, оскільки вектор перших похідних функції F (X) по оптимізуються змінним X є градієнт цільової функції:

Методи першого порядку називають також градієнтними, оскільки вектор перших похідних функції F (X) по оптимізуються змінним X є градієнт цільової функції:

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

Найбільш популярними (з точки зору навчання у вищій школі) є такі методи вирішення оптимізаційних задач першого порядку:

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

- Метод найшвидшого спуску - це метод знаходження локального мінімуму (максимуму) функції при русі вздовж градієнта з оптимальним кроком. Крок розрахунку вибирається мінімуму цільової (мінімізується) функції в напрямку спуску.

- Метод сполучених градієнтів (метод Флетчера-Ривса) - це метод безумовної оптимізації першого порядку, в якому напрям пошуку на черговому кроці є градиентное напрямок, скориговане з урахуванням напрямку пошуку на попередньому кроці.

- Метод змінної метрики (метод Девідона-Флетчера-Пауелла) - це метод безумовної оптимізації, в якому за основу взято рішення системи рівнянь, що виражають необхідні умови екстремуму.

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

Найбільш популярними (з точки зору навчання у вищій школі) є такі методи вирішення оптимізаційних задач другого порядку:

- метод Ньютона - це метод безумовної оптимізації, заснований на використанні необхідних умов безумовного екстремуму цільової функції: рівності нулю першої похідної. В Відповідно до даного методу визначають матрицю друге приватних похідних цільової функції по керованим параметрам (матрицю Гессе).

- Метод Марквардта - це метод безумовної оптимізації, спрямований на вирішення завдань про найменших квадратах. Є альтернативою методу Гаусса - Ньютона. Може розглядатися як комбінація останнього з методом градієнтного спуску або як метод довірчих інтервалів.

Методи умовної оптимізації

Класична задача умовної оптимізації формулюється в такий спосіб: необхідно знайти вектор змінних Класична задача умовної оптимізації формулюється в такий спосіб: необхідно знайти вектор змінних   , При якому цільова функція приймає екстремальне (максимальне або мінімальне значення) значення , При якому цільова функція приймає екстремальне (максимальне або мінімальне значення) значення

при заданих умовах (равенствами і / або нерівностями), при цьому число обмежень m може бути як більше, так і менше числа змінних n.

, J = 1,2, , J = 1,2, ..., m.

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

Завдання умовної оптимізації для функції двох змінних

Залежно від використовуваного методу розв'язання методи умовної оптимізації можна розділити на методи зведення задачі до безумовної оптимізації та методи безпосереднього вирішення.

  • Методи зведення задачі до безумовної оптимізації - це завдання умовної оптимізації, заснована на перетворення завдання нелінійного програмування в послідовність завдань безумовної оптимізації шляхом побудови допоміжних функцій

Найбільш популярними (з точки зору навчання у вищій школі) є такі методи вирішення оптимізаційних задач умовної оптимізації:

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

- Умови Куна-Таккера - це метод розв'язання оптимізаційної задачі математичного програмування із заданими обмеженнями. Метод є узагальненням методу множників Лагранжа на випадок загальної задачі нелінійного програмування з обмеженнями, як у вигляді рівності, так і у вигляді нерівностей.

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

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

Найбільш популярними (з точки зору навчання у вищій школі) є такі методи вирішення оптимізаційних задач умовної оптимізації:

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

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

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

Для того, щоб додати Ваш коментар до статті, будь ласка, зареєструйтесь на сайті.