Практика 3: Метод симплексов

Для начала необходимо задать стартовую точку и построить в её окружности симплекс. Путём операций по сжатию, растяжению, отражению переходим к точке минимума. Подробнее об этом в теории.

Пример решения задачи

Дано:

Функция $f(x) = x^2+y^2$

Начальные точки симплекса
$\overline{x}_{0} = [5; 5], \overline{x}_{1} = [3, 6],\overline{x}_{2} = [5, 2]$

Параметры: $\alpha = 1,\beta = 0,5,\gamma = 1$

Шаг 1. Обозначение точек

Необходимо вычислить значения функции в точках симплекса и обозначить их как: best, lousy, worst.

$f(x_0) = 50, f(x_1) = 45, f(x_2) = 29.$ $x_b = x_2 = [5, 2], x_l = x_1 = [3, 6], x_w = x_0 = [5, 5]$

Находим $x_a$ - среднее значение точек (кроме worst)

$x_a = \frac{([5, 2] +[3, 6])}{2} = [4, 4]$

Шаг 2. Отражение

(производится всегда после оценки точек) по формуле: $x_r = x_a + \alpha(x_a - x_w)$ $x_r = [4, 4] + 1*([4, 4]-[5, 5]) = [3, 3]$

Находим значение функции в точке f($x_r$) = 18. Далее у нас есть несколько вариантов событий, но так как f($x_r$) < f($x_b$), то следующим шагом будет

Шаг 3. Растяжение

$x_e = x_r + \gamma *(x_r-x_a)$ $x_e = [3, 3] + 1 *([3, 3] - [4, 4]) = [2, 2]$ Находим значение функции в точке $f(x_e) = 8$. Так как $f(x_e)<f(x_b)$, тогда $x_w = x_e$ Затем переходим на шаг 1

Обозначаем точки $f(5,2) = 29, f(3, 6) = 45, f(2, 2) = 8$ На этот раз $x_b = [2, 2], x_l = [5, 2], x_w = [3, 6]$. Находим $x_a = \frac{([2, 2] +[5, 2])}{2} = [3,5, 2]$

Затем следует отражение: $x_r = [3,5, 2] + 1*([3,5, 2]-[3, 6]) = [4, -2]$

Находим значение функции в точке f($x_r$) = 20. В этот раз $f(x_b)<f(x_r)$ и $f(x_r)<f(x_l)$ в этом случае $x_w = x_r$.

Обозначаем точки $f(5,2) = 29, f(4, -2) = 20, f(2, 2) = 8$ На этот раз $x_b = [2, 2], x_l = [4, -2], x_w = [5, 2]$. Находим $x_a = \frac{([2, 2] +[4, -2])}{2} = [3, 0]$

Затем следует отражение: $x_r = [3, 0] + 1*([3, 0]-[5, 2]) = [1, -2]$ Находим значение функции в точке f($x_r$) = 5. В этот раз $f(x_r)<f(x_b)$, поэтому следующим шагом будет

Растяжение $x_e = x_r + \gamma = 1 *(x_r-x_a)$ $x_e = [1, -2] + 1 *([1, -2] - [3, 0]) = [-1, 0]$ Находим значение функции в точке $f(x_e) = 1$. Так как $f(x_e)<f(x_b)$, тогда $x_w = x_e$ Затем переходим на шаг 1

Обозначаем точки $f(-1,0) = 1, f(4, -2) = 20, f(2, 2) = 8$ На этот раз $x_b = [-1, 0], x_l = [2, 2], x_w = [4, -2]$. Находим $x_a = \frac{([-1, 0] +[2, 2])}{2} = [0,5, 1]$

Затем следует отражение: $x_r = [0,5, 1] + 1*([0,5, 1]-[4, 2]) = [-3, 0]$ Находим значение функции в точке f($x_r$) = 9. В этот раз $f(x_r)>f(x_b)$ и $f(x_r)>f(x_l)$, но в то же время $f(x_r)<f(x_w)$, поэтому настало время для

Шаг 4. Внешнее сжатие

$x_o = x_a + \beta *(x_a-x_w)$ $x_o = [0,5, 1] + 0,5*([0,5,1] - [4,-2]) = [-1,25, 2,25]$ Найдем значение функции $f(x_o) = 6,625$ и $f(x_o)<f(x_r)$, поэтому $x_w = x_o$ и возвращаемся на шаг 1. И это было 10 вычисление целевой функции, поэтому можно остановиться.