Постановка задачі. Позначення. Допоміжні відомості.

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

1. знайти ;

2. якщо на нижня грань досягається, то знайти точку , у якій

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

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

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

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

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

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

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

Як відомо, для будь-яких вірна нерівність Коші – Буняковського: , причому знак рівності при можливий тоді і тільки тоді, коли .