Численные методы поиска экстремума функций многих переменных

Метод поиска:

Градиентный метод с постоянным шагом (без ограничений).
Градиентный метод с переменным шагом (без ограничений).
Метод наискорейшего спуска (без ограничений).
Метод сопряженных направлений (без ограничений).
Метод сопряженных направлений (при наличии ограничений).

Вид квадратичной формы: 2x₁²-x₁·x₂+2x₂²-6x₁+6 = 0
Вид ограничений: x₁+x₂-1=0
Координаты начальной точки x⁰=(3;-2)

Этапы проектирования

Постановка задачи в соответствии с вариантом задания.
Представление заданной квадратичной формы в матричной форме записи.
Исследование характера экстремума.
Описание в матричной форме метода поиска и составление алгоритма.
Составление структурной схемы алгоритма поиска.
Программирование в среде Math Cad.
Расчет.
Выводы по работе.

Постановка и решение задач многомерной безусловной оптимизации

Задачи многомерной безусловной минимизации

Для заданной функции решить задачу многомерной безусловной минимизации f(x₁, x₂), x∈X (X⊂R) и начальной точки x₀.
Пусть f(x) = f(x₁, x₂, … ,x_n) – действительная функция n переменных, определенная на множестве X Ì R_n. Точка x* Î X называется точкой локального минимума f(x) на множестве X, если существует такая
e-окрестность этой точки, что для всех x из этой окрестности, т. е., если
|| x - x*|| < e, выполняется условие f(x*) £ f(x).
Если выполняется условие f(x*) < f(x), то x* называется точкой строгого локального минимума. У функции может быть несколько локальных минимумов. Точка x*Î X называется точкой глобального минимума f(x) на множестве X, если для всех x Î X выполняется условие f(x*) £ f(x). Значение функции f(x*) называется минимальным значением f(x) на множестве X. Для нахождения глобального минимума необходимо найти все локальные минимумы и выбрать наименьшее значение. В дальнейшем будем рассматривать задачу нахождения локального минимума.

Теорема 1 (необходимое условие экстремума)
Пусть x*∈Rⁿ есть точка локального минимума (максимума) функции f(x) на множестве Rⁿ и она дифференцируема в точке х*. Тогда градиент функции в точке х* равен нулю:
▽f(x*)=0

Теорема 2 (достаточное условие)
Пусть функция f(x) в точке х* дважды дифференцируема, ее градиент равен нулю, а матрица Гессе является положительно определенной (отрицательно определенной), т. е. ▽f(x*)=0.
H(x*)>0 (H(x*)<0)
Тогда точка х* есть точка локального минимума (максимума) функции на множестве Rⁿ.
Для определения знака матрицы Гессе используется критерий Сильвестра.

Задание 1 Найти минимум функции классическим методом, используя необходимые и достаточные условия.
Данную задачу будем решать для функции f(x₁,x₂).
Начальная точка x₀
f(x)=3x²₁+x²₂-x₁x₂+x₁; x₀=(1.5,1.5)

Найдем частные производные первого порядка функции f(x):

; ; ;

Найдем производные второго порядка функции f(x):

Составим матрицу Гессе

Классифицируем матрицу Гессе, используя критерий Сильвестра:
Δ₁=11>0
Δ₂=6>0
Следовательно, матрица является положительно определенной.
Используя критерии проверки достаточных условий экстремума, можно сделать вывод: точка - является точкой локального минимума.
Значение функции в точке минимума:
;

Задание 2
Найти минимум данной функции методом градиентного спуска с дроблением шага.

Метод градиентного спуска с дроблением шага

Метод градиентного спуска является одним из самых распространенных и самых простых методов решения задачи безусловной оптимизации. Он основан на свойстве градиента функции, согласно которому направление градиента совпадает с направлением наискорейшего возрастания функции, а направление антиградиента – с направлением наискорейшего убывания функции. При решении задачи безусловной минимизации за направление спуска из точки x(m) выбирается

p(m) = –g(x(m)) = –f '(x(m)).

Таким образом, итерационная процедура для этого метода имеет вид

x(m+1) = x(m) – a(m)g(x(m)) (*)

Для выбора шага a(m) можно использовать процедуру дробления шага, которая состоит в следующем. Произвольно фиксируют начальное значение шага a(m) = a(m – 1) = a. Если в точке x(m+1), вычисленной в соответствии с (2.24), выполняется неравенство

f(x(m+1)) > f(x(m)),

то шаг дробится, например, пополам, т.е. полагается a(m +1) = 0.5a(m).
Применим метод градиентного спуска с дроблением шага для минимизации квадратичной функции
f(x) = ½(Ax, x) + (b, x) + c
с симметричной положительно определенной матрицей A.
Алгоритм метода градиентного спуска с дроблением шага для квадратичной функции
Шаг 1. Для квадратичной функции f(x) = + + с, ввести матрицу A =(a_ij), вектор b = (b₁, b₂, … , b_n)^T и коэффициент c,
i = 1, … , n; j = 1, … , n.
Выбрать произвольную начальную точку x = (x₁, x₂, … , x_n)^T, например,
x = (0, 0, … , 0)^T, начальный шаг a и e > 0. Вычислить f(x).
Шаг 2. Вычислить g = f '(x) = Ax + b, или покоординатно
g = (g₁, g₂, … , g_n)^T,
g_i = + b_i, i = 1, …, n.
Шаг 3. Проверить выполнение критерия окончания вычислений:
||f '(x)|| < e.
Если это условие выполнено, вычисления закончить и за приближенное значение точки минимума принять точку
x* = x = (x₁, x₂, … , x_n)^T.
В противном случае перейти к шагу 4.
Шаг 4. Вычислить
y = (y₁, y₂, … , y_n), y_i= x_i– a g_i, i = 1, …, n.
Шаг 5. Вычислить f(y).
Шаг 6. Если f(y) < f(x), то положить x = y, f(x) = f(y) и перейти к шагу 2, иначе – перейти к шагу 7.
Шаг 7. Положить α=α/2 и перейти к шагу 4.