26 Метод симплекса.

Основной недостаток – регулярный рост количества вычисленной значений целевой ф-и при увеличении размерности пространства n ( порядка 2 ^n).Геометрически это соответствуют процедуре построения вокруг базовой точки в качестве образца не n-мерного куба,а фигуры с меньшим кол-м вершин.

Под симплексом понимается n-мерный выпуклый многогранник n-мерного пространства, имеющий n+1 вершину. Для n=2 это треугольник, а при n=3 это тетраэдр.

Идея метода состоит в сравнении значений функции в n+1 вершинах симплекса и перемещении симплекса в направлении лучшей точки. В рассматриваемом методе симплекс перемещается с помощью операций отражения. Далее принято следующее: х₀(k), х₁(k), … , х_n(k) – вершины симплекса, где к - номер итерации, отрезок соединяющие вершины – ребра симплекса. После построения симплекса вычисляют значения целевой функции в вершинах симплекса и выбирают вершину с наибольшим значением целевой ф-и. Если таких вершин несколько, то может быть взята любая из них. Находят точку u из формул, симметричную вершине x(k) относительно гиперплоскости, в которой лежат остальные вершин симплекса ( xi !=xk). Нахождение точки u называется отражением вершины. В результате получают новый симплекс, образованный новой вершинной u и n вершиной xi. Если fu>=fxk, то следует вернуться к предыдущему симплексу, считается отражение вершины xk неудачным. В этом случае новый симплекс строится уменьшением размера предыдущего симплекса. При этом длину всех ребер симплекса уменьшают в 2 раза. Вершины нового симплекса находят по формулам, сжимая симплекс в 2 раза к вершине xm, в которой значение целевой ф-и меньше, чем в других вершинах симплекса. После того как новый симплекс построим осуществляют переход к этапу построению отпряжённой вершины дна нового симплекса все повторяется, условным прекращения поиска является уменьшение размеров симплекса до заранее выбранного значения (n<=E)

27 Метод циклического покоординатного спуска.

Заключается в последовательном минимизации целевой ф-и f(x) с поиском оптимальных шагов сначала по направлению единичной орты e1 вдоль первой координатной оси, затем по направлению единичной орты e2 вдоль второй координатной оси и т.д. После окончания минимизации по направлению единичной орты en вдоль n координатной оси цикл повторяется. Выберем начальную точку x0, Поиск точки минимума целевой функции проводят по формулам xl+1=xl+альфа*ej, где l-номер текущей точки приближения. Значения альфы находят из решения задачи одномерной минимизации. Индекс j изменяется циклически, пробегая на каждом шаге покоординатного спуска. Все значения от 1 до n, причем альфа могут быть + и -. Условная остановка рассматриваемого метода является модуль дельта <= E

29 Градиентные методы

Как известно, градиент функции в некоторой точке x_k направлен в сторону наискорейшего локального возрастания функции и перпендикулярен линии уровня (поверхность постоянного значения функции f(x), проходящей через точку x_k). Вектор, противоположный градиенту , называется антиградиентом, который направлен в сторону наискорейшего убывания функции f(x). Выбирая в качестве направления спуска p_k антиградиент - в точке x_k, мы приходим к итерационному процессу вида:

x_k+1 = x_k - a_k f’(x_k), a_k>0, k=0,1,2,… .

В координатной форме этот процесс записывается следующим образом:

Все итерационные процессы, в которых направление движения на каждом шаге совпадает с антиградиентом функции, называются градиентными методами. Они отличаются друг от друга только способом выбора шага a_k. Существует много различных способов выбора a_k, но наиболее распространены: метод с постоянным шагом, метод с дроблением шага и метод наискорейшего спуска.