1.2& Метод покоординатного спуска.

Основан на поочередной оптимизации вдоль каждой из координатных осей.

АЛГОРИТМ ПОКООРДИНАТНОГО СПУСКА.

1. Выбор x0 (начального приближения), eps_g и eps_x (точности решения по градиенту и аргументу).

2. iter:= 0; h= 0,1*eps_x. (инициализация счетчика итераций и пробного шага)

3. j=1.

4. x=x0, f0=f(x0)

5. x_j= x0_j+h; x=x-x0

6. Расчет значения функции f(x).

7. Если f(x_j)< f0, то p=+x, иначе p=-x. (направление поиска)

8. Выбор длины шага s=a*p (a>0) вдоль выбранного направления p.

9. x0:= x0 + s; j=j+1;

10. Если j<n, то идти к п.4.

11. iter:=iter+1.

12. Если |s|> eps_x (точность по аргументу), то идти к п.3.

13. Печать вектора x0, значения оптимизируемой функции f(x0) и количества итераций iter.

10. Постановка задачи безусловной оптимизации фнп. Метод многогранника. Алгоритм метода.

Оптимизируемую функцию f(x) называют целевой функцией или критерием оптимальности. ПЗ: àmin. Найти хотя бы один локальный мин.функции , (существует или удовлетворяет определенному условию) с заданной точностью:

1. по решению , где -приблизиженное значение, -лок. Мин.

2. по градиенту ,

М етод многогранника (Нелдера и Мида).

Основан на построении симплекса. Суть: строится простейший многогранник (треугольник) в центре х0, Дальше вершины нумеруются По принципу худшая- лучшая вершина.В данном случае худшая -3, лучшая -1.

И так далее на каждую лучшую точу строится треугольник

Алгоритм:

1. Вводим начальную точку х0, размер R, точность по х , точность по значению функции , точность по производной . Дана функция àmin, коэффициент шагов х.

2. Строим многогранник (симплекс) с центром в точке х0 и размером R.

, где <i>-i-я вершина i=1...n

3. Расчет значений функций

В точке симплекса i=0..n

4. Переупорядочиваем вершины симплекса

Редукция симплекса – стягивание всех вершин

4а. Самая лучшая точка симплекса .

Оценки значения критерия останова:

1)Размер симплекса меньше по значению точности

,

2)Отключение от хорошей точки до плохой точки

3)Оценка производной

5. коэффициенты . Делаем пробный шаг , где xc – центр отображения. ,

6. Принимаем решение: делаем растягивающий шаг или сжимающий шаг, если ,то делаем шаг , , if , then h=p, else h=f

7. Иначе если шаг хуже, то в этом случае сравниваем значение функции с самой худшей точкой , то h=α, а если он еще хуже, то , if , then h=γ, else редукция симплекса в самой лучшей точке х0

, и переупорядочиваем вершины (п.4а), а потом возвращаемся к п.5

8. Делаем шаг (нормированный шаг) h , , , мы получаем новую точку.

9. Теперь переупорядочиваем точки с учетом новой точки х^<n>

1. идем к п.4а

2. Постановка задачи безусловной оптимизации фнп. Метод Монтер-Карло. Алгоритм метода. Основные параметры метода.

ПЗ: àmin. Найти хотя бы один локальный мин.функции , (существует или удовлетворяет определенному условию) с заданной точностью:

1.по решению , где -приблизиженное значение, -лок. Мин.

2 .по градиенту ,

Метод Монтер-Карло

Суть: задаем начальную точку и куб с n количеством разбросанных точек, если х1 лучше х0, то рис следующий квадрат и разбрасываем снова точки и ищем наилучшую,если ее нет то уменьшаем область R(квадрата) и т д

Алгоритм:

1. Ввод начальной точки х0, размера R, количество точек N, которые бросаем, точность Ех, Еf

2. Вокруг начальной точки разбрасываем N точек в куб размером R.

For i=1,N, теперь для каждой точки, рассчитываем случайное отклонение от х0

For j=1,n, где n- размерность задачи.

Δj= - R/2+rnd R, где rnd – число в интервале [0,1]

x ^<i> =x0+Δ сгенерировали точки

3.Расчитываем , при i=1,N

4. Ищем х-мин. fmin=f(xmin), xmin= ?

5. Локализуем удачность шага, если fmin<f(x0), то шаг удачен x0=xmin, иначе шаг не удачен, то уменьшаем R=R/2

6. если не удовлетворяется условие Ех, то идем к п.2

7.выводим х0, f(x0), R, Δf

Критерии останова сходимости метода:

1)R<Ex

2) Δf<Ef, где Δf-значение получившейся функции f ^n-1 – f ⁿ

Δf=f ^n-1 – f ⁿ >0

3) Δf/ Δr <Eg