17. Метод золотого сечения
это численный метод нахождения решения x (с заданной точностью ε), минимизирующего функцию f(x) на отрезке.
Суть метода золотого сечения состоит в разбиении отрезка [a,b] на три отрезка в пропорции золотого сечения, определении минимального значения функции f(x)из значений на границах этих отрезков и выборе нового отрезка, на котором функция содержит минимизирующее решение.
Деление отрезка продолжается до достижения необходимой точности решения ε.
Сначала находим отрезок [a,b] такой, что функция f(x) непрерывна и вогнута на отрезке, то есть f"(x)>0.
Далее применяем алгоритм.
Выходные данные: x.
Значение x является минимизирующим решением для функции f(x) с заданной точностью ε.
Заметим, что для нахождения решения x, максимизирующего выпуклую функцию f(x) на отрезке, алгоритм решения модифицируется в части строки 2, она меняется на строку вида:
18. Метод чисел Фибоначчи
лучший метод среди методов дихотомии, деления отрезка пополам, поразрядного поиска.
19. Метод касательных
20. Метод средней точки
21. Метод хорд
22. Метод Ньютона
23 Многомерная безусловная оптимизация. Методы спуска.
Большинство задач являются многомерными, причем число аргументов целевой функции иногда может быть весьма большим. Характер задач и возможные методы решения существенно зависят от информации целевой функции. В одном случае, в градиентных методах, функция задается аналитически, являясь при этом дифференцируемой функцией. Тогда можно вычислить ее частные производные, получить явное выражение для градиента, определяющего в каждой точке направление возрастания и убывания ф-и, и использовать эту информацию для решения задач. В других случаях, никакого аналитического выражения для целевой функции нет, а имеется лишь возможность определить значение в любой точке рассматриваемой области(с помощью расчетов, в результате экспериментов и т. д.) В таких задачах в процессе решения можно найти значение целевой функции лишь в конечном числе точек, и по этой информации необходимо приближенно установить ее наименьшее значение для всей области. Это можно выполнить с помощью методов: Поиск по образцу. М конфигураций. М симплекса. М циклического покоординатного спуска.
24 Поиск по образцу.
Берем базовую точку x0( нач. приближение). Вычислим в ней значение f(x0), а затем построим n-мерный куб с центром в этой точке и ребрами длиной 2h. Вычислить значения функции в вершинах куба, берем в качестве новой базовой точки ту из вершин, в которой значение ф-и меньше f(x0) и повторим процедуру для выбора следующей базовой точки и построения образца .Если такой вершины не оказалось, то оставим прежнюю базовую точку x0 и построим куб с уменьшенной длиной ребер, например h. Поиск заканчивается, когда длинна ребра станет меньше заданного числа E>0
.
25 Метод конфигурации.
Алгоритм включает в себя два основных этапа поиска.
а) В начале обследуется окрестность выбранной точки (базисной точки), в результате находится приемлемое направление спуска; Если значение ф-и в пробной точке меньше чем в исходной, шаг считается удачным. В противном случае возвращаемся назад и делаем шаг в противоположном направлении. После перебора всех координатных исследования окрестности базовой точки – конец. В результате поиска получена точка x(l+1), если исследование оказалось неудачным x(l+1)=x(l), уменьшаем шаг в 2 раза и продолжаем процедуру.
б) Затем в этом направлении находится точка с наименьшим значением целевой функции. Таким образом находится новая базисная точка. Если же пробное перемещение оказалось неудачным, то уменьшаем ускоряющий множитель, то уменьшаем ускоряющий коэффициент в 2 раза и осуществляем пробное перемещение в точку x(l+2) с этим множителем. Процесс продолжается пока не найдется подходящий множитель.