додати матеріал


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

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Південно-Уральський державний університет
Кафедра АІУ
реферат на тему:
Нелінійне програмування
Виконав: Пушніков А. А., ПС-263.
Перевірив: різностатева О.А.
Челябінськ - 2003.

Зміст
1. Постановка задачі нелінійного програмування
2. Критерії оптимальності в задачах з обмеженнями
2.1. Завдання з обмеженням у вигляді рівностей
2.2. Множники Лагранжа
3. Умови Куна-Таккера
3.1. Умови Куна-Таккера і завдання Куна-Таккера
3.2. Інтерпретація умов Куна-Таккера
3.3. Теореми Куна-Таккера
4. Функції декількох змінних
4.1. Методи прямого пошуку
4.1.1. Метод пошуку по симплекс (S2 - метод)
4.1.2. Метод пошуку Хука-Дживса

1. Постановка задачі нелінійного програмування.
У задачі нелінійного програмування (НЛП) потрібно знайти значення багатовимірної змінної х = ( ), Мінімізує цільову функцію f (x) за умов, коли на змінну х накладені обмеження типу нерівностей
, I = 1,2, ..., m (1)
а змінні , Тобто компоненти вектора х, ненегативні:
(2)
Іноді у формулюванні задачі обмеження (1) мають протилежні знаки нерівностей. Враховуючи, проте, що якщо , То , Завжди можна звести задачу до нерівностей одного знака. Якщо деякі обмеження входять в завдання зі знаком рівності, наприклад , То їх можна представити у вигляді пари нерівностей , , Зберігши тим самим типову формулювання завдання.

2. Критерії оптимальності в задачах з обмеженнями.

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

2.1. Завдання з обмеженнями у вигляді рівностей

Розглянемо загальну задачу оптимізації, яка містить кілька обмежень у вигляді рівностей:
Мінімізувати
при обмеженнях , K = 1, ..., n
Це завдання в принципі може бути вирішена як завдання безумовної оптимізації, отримана шляхом виключення з цільової функції k незалежних змінних за допомогою заданих рівностей. Наявність обмежень у вигляді рівностей фактично дозволяє зменшити розмірність вихідної задачі з n до nk .. В якості ілюстрації розглянемо наступний приклад.
Приклад 1
Мінімізувати
при обмеженні
Виключивши змінну , За допомогою рівняння , Отримаємо
оптимізаційних задач з двома змінними без обмежень
min
Метод виключення змінних можна застосовувати лише в тих випадках, коли рівняння, що представляють обмеження, можна дозволити щодо деякого конкретного набору незалежних змінних. При наявності великої кількості обмежень у вигляді рівностей, процес виключення змінних стає дуже трудомісткою процедурою. Крім того, можливі ситуації, коли рівняння не вдається вирішити щодо змінної. Зокрема, якщо в прикладі 1 обмеження задати у вигляді

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

2.2. Множники Лагранжа

За допомогою методу множників Лагранжа по суті встановлюються необхідні умови, що дозволяють ідентифікувати точки оптимуму в задачах оптимізації з обмеженнями у вигляді рівностей. При цьому завдання з обмеженнями перетворюється на еквівалентну завдання безумовної оптимізації, в якій фігурують деякі невідомі параметри, звані множниками Лагранжа.
Розглянемо задачу мінімізації функції n змінних з урахуванням одного обмеження у вигляді рівності:
Мінімізувати (3)
при обмеженнях (4)
Відповідно до методу множників Лагранжа це завдання перетвориться в таку задачу безумовної оптимізації:
мінімізувати L (x, u) = f (x)-u * h (x) (5)
Функція L (х; u) називається функцією Лагранжа, u - невідома стала, яка носить назву множника Лагранжа. На знак u ніяких вимог не накладається.
Нехай при заданому значенні u = u 0 безумовний мінімум функції L (x, u) по х досягається в точці і задовольняє рівнянню . Тоді, як неважко бачити, x 0 мінімізує (1) з урахуванням (4), оскільки для всіх значень х, що задовольняють (4), і L (x, u) = min f (x).
Зрозуміло, необхідно підібрати значення u = u ° таким чином, щоб координата точки безумовного мінімуму х ° задовольняла рівності (4). Це можна зробити, якщо, розглядаючи u як змінну, знайти безумовний мінімум функції (5) у вигляді функції u, а потім вибрати значення u, при якому виконується рівність (4). Проілюструємо це на конкретному прикладі.
Приклад 2
Мінімізувати
при обмеженні = 0
Відповідна завдання безумовної оптимізації записується в наступному вигляді:
мінімізувати L (x, u) = -U
Рішення. Прирівнявши дві компоненти градієнта L до нуля, одержимо


Для того щоб перевірити, чи відповідає стаціонарна точка х ° мінімуму, обчислимо елементи матриці Гессе функції L (х; u), що розглядається як функція х,
,
яка виявляється позитивно визначеною. Це означає, що L (х,, u) - опукла функція х. Отже, координати , визначають точку глобального мінімуму. Оптимальне значення u знаходиться шляхом підстановки значень і в рівняння = 2, звідки 2u + u / 2 = 2 або . Таким чином, умовний мінімум досягається при і і дорівнює min f (x) = 4 / 5.
При вирішенні завдання з прикладу 2 ми розглядали L (х; u) як функцію двох змінних і і, крім того, припускали, що значення параметра u вибрано так, щоб виконувалося обмеження. Якщо ж рішення системи
, J = 1,2,3, ..., n
у вигляді явних функцій u отримати не можна, то значення х і u знаходяться шляхом рішення наступної системи, що складається з n +1 рівнянь з n +1 невідомими:
, J = 1,2,3, ..., n
Для знаходження всіх можливих рішень даної системи можна використовувати чисельні методи пошуку (наприклад, метод Ньютона). Для кожного з рішень ( ) Слід обчислити елементи матриці Гессе функції L, що розглядається як функція х, і з'ясувати, чи є ця матриця позитивно визначеною (локальний мінімум) або негативно певної (локальний максимум).
Метод множників Лагранжа можна поширити на випадок, коли завдання має кілька обмежень у вигляді рівностей. Розглянемо загальну задачу, в якій потрібно
Мінімізувати f (x)
при обмеженнях = 0, k = 1, 2, ..., К.
Функція Лагранжа приймає наступний вигляд:
L (x, u) = f (x) -
Тут -Множники Лагранжа, тобто невідомі параметри, значення яких необхідно визначити. Прирівнюючи приватні похідні L по х до нуля, отримуємо таку систему n рівнянні з n невідомими:


... ... ... ..

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



Рішення розширеної системи, що складається з n + К рівнянь з n + К невідомими, визначає стаціонарну точку функції L. Потім реалізується процедура перевірки на мінімум чи максимум, яка проводиться на основі обчислення елементів матриці Гессе функції L, що розглядається як функція х, подібно до того, як це було зроблено в разі завдання з одним обмеженням. Для деяких завдань розширена система n + К рівнянь з n + K невідомими може не мати рішень, і метод множників Лагранжа виявляється непридатним. Слід, однак, відзначити, що такі завдання на практиці зустрічаються досить рідко.

3. Умови Куна-Таккера

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

3.1. Умови Куна-Таккера і завдання Куна-Таккера

Знайти вектори , Що задовольняють таким умовам
(3)
(4)
(5)
(6)
(7)
Перш за все проілюструємо умови Куна - Таккера на прикладі.
Приклад 3
Мінімізувати
при обмеженнях
Рішення.
Записавши цю задачу у вигляді задачі нелінійного програмування (0) - (2), отримаємо




Рівняння (3), що входить до складу умов Куна-Таккера, приймає наступний вигляд:

звідки

Нерівності (4) і рівняння (5) завдання Куна - Таккера в даному випадку записуються у вигляді

Рівняння (5.16), відомі як умова доповнює нежорсткої, приймають вигляд

Зауважимо, що на змінні і накладається вимога неотрицательности, тоді як обмеження на знак відсутня.
Таким чином, цього завдання умови Куна-танкера записуються в наступному вигляді:

3.2. Інтерпретація умов Куна - Таккера

Для того щоб інтерпретувати умови Куна - Таккера, розглянемо завдання нелінійного програмування з обмеженнями у вигляді рівностей:
мінімізувати
при обмеженнях
Запишемо умови Куна-Таккера
(8)
(9)
Далі розглянемо функцію Лагранжа для задачі нелінійного програмування з обмеженнями у вигляді рівностей

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

Неважко бачити, що умови Куна-Таккера (8) і (9) збігаються з умовами оптимальності першого порядку для задачі Лагранжа.
Розглянемо завдання нелінійного програмування з обмеженнями у вигляді нерівностей:
мінімізувати
при обмеженнях
Запишемо умови Куна-Таккера

Відповідна функція Лагранжа має вигляд

Умови оптимальності першого порядку записуються як

Зауважимо, що - Множник Лагранжа, відповідний обмеження . Раніше було показано, що представляє неявну ціну, асоційовану з обмеженням ; Іншими словами, величина відображає зміну мінімального значення цільової функції , Що викликається одиничним збільшенням правій частині - Го обмеження.
Якщо припустити, що - Е обмеження є неактивним (тобто З іншого боку, якщо -Е обмеження активне (тобто ), То відповідна неявна ціна не обов'язково дорівнює нулю, однак , Так як . Таким чином, для всіх значень .
Для того щоб визначити знак (Неявній ціни, асоційованої з обмеженням ), Слід збільшити праву частину обмеження від 0 до 1. Ясно, що при цьому область допустимих рішень звужується, оскільки будь-яке рішення, яке задовольняє обмеження , Автоматично задовольняє нерівності . Отже, розміри допустимої області зменшуються, і мінімальне значення поліпшити неможливо (так як взагалі воно може тільки зростати). Іншими словами, неявна ціна , Асоційована з -М обмеженням, повинна бути неотрицательной, що відповідає умовам Куна-Таккера.

3.3. Теореми Куна-Таккера

У попередньому розділі побудовані умови Куна-Таккера для задач умовної оптимізації. За допомогою методу множників Лагранжа отримано інтуїтивне уявлення про те, що умови Куна - танкер тісно пов'язані з необхідними умовами оптимальності. У даному розділі розглядаються строгі формулювання необхідних і достатніх умов оптимальності рішення задачі нелінійного програмування.
Теорема 1. Необхідність умов Куна-Таккера
Розглянемо завдання нелінійного програмування (0) - (2). Нехай - Диференційовні функції, а х * - допустиме рішення даного завдання. Покладемо . Далі нехай лінійно незалежні. Якщо х * - оптимальне рішення задачі нелінійного програмування, то існує така пара векторів , Що є рішенням задачі Куна-Таккера (3) - (7).
Умова, згідно з яким повинні бути лінійно незалежними, відоме як умова лінійної незалежності і по суті являє собою деяке умова регулярності допустимої області, яке майже завжди виконується для зустрічаються на практиці завдань оптимізації. Проте взагалі перевірка виконання умови лінійної незалежності певні складнощі, тому що потрібно, щоб оптимальне рішення задачі було відомо заздалегідь. Разом з тим умова лінійної незалежності завжди виконується для задач нелінійного програмування, що володіють такими властивостями.
1. Всі обмеження у вигляді рівностей та нерівностей містять лінійні функції.
2. Всі обмеження у вигляді нерівностей містять увігнуті функції, всі обмеження-рівності - лінійні функції, а також існує, принаймні, одна допустима точка х, яка розташована у внутрішній частині області, яка визначається обмеженнями-нерівностями. Іншими словами, існує така точка х, що

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


Рис.1 Допустима область в задачі 4
Так як
Легко бачити, що вектори лінійно залежні, тобто умова лінійної незалежності в точці не виконується.
Запишемо умови Куна-Таккера і перевіримо, чи виконуються вони в точці (1, 0). Умови (3), (6) і (7) приймають такий вигляд;
(11)
(12)
(13)
(14)
(15)
(16)
При з рівняння (11) випливає, що , Тоді як рівняння (14) дає , Отже, точка оптимуму не є точкою Куна - Таккера.
Зауважимо, що порушення умови лінійної незалежності не обов'язково означає, що точка Куна-Таккера не існує. Для того щоб підтвердити це, замінимо цільову функцію з цього прикладу функцією . При цьому оптимум, як і раніше досягається в точці (1,0), в якій умова лінійної незалежності не виконується. Умови Куна-Таккера (12) - (16) залишаються незмінними, а рівняння (11) набуває вигляду

Неважко перевірити, що точка є точкою Куна-Таккера, тобто задовольняє умовам Куна-Таккера.
Теорема про необхідність умов Куна-Таккера дозволяє ідентифікувати неоптимальні точки. Іншими словами, теорему 1 можна використовувати для доказу того, що задана допустима точка, яка задовольняє умові лінійної незалежності, не є оптимальною, якщо вона не задовольняє умовам Куна-Таккера. З іншого боку, якщо в цій точці умови Куна-Таккера виконуються, то немає гарантії, що знайдено оптимальне рішення нелінійної задачі. Як приклад розглянемо таку задачу нелінійного програмування.
Наступна теорема встановлює умови, при виконанні яких точка Куна-Таккера автоматично відповідає оптимальному вирішенню задачі нелінійного програмування.
Теорема.2 Достатність умов Куна-Таккера
Розглянемо завдання нелінійного програмування (0) - (2). Нехай цільова функція опукла, всі обмеження у вигляді нерівностей містять увігнуті функції , А обмеження у вигляді рівностей містять лінійні функції . Тоді якщо існує рішення , Що задовольняє умовам Куна-Таккера (3) - (7), то x * - оптимальне рішення задачі нелінійного програмування.
Якщо умови теореми 2 виконуються, то знаходження точки Куна-Таккера забезпечує отримання оптимального розв'язку задачі нелінійного програмування.
Теорему 2 можна також використовувати для доказу оптимальності даного рішення задачі нелінійного програмування. В якості ілюстрації знову розглянемо приклад:
Мінімізувати
при обмеженнях
За допомогою теореми 2 доведемо, що рішення є оптимальним. Маємо

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

Оскільки матриця негативно визначена, функція є увігнутою. Функція входить в лінійне обмеження в вяде рівності. Отже, всі умови теореми 2 виконані; якщо ми покажемо, що - Точка Куна-Таккера, то дійсно встановимо оптимальність рішення . Умови Куна-Таккера для прикладу 2 мають вигляд
(22)
(23)
(24)
(25)
, (26)
, (27)
(28)
(29)
Точка задовольняє обмеженням (24) - (26) і, отже, є допустимими. Рівняння (22) і (23) приймають такий вигляд:

Поклавши , Отримаємо і . Таким чином, рішення x *= (1, 5), задовольняє умовам Куна-Таккера. Оскільки умови теореми 2 виконані, то оптимальне вирішення завдання з прикладу 3. Зауважимо, що існують також і інші значення і , Які задовольняють систему (22) - (29).
Зауваження
1.Для зустрічаються на практиці завдань умова лінійної незалежності, як правило, виконується. Якщо в задачі всі функції диференційовні, то точку Куна-Таккера слід розглядати як можливу точку оптимуму. Таким чином, багато хто з методів нелінійного програмування сходяться до точки Куна-Таккера. (Тут доречно провести аналогію з випадком безумовної оптимізації, коли відповідні алгоритми дозволяють визначити стаціонарну крапку.)
2. Якщо умови теореми 2 виконані, точка Куна-Таккера в той же час виявляється точкою глобального мінімуму. На жаль, перевірка достатніх умов дуже складною, і, крім того, прикладні задачі часто не володіють необхідними властивостями. Слід зазначити, що наявність хоча б одного нелінійного обмеження у вигляді рівності призводить до порушення припущень теореми 2.
3.Достаточние умови, встановлені теоремою 2, можна узагальнити на випадок завдань з неопуклих функціями, що входять в обмеження у вигляді нерівностей, неопуклих цільовими функціями і нелінійними обмеженнями-рівностями. При цьому використовуються такі узагальнення опуклих функцій, як квазівипуклие і псевдовипуклие функції.

4. Функції декількох змінних

Обмежені можливості симплексного методу, укладені в задачах з складними видами обмежень і довільним видом цільової функції, привели до широкого використання ітеративних методів пошуку оптимального рішення.
Спочатку розглянемо питання аналізу «в статиці» з використанням положень лінійної алгебри та диференціального числення, а також умови, які (в досить загальних можливих ситуаціях) дозволяють ідентифікувати точки оптимуму. Такі умови використовуються для перевірки вибраних точок і дають можливість з'ясувати, чи є ці точки точками мінімуму або максимуму. При цьому завдання вибору зазначених точок залишається поза рамками проведеного аналізу; основна увага приділяється вирішенню питання про те, чи відповідають досліджувані точки рішенням багатовимірної задачі безумовної оптимізації, в якій потрібно мінімізувати f (x) x при відсутності обмежень на x, де x - вектор керованих змінних розмірності n, f - скалярна цільова функція. Звичайно передбачається, що x i (для всіх значень i = 1, 2, ..., n) можуть приймати будь-які значення, хоча в ряді практичних додатків область значень x вибирається у вигляді дискретного безлічі. Крім того, часто виявляється зручним припускати, що функція f і її похідні існують і безперервні всюди, хоча відомо, що оптимуми можуть досягатися в точках розриву f або її градієнта

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

4.1. Методи прямого пошуку

Нижче розглядається питання аналізу «в динаміці» для функцій декількох змінних, тобто досліджуються методи і алгоритми, що дозволяють на ітераційної основі отримувати оцінки х *- вектора керованих змінних, якому відповідає мінімальне значення функції f (x). Зазначені методи застосовуються також до завдань максимізації, у яких цільову функцію слід замінити на-f (х). Методи, орієнтовані на вирішення задач безумовної оптимізації, можна розділити на три широких класу відповідно до типу використовуваної при реалізації того чи іншого методу інформації.
1. Методи прямого пошуку, засновані на обчисленні тільки значень цільової функції.
2. Градієнтні методи, в яких використовуються точні значення перших похідних f (x).
3. Методи другого порядку, в яких поряд з першими похідними використовуються також другі похідні функції f (x).
Нижче розглядаються методи, що відносяться до кожного з перерахованих класів, оскільки ні один метод або клас методів не відрізняється високою ефективністю при вирішенні оптимізаційних задач різних типів. Зокрема, можливі випадки, коли відбувається переповнювання пам'яті ЕОМ; в інших ситуаціях обчислення значень цільової функції вимагає надмірних витрат часу; в деяких завданнях потрібно отримати рішення з дуже високим ступенем точності. У ряді програм або неможливо, або дуже важко знайти аналітичні вирази для похідних цільової функції. Тому якщо передбачається використовувати градієнтні методи, слід застосувати процедуру різницевої апроксимації похідних. У свою чергу це призводить до необхідності експериментального визначення довжини кроків, що дозволяє встановити належне відповідність між помилкою округлення і помилкою апроксимації. Таким чином, інженер змушений пристосовувати застосовуваний метод до конкретним характеристикам розв'язуваної задачі.
Методи рішення задач безумовної оптимізації відрізняються відносно високим рівнем розвитку в порівнянні з іншими методами нелінійного програмування. Нижче мова йде про методи прямого пошуку, для реалізації яких потрібні лише значення цільової функції; в наступному розділі розглядаються градієнтні методи і методи другого порядку. Тут передбачається, що f (x) неперервна, а може як існувати, так і не існувати, оскільки відповідні числові значення не використовуються. Однак слід зазначити, що методи прямого пошуку можна застосовувати для вирішення задач, в яких існує, і вони часто використовуються в тих випадках, коли являє собою складну векторну функцію керованих змінних. Нарешті, в цьому і наступних розділах передбачається, що функція f (х) унімодальному в даній області. Якщо ж вивчаються методи застосовуються для аналізу мультимодальних функцій, то доводиться обмежуватися ідентифікацією локальних мінімумів.
Багатовимірні методи, що реалізують процедуру пошуку оптимуму на основі обчислення значень функції, із загальних позицій можна розділити на евристичні та теоретичні. Евристичні методи, як це випливає з назви, реалізують процедури пошуку за допомогою інтуїтивних геометричних уявлень і забезпечують отримання приватних емпіричних результатів. З іншого боку, теоретичні методи засновані на фундаментальних математичних теоремах і володіють такими операційними властивостями, як збіжність (принаймні при виконанні деяких певних умов). Нижче детально розглядаються три методи прямого пошуку:
1) пошук по симплекс, або S 2-метод;
2) метод пошуку Хука-Дживса;
3) метод пов'язаних напрямків Пауелла.
Перші два з перерахованих методів відносяться до категорії евристичних і реалізують принципово різняться стратегії пошуку. У процесі пошуку по S 2-методом послідовно оперують регулярними симплексом в просторі керованих змінних, тоді як при реалізації методу Хука-Дживса використовується фіксоване безліч (координатних) напрямків, обираних рекурсивним способом. Метод Пауелла заснований на теоретичних результатах і орієнтований на вирішення завдань з квадратичними цільовими функціями; для таких завдань метод сходиться за кінцеве число ітерацій. До числа загальних особливостей всіх трьох методів слід віднести відносну простоту відповідних обчислювальних процедур, які легко реалізуються і швидко коригуються. З іншого боку, реалізація зазначених методів може вимагати (і часто вимагає) більш значних витрат часу в порівнянні з методами з використанням похідних.

4.1.1. Метод пошуку по симплекс (S 2-метод)

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


Рис 2. Квадратний зразок (приватний випадок кубічного зразка)
Потім «найкраща» з п'яти досліджуваних точок вибирається в якості наступної базової точки, навколо якої будується аналогічний зразок. Якщо жодна з кутових точок не має переваги перед базової, розміри зразка слід зменшити, після чого продовжити пошук.
Цей тип еволюційної оптимізації був використаний Боксом і іншими дослідниками для аналізу функціонування промислових підприємств, коли ефект варіювання значень змінних, що описують виробничі процеси, вимірюється з помилкою. У задачах великої розмірності обчислення значень цільової функції проводиться у всіх вершинах, а також у центрі ваги гіперкуба (гіперкуб - куб в n-мірному евклідовому просторі, тобто множина S = {x = ( ) | }, Де а і b - задані числа), тобто в точках так званого кубічного зразка. Якщо кількість змінних (розмірність простору, в якому ведеться пошук) дорівнює n, то пошук по кубічному зразком вимагає +1 Обчислень значення функцій для одного зразка. При збільшенні розмірності задачі необхідну кількість обчислень значення цільової функції зростає надзвичайно швидко. Таким чином, незважаючи на логічну простоту пошуку по кубічному зразком, виникає необхідність використання більш ефективних методів прямого пошуку для вирішення виникаючих на практиці завдань оптимізації.
Одна з викликають особливий інтерес стратегій пошуку покладена в основу методу пошуку по симплекс, запропонованого Спендлі, Хекста і Хімсвортом. Слід зазначити, що вказаний метод і інші подібні методи не мають відношення до симплекс-методу лінійного програмування, а схожість назв носить випадковий характер. Процедура симплексного пошуку Спендлі, Хекста і Хімсворта базується на тому, що експериментальним зразком, що містить найменшу кількість точок, є регулярний симплекс. Регулярний симплекс в n-мірному просторі представляє собою багатогранник, утворений n +1 равностоящими один від одного крапками-вершинами. Наприклад, у випадку двох змінних симплексом є рівносторонній трикутник; в тривимірному просторі симплекс є тетраедр. В алгоритмі симплексного пошуку використовується важлива властивість симплексу, згідно з яким новий симплекс можна побудувати на будь-якої грані початкового симплекса шляхом переносу обраної вершини на належне відстань уздовж прямої, проведеної через центр тяжіння інших вершин початкового симплекса. Отримана таким чином точка є вершиною нового симплекса, а обрана при побудові вершина початкового симплекса виключається. Неважко бачити, що при переході до нового симплекс потрібно одне обчислення значення цільової функції. Рис 3 ілюструє процес побудови нового симплекса на площині.



Ріс.3.Построеніе нового симплекса.
а - початковий симплекс
б - новий симплекс

Робота алгоритму симплексного пошуку починається з побудови регулярного симплекса у просторі незалежних змінних і оцінювання значень цільової функції в кожній з вершин симплекса. При цьому визначається вершина, якої відповідає найбільше значення цільової функції. Потім знайдена вершина проектується через центр ваги інших вершин симплекса в нову точку, яка використовується як вершини нового симплекса. Якщо функція спадає досить плавно, ітерації тривають до тих пір, поки або не буде накрита точка мінімуму, або не почнеться циклічний рух по двох або більше симплексом. У таких ситуаціях можна скористатися наступними трьома правилами.
Правило 1. «Накриття» точки мінімуму
Якщо вершина, якої відповідає найбільше значення цільової функції, побудована на попередній ітерації, то замість неї береться вершина, якої відповідає наступне за величиною значення цільової функції.
Правило 2. Циклічний рух
Якщо деяка вершина симплекса не виключається протягом більш ніж М ітерацій, то необхідно зменшити розміри симплекса за допомогою коефіцієнта редукції і побудувати новий симплекс, вибравши в якості базової точку, якій відповідає мінімальне значення цільової функції. Спендлі, Хекста і Хімс-Ворт запропонували обчислювати М за формулою
M = 1,65 n +0,05
де n - розмірність задачі, а М округляється до найближчого цілого числа. Для застосування цього правила потрібно встановити величину коефіцієнта редукції.
Правило 3. Критерій закінчення пошуку
Пошук завершується, коли або розміри симплекса, або різниці між значеннями функції в вершинах стають досить малими. Щоб можна було застосовувати ці правила, необхідно задати величину параметра закінчення пошуку.
Реалізація досліджуваного алгоритму заснована на обчисленнях двох типів: (1) побудові регулярного симплекса при заданих базовій точці і масштабному множник і (2) розрахунку координат відбитої точки. Побудова симплекса є досить простою процедурою, так як з елементарної геометрії відомо, що при заданих початкової (базової) точці і масштабному множник координати інших n вершин симплекса в n-мірному просторі обчислюються за формулою
(7)
для i та j = 1,2,3, ..., n
Прирости і , Що залежать тільки від n і вибраного масштабного множника , Визначаються за формулами
(8)
(9)
Зауважимо, що величина масштабного множника вибирається дослідником, виходячи з характеристик розв'язуваної задачі. При = 1 ребра регулярного симплекса мають одиничну довжину. Обчислення другого типу, пов'язані з відображенням відносно центра ваги, також представляють нескладну процедуру. Нехай - Точка, що підлягає відображенню. Центр ваги інших n точок розташований в точці
(10)
Всі точки прямої, що проходить через і х с, задаються формулою
(11)
При = 0 одержуємо вихідну точку , Тоді як значення = 1 відповідає центру ваги x с. Для того щоб побудований симплекс володів властивістю регулярності, відображення має бути симетричним. Отже, нова вершина виходить при = 2. Таким чином,
(12)
Проілюструємо обчислювальну схему методу таким прикладом.
Приклад 5. Обчислення у відповідності з методом пошуку по симплекс
Мінімізувати f (x) =
Рішення.
Для побудови вихідного симплекса потрібно задати початкову точку і масштабний множник. Нехай x = і = 2. Тоді


Використовуючи ці два параметри, обчислимо координати двох інших вершин симплекса:


яким відповідають значення цільової функції, рівні = 0,2374 і 3,0658. Так як 5, необхідно відобразити точку відносно центра ваги двох інших вершин симплекса

Використовуючи формулу (12), отримуємо


В отриманій точці 2,3027, тобто спостерігається зменшення цільової функції. Новий симплекс утворений точками і . Відповідно до алгоритму слід відобразити точку г (2), якій відповідає найбільше значення цільової функції, щодо центра ваги точок і х (3). Ітерації тривають до тих пір, поки не буде потрібно застосування правил 1, 2 і 3, які були сформульовані вище.
Викладений вище алгоритм - Методу має кілька очевидних переваг.
1. Розрахунки та логічна структура методу відрізняються порівняльної простотою, і, отже, відповідна програма для ЕОМ виявляється відносно короткою.
2. Рівень вимог до обсягу пам'яті ЕОМ невисокий, масив має розмірність (n +1, n +2).
3. Використовується порівняно невелике число заздалегідь встановлених параметрів: масштабний множник , Коефіцієнт зменшення множника (Якщо застосовується правило 2) і параметри закінчення пошуку.
4. Алгоритм виявляється ефективним навіть у тих випадках, коли помилка обчислення значень цільової функції велика, оскільки при його реалізації оперують найбільшими значеннями функції в вершинах, а не найменшими.
Перераховані фактори характеризують метод пошуку по симплекс як дуже корисний при проведенні обчислень в реальному часі.
Алгоритм має також низкою істотних недоліків.
1. Не виключено виникнення труднощів, пов'язаних з масштабуванням, оскільки всі координати вершин симплекса залежать від одного і того ж масштабного множника . Щоб обійти труднощі такого роду, в практичних завданнях слід промасштабіровать всі змінні з тим, щоб їх значення були порівнянними за величиною.
2. Алгоритм працює надто повільно, так як отримана на попередніх ітераціях інформація не використовується для прискорення пошуку.
3. Не існує простого способу розширення симплекса, що не вимагає перерахунку значень цільової функції у всіх точках зразка. Таким чином, якщо з якої-небудь причини зменшується (наприклад, якщо зустрічається область з вузьким «яром» або «хребтом»), то пошук має продовжуватися зі зменшеною величиною кроку.

4.1.2. Метод пошуку Хука-Дживса.

Метод, розроблений Хуком і Дживс, є одним з перших алгоритмів, в яких при визначенні нового напряму пошуку враховується інформація, отримана на попередніх ітераціях. По суті процедура Хука-Дживса представляє собою комбінацію «досліджує» пошуку з циклічним зміною змінних і прискореного пошуку за зразком з використанням певних евристичних правил. Досліджує пошук орієнтований на виявлення характеру локального поведінки цільової функції і визначення напрямків уздовж «ярів». Отримана в результаті досліджує пошуку інформація потім використовується в процесі пошуку за зразком при русі по «ярах».
Досліджує пошук.
Для проведення досліджує пошуку необхідно задати величину кроку, яка може бути різною для різних координатних напрямків і змінюватися в процесі пошуку. Досліджує пошук починається в деякій вихідної точки. Якщо значення цільової функції у пробній точці не перевищує значення функції у вихідній точці, то крок пошуку розглядається як успішний. В іншому випадку необхідно повернутися в попередню точку і зробити крок у протилежному напрямку з подальшою перевіркою значення цільової функції. Після перебору всіх N координат досліджує пошук завершується. Отриману в результаті точку називають базовою точкою.
Пошук за зразком.
Пошук за зразком полягає в реалізації єдиного кроку з отриманої базової точки вздовж-прямій, що сполучає цю точку з попередньою базовою точкою. Новий пункт зразка визначається відповідно до формули

Як тільки рух за зразком не призводить до зменшення цільової функція, точка фіксується в якості тимчасової базової точки і знову проводиться досліджує пошук. Якщо в результаті виходить крапка з меншим значенням цільової функції, ніж у точці , То вона розглядається як нова базова точка . З іншого боку, якщо досліджує пошук невдалий, необхідно повернутися в точку і провести досліджує пошук з метою виявлення нового напрямку мінімізації. У кінцевому рахунку, виникає ситуація, коли такий пошук не приводить до успіху. У цьому випадку потрібно зменшити величину кроку шляхом введення деякого множника і відновити досліджує пошук. Пошук завершується, коли величина кроку стає досить малою. Послідовність точок, що отримується в процесі реалізації методу, можна записати в наступному вигляді:
- Поточна базова точка,
- Попередня базова точка,
- Точка, побудована при русі за зразком,
- Наступна (нова) базова точка.
Наведена послідовність характеризує логічну структуру пошуку за методом Хука - Дживса.
Структура методу пошуку Хука - Дживса
Крок 1. Визначити:
початкову точку ,
збільшення
коефіцієнт зменшення кроку ,
параметр закінчення пошуку .
Ш а г 2. ровесті досліджує пошук.
Ш а р 3. Чи був досліджує пошук вдалим (знайдена точка з меншим значенням
цільової функції)?
Так: перейти до кроку 5.
Ні: продовжувати.
Ш а р 4. Перевірка на закінчення пошуку.
Чи виконується нерівність ?
Так: припинити пошук; поточна точка апроксимує точку оптимуму .
Ні: зменшити збільшення по формулі

Перейти до кроку 2.
Ш а р 5. Провести пошук за зразком:

Крок 6. Провести досліджує пошук, використовуючи в якості базової точки;
нехай отримана в результаті точка.
Ш а р 7. Чи виконується нерівність ?
Так: покласти Перейти до кроку 5.
Ні: перейти до кроку 4.
Приклад 6 Пошук за методом Хука - Дживса
Знайти точку мінімуму функції використовуючи початкову точку .
Рішення.
Для того щоб застосувати метод прямого пошуку. Хука - Дживса, необхідно поставити такі величини:
векторна величина збільшення = ,
коефіцієнт зменшення кроку = 2,
параметр закінчення пошуку = 10 -4.
Ітерації починаються з досліджує пошуку навколо точки , Якій відповідає значення функції Фіксуючи , Дамо прирощення перемінної :

Успіх.
Отже, необхідно зафіксувати і дати приріст змінної :

Успіх.
Таким чином, в результаті досліджує пошуку знайдена точка

Оскільки досліджує пошук був вдалим, переходимо до пошуку за зразком:


Далі проводиться досліджує пошук навколо точки , Який виявляється вдалим при використанні позитивних збільшень змінних х 1 і х 2. У результаті отримуємо точку

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


Ітерації пошуку за методом Хука-Дживса на прикладі
Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Реферат
131.9кб. | скачати


Схожі роботи:
Лінійне та нелінійне програмування
Нелінійне рівняння і інтервал ізоляції кореня
Нелінійне подання інформації гіпертекст і його використання в комунікації
Основні поняття математичного програмування Побудова моделі задачі лінійного програмування
Програмування мовою С з використанням об єктно орієнтованого програмування
Програмування мовою С з використанням обєктно-орієнтованого програмування
Програмування
Програмування в СІ
Програмування
© Усі права захищені
написати до нас
Рейтинг@Mail.ru