Задание нп-7
Найти локальный минимум функции Задания №2 методом:
а) методом градиентного спуска с постоянным шагом;
б) методом Ньютона.
Задание нп-8
Решить задачу условной оптимизации с целевой функцией из Задания НП-3б) при условии ax1+bx2+c=0:
а) методом последовательной безусловной оптимизации;
б) методом проекции градиента:
№ в-та |
a |
b |
c |
№ в-та |
a |
b |
c |
№ в-та |
a |
b |
c |
№ в-та |
a |
b |
c |
1 |
3 |
6 |
3 |
6 |
2 |
5 |
3 |
11 |
3 |
8 |
5 |
16 |
2 |
4 |
6 |
2 |
2 |
5 |
7 |
7 |
4 |
2 |
2 |
12 |
4 |
2 |
6 |
17 |
3 |
7 |
4 |
3 |
5 |
3 |
2 |
8 |
2 |
6 |
4 |
13 |
2 |
8 |
6 |
18 |
2 |
2 |
4 |
4 |
4 |
5 |
9 |
9 |
3 |
4 |
1 |
14 |
5 |
3 |
2 |
19 |
3 |
5 |
2 |
5 |
3 |
4 |
7 |
10 |
4 |
2 |
6 |
15 |
4 |
3 |
7 |
20 |
2 |
5 |
3 |
Приложение 2. Образец решения индивидуального задания
Задание НП-1. Дана функция y=4x3+9x2+6x1. Найти:
а) Безусловные экстремумы функции.
б) Условные экстремумы функции на отрезке [2, 3].
Решение. а) Способ 1 (с применением первого достаточного условия). Для того, чтобы исследовать функцию одной переменной на безусловный экстремум (то есть найти для функции точки экстремумов, определить их характер и вычислить значения функции в этих точках) с применением первого достаточного условия, достаточно:
Найти у функции производную.
Решив уравнение y=0, найти стационарные точки функции.
Решив неравенство y>0 (y<0), определить, меняет ли знак производная в стационарных точках.
По характеру перемены знака производной определить, какие из стационарных точек являются точками максимума, какие точками минимума, какие ни теми, ни другими.
Вычислить значения экстремумов функции (то есть вычислить значения функции в точках экстремума).
Итак:
1. Найдём у функции производную: y=12x2+18x+6.
2. Решая уравнение y=0, найдём стационарные точки функции:
y=0 12x2+18x+6=0 2x2+3x+1=0, D=32421=1, x1, 2= = ,
то есть x1= , x2=1 стационарные точки функции.
3. Решая неравенство y>0, определяем, меняет ли знак производная в стационарных точках (используя метод интервалов):
y>0 2x2+3x+1=0 2(x+ )(x+1)>0 x( ; 1)( ; + ).
В частности, это означает, что y<0 x(1; ), то есть y меняет знак на противоположный в обеих стационарных точках.
4. В точке x1= y меняет знак с «» на «+». Поэтому эта точка точка минимума. В точке x2=1 y меняет знак с «+» на «». Поэтому эта точка точка максимума.
5. Вычисляем значения экстремумов функции в точках экстремума:
fmin(x)=f =4 +9 +6 1= ,
fmax(x)=f(1)=4(1)3+9(1)2+6(1)1=2.
Способ 2 (с применением второго достаточного условия). Для того, чтобы исследовать функцию на безусловный экстремум с применением второго достаточного условия, достаточно:
Найти у функции производную.
Решив уравнение y=0, найти стационарные точки функции.
Найти у функции производную второго порядка.
Определить, какие из стационарных точек являются точками максимума, какие точками минимума, какие ни теми, ни другими. Для этого вычисляем значение второй производной в стационарных точках.
Вычислить значения экстремумов функции.
Итак:
1. y=12x2+18x+6.
2. y=0 x1= и x2=1.
3. Найдём у функции производную второго порядка: y=24x+18.
4. Подставляя в y стационарные точки. Определяем, какие из них являются точками максимума, какие точками минимума: y(1)=24(1)+18=6<0. Поэтому x=1 точка максимума.
Далее,
y
=24
+18=6>0.
Поэтому x=
точка минимума.
5.
fmax(x)=f(1)=2,
fmin(x)=f
=
.
б) Для того, чтобы исследовать функцию y=f(x) одной переменной на условный экстремум на отрезке [a, b], достаточно:
1. Найти производную функции y.
2. Решив уравнение y=0, найти стационарные точки функции.
3. Вычислить значения функции в стационарных точках и на концах отрезка [a, b].
4. Выделить из значений функции, вычисленных в пункте 3, наибольшее и наименьшее значения.
Итак,
1. Найдём у функции производную: y=12x2+18x+6.
2. Решая уравнение y=0, найдём стационарные точки функции:
y=0
x1=
,
x2=1
стационарные точки функции
(подробности приведены при решение задания а))
3. Вычислим значения функции в стационарных точках и на концах отрезка [2, 3]:
f(1)=2,
f
=
(подробности см. решение задания а)),
f(2)=4(2)3+9(2)2+6(2)1=3, f(3)=433+932+631=206.
4. Сравнивая полученные в предыдущем пункте значения функции, выделяем из них наибольшее и наименьшее значения: fнаим(x)=f(2)=3, fнаиб(x)=f(3)=206.
Ответ: а) x=1 точка локального максимума, fmax(x)=2,
x=
точка локального минимума, fmin(x)=
.
б) fнаим(x)=3 достигается в точке x=2,
fнаиб(x)=206 достигается в точке x=3.
Задание НП-2. Исследовать на безусловный экстремум функцию:
а) f(x, y)=2x2+3xy+2y2+3x3y+2;
б)
f(x,
y)=6x3+6x2y3x+
y3
y;
в) f(x1, x2, x3)= 2 3 x12x2+x1x2;
г) f(x1, x2, x3)=2 +2 +3 2x1+3x2+2x1x3;
д) f(x1, x2, x3)= +2 +4x1+x22x1x2;
е) f(x1, x2, x3)=2 + + +x1x312x2+5x3+6.
Решение. а) Для того, чтобы исследовать функцию на безусловный экстремум (то есть для того, чтобы найти для функции точки экстремумов, определить их характер и вычислить значения функции в этих точках), достаточно:
1. Найти у функции частные производные первого порядка.
2. Решив систему
=0, i=1, 2, …, n, (1)
найти стационарные точки функции.
3. Найти у функции частные производные второго порядка и составить матрицу Гессе
H(X)
=
.
4. Определить, какие из стационарных точек являются точками максимума, какие точками минимума, какие ни тем, ни другим. Для этого используем информацию о знакоопределённости матрицы Гессе в стационарных точках.
5. Вычислить значения функции в точках экстремумов.
Итак, действуем по вышеуказанной схеме:
1.
Найдём у функции частные производные
первого порядка:
=4x+3y+3,
=3x+6y3.
2. Решая систему (1), найдём стационарные точки функции:
Применив
к последней системе, например, правило
Крамера, получаем =
=5,
x=
=9,
y=
=7,
(x,
y)=
=
,
то есть X0=
стационарная точка.
3.
Найдём у функции частные производные
второго порядка и составим матрицу
Гессе H(X)=
:
=4,
=
=3,
=6,
H(X)=
.
4. Так как = =15>0, то в точке X0= функция достигает своего экстремума. При этом =4>0. Поэтому в точке X0 функция достигает минимума.
5. Вычисляем значение функции в точке минимума:
fmin(x, y)=f =2 +3 +2 +3 3 +2= .
б) Действуем по вышеописанной схеме:
1.
Найдём у функции частные производные
первого порядка:
=18
+12xy3,
=6x2+y2
.
2. Решая систему (1), найдём стационарные точки функции:
(2)
Первое
уравнение системы (2) умножим на 7 и вычтем
из второго:
.
(3)
Заметим,
что y0
(в противном случае из уравнения (3)
получаем x=0,
то есть имеем x=0
и y=0,
что противоречит любому уравнению
системы (2)). Разделим уравнение (3) на y2:
,
и сделаем замену
.
Приходим к уравнению
,
и решаем его:
D=142415(1)=196+60=256=162,
,
,
,
то
есть
или
.
Дальше рассмотрим отдельно два случая:
Случай
1.
,
то есть x=y.
Подставляя это равенство, например, в
первое уравнение системы (3), получаем
уравнение
,
решениями которого являются y1,
2=
=
,
откуда и x1,
2=
,
и Х1=(
,
),
Х2=(
,
)
стационарные точки.
Случай 2. , то есть y=15x. Подставляя это равенство в первое уравнение системы (3), получаем
x3,
4=
,
откуда
y3,
4=
,
и Х3=(
,
),
Х4=(
,
)
ещё две стационарные точки.
3. Найдём у функции частные производные второго порядка и составим матрицу Гессе H(X):
=36х+12y,
=2y,
=
=12x,
H(X)=
.
4. Определим, какие из стационарных точек являются точками максимума, какие точками минимума, какие ни тем, ни другим.
Имеем
H(X1)=
=
,
1=
>0,
2=
=122
<0,
то есть 1>0 и 2<0, знаки угловых миноров хотя и чередуются, но начиная с «+». Значит, матрица Гессе знаконеопределённая, и точка X1 точкой экстремума не является.
Далее,
H(X2)=
=
,
1=
<0,
2=
=122
<0,
и снова матрица Гессе знаконеопределённая, то есть X2 точкой экстремума не является.
H(X3)=
=
,
1=
>0,
2=
>0.
Следовательно, H(X3) положительно определённая, и X3 точка локального минимума.
Аналогично
H(X4)=
,
1=
<0,
2=
>0,
и H(X4) отрицательно определённая. Это означает, что X4 точка локального максимума.
Таким образом, из стационарных точек точки X3 и X4 являются точками локальных экстремумов, причём X3 точка минимума, X4 точка максимума.
5. Вычислим значения функции в этих точках:
fmin=f(X3)=6
+6
3
+
=
.
Заметим, что
f(X)=6(x)3+6(x)2(y)3(x)+ (y)3 (y)=(6x3+6x2y3x+ y3 y)=f(X).
И так как X4=X3, то fmax=f(X4)=f(X3)=f(X3)= .
в) 1. Найдём у функции частные производные первого порядка: =2x11+x2, =4x22+x1, =6x3.
2. Решая систему (1), найдём стационарные точки функции:
Из последнего уравнения получаем x3=0, а первые два рассматриваем как отдельную систему из двух уравнений с двумя неизвестными, и решаем, например, правилом Крамера:
=
=7,
=
=6,
=
=5,
x1= = , x2= = .
Таким образом, X0= , стационарная точка функции.
3. Найдём у функции частные производные второго порядка и составим матрицу Гессе H(X):
=2, =4, =6, = =1,
= =1, = =0,
H(X)=
4. Определим, является ли стационарная точка точкой экстремума, и если да, то какой вид экстремума достигается в точке. Для этого исследуем на знакоопределённость матрицы Гессе, например, используя угловые миноры:
1=2<0, 2= =7>0, 3= =42<0,
то есть 1<0, 2>0, 3<0. Следовательно, H(X)<0 (матрица Гессе отрицательно определённая), и по достаточному условию экстремума точка X0= , является точкой максимума.
5. Вычислим значение функции в этой точке:
fmax=f(X0)=f , = 2 302 2 + = .
г) Действуем по схеме решения задачи, опуская подробные комментарии:
1. =4x12+2x3, =4x2+3, =6x3+2x1.
2. x2= .
Найдём x1 и x3:
= =5, = =3, = =1,
x1=
=
,
x3=
=
,
X0=
,
стационарная точка.
3. =4, =4, =6, = =0, = =2, = =0, H(X)= .
4. 1=4>0, 2= =16>0, 3= =80>0, H(X)>0 (матрица Гессе положительно определённая), и X0= , точка минимума.
5. fmin=f(X0)=f , =
=2 +2 +3 2 +3 +2 = .
д) 1. =2x1+42x2, =4x2+12x1, =2x3.
2. x3=0.
Найдём x1 и x2:
= =2, = =9, = =5,
x1= = , x2= = , X0= , стационарная точка.
3. =2, =4, =2, = =2, = =0, = =0, H(X)= .
4. 1=2>0, 2= =4>0, 3= =8<0, то есть 1>0, 2>0, 3<0, и матрица Гессе знаконеопределённая. Следовательно, X0= , точкой экстремума не является.
е) 1. Найдём у функции частные производные первого порядка: =4x1+x3, =3 12, =2x3+x1+5.
2. Найдём стационарные точки функции:
x2=2.
Отдельно ищем x1 и x3: = =7, = =5, = =20, x1= = , x3= = .
Таким образом, X1= , , X0= , стационарные точки функции.
3. Составим матрицу Гессе H(X):
=4, =6x2, =2, = =0,
= =1, = =0,
H(X)= .
4. Определим, какие из стационарных точек X1 и X2 являются точками максимума, какие точками минимума, какие ни тем, ни другим. Для этого используем информацию о знакоопределённости матрицы Гессе в стационарных точках.
Имеем H(X1)= , и
1=4>0, 2= =48>0, 3= =84>0,
и H(X1)>0. Значит, точка X1= , точка минимума.
Далее, H(X2)= , и
1=4>0, 2= =48<0, 3= =84<0,
то есть 1>0, 2<0, 3<0, и H(X1) является знаконеопределённой. Это означает, что точка X2= , не является точкой экстремума.
Таким образом, из стационарных точек только X1 является точкой экстремума, причём является точкой минимума.
5. Вычислим значение функции в точке X1:
fmin=f(X1)=f , =2 +23+ + 122+5 +6= .
Ответ: а) fmin(x, y)= достигается в точке , точек максимума у функции нет.
б) Х=( , ) точка локального минимума, fmin= ,
Х=( , ) точка локального максимума, fmax= .
в) fmax= достигается в точке X= , , точек минимума у функции нет;
г) fmin= достигается в точке X0= , , точек максимума у функции нет;
д) точки экстремума у функции не существует.
е) fmin= достигается в точке X1= , , точек максимума у функции нет.
Задание НП-3. Исследовать на безусловный экстремум функцию:
а) f(x1, x2)=x1+x2 при условии ;
б)
f(x1,
x2)=
при условии
;
Решение. Для того, чтобы исследовать функцию на условный экстремум с ограничениями типа равенства (то есть найти для функции точки условных экстремумов, определить их характер и вычислить значения функции в этих точках), достаточно:
Составить обобщённую функцию Лагранжа:
L(X, 0, )=0f(X)+
Составить систему:
(1)
Решить систему (4) для двух случаев:
а) 0=0;
б) 0=1.
В результате находятся условно-стационарные точки X*.
Для условно стационарных точек X*, полученных в пункте 3, проверить достаточные условия экстремума. Для этого можно применить критерии типа Сильвестра к функции d2L(X*, *), или проверить это непосредственно, выразив из системы
любые m
дифференциалов через остальные nm
и подставив их в d2L(X*,
*).
Если d2L(X*,
*)>0
при ненулевых dx,
то точка X*
является точкой условного минимума, а
если d2L(X*,
*)<0,
то
точкой условного максимума. Если
достаточные условия не выполняются,
то проверяются необходимые условия
второго порядка. Если они выполняются,
то требуется дополнительные исследования;
если нет, то точка X*
не является точкой условного экстремума.Вычислить значения функции в точках условного экстремума.
Итак, действуем по приведённой схеме:
Составим обобщённую функцию Лагранжа:
L(X, 0, )=0(x1+x2)+1( ).
Составим систему (1). Имеем =0+21x1, =0+21x2. Поэтому
(2)
Решаем систему для двух случаев:
а) 0=0.
Имеем 1≠0, так как в точке локального экстремума X* не все 0 и 1 равны нулю. Тогда x1=0 и x2=0. Но тогда (X*)≠0, то есть X*=(0, 0) не удовлетворяет ограничению задачи. Значит, условно-стационарных точек при 0=0 нет.
б) 0=1. Тогда
(2)
Из первых двух уравнений системы получаем x1= , x2= , подставляя которые в третье, имеем =8 = 1= . Отсюда x1= 2, x2= 2, то есть (X1, 1)=(2, 2, ), (X2, 2)=(2, 2, ) две условно-стационарные точки.
Для условно стационарных точек X*, полученных при 0=1, проверим достаточные условия экстремума. Для этого исследуем полный дифференциал второго порядка d2L(X*, *) классической функции Лагранжа как квадратичную форму от dx1, dx2.
Имеем
= =21, = =0.
Поэтому d2L=21d +21d .
Способ 1. Имеем H(X)= , для которого угловые миноры равны 1=21 и 2=4 . При 1= , то есть для точки X1=(2, 2), имеем 1= <0 и 2= >0. Это означает, что в точке (X1, 1)=(2, 2, ) d2L отрицательно определена, и X1 точка регулярного условного локального максимума. При 1= имеем 1= >0 и 2= >0, и в точке (X2, 2)=(2, 2, ) d2L положительно определена, и X2 точка регулярного условного локального минимума.
Способ 2. Имеем d=2x1dx1+2x2dx2. Выразим из d=0 dx2 через dx1: dx2=dx1 и подставим его в d2L: d2L=21d +21(dx1)2=41d , то есть d2L=41d . Тогда
d2L(X1, 1)=d <0 при dx1≠0 и
d2L(X2, 2)=d >0 при dx1≠0.
Поэтому X1 точка регулярного условного локального максимума, X2 точка регулярного условного локального минимума.
Вычислим значения функции в точках условного экстремума:
fmax=f(X1)=2+2=4, fmin=f(X2)=22=4.
б) Действуем по приведённой схеме:
1) Составим обобщённую функцию Лагранжа:
L(X,
0,
)=0(
)+1(
).
2) Составим систему (4). Имеем
=0(
)+81x1,
=0(
)+
1x2.
Поэтому
(3)
3) Решаем систему для двух случаев:
а) 0=0. Тогда (3) равносильно
Имеем 1≠0, откуда x1=0 и x2=0, что противоречит ограничению. Значит, условно-стационарных точек при 0=0 нет.
б) 0=1.
(3)
(4)
Одновременно
x1
и x2
в ноль обращаться не могут. Покажем, что
они одновременно не равны нулю. Допустим,
x1=0.
Тогда из первого уравнения системы (4)
вытекает x2=0.
Если x2=0,
то из второго уравнения получаем x1=0.
Следовательно, x1
и x2
оба не равны нулю. Тогда из первых двух
уравнений системы (4) можно выразить
через x1
и x2:
1=
и 1=
,
откуда получаем следующую последовательность
равносильностей:
=
=
=
.
Разделим
последнее уравнение на
:
,
и сделаем замену:
.
Решаем полученное уравнение
:
D=2243(1)=4+12=16=42,
t1,
2=
=
,
t1=1,
t2=
,
то
есть
или
.
Далее отдельно рассмотрим случаи.
Случай 1. . Тогда x1=x2, подставляя которое в ограничение, получаем уравнение с последующими равносильными преобразованиями:
,
откуда
.
Также имеем
1=
=
=
=
,
и
(X1,
1)=(
,
;
),
(X2,
2)=(
,
;
)
две условно-стационарные точки.
Случай 2. . Тогда x2=3x1, подставляя которое в ограничение, получаем уравнение с последующими равносильными преобразованиями:
,
и
,
1=
=
=
,
и (X3,
3)=(
,
;
),
(X4,
4)=(
,
;
)
ещё две условно-стационарные точки.
4. Проверим достаточные условия экстремума. Имеем
=8+81, =2+ 1, = =2.
Имеем
H(X)=
,
для которого угловые миноры равны
1=8+81
и 2=
=
.
Для
точек X1=(
,
)
и (X2,
2)=(
,
;
)
имеем 1=
,
и 1=8+8
=2>0
и 2=
=4<0,
то есть 1>0
и 2<0,
и H(X1,
2)
знаконеопределённая, и эти точки не
являются точками экстремумов.
Для
точек X3=(
,
)
и X4=(
,
)
имеем 1=
,
и 1=8+8
=6<0,
2=
=8>0,
то есть 1<0,
2>0,
H(X3,
4)
отрицательно определённая, и X3,
X4
точки регулярного условного локального
максимума.
5. Вычислим значения функции в точках условных максимумов:
fmax=f(X3)=f(X4)=
=
.
Ответ: а) X=(2, 2) точка регулярного условного локального максимума, fmax=4, X=(2, 2) точка регулярного условного локального минимума, fmin=4;
б) точки X=( , ) и X=( , ) точки регулярного условного локального максимума, fmax= ; точек регулярного локального минимума нет.
Задание НП-4. Исследовать на условный экстремум функцию:
а) f(x1, x2)=2 +3 при условии + 4;
б) f(X)=(x14)2+ при условиях
в) f(X)=(x12)2+ при условиях
Решение. Для того, чтобы исследовать функцию на условный экстремум с условиями типа неравенства, достаточно:
1. Составить обобщённую функцию Лагранжа:
L(X, 0, )=0f(X)+ .
2. Составить систему:
(1)
3. Решить систему (1) для двух случаев:
а) 0=0;
б) 0=1.
В результате находятся условно-стационарные точки X*.
4. Для условно стационарных точек X*, полученных в пункте 3, проверить достаточные условия экстремума. Для этого:
1) определить число l активных в точке X* ограничений;
2) если l=n и >0 для всех iIa, то в точке X* локальный минимум. Если l=n и <0 для всех iIa, то в точке X* локальный максимум. Если l<n или соответствующие множители Лагранжа не удовлетворяют достаточным условиям первого порядка, то проверить достаточные условия второго порядка. Для этого:
1) записать выражение для второго дифференциала классической функции Лагранжа в точке (X*, *):
d2L(X*, *)= ;
2) записать условия, накладываемые на первые дифференциалы активных ограничений:
(2)
3) исследовать знак второго дифференциала функции Лагранжа для ненулевых dx, удовлетворяемых системе (2). Если d2L(X*, *)>0, то в точке X* условный локальный минимум. Если d2L(X*, *)<0, то в точке X* условный локальный максимум.
Если достаточные условия первого и второго порядка не выполняются, то проверяется выполнение необходимых условий второго порядка. Если они не выполняются, то в точке X* нет условного экстремума, а если выполняются, то требуется дополнительное исследование.
5. Вычислить значения функции в точках условного экстремума.
а)
Имеем 1(Х)=(Х)=
Действуем по нижеприведённой схеме:
1. Составим функцию Лагранжа:
L(X,
0,
)=0(
)+1(
).
2. Составим систему (1). Имеем =60 +21x1, =90 +21x2. Поэтому
(3)
3. Решаем систему для двух случаев:
a)
0=0.
Тогда из первых двух уравнений системы
(3) имеем
и
.
Имеем 1≠0
(так как в точке условного экстремума
0
и 1
одновременно не равны нулю). Поэтому
x1=0
и x2=0,
и из последнего уравнения получаем,
,
что невозможно при x1=0
и x2=0.
То есть условно-стационарных точек при
0=0
нет.
б) 0=1. Система (10) принимает вид
(4)
Из
первых двух уравнений системы (4) получаем
1≠0
(так как в противном случае имеем
,
и
,
то есть x1=0,
x2=0
и 4=0
противоречие). Тогда из последнего
уравнения системы получаем
.
В частности, x1
и x2
одновременно нулю не обращаются.
Далее отдельно рассматриваем случаи x1=0, x2=0 и x1x20.
Случай
1. x1=0.
Тогда
и x2=2.
Из второго уравнения системы (4) получаем
уравнение
,
откуда
,
то есть
=
9.
Таким образом, (
)=(0,
2; 9),
(
)=(0,
2;
9)
условно-стационарные точки.
Случай
2. x2=0.
Тогда
и x1=2.
Из первого уравнения системы (11) получаем
уравнение
,
откуда
=
6,
и (
)=(2,
0; 6),
(
)=(2,
0; 9)
ещё две условно-стационарные точки.
Случай
3. x1x20,
то есть x10
и x20.
Тогда из первых двух уравнений системы
(11) получаем
и
,
откуда
=
=
,
подставляя которое в уравнение
,
получаем
,
откуда
=
=
.
При этом
=
.
Таким образом, получили ещё две
условно-стационарные точки (
)=(
,
,
)
и (
)=(
,
;
).
4. Для полученных условно-стационарных точек проверим достаточные условия экстремума.
Число ограничений всего одно. Поэтому число l активных ограничений не может равняться n=2 числу переменных: l<n. Поэтому достаточные условия первого порядка не выполняются. Проверим достаточные условия второго порядка. Для этого:
1) Запишем выражение для второго дифференциала классической функции Лагранжа в условно-стационарных точках (X*, *). Имеем
=12x1+21,
=18x2+21,
=
=0.
Поэтому
d2L=(12x1+21)d
+(18x2+21)d
.
2) Запишем условия (2), накладываемые на первый дифференциал активного ограничения. В нашем случае ограничение одно, и только оно может быть активным:
d1(X)=2x1dx1+2x2dx2. (5)
3) Исследуем знак второго дифференциала функции Лагранжа для ненулевых dx, удовлетворяющих равенству (5). Если d2L(X*, *)>0, то в точке X* условный локальный минимум. Если d2L(X*, *)<0, то в точке X* условный локальный максимум.
Итак, пусть (X*, *)=( )=(0, 2; 9). Тогда
d2L( )=(120+2(9))d +(182+2(9))d =18d +18d =
=18(d +d ),
d(X1)=20dx1+22dx2=4dx2 и d(X1)=0 dx2=0, откуда d2L( )=18d <0. Значит, X1=(0, 2) точка регулярного условного максимума.
Пусть
(X*,
*)=(
)=(0,
2;
9). Тогда
d2L( )=(120+29)d +(18(2)+29)d =18d 18d =
=18(d d ),
d(X2)=20dx1+2(2)dx2=4dx2 и d(X2)=0 dx2=0, откуда d2L( )=18d >0. Значит, X2=(0, 2) точка регулярного условного минимума.
Пусть (X*, *)=( )=(2, 0; 6). Тогда
d2L( )=(122+2(6))d +(182+2(6))d =12d +24d =
=12(d +d )>0.
Итак, имеем, d2L( )>0, но 1<0, что означает, что необходимое условие второго порядка не выполнено. Значит, точка X3 не является точкой условного экстремума.
Пусть (X*, *)=( )=(2, 0, 6). Тогда
d2L( )=(12(2)+26)d +(18(2)+26)d =12d 24d =
=12(d +d )<0.
Итак, имеем, d2L( )<0, но 1>0, и снова необходимое условие второго порядка не выполнено. Значит, точка X4 не является точкой условного экстремума.
Пусть (X*, *)=( )=( , ; ). Тогда
d2L(
)=(12
+2
)d
+(18
+2
)d
=
=
d
+
d
>0.
Снова имеем, d2L( )>0 и 1<0, и снова необходимое условие второго порядка не выполнено. Значит, точка X5 не является точкой условного экстремума.
Наконец, если (X*, *)=( )=( , ; ), то
d2L(
)=(12
+2
)d
+(18
+2
)d
=
= d d <0,
и так как 1>0, то снова необходимое условие второго порядка не выполнено с соответствующим выводом: точка X6 не является точкой условного экстремума.
Таким образом, из найденных 6 условно-стационарных точек только две точки являются точками (регулярного) условного экстремума. Это X1=(0, 2) точка регулярного условного максимума, и X2=(0, 2) точка регулярного условного минимума.
5. Вычислим значение функции в точках условных экстремумов:
fmax=f(X1)=203+323=24, fmin=f(X2)=203+3(2)3=24.
б)
В данном случае 1(Х)=
и 2(Х)=
.
Действуем по общей схеме:
1. Составим обобщённую функцию Лагранжа:
L(X,
0,
)=0((x14)2+
)+1(
)+2(
).
2.
=20(x14)+21(x1+4)+22x1,
=20x2+21x2+22x2.
(6)
3. а) 0=0. Тогда 1≠0 или 2≠0, и,
(7)
(8)
В
частности,
.
Случай
невозможен, так как в противном случае
в силу
и
(либо
и
)
имеем
(1
и 2
не могут иметь разные знаки). Поэтому
и
.
Если
,
то
,
откуда
и
или
.
Второе невозможно, так как в противном
случае
,
что противоречит четвёртому соотношению
системы (8). Значит,
,
подставляя которое в первое уравнение
системы (8), получаем
,
то есть
,
откуда
,
что противоречит тому, что
и
.
Если
,
то
,
откуда
.
невозможно, так как в противном случае
,
что противоречит третьему соотношению
системы (8). Значит,
,
подставляя которое в первое уравнение
системы (8), получаем
,
откуда
противоречие. Таким образом,
.
б) 0=1. Тогда
(8)
(9)
в
частности,
.
Случай
1.
.
Из первого уравнения получаем
,
откуда
и
,
и
с
имеют разные знаки, что невозможно.
Случай 2. .
Случай
2.1.
.
Тогда из первого уравнения получаем
,
то есть
.
Это противоречит третьему соотношению
системы (9).
Случай
2.2.
.
Тогда
и
,
откуда
.
Как мы уже видели,
.
Значит,
.
Теперь первое уравнение системы (9) даёт
,
откуда
.
Таким образом, (
)=(4,
0; 0, 2)
условно-стационарная точка.
Случай
2.3.
.
Тогда
и, как мы уже видели,
,
подставляя которое в первое уравнение,
получаем
,
откуда
.
Таким образом, (
)=(1,
0;
,
0)
вторая условно-стационарная точка.
Случай
2.4.
.
Тогда
в силу
,
и получаем противоречие.
Таким образом, получили две условно-стационарные точки:
( )=(4, 0; 0, 2), ( )=(1, 0; , 0).
4. В точке X1 первое ограничение не является активным, а в точке X2 второе. Поэтому достаточные условия первого порядка не выполнены. Проверим достаточные условия второго порядка.
1) Имеем = =1+1+2, = =0.
d2L=(1+1+2)d +(1+1+2)d =(1+1+2)(d +d ).
2) d1(X)=2(x1+4)dx1+2x2dx2, d2(X)=2x1dx1+2x2dx2.
3)
В любом случае dx1=0. Тогда
d2L( )=(d +d )=d <0 (при этом 1=00, 2=2<0),
d2L( )=(1+ )(d +d )= d >0 (при этом 1= >0, 2=00).
Следовательно, X1=(4, 0) точка регулярного условного максимума, а X2=(1, 0) точка регулярного условного минимума.
5. Вычислим значения функции в точках условного экстремума:
fmax=f(
)=(44)2+02=64,
fmin=f(
)=(14)2+02=25.
в)
В нашем случае 1(Х)=
и 2(Х)=x1.
Действуем по общей схеме:
1. L(X, 0, )=0((x12)2+ )+1( )+2(x1).
2. =20(x12)+21x12, =20x2+21x2.
(10)
3. а) 0=0. Тогда первые два уравнения образуют систему
Так как 0, 1 и 2 одновременно не равны нулю, то 1≠0 или 2≠0.
Если
1≠0,
то
откуда
и
.
Тогда
,
то
есть 2≠0,
и из последнего уравнения системы (10)
получаем, что
противоречие.
Таким образом, 0≠0.
б) 0=1. Тогда
(10)
(11)
Отдельно рассмотрим случаи:
Случай
1.
.
Из первого уравнения системы (11) получаем
,
то есть
.
Из второго уравнения
.
Таким образом, (X1,
1)=(2,
0; 0, 0)
условно-стационарная точка.
Случай
2.
.
Тогда из второго уравнения получаем
,
а из последнего
.
Теперь первое уравнение примет вид
,
то есть
,
и получили условно-стационарную точку
(X2,
2)=(0,
0; 0, 4).
Случай 3. . Тогда из системы (11) получаем систему
(12)
Первое уравнение преобразуется:
.
Поэтому
равенство
невозможно. Значит,
,
и из второго уравнения системы (3.3.9)
получаем
,
откуда и из последнего уравнения получаем
.
Так как 
,
то
.
Теперь из
получаем
и
,
что противоречит условию случая.
Случай 4. . Тогда из последних двух уравнений системы (11) получаем
Теперь
первое уравнение (11) принимает вид
,
то есть
,
а второе принимает вид
,
где
.
Значит,
,
и получили ещё две условно-стационарные
точки:
(X3, 3)=(0, 2; 1, 4), (X4, 4)=(0, 2; 1, 4).
4.
В точках X3
и X4
оба ограничения активны:
и l=2=n,
то есть выполнены достаточные условия
первого порядка. При этом 3=4=(1,
4),
то есть
и
.
Значит, X3
и X4
точки регулярного условного максимума.
В точке X1 активно только первое ограничение и l=1<n=2, то есть достаточные условия первого порядка не выполнены. Проверим достаточные условия второго порядка.
1) Имеем = =1+1, = =0.
d2L=(1+1)d +(1+1)d =(1+1)(d +d ).
При X=X1 имеем и d2L=d +d >0, то есть X1 точка регулярного условного минимума.
В точке X2 активно только второе ограничение и l<n. Проверим достаточные условия второго порядка.
1) Как мы уже видели, d2L=(1+1)(d +d ), и при X=X2 снова и d2L=d +d >0. При этом 2=4<0, то есть знаки d2L( )>0 и не согласуются, и необходимые условия второго порядка в точке X2 не выполнены.
5. Вычислим значения функции в точках условного экстремума:
fmin=f(
)=(22)2+02=0,
fmax=f(
)=f(
)=(02)2+(2)2=8.
Ответ: а) X=(0, 2) точки регулярного условного локального максимума, fmax=24; X2=(0, 2) точка регулярного условного локального минимума, fmin=24.
б) X=(4, 0) точка регулярного условного максимума, fmax=64, X=(1, 0) точка регулярного условного минимума, fmin=4.
в) X=(2, 0) точка регулярного условного минимума, fmin=0; X=(0, 2), X=(0, 2) точки регулярного условного максимума, fmax=8.
Задание НП-6. Решить задачу f(x)=x26x+14min методом
а) равномерного поиска;
б) деления интервала пополам.
Решение. а) Метод равномерного поиска заключается в следующем:
1. Определяется начальный интервал неопределённости L0=[a0, b0] и количество N вычислений функции.
2.
L0
разбивается на N+1
равных интервалов точками xi=a0+i
вычисления функции.
3. Вычисляются значения функции в найденных точках: f(xi), i=1, 2, …, N.
4.
Среди точек xi,
i=1,
2, …, N
находится точка x*
такая, в которой функция принимает
наименьшее значение: f(xk)=
.
Применяем описанный алгоритм:
1. Определим начальный интервал неопределённости L0=[a0, b0] и количество N=11 вычислений функции.
Для определения начального интервала неопределённости можно применить алгоритм Свенна, который заключается в следующем:
1. Задать произвольно следующие параметры: x0 некоторую точку, h>0 величину шага. Положить k=0.
2. Вычислить значение функции в точках x0h, x0, x0+h.
3. Проверить условие окончания:
а) если f(x0h)f(x0)f(x0+h), то начальный интервал неопределённости определён: [a0, b0]=[x0h, x0+h];
б) если f(x0h)f(x0)f(x0+h), то функция не является унимодулярной, и требуемый интервал не может быть найден. Требуется задать другую x0.
в) если условие окончания не выполняется, то перейти к шагу 4.
4. Определить величину :
а) если f(x0h)f(x0)f(x0+h), то =h, a0=x0, x1=x0+h;
б) если f(x0h)f(x0)f(x0+h), то =h, b0=x0, x1=x0h, k=1
5. Найти следующую точку xk+1=xk+2k;
6. Проверить условие убывания функции:
а) если f(xk+1)<f(xk) и =h, то a0=xk;
если f(xk+1)<f(xk) и =h, то b0=xk;
в обоих случаях положить k=k+1 и перейти к шагу 5);
б) если f(xk+1)f(xk), то процедура завершается. При =h положить b0=xk+1, а при =h положить a0=xk+1. В результате имеем [a0, b0] искомый интервал неопределённости.
Итак, найдём методом Свенна начальный интервал неопределённости для решения нашей задачи, положив x0=0 и h=1:
1. Положим k=0.
2.0. Вычисляем значение функции в точках x0h=1, x0=0, x0+h=1:
f(1)=21, f(0)=14, f(1)=9.
3.0. Так как f(1)>f(0)>f(1)=9, то условие окончания не выполняется.
4.0. Полагаем =h=1, a0=x0=0, x1=x0+h=1, k=1.
5.1. Найдём следующую точку x2=x1+2=3.
6.1. Проверим условие убывания функции. Так как f(x2)=5<f(x1)=9 и =h, то a0=x1=1. Положим k=2.
5.2. Найдём следующую точку x3=x2+22=7;
6.2. Проверим условие убывания функции. Так как f(x3)=21>5=f(x2) то поиск завершён: правая граница b0=7.
Таким образом, [1; 7] начальный интервал неопределённости.
Продолжаем алгоритм равномерного поиска:
2.
Найдём точки xi=a0+i
=1+i
=1+0,5i
вычислений функции: x1=1,5,
x2=2,
x3=2,5,
x4=3,
x5=3,5,
x6=4,
x7=4,5,
x8=5,
x9=5,5,
x10=6,
x11=6,5.
3. Вычислим значения функции в найденных точках: f(1,5)=7,25, f(2)=6, f(2,5)=5,25, f(3)=5, f(3,5)=5,25, f(4)=6, f(4,5)=7,25, f(5)=9, f(5,5)=11,25, f(6)=14, f(6,5)=17,25.
4. В точке x4=3 функция принимает наименьшее значение: f(3)=5minf(x).
б) Метод деления интервала пополам заключается в том, что на очередном шаге интервал делится на четыре равные части и, сравнивая в точках деления значения функции, оставляется та половина интервала, которая содержит точку с наименьшим значением. Процесс деления продолжается до тех пор, пока длина интервала не окажется меньше некоторой заданной величины . Более подробно метод следующий алгоритм:
Задать начальный интервал неопределённости L0=[a0, b0] и >0 точность.
Положить k=0.
Разбиваем интервал [ak, bk] на 4 равные части точками
=
(середина интервала), yk=
(середина интервала [ak,
]),
zk=
(середина интервала [
,
bk])Вычислить значения f(yk), f( ), f(zk) функции f(x) в точках yk, , zk соответственно.
Сравнить значения f(yk) и f( ):
а)
если f(yk)<f(
),
то полагаем bk+1=
,
ak+1=ak
(из рассмотрения исключается интервал
(
,
bk]),
=yk
(yk
становится серединой нового интервала).
Перейти к шагу 7.
б) если f(yk)f( ), то перейти к шагу 6.
Сравнить f(zk) и f( ):
а) если f(zk)<f( ), то полагаем ak+1= , bk+1=bk, =zk (из рассмотрения исключается интервал [ak, ), zk становится серединой нового интервала. Перейти к шагу 7.
б) если f(zk)f( ), то полагаем ak+1=yk, bk+1=zk, = (из рассмотрения исключаются интервалы [ak, yk), (zk, bk], становится серединой нового интервала). Перейти к шагу 7.
Вычислить |bk+1ak+1| и проверить условие окончания:
а) если |bk+1ak+1|<, то поиск завершается, x*[bk+1, ak+1] и x* ;
б) если |bk+1ak+1|, то положить k=k+1 и перейти к шагу 3.
Итак, решаем задачу методом деления пополам:
1. Задаём начальный интервал неопределённости L0=[1; 7] (см. решение задания а) и =1 точность.
2. Положим k=0.
3.0.
Разбиваем интервал [1; 7] на 4 равные части
точками
=
=4,
y0=
=2,5,
z0=
=5,5.
4.0. Вычисляем значения f(y0)=5,25, f( )=6, f(z0)=11,25 функции f(x) в точках y0, , z0 соответственно.
5.0. Сравним значения f(y0) и f( ). Так как f(y0)=5,25<6=f( ), то полагаем b1= =4, a1=a0=1 и переходим к шагу 7.
7.0. Вычисляем |b1a1|=3>. Полагаем k=1 и переходим к шагу 3.
3.1.
Разбиваем интервал [1; 4] на 4 равные части
точками
=
=2,5,
y1=
=1,75,
z1=
=3,25.
4.1. Вычисляем значения f(y1)=6,5625, f( )=5,25, f(z1)=5,0625 функции f(x) в точках y1, , z1 соответственно.
5.1. Сравним значения f(y1) и f( ). Так как f(y1)=6,5625>5,25=f( ), то переходим к шагу 6.
6.1.
Сравним f(z1)
и f(
).
Так как f(
)>f(z1),
то полагаем a2=
=2,5,
b2=b1=4,
=z1=3,25
и переходим к шагу 7.
7.1. Вычисляем |b2a2|=1,25>. Полагаем k=2 и переходим к шагу 3.
3.2.
Разбиваем интервал [2,5; 4] на 4 равные
части точками
=
=3,25,
y2=
=2,875,
z2=
=3,625.
4.2. Вычисляем значения f(y2)=5,015625, f( )=5,0625, f(z2)=5,390625 функции f(x) в точках y2, , z2 соответственно.
5.2.
Сравним f(y2)
и f(
).
Так как f(y2)<f(
),
то полагаем a3=a2=2,5;
b3=
=3,25,
=y2=2,875
и переходим к шагу 7.
7.2. Вычисляем |b3a3|=0,75<. Поиск завершается: x* =2,875.
fmin(x)f(2,875)=5,015625.
Ответ: а) fmin(x)f(3)=5.
б) fmin(x)5,015625.
Задание НП-7. Найти локальный минимум функции
f(x1, x2)=3 +2x1x2+2 .
а) методом градиентного спуска с постоянным шагом;
б) методом Ньютона.
Решение. а) Метод градиентного спуска численных методов минимизации заключается в построении итерационной последовательности {Xk} по формулам Xk+1=Xkhkf(Xk), hk (постоянная) величина шага. Убывание целевой функции контролируется путём проверки выполнения условия f(Xk+1)f(Xk)<0. Построение последовательности {Xk} заканчивается в точке Xk, для которой |f(Xk)|<1, или выполняется система
где 1, 2 заданные положительные числа, или kk0, где k0 предельное число итераций. Дополнительно необходимо провести исследование вопроса, является ли найденная точка действительным приближением искомой функции. Более подробно:
1.
Задать X0,
1>0,
2>0,
k0.
Найти градиент функции f(X)=
,
…,
.
2. Положить k=0.
3. Вычислить f(Xk).
4. Проверить критерий окончания |f(Xk)|1:
а) если критерий выполнен, то расчёт закончен: X*=Xk;
б) если критерий не выполнен, то перейти к шагу 5.
5. Проверить выполнение неравенства kk0:
а) если неравенство выполнено, то расчёт окончен: X*=Xk;
б) если нет, то перейти к шагу 6.
6. Задать величину шага hk.
7. Вычислить Xk+1=Xkhkf(Xk).
8. Проверить выполнение условия f(Xk+1)f(Xk)<0:
а) если условие выполнено, то перейти к шагу 9;
б)
если условие не выполнено, то положить
hk=
и перейти к шагу 7.
9. Проверить условия (Xk+1, Xk)<2 и |f(Xk+1)f(Xk)|<2:
а) если оба условия выполнены при текущем значении k и k1, то расчёт окончен: X*=Xk;
б) если хотя бы одно условие не выполнено, то положить k=k+1 и перейти к шагу 3.
Вопрос о сходимости последовательности {Xk} к решению X* решается в общем в случае с помощью условия Липшица: если f(X) сильно выпуклая функция, то при любом выборе X0 последовательность {Xk}, полученная методом градиентного спуска, сходится к точке X*. Поэтому прежде, чем начинать строить последовательность {Xk}, необходимо проверить условие сильной выпуклости функции.
После окончания процедуры нахождения X*Xk, необходимо проверить, что найденная точка, действительно, является приближением решения задачи. Если f(X) дважды непрерывно дифференцируемая, то при H(Xk)>0 точка Xk является приближением искомой точки.
Итак,
применяем вышеописанный алгоритм.
Прежде всего убедимся, что функция
выпукла. Так как H(X)=
,
то H(X)>0
и функция сильно выпукла, и сходимость
итерационного процесса гарантирована.
I. Найдём Xk.
1. Зададим X0=(1, 1), 1=0,1, 2=0,1, k0=10 и найдём градиент f(X)=(6x1+2x2, 2x1+4x2).
2. Положим k=0.
3.0. Вычислим f(X0)=(8; 6).
4.0.
Вычислим |f(X0)|
и проверим критерий окончания:
|f(X0)|=
=10>0,1.
Переходим к шагу 5.
5.0. Проверим условие k>k0: k=0<10=k0. Переходим к шагу 6.
6.0. Зададим h0=0,2.
7.0. Вычислим X1=X00,2f(X0)=(1; 1)0,2(8; 6)=(0,6; 0,2).
8.0. Проверим выполнение условия f(X1)f(X0)<0. Так как f(X1)=1,4, f(X0)=7, то условие выполняется. Переходим к шагу 9.
9.0. Проверим условия (X1, X0)<0,1 и |f(X1)f(X0)|<0,1. Второе условие не выполняется: |f(X1)f(X0)|=5,6>0,1. Полагаем k=1 и переходим к шагу 3.
3.1. Вычислим f(X1)=(4; 2).
4.1.
Вычислим |f(X1)|
и проверим критерий окончания:
|f(X1)|=
=
>0,1.
Переходим к шагу 5.
5.1. Проверим условие k>k0: k=1<10=k0. Переходим к шагу 6.
6.1. Зададим h1=0,2.
7.1. Вычислим X2=X10,2f(X1)=(0,6; 0,2)0,2(4; 2)Т=(0,2; 0,2).
8.1. Проверим выполнение условия f(X2)f(X1)<0. Так как f(X2)=0,28, f(X1)=1,4, то условие выполняется: f(X2)f(X1)=0,281,4=1,12. Переходим к шагу 9.
9.1. Проверим условия (X2, X1)<0,1 и |f(X2)f(X1)|<0,1. Второе условие не выполняется: |f(X2)f(X1)|=1,12>0,1. Полагаем k=2 и переходим к шагу 3.
3.2. Вычислим f(X2)=(1,6; 1,2).
4.2.
Вычислим |f(X1)|
и проверим критерий окончания:
|f(X1)|=
=2>0,1.
Переходим к шагу 5.
5.2. Проверим условие k>k0: k=2<10=k0. Переходим к шагу 6.
6.2. Зададим h2=0,2.
7.2. Вычислим X3=X20,2f(X2)=(0,2; 0,2)0,2(1,6; 1,2)=(0,12; 0,04).
8.2. Проверим выполнение условия f(X3)f(X2)<0. Так как f(X3)=0,056, f(X2)=0,28, то условие выполняется: f(X3)f(X2)=0,224. Переходим к шагу 9.
9.2. Проверим условия (X3, X2)<0,1 и |f(X3)f(X2)|<0,1. Второе условие не выполняется: |f(X3)f(X2)|=0,224>0,1. Полагаем k=3 и переходим к шагу 3.
3.3. Вычислим f(X3)=(0,8; 0,4).
4.3. Вычислим |f(X3)| и проверим критерий окончания: |f(X3)|=0,8944>0,1. Переходим к шагу 5.
5.3. Проверим условие k>k0: k=3<10=k0. Переходим к шагу 6.
6.3. Зададим h3=0,2.
7.3. Вычислим X4=X30,2f(X3)=(0,12; 0,02)0,2(0,8; 0,4)=(0,04; 0,04).
8.3. Проверим выполнение условия f(X4)f(X3)<0. Так как f(X4)=0,0112, f(X3)=0,056, то условие выполняется: f(X4)f(X3)=0,0448. Переходим к шагу 9.
9.3. Проверим условия (X4, X3)<0,1 и |f(X4)f(X3)|<0,1. Второе условие выполняется: |f(X4)f(X3)|=0,0448<0,1. Для первого имеем
(X4,
X3)=
=
0,1789>0,1,
и условие не выполняется. Полагаем k=4 и переходим к шагу 3.
3.4. Вычислим f(X4)=(0,32; 0,24).
4.4. Вычислим |f(X4)| и проверим критерий окончания: |f(X4)|=0,4>0,1. Переходим к шагу 5.
5.4. Проверим условие k>k0: k=4<10=k0. Переходим к шагу 6.
6.4. Зададим h4=0,2.
7.4. Вычислим X5=X40,2f(X4)=(0,04; 0,04)0,2(0,32; 0,24)=(0,024; 0,008).
8.4. Проверим выполнение условия f(X5)f(X4)<0. Так как f(X5)=0,0022, f(X4)=0,0112, то условие выполняется: f(X5)f(X4)=0,009. Переходим к шагу 9.
9.4. Проверим условия (X5, X4)<0,1 и |f(X5)f(X4)|<0,1. Второе условие выполняется: |f(X5)f(X4)|=0,009<0,1. Для первого имеем
(X5,
X4)=
=
0,08<0,1,
и условия выполняются. Условия должны выполняться для текущего k и k1. Поэтому полагаем k=5 и переходим к шагу 3.
3.5. Вычислим f(X5)=(0,16; 0,08).
4.5. Вычислим |f(X5)| и проверим критерий окончания: |f(X5)|=0,1799>0,1. Переходим к шагу 5.
5.5. Проверим условие k>k0: k=5<10=k0. Переходим к шагу 6.
6.5. Зададим h5=0,2.
7.5. Вычислим
X6=X50,2f(X4)=(0,024; 0,008)0,2(0,16; 0,08)=(0,008; 0,008).
8.5. Проверим выполнение условия f(X6)f(X5)<0. Так как f(X6)=0,0005, f(X5)=0,0022, то условие выполняется: f(X6)f(X5)=0,0017. Переходим к шагу 9.
9.5. Проверим условия (X6, X5)<0,1 и |f(X6)f(X5)|<0,1. Второе условие выполняется: |f(X6)f(X5)|=0,0017<0,1. Для первого имеем
(X6,
X5)=
0,0358<0,1.
Так как оба условия выполнены при текущем значении k=5 k1=4, то расчёт окончен: X*=X5=(0,024; 0,008).
II. Анализ точки X5.
Функция f(x1, x2)=3 +2x1x2+2 является дважды дифференцируемой. Так как матрица Гессе постоянна и является положительно определённой, то точка X5 является точкой локального минимума, а значение f(X5)=0,0022 приближённое значение локального минимума.
б)
В методе Ньютона точки последовательности
{Xk}
вычисляются по формуле Xk+1=Xk+Dk,
где направление спуска Dk
определяется для каждого значения k
по формуле Dk=H
(Xk)f(Xk).
Если H(Xk)>0,
то эта формула гарантирует выполнение
условия f(Xk+1)<f(Xk).
Построение {Xk}
заканчивается в точке Xk,
для которой выполняются условия
завершения, как и в методе градиентного
спуска.
Таким образом, алгоритм метода следующий:
1. Задать X0, 1>0, 2>0, k0 предельное число итераций. Найти f(X0) и H(X0).
2. Положить k=0.
3. Вычислить f(Xk).
4. Проверить условие выполнения критерия окончания |f(Xk)|<1:
а) если неравенство выполнено, то расчёт закончен: X*=Xk;
б) если критерий не выполнен, то перейти к шагу 5.
5. Проверить выполнение неравенства kk0:
а) если неравенство выполнено, то расчёт окончен: X*=Xk;
б) если нет, то перейти к шагу 6.
6. Вычислить матрицу H(Xk).
7. Вычислить матрицу H (Xk).
8. Проверить выполнение условия H (Xk)>0:
а) если H (Xk)>0, то перейти к шагу 9;
б) в противном случае перейти к шагу 10, положив Dk=f(Xk).
9. Определить Dk=H (Xk)f(Xk).
10. Определить Xk+1=Xk+hkDk, положив hk=1, если Dk=H (Xk)f(Xk) или выбрав hk из условия f(Xk+1)<f(Xk), если Dk=f(Xk).
11. Проверить условий (Xk+1, Xk)<2 и |f(Xk+1)f(Xk)|<2:
а) если оба условия выполнены при текущем значении k и k1, то расчёт окончен: X*=Xk;
б) если хотя бы одно условие не выполнено, то положить k=k+1 и перейти к шагу 3.
Сходимость метода Ньютона гарантируется для сильно выпуклых функций. Поэтому также необходимо проверять, является ли найденная точка приближением искомой X*.
Итак, реализуем алгоритм. Мы уже убедились (при решении задания а)), что сходимость итерационного процесса гарантирована. Так что, осталось найти X* и провести его анализ.
I. Найдём Xk.
1. Зададим X0=(1, 1), 1=0,1, 2=0,1, k0=10 и найдём градиент f(X)=(6x1+2x2, 2x1+4x2) и H(X)= (см. решение задания а)).
2. Положим k=0.
3.0. Вычислим f(X0)=(8; 6).
4.0. Проверим критерий окончания: |f(X0)|=10>0,1. Переходим к шагу 5.
5.0. Проверим условие k>k0: k=0<10=k0. Переходим к шагу 6.
6.0. Вычислим матрицу H(X0)= .
7.0.
Вычислим матрицу H
(X0)=
=
.
8.0.
Проверим выполнение условия H
(X0)>0.
Так как 1=0,2,
2=
=0,05>0,
то условие выполнено. Переходим к шагу
9.
9.0. Определим D0:
D0=H
(X0)f(X0)=
=
.
10.0. Определим X1=X0+h0D0, полагая h0=1 (так как D0=H (X0)f(X0)): X1=(1; 1)+(1; 1)=(0; 0).
11.0. Проверим условия (X1, X0)<0,1 и |f(X1)f(X0)|<0,1. Имеем
(X1,
X0)=
=
>0,1,
то есть первое условие не выполнено. Полагаем k=1 и переходим к шагу 3.
3.1. Вычислим f(X1)=(0; 0).
4.1. Проверим критерий окончания |f(X1)|<0,1: |f(X1)|=0. Расчёт окончен: X*=X1=(0; 0).
II. Анализ точки X1.
Функция f(x1, x2)=3 +2x1x2+2 является строго выпуклой, так как матрица Гессе постоянна и является положительно определённой. Поэтому точка X1 является точкой локального минимума, а значение f(X1)=0 приближённое значение локального минимума (на самом деле это точное значение локального минимума).
Ответ: а) точкой локального минимума является точка X*=(0,024; 0,008), f(X*)=0,0022 локальный минимум.
б) точкой локального минимума является точка X*=(0; 0), f(X*)=0 локальный минимум.
Задание НП-8. Решить задачу условной оптимизации
f(X)=
min
3x12x25=0
а) методом последовательной безусловной оптимизации;
б) методом проекции градиента.
Решение. а) При этом методе исходная задача
f(X) min
заменяется на задачу
F(X, rs)=f(X)+P(X, rs) min,
где
P(X,
rs)=
,
=max{0,
}=
rs так называемый параметр штрафа. Функция P(X, rs) называется штрафной функцией. К полученной задаче применяются численные методы безусловной оптимизации (нулевого, первого или второго порядков). При этом начальная точка поиска задаётся обычно вне множества допустимых решений X. На каждой s-й итерации ищется точка X*(rs) минимума вспомогательной функции F(X, rs) при заданном параметре rs с помощью одного из методов безусловной минимизации. Полученная точка X*(rs) используется в качестве начальной на следующей итерации, выполняемой при возрастающем значении параметра штрафа. При неограниченном возрастании rs последовательность точек X*(rs) стремится к точке условного минимума X*.
Более подробно:
1. Задать: начальную точку X0 внутри области X; начальное значение параметра rs0; число C>1 для уменьшения параметра штрафа; малое число 0 для остановки алгоритма. Положить s=0.
2. Составить вспомогательную функцию
F(X, rs)=f(X)+ .
3. Найти точку X*(rs) безусловного экстремума функции F(X, rs) по X с помощью какого-либо метода (нулевого, первого или второго порядка):
F(X*(rs),
rs)=
F(X,
rs).
При этом задать все требуемые выбранным методом параметры. В качестве начальной точки взять Xs. Вычислить P(X*(rs), rs).
4. Проверить условие окончания:
а) если P(X*(rs), rs), то процесс поиска закончить:
X*=X*(rs), f(X*)=f(X*(rs));
б) если P(X*(rs), rs)<, то положить: rs+1=Crs, Xs+1=X*(rs), s=s+1 и перейти к шагу 2.
Обычно выбирается r0{0,01; 0,1; 1}, а C[4, 10].
Итак, реализуем описанный алгоритм.
Нам потребуется вспомогательная функция F(X, rs) при различных значениях параметра rs и её градиент. Поэтому предварительно выпишем эти элементы задачи в общем виде:
F(X,
rs)=
+
(3x12x25)2,
=4x1+3rs(3x12x25),
=8x22rs(3x12x25),
F(X, rs)=(4x1+3rs(3x12x25), 8x22rs(3x12x25)).
Далее действуем пошагово согласно вышеописанной схеме.
Шаг 1. Зададим: начальную точку X0=(1, 1) внутри области X; начальное значение параметра rs=0,1; число C=4 для уменьшения параметра штрафа; малое число =0,1 для остановки алгоритма. Положить s=0.
Шаг 2. Составим вспомогательную функцию
F(X; 0,1)= +0,05(3x12x25)2.
Шаг 3. Найдём точку X*(0,1) безусловного минимума функции F(X, 0,1) по X с помощью метода градиетного спуска:
F(X*(0,1), 0,1)= +0,05(3x12x25)2 min (1)
1. Зададим X0=(1, 1), 1=0,1, 2=0,1, k0=10, найдём градиент
F(X; 0,1)=(4x1+0,3(3x12x25), 8x20,2(3x12x25)).
2. Положим k=0.
3.0. Вычислим F(X0; 0,1)=(4; 8).
4.0.
Вычислим |F(X0;
0,1)| и проверим критерий окончания:
|F(X0;
0,1)|=
8,9443>0,1.
Переходим к шагу 5.
5.0. Проверим условие k>k0: k=0<10=k0. Переходим к шагу 6.
6.0. Зададим h0=0,1.
7.0. Вычислим X1=X00,1F(X1; 0,1)=(1; 1)0,1(4; 8)=(0,6; 0,2).
8.0. Проверим выполнение условия F(X1; 0,1)F(X0; 0,1)<0. Так как F(X1; 0,1)=1,272, F(X0; 0,1)=7, то условие выполняется. Переходим к шагу 9.
9.0. Проверим условия (X1, X0)<0,1 и |F(X1; 0,1)F(X0; 0,1)|<0,1. Второе условие не выполняется: |F(X1; 0,1)F(X0; 0,1)|=4,728>0,1. Полагаем k=1 и переходим к шагу 3.
3.1. Вычислим F(X1; 0,1)=(1,56; 1,04).
4.1.
Вычислим |F(X1;
0,1)| и проверим критерий окончания:
|F(X1;
0,1)|=
1,8749>0,1.
Переходим к шагу 5.
5.1. Проверим условие k>k0: k=1<10=k0. Переходим к шагу 6.
6.1. Зададим h1=0,1.
7.1. Вычислим X2:
X2=X10,1F(X1; 0,1)=(0,6; 0,2)0,1(1,56; 1,04)=(0,444; 0,096).
8.1. Проверим выполнение условия F(X2; 0,1)F(X1; 0,1)<0. Так как F(X2; 0,1)=1,0353, F(X1; 0,1)=1,272, то условие выполняется: F(X2; 0,1)F(X1; 0,1)=1,03531,272=0,2367. Переходим к шагу 9.
9.1. Проверим условия (X2, X1)<0,1 и |F(X2; 0,1)F(X1; 0,1)|<0,1. Второе условие не выполняется: |F(X2; 0,1)F(X1; 0,1)|=0,2367>0,1. Полагаем k=2 и переходим к шагу 3.
3.2. Вычислим F(X2; 0,1)=(0,7332; 0,0728).
4.2.
Вычислим |F(X2;
0,1)| и проверим критерий окончания:
|F(X2;
0,1)|=
=0,7368>0,1.
Переходим к шагу 5.
5.2. Проверим условие k>k0: k=2<10=k0. Переходим к шагу 6.
6.2. Зададим h2=0,1.
7.2. Вычислим X3:
X3=X20,1F(X2; 0,1)=(0,444; 0,096)0,1(0,7332; 0,0728)=(0,3707;0,0887).
8.2. Проверим выполнение условия F(X3; 0,1)F(X2; 0,1)<0. Так как F(X3; 0,1)=0,9947, F(X2; 0,1)=1,0353, то условие выполняется: F(X3; 0,1)F(X2; 0,1)=0,0406. Переходим к шагу 9.
9.2. Проверим условия (X3, X2)<0,1 и |F(X3; 0,1)F(X2; 0,1)|<0,1. Оба условия выполняются:
(X3,
X2)=
=0,0737<0,1,
|F(X3; 0,1)F(X2; 0,1)|=0,0406<0,1.
Это значит, что X*(0,1)=(0,3707; 0,0887) решение задачи (1).
Вычислим P(X*(0,1), 0,1)=0,05(30,37072(0,0887)5)2=0,6941.
Шаг 4. Проверить условие окончания:
а) если P(X*(rs), rs), то процесс поиска закончить:
X*=X*(rs), f(X*)=f(X*(rs));
б) если P(X*(rs), rs)>, то положить: rs+1=Crs, Xs+1=X*(rs), s=s+1 и перейти к шагу 2.
Имеем P(X*(0,1), 0,1)=0,6941>0,1. Поэтому полагаем r1=Cr0=40,1=0,4, X0=X*(0,1)=(0,3707; 0,0887), и перейти к шагу 2, то есть решаем задачу
F(X*(0,4), 0,4)= +0,2(3x12x25)2 min (2)
Ниже приводим только результаты пунктов алгоритма без комментариев:
1. X0=(0,3707; 0,0887), 1=0,1, 2=0,1, k0=10,
F(X; 0,4)=(4x1+1,2(3x12x25), 8x20,8(3x12x25)).
2. k=0.
3.0. F(X0; 0,4)=(2,9698; 2,2588).
4.0. |F(X0; 0,4)|3,7312>0,1.
5.0. k>k0? k=0<10=k0. 6.
6.0. h0=0,1.
7.0. X1=(0,6677; 0,3146).
8.0. F(X1; 0,1)F(X0; 0,1)=0,6511<0. 9.
9.0. |F(X1; 0,1)F(X0; 0,1)|= 0,6511>0,1. k=1 и 3.
3.1. F(X1; 0,1)=(0,1704; 0,6226).
4.1. |F(X1; 0,1)|0,6456>0,1. 5.
5.1. k>k0? k=1<10=k0. 6.
6.1. h1=0,1.
7.1. X2=(0,6847; 0,2523).
8.1. F(X2; 0,1)F(X1; 0,1)=0,0245. 9.
9.1. (X2, X1)=0,0646<0,1 и |F(X2; 0,1)F(X1; 0,1)|=0,0245<0,1.
Значит, X*(0,4)=(0,6847; 0,2523) решение задачи (2).
Вычислим P(X*(0,4), 0,4)=1,1212.
Шаг 4. Проверим условие окончания: P(X*(0,4), 0,4)=1,1212>0,1. Поэтому полагаем r2=Cr1=40,4=1,6, X0=X*(0,4)=(0,6847; 0,2523), и переходим к шагу 2, то есть решаем задачу
F(X*(1,6), 1,6)= +0,8(3x12x25)2 min (3)
Ниже в таблице приведены результаты вычислений. В таблице применяются следующие сокращённые обозначения: Fk=F(Xk; 1,6), Fk=F(Xk; 1,6), Fk=F(Xk+1; 1,6)F(Xk; 1,6), k+1=(Xk+1, Xk).
k |
Xk |
Fk |
|Fk| |
Xk+1 |
Fk+1 |
Fk |
k+1 |
Pk+1 |
0 |
(0,6847; 0,2523) |
(8,9794; 5,9738) |
10,6864 |
(1,5826; 0,8317) |
9,3696 |
9,3696>0 |
h0=0,05 |
|
|
(1,1337; 0,542) |
3,9576 |
2,0026 |
0,5343 |
|
|||
1 |
(1,1337; 0,542) |
(2,0633; 2,6883) |
3,3888 |
(1,0305; 0,4076) |
3,7446 |
0,2131 |
0,1694 |
1,1212 |
2 |
(1,0305; 0,4076) |
(1,1258; 0,2378) |
1,1507 |
(1,087; 0,4195) |
3,7151 |
0,0296 |
0,0575 |
0,9562 |
Таким образом, X*(1,6)=(1,087; 0,4195) решение задачи (3). При этом P(X*(1,6), 1,6)=0,9562>0,1. Полагаем r3=Cr2=41,6=6,4, X0=X*(1,6)= =(1,087; 0,4195), и переходим к шагу 2 решаем задачу
F(X*(6,4), 6,4)= +3,2(3x12x25)2 min.
Решение получается за одну итерацию: X*(6,4)=(1,0856; 0,3957). При этом P(X*(6,4), 6,4)=0,648>0,1.
Шаг 4. Так как P(X*(6,4), 6,4)=0,648>0,1, то полагаем r4=Cr3=46,4=25,4, X0=X*(6,4)=(1,0856; 0,3957), и переходим к шагу 2 решаем задачу
F(X*(6,4), 6,4)= +12,8(3x12x25)2 min
k |
Xk |
Fk |
|Fk| |
Xk+1 |
Fk+1 |
Fk |
k+1 |
Pk+1 |
|||||
0 |
(1,0856; 0,3957) |
(68,7558; 45,5666) |
82,4844 |
(4,5234; 2,674) |
2549,104 |
2534, 525>0 |
h0=0,025 |
|
|||||
|
(2,8045; 1,5349) |
536,1644 |
548, 5852>0 |
h0=0,01 |
|
||||||||
(1,7732; 0,8514) |
61,5308 |
46,9516>0 |
h0=0,005 |
|
|||||||||
(1,7294; 0,6235) |
9,3079 |
5,2713 |
0,4124 |
|
|||||||||
1 |
(1,4294; 0,6235) |
(42,821; 32,3902) |
56,9327 |
(1,1953; 0,4616) |
6,7956 |
2,5122 |
0,2847 |
|
|||||
2 |
(1,1953; 0,4616) |
(32,9199; 21,4413) |
39,2868 |
(1,3599; 0,5688) |
5,5973 |
1,1971 |
0,1964 |
|
|||||
3 |
(1,3599; 0,5688) |
(22,1282; 15,6762) |
27,1183 |
(1,2493; 0,4904) |
5,0261 |
0,5711 |
0,1356 |
|
|||||
4 |
(1,2493; 0,4904) |
(15,8386; 9,9674) |
18,7139 |
(1,3285; 0,5402) |
4,7529 |
0,2727 |
0,0936 |
|
|||||
5 |
(1,3285; 0,5402) |
(10,3751; 7,6957) |
12,9177 |
(1,2766; 0,5017) |
4,6221 |
0,1306 |
0,0646 |
|
|||||
6 |
(1,2799; 0,5017) |
(7,7038; 4,5266) |
8,9353 |
(1,3151; 0,5243) |
4,5592 |
0,0631 |
0,0447 |
0,3561 |
|||||
7 |
(1,3151; 0,5243) |
(4,7919; 3,8821) |
6,1671 |
(1,2911; 0,5049) |
4,5284 |
0,0307 |
0,0308 |
0,0005 |
|||||
На последних двух шагах получаем (Xk+1, Xk)<0,1 и |f(Xk+1)f(Xk)|<0,1, а в последнем шаге P(X*(25,4), 25,4)=0,0005<0,1. Процесс поиска закончен.
б) Алгоритм метода проекции градиента следующий:
1. Задать X0, 0, k0 число итераций.
2. Найти
A(X)=
(напоминаем, что решается задача
),
f(X),
X=[E
(A
)
A]f(X),
2X=AT(AAT)
T(X)
где
T(X)=(1(Xk),
…, m(Xk))T.
3. Положить k=0.
4. Проверить выполнение условия kk0:
а)
если неравенство выполнено, то расчёт
окончен. Вычислить k=(Ak
)
Akf(Xk),
проверить необходимое условие минимума,
оценить результаты;
б) если неравенство не выполнено, то перейти к шагу 5.
5. Вычислить матрицу Ak=A(Xk).
6. Вычислить 2Xk.
7. Вычислить |2Xk|.
8. Вычислить Xk.
9. Вычислить |Xk|.
10. Проверить выполнение условий |Xk| и |2Xk|:
а) если условия выполняются, то расчёт окончен. Вычислить k и проверить достаточные условия минимума;
б) если |Xk|>, |2Xk|, то положить 2Xk=0 и перейти к шагу 11;
в) если |Xk| и |2Xk|>, то положить Xk=0 и перейти к шагу 13;
г) если |Xk|>, |2Xk|>, то перейти к шагу 11.
11.
Получить выражение для точки Xk+
Xk.
12.
Определить
из условия f(Xk+hkXk)
.
13. Вычислить Xk+1=Xk+ Xk+2Xk. Положить k=k+1 и перейти к шагу 4.
Если ограничения в задаче линейны, то при k1 на шаге 4 переходим к шагу 8. При этом на шаге 10 полагаем |2Xk|=0.
Итак, реализуем алгоритм:
1. Задаём X0=(1, 1) =0,1, k0=10 число итераций.
2.
Найдём
A(X)=
=(3;
2),
f(X)=(4x1,
8x2)Т,
X=[E
(A
)
A]f(X)=
=
=
=
=
=
=
=
,
то
есть
X
,
T(X)=1(Xk)=3x1+2x2+5,
2X=AT(AAT)
T(X)=
(3x1+2x2+5)=
=
(3x1+2x2+5)=
=
,
то
есть 2X
.
3. Полагаем k=0.
4.0. Проверим выполнение условия kk0: k=0<10=k0 неравенство не выполнено. Поэтому идём к пункту 5.
5.0. Вычисляем матрицу A0=A(X0)=(3; 2).
6.0.
Вычисляем 2X0=
=
.
7.0.
Вычисляем |2X0|=
=0.
8.0.
Вычисляем X0=
.
9.0.
Вычисляем |X0|=
0,832.
10.0. Проверяем выполнение условий |X0|0,1 и |2X0|0,1. Имеем |X0|>0,1 и |2X0|0,1. Поэтому полагаем 2X0=0 и переходим к шагу 11.
11.0. Получим выражение для точки X0+h0X0:
X0+h0X0=(1; 1)+h0(2,462; 3,692)=(1+2,462h0; 1+3,692h0).
12.0.
Определяем h0
из условия f(X0+h0X0)
.
Имеем
f(X0+h0X0)=2(1+2,462h0)2+4(1+3,692h0)2=
=2(1+4,924h0+6,061
)+4(17,384h0+13,631
)=
=66,646 19,688h0+6.
Так
как f(X0+h0X0)
квадратный трёхчлен относительно h0
с положительным коэффициентом при
,
то минимум f(X0+h0X0)
достигается при h0,
удовлетворяющем уравнению
(X0+h0X0)=0.
Имеем
(X0+h0X0)=133,292h019,688=0 h00,15.
13.0. Вычисляем X1:
X1=X0+h0X0+2X0=X0+h0X0=(1+2,4620,15; 1+3,6920,15)=(1,3693; 0,4462).
Положим k=1 и перейдём к шагу 4.
4.1. Проверим выполнение условия kk0: k=1<10=k0 неравенство не выполнено. Поэтому идём к пункту 5.
5.1. Вычисляем матрицу A1=A(X1)=(3; 2).
6.1.
Вычисляем 2X1=
=
.
7.1.
Вычисляем |2X1|=
0.
8.1.
Вычисляем X1=
.
9.1.
Вычисляем |X1|=
0,0677.
10.1. Проверяем выполнение условий |X1|0,1 и |2X1|0,1. Имеем |X1|0,1 и |2X1|0,1. Поэтому расчёт окончен. Вычисляем 1 для проверки необходимых и достаточных условий экстремума в найденной точке X1=(1,3693; 0,4462):
1=(A1
)
A1f(X1)=
=1,8135.
Выпишем необходимые условия экстремума с учётом функции Лагранжа: L(X, )= +1(3x12x25):
=4x1+31, =8x221,
(4)
Будем считать, что необходимые условия выполнены, если уравнения системы (4) выполняются с точностью до 0,1. Подставляем X1=(1,3693; 0,4462) и 1=1,8135 в систему (4):
Следовательно, необходимые условия экстремума в точке X1 выполнены. Проверим достаточные условия экстремума. Имеем
=4, =8, = =0, d2L=4d +8d >0,
то есть достаточное условие минимума выполняется. Таким образом,
Ответ: а) точкой условного локального минимума является точка X*=(1,2911; 0,5049), f(X*)=4,5284 условный локальный минимум.
б) точкой условного локального минимума является точка X*(1,3693; 0,4462), f(X*)4,5447 условный локальный минимум.