XIV Міжнародна наукова інтернет-конференція ADVANCED TECHNOLOGIES OF SCIENCE AND EDUCATION (19-21.04.2018)

Русский English




Научные конференции Наукові конференції

Чупиря О.В. ОГЛЯД МЕТОДІВ РОЗВ’ЯЗКУ ЗАДАЧ КВАДРАТИЧНОЇ ОПТИМІЗАЦІЇ

Магістрант Чупиря Ольга Володимирівна

Дніпропетровський національний університет ім. О. Гончара

ОГЛЯД МЕТОДІВ РОЗВ'ЯЗКУ ЗАДАЧ КВАДРАТИЧНОЇ ОПТИМІЗАЦІЇ

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

У даній статті ми розглянемо методи розв'язку задач квадратичної оптимізації.

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

image002180.gif , (1)

де як цільова функція, так і обмеження можуть бути опуклими або ввігнутими.

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

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

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

Спочатку розглянемо алгоритми розв'язку одноекстремальних квадратичних задач.

З великої кількості методів одноекстремальної оптимізації [1,2] можна виділити 3 основні групи:

1. Методи можливих напрямків: метод проектування градієнта, методи Зойтендейка, Вулфа й ін.;

2. Методи штрафних і бар'єрних функцій;

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

У методі проектування градієнта (image002181.gif ) використовується ітераційна формула:

image002182.gif,

виміром точності є:

image002183.gif,

а параметри знаходяться із системи лінійних рівнянь:

image002184.gif.

У методі штрафних функцій (image002185.gif  ) задача перетворюється до задачі безумовної оптимізації image002186.gif, де image002187.gif, image002188.gif, image002189.gif.

У методі бар'єрних функцій ( image002190.gif ) задача також перетворюється до задачі безумовної оптимізації image002191.gif, де image002192.gif.

Тепер перейдемо до методів розв'язку багатоекстремальних задач.

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

Також можна виділити три методи розв'язку багатоекстремальних квадратичних задач:

1. Метод квадратичної релаксації. [3]

2. Індексний метод. [4,5]

3. Метод напіввизначеної релаксації. [3]

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

image002193.gif.

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

У методі напіввизначеної релаксації задача зводиться до задачі напіввизначеної оптимізації:

image002194.gif,

де:

image002195.gif - означає що Y є позитивно напіввизначеною матрицею,

image002196.gif - однозначне перетворення для перетворення розв'язку напіввизначеної задачі до розв"язку вихідної квадратичної задачі.

Література:

1. Таха Х. Введение в исследование операций. В 2-х книгах. Кн. 1. Пер. с англ. - М.: Мир, 1985.

2. Исследование операций / Под ред. Дж.Моудера, С.Элмаграби. - Т. 1,2. - М.: Мир, 1981.-712 с.

3. Косолап А.И.   Выпуклый анализ и многоэкстремальные задачи.: Моногр. Днепропетровск, Изд-во ДНУ, 2007. 280 с.

4. Strongin R.G. (1992) Algorithms for multi-extremal mathematical programming problems employing the set of joint space-filling curves. Journal of Global Optimization, №2. P. 357-378.

5. Strongin R.G., Sergeyev Ya.D. (2000). Global optimization with non-convex constraints. Sequential and parallel algorithms. - Dordrecht: Kluwer Academic Publishers.

 

olya-ua@yandex.ru

 


Залиште коментар!

Дозволено використання тегів:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <code> <em> <i> <strike> <strong>