Методы безусловной оптимизации
Задана функция:
Fx=2x12+x1x2+3x22+39x1-13x2
Найти экстремум и определить его тип (max или min) для заданной функции классическим методом, используя необходимые и достаточные условия существования экстремума.
Задать начальную точку и выполнить четыре шага градиентным методом с постоянным шагом
Задать начальную точку и выполнить три шага методом наискорейшего спуска.
Задать начальную точку и выполнить два шага методом Гаусса - Зейделя.
Задать начальную точку и выполнить 1 шаг методом Ньютона
Дать графическую иллюстрацию каждого метода на одном рисунке.
Выбрать одну и ту же начальную точку для каждого метода исходя из точного решения самостоятельно.
Решение
Fx=2x12+x1x2+3x22+39x1-13x2
1) Найдем стационарные точки, в которых , (необходимые условия экстремума).
Решим систему уравнений:
;
Найдена стационарная точка .
Исследуем ее на экстремум с помощью достаточных условий, рассмотрев знакоопределённость матрицы Гёссе:
H=∂2F∂x12∂2F∂x1∂x2∂2F∂x1∂x2∂2F∂x22=4116
a1=4>0, a2=4116=24-1=23>0
Определители первого и второго порядка больше нуля, следовательно гессиан положительно определён и - точка минимума.
2) Градиентный метод
Найдём градиент функции:
∇F=∂F∂x1∂F∂x2=4x1+x2+39x1+6x2-13
Каждое следующее приближение ищется в виде
X(j+1)=X(j)-h∙∇F(Xj)
h - шаг метода, который примем равным 0.2.
Примем в качестве начального приближения
X(0)=00 (x1=0; x2=0)
Будем использовать эту начальную точку для всех методов.
Оформим вычисления в таблицу:
№ шага j
Xj-1
∇F(Xj-1)
X(j)
1 00
39-13
00-0.239-13=-7.82.6
2 -7.82.6
10.4-5.2
-7.82.6-0.210.4-5.2=-9.883.64
3 -9.883.64
3.12-1.04
-9.883.64-0.23.12-1.04=-10.5043.848
4 -10.5043.848
0.832-0.416
-10.5043.848-0.20.832-0.416=-10.67043.9312
Получаем после четвёртой итерации
x1≈-10.6704; x2≈3.9312
3) Метод наискорейшего спуска
Каждое следующее приближение ищется в виде
Xn+1=Xn-λn∙∇FXn
Коэффициент λn определяется из условия минимума величины
F(Xn-λn∙∇FXn)
На каждом шаге сначала определяем λn, а затем соответствующее значение Xn+1.
Шаг 1
X0=00; ∇FX0=39-13
F00-λ0∙39-13=
=2-39λ02+-39λ013λ0+313λ02+39-39λ0-1313λ0=
=3042λ02-1690λ0
Отсюда
3042λ02-1690λ0'=6084λ0-1690, λ0=16906084
X1=00-16906084∙39-13≈-10.83333.61111
Шаг 2
X1=-10.83333.61111; ∇FX1=-0.72209-2.16664
FX1-λ1∙∇FX1=F0.72209λ1-10.8333-2.16664λ1+3.61111=
=-5.2257λ1+16.69λ12-234.72
Отсюда
-5.2257λ1+16.69λ12-234.72'=33.38λ1-5.2157=0, λ1=0.1563
X2=-10.83333.61111-0.1563∙-0.72209-2.16664≈-10.72053.94965
Шаг 3
X2=-10.72053.94965; ∇FX2=0.06765-0.0226
FX2-λ2∙∇FX2=F-10.7205-0.06765λ23.94965+0.0226λ2=
=-0.0050873λ2+0.0091564λ22-235.13
Отсюда
-0.0050873λ2+0.0091564λ22-235.13'=0.0183128λ2-0.0050873=0
λ2=0.2778
X3=-10.72053.94965-0.2778∙0.06765-0.0226≈-10.73933.95593
4) Метод Гаусса – Зейделя
Шаг 1:
Определяем значение функции в начальной точке:
X0=00;FX0=0
Осуществляем одномерный поиск по координате x1 при x2=0:
Fx1,x2=0=2x12+39x1
dFdx1=4x1+39=0⟹x1=394=-9.75
Осуществляем одномерный поиск по координате x2 при x1=-9.75:
Fx1=-9.75,x2=-22.75x2+3x22-190.125
dFdx2=6x2-22.75=0⟹x2=9124≈3.792
Шаг 2:
Получили точку
X1=-9.753.742;FX1=-233.255
Осуществляем одномерный поиск по координате x1 при x2=9124:
Fx1,x2=9124=2x12+102724x1-1183192
dFdx1=4x1+102724=0⟹x1=-102796≈-10.6979
Осуществляем одномерный поиск по координате x2 при x1=-102796:
Fx1=-102796,x2=-227596x2+3x22-8678154608
dFdx2=6x2-227596=0⟹x2=2275576≈3.9497
Получили точку
X2=-10.69793.9497;FX2=-235.127
5) Метод Ньютона
Сначала зададим начальное приближение
X(0)=00
Тогда итерационный процесс метода Ньютона будет иметь вид:
X(j+1)=X(j)-H-1(Xj)∙∇F(Xj)
где HXj – матрица Гёссе для j-го приближения Xj
Задать вопрос
на новый заказ в Автор24.
