Сходимость метода и оценка погрешности
Теорема 1. Пусть
функция
выпукла на
и принадлежит классу
,
а начальное приближение
таково, что множество
- ограничено. Тогда последовательность
,
получаемая описанным методом, минимизирует
на
и сходится к множеству
,
причем справедлива следующая оценка
погрешности:
(8)
Задание к лабораторной работе
Разработать
программу, реализующую метод покоординатного
спуска для функции
(значения
,
,
c, d определяются
вариантами заданий) и
, 
,
.
Программа должна выводить: координаты
точки минимума
;
значение функции в данной точке
;
количество итераций, после которых
достигается точность
.
Варианты заданий
№ вар. |
|
|
|
|
№ вар. |
|
|
|
|
1 |
1 |
-1.4 |
0.01 |
0.11 |
16 |
16 |
0.0 |
1.99 |
0.26 |
2 |
2 |
-1.3 |
0.04 |
0.12 |
17 |
17 |
0.1 |
2.56 |
0.27 |
3 |
3 |
-1.2 |
0.02 |
0.13 |
18 |
18 |
0.2 |
2.89 |
0.28 |
4 |
4 |
-1.1 |
0.16 |
0.14 |
19 |
19 |
0.3 |
3.24 |
0.29 |
5 |
5 |
-1.0 |
0.25 |
0.15 |
20 |
20 |
0.4 |
3.81 |
0.30 |
6 |
6 |
-0.9 |
0.36 |
0.16 |
21 |
21 |
0.5 |
4.00 |
0.31 |
7 |
7 |
-0.8 |
0.49 |
0.17 |
22 |
22 |
0.6 |
5.02 |
0.32 |
8 |
8 |
-0.7 |
0.64 |
0.18 |
23 |
23 |
0.7 |
4.84 |
0.33 |
9 |
9 |
-0.6 |
0.81 |
0.19 |
24 |
24 |
0.8 |
5.29 |
0.34 |
10 |
10 |
-0.5 |
0.94 |
0.20 |
25 |
25 |
0.9 |
5.76 |
0.35 |
11 |
11 |
-0.4 |
1.00 |
0.21 |
26 |
26 |
1.0 |
6.25 |
0.36 |
12 |
12 |
-0.3 |
1.21 |
0.22 |
27 |
27 |
1.1 |
6.76 |
0.37 |
13 |
13 |
-0.2 |
1.44 |
0.23 |
28 |
28 |
1.2 |
6.98 |
0.38 |
14 |
14 |
-0.1 |
1.69 |
0.24 |
29 |
29 |
1.3 |
7.29 |
0.39 |
15 |
15 |
0.0 |
1.96 |
0.25 |
30 |
30 |
1.4 |
8.41 |
0.40 |
Лабораторная работа №6. Метод штрафных функций
Постановка задачи
Требуется решить задачу оптимизации:
,
(1)
Теоретическая часть
Алгоритм
В методе штрафных функций задача (1) сводится к последовательности задач минимизации:
(2)
где
,
- некоторая вспомогательная функция,
причем,
должна быть такой, что с ростом
она мало отличается от
на
и быстро возрастает на
.
В качестве множества
обычно выбирается множество простой
структуры типа параллелепипеда или
шара.
Опр. 1.
Последовательность функций
,
определенных и неотрицательных на
множестве
,
содержащем
,
называют штрафами или штрафными функциями
множества
на множестве
,
если
(3)
Так, если множество имеет вид
, (4)
то в качестве штрафных могут выбираться следующие функции:
(5)
или
,
где (6)
;
.
Пусть
,
уже выбраны,
определена на
.
В качестве функции
будем брать:
.
(7)
Будем считать, что
(8).
Если при каждом
нижняя граница достигается, то условия
(9)
определяют последовательность . Если же нижняя грань не достигается, то в качестве элементов последовательности будем брать точки , удовлетворяющие условиям:
, (10)
где
для всех к и
при
.