Задача Знайти для заданої опуклої вниз функції. Припущення Множина розв’язків непорожня


Методи послідовних наближень для розв’язування дискретних мінімаксних задач



Скачати 325,12 Kb.
Сторінка13/24
Дата конвертації27.01.2020
Розмір325,12 Kb.
ТипЗадача
1   ...   9   10   11   12   13   14   15   16   ...   24
4.6. Методи послідовних наближень для розв’язування дискретних мінімаксних задач

Задача 0. Знайти для заданих функцій та заданої множини .

Припущення 0. функції – неперервно диференційовані в .

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



де

.

Вектор при називають напрямком - найшвидшого спуску.

1. Перший метод послідовних наближень

Алгоритм 1

Початок. І. Вибрати довільне початкове наближення .

II. Вибрати константи і .

III. Покласти .

Основний цикл. IV. Покласти і перейти на крок VII.

V. Покласти .

VI. Покласти .

VII. Знайти множину індексів



(4.3)

VIII. Знайти багатогранник ( ), який є опуклою оболонкою, натягнутою на множину точок



IX. Якщо , то перейти на крок X; інакше перейти на крок XI.

X. Використовуючи алгоритм 1', визначити, чи належить початок координат багатограннику Якщо початок координат належить то покласти і зупинити обчислення; інакше перейти на крок XI.

ХІ. Використовуючи алгоритм 1", знайти точку що є найближчою до початку координат точкою багатогранника



  1. Обчислити за формулою

  2. Якщо виконується нерівність то перейти на крок XIV; інакше покласти і перейти на крок VI.

XIV. Обчислити вектор – напрямок -найшвидшого спуску функції у точці за формулою .

XV. Обчислити кроковий множник з умови



= .

  1. Обчислити наступне наближення



  1. Покласти і перейти на крок IV.

Теорема 1. Якщо виконане припущення 0 і початкове наближення в алгоритмі 1 таке, що множина



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

(Точка , для якої виконується нерівність



називається стаціонарною точкою функції на . Якщо функція опукла вниз, тo стаціонарна точка є точкою мінімуму).



Зауваження 1. Щоб на k-й ітерації зменшити кількість порівнянь у [17], рекомендується починати порівняння не з , а зі значення , отриманого на попередній -й ітерації, тобто при такому , яке отримується при виході з циклу, утвореного кроками VI—XIII на -й ітерації.


Каталог: MatMet


Поділіться з Вашими друзьями:
1   ...   9   10   11   12   13   14   15   16   ...   24


База даних захищена авторським правом ©pedagogi.org 2019
звернутися до адміністрації

    Головна сторінка