Контрольна робота
Чисельні методи пошуку стаціонарних точок у оптимізаційних задачах: метод Ньютона
1. Чисельні методи пошуку стаціонарних точок у оптимізаційних задачах: метод Ньютона
Як науковий напрям, теорія оптимізації виникла лише в епоху ЕОМ, оскільки реалізація алгоритмів відшукання екстремумів надзвичайно трудомістка, але основні методи і підходи, що використовуються в теорії оптимізації, були розроблені найбільшими математиками минулого - Ньютоном, Ейлером, Лагранжем.
Звичайна постановка задачі оптимізації (яку ми будемо називати класичною) полягає в наступному. У певному -мірному просторі тим чи іншим способом виділяється деяка непорожнє безліч точок цього простору, зване допустимим безліччю. Далі фіксується деяка речова функція, задана у всіх точках допустимого безлічі. Завдання оптимізації полягає в тому, щоб знайти точку в безлічі, для якої функція (цільова функція) приймає екстремальне - мінімальне або максимальне значення.
Під точкою простору розуміється -мірний вектор і, відповідно, є функцією -мірного векторного аргументу.
Особливо слід зазначити, що при поданні про систему у формі поняття допустимої безлічі збігається з поняттям області допустимих траєкторій або області існування системи.
Завдання оптимізації ми будемо записувати в такий спосіб:
або (1)
При зміні знака цільової функції всі крапки її максимуму перетворюються, очевидно, в точки мінімуму і навпаки. Тому в теорії досить розглядати лише який-небудь один з видів оптимуму (максимум або мінімум).
У сучасній теорії оптимізації найчастіше зупиняються на знаходженні мінімуму. Всі результати цієї задачі очевидним чином переходять на задачу максимізації.
Зауважимо, що термін «оптимізація функції» не цілком точно відображає істота процесу оптимізації у формі (1). У такому процесі сама функція залишається незмінною.
Мова йде про оптимізацію її значення (шляхом вибору відповідної точки в допустимому -мірному допустимому безлічі значень її аргументу). Крім такої задачі (задачі оптимізації функцій) можлива постановка оптимізаційної задачі, при якій в якості допустимого безлічі виступає деяка безліч дійсних функцій, а цільова функція є деякий функціонал, сопоставляющей кожної функції деякий дійсне число. Таке завдання ми називатимемо задачею оптимізації функціоналів або варіаційної завданням.
У стандартних формах завдань об'єктом оптимізації є безперервна функція речових змінних, допустима область задається кінцевої системою рівностей і нерівностей з безперервними лівими частинами та. Якщо при цьому область обмежена, то в ній обов'язково існує принаймні одна точка абсолютного максимуму і одна точка абсолютного мінімуму функції. Оскільки зміна знака у лівих частин нерівностей і змінює знаки цих нерівностей на протилежні, можна обмежитися одним з двох типів нерівностей.
Зазвичай при максимізації використовуються нерівності виду, а при мінімізації - нерівності виду.
Таким чином, виникають дві стандартні форми постановки задач оптимізації:
(2)
Обмеження типу нерівностей легко замінити обмеженнями типу рівностей і простими координатними нерівностями, вводячи додаткові (речові) змінні. При цьому обмеження виду заміняться парою обмежень,, а обмеження - парою обмежень,.
Цей прийом буде надалі іменуватися прийомом елімінації нетривіальних нерівностей. Його особливо зручно застосовувати в тих випадках, коли за змістом задачі всі крапки допустимої області мають невід'ємні координати.
У результаті його застосування в таких умовах виникає третя стандартна форма постановки задачі оптимізації:
(3)
У всіх перерахованих постановках може бути присутнім додаткова вимога про те, щоб всі координати точки оптимуму були цілими числами (або числами деякого заданого ряду). Ця вимога перетворює задачу безперервної оптимізації в завдання целочисленной оптимізації. У випадку, коли допустима область обмежена, в ній може знаходитися лише кінцеве безліч точок з цілочисельними координатами.
Тому завдання целочисленной оптимізації в обмеженій області в принципі може бути вирішена методом перебору, тобто шляхом обчислення значення цільової функції у всіх допустимих точках і вибору з них точки (або точок) з оптимальними значеннями критерію.
Розглянемо метод Ньютона.
Припустимо, що у нас визначено початкове наближення х0 до одного з коренів рівняння (4).
(4)
Тоді в точці х 0 можна обчислити ліву частину решаемого рівняння f (x 0).
