Файл: Методы оптимизации лабораторный практикум.pdf

---

---

---

№4 ЗАДАЧИ НА БЕЗУСЛОВНЫЙ ЭКСТРЕМУМ Цель работы овладеть навыками решения задач безусловной оптимизации в пакете MAPLE. Требуется
− изучить теоретический материал
− решить задачу в математическом пакете Maple. Необходимые теоретические сведения Дана функция
 
f X
, определенная и непрерывная на множестве. Требуется исследовать функцию
 
f на экстремум, то есть определить точки
*
n
X

ее локальных максимумов и максимумов на
n
:
 
 
*
min
n
X
f X
f X


или
 
 
*
max
n
X
f X
f X


(4.1) Точки
*
X
находятся с помощью необходимых условий локального экстремума первого и второго порядков (порядок условий определяется порядком используемых производных, а также достаточных условий безусловного локального экстремума. Утверждение 1 (необходимые условия экстремума первого порядка. Пусть
*
n
X

есть точка локального минимума (максимума) функции
 
f X на множестве
n
и
 
f дифференцируема в точке
*
X
. Тогда градиент функции
 
f в точке
*
X
равен нулю, то есть
 
*
0
f X


(4.2) или
 
*
0,
1, .
i
f
X
i
n
x




(4.3) Точки
*
X
, удовлетворяющие условию (4.2) или (4.3), называются стационарными. Утверждение 2 (необходимые условия экстремума второго порядка. Пусть точка
*
X
есть точка локального минимума (максимума) функции
 
f X на множестве
n
и функция
 
f X дважды дифференцируема в этой точке. Тогда матрица Гессе
 
*
H X
функции

 
f X
, вычисленная в точке
*
X
, является положительно полуопреде- ленной (отрицательно полуопределенной), то есть
 
*
0
H X

,
(4.4)
 


*
0
H X

(4.5) Утверждение 3 (достаточные условия экстремума. Пусть функция
 
f X в точке
*
n
X

дважды дифференцируема, ее градиент в точке
*
X
равен нулю, а матрица Гессе является положительно определенной (отрицательно определенной) в точке
*
,
X
то есть
 
*
0
f X


и
 
*
0
H X

(4.6)
 
*
0
f X


и
 


*
0
H Тогда точка
*
X
есть точка локального минимума (максимума) функции
 
f на множестве Рассмотрим определитель матрицы Гессе, вычисленной в стационарной точке
 
11 12 1
21 22 2
*
1 2
det
n
n
n
n
nn
h h
h
h h
h
H X
h h
h

1. Определители
1 11
h
 
,
11 12 2
21 22
h h
h h
 
, …,
11 12 1
21 22 2
1 2
n
n
n
n
n
nn
h h
h
h h
h
h h
h
 называются угловыми минорами.
2. Определители ого порядка (m≤n), получающиеся из определителя матрицы
 
*
H вычеркиванием каких-либо (n−m) строки) столбцов с одними и теми же номерами, называются главными минорами. Для проверки выполнения достаточных условий экстремума и необходимых условий второго порядка используются два способа. Первый способ с помощью угловых и главных миноров)
Критерий проверки достаточных условий экстремума критерий Сильвестра).

1. Для того чтобы матрица Гессе
 
*
H X
была положительно определенной и точка
*
X
являлась точкой локального минимума, необходимо и достаточно, чтобы знаки угловых миноров были строго положительны
1 0
 
,
2 0
 
, …,
0
n
 
(4.8)
2. Для того чтобы матрица Гессе
 
*
H X
была отрицательно определенной и точка
*
X
являлась точкой локального максимума, необходимо и достаточно, чтобы знаки угловых миноров чередовались, начиная с отрицательного
1 0
 
,
2 0
 
,
3 0
 
,…,
 
1 0
n
n

 
(4.9) Критерий проверки необходимых условий экстремума второго порядка критерий Сильвестра).
1. Для того чтобы матрица Гессе
 
*
H X
была положительно полуопределенной и точка
*
X
может быть являлась точкой локального минимума, необходимо и достаточно, чтобы все главные миноры матрицы Гессе были неотрицательны.
2. Для того чтобы матрица Гессе
 
*
H X
была отрицательно по- луопределенной и точка
*
X
может быть являлась точкой локального максимума, необходимо и достаточно, чтобы все главные миноры четного порядка были неотрицательны, а все главные миноры нечетного порядка – неположительны. Второй способ (с помощью собственных значений матрицы
Гессе) Собственные значения
,
1,
i
i
n


матрицы
 
*
H X
размера
n n

находятся как корни характеристического уравнения (алгебраического уравнения ой степени
 
11 12 1
21 22 2
*
1 2
0.
n
n
n
n
nn
h
h
h
h
h
h
H X
E
h
h
h










(4.10) Замечание 1. Собственные значения вещественной симметрической матрицы
 
*
H X
вещественны.

Алгоритм решения задачи
1. Записать необходимые условия экстремума первого порядка в форме (4.3) и найти стационарные точки
*
X
в результате решения системы, в общем случае, n нелинейных алгебраических уравнений с n неизвестными.
2. В найденных стационарных точках
*
X
проверить выполнение достаточных, а если они не выполняются, то необходимых условий второго порядка.
3. Вычислить значения
 
*
f X
в точках экстремума. Описанный алгоритм отображен на Рис. 4.1, где показана последовательность действий в случае выполнения и невыполнения соответствующих условий экстремума при применении первого способа. Рис. 4.1 Замечание 2: Если требуется определить глобальные экстремумы, то они находятся в результате сравнения значений функции в точках локальных минимумов и максимумов с учетом ограниченности функции на Критерий безусловного экстремума для функции одной переменной. Если функция
 
f и ее производные непрерывны, то точка
*
X
является точкой экстремума тогда и только тогда, когда
 
 


 
 
 
1
*
*
*
*
0,
0
m
m
f
X
f
X
f
X
f
X




 



и m – четно. При этом если
 
 
*
0
m
f
X

, тов точке
*
X
– локальный минимума если
 
 
*
0
m
f
X

, тов точке
*
X
– локальный максимум. Если число m нечетное, тов точке
*
X
нет экстремума. Пример Исследовать на экстремум функцию
4 4
2 2
2
f
x
y
x
x y
y



   Решение задачи в пакете Maple
1. Зададим функцию с помощью функционального оператора
>
f:=(x, y)->x^4+y^4-x^2-2*x*y-y^2;
2. Прежде всего, нарисуем (трехмерный) график нашей функции. Для этого необходимо подключить пакет расширения plots с помощью команды with:
>
with(plots): plot3d(f(x,y), x=-2.5..2.5, y=-2.5..2.5, axes = В этой команде указана опция axes, которая задает вид координатных осей. На самом деле, в данной команде, можно указывать большое количество различных опций, которые задают вид графиков цвет, тип и толщину линий, угол поворота осей и др. Их подробное описание можно найти в Help. Итак, мы получаем график, изображенный на риса. Теперь построим контурный график, только в команде plot3d укажем опцию style и присвоим значение patchcontour:
>
plot3d(f(x,y), x=-2.5..2.5, y=-2.5..2.5, style=patchcontour, ax-
es=frame, Опция contours задает количество линий уровня функций на поверхности. Получаем график, изображенный на рис. баб) Рис Трехмерный график функции
 
,
f x y
:=
f

(
)
,
x y
  

x
4
y
4
x
2 2 x y
y
2

На контурном графике чуть лучше виден характер функции, но все равно для определения экстремумов удобнее использовать двумерные линии уровня функции. Их можно получить таким образом Рис 4.3):
>
contourplot(f(x,y), x=-2.5..2.5, y=-2.5.. 2.5, axes=frame,
filled=true, contours=50, coloring=[yellow, В этой команде опция filled равна true. Это означает, что Maple автоматически закрашивает области между линиями уровняв разные цвета в зависимости от значения функции f на этих линиях уровня. Это делает график более выразительными позволяет визуально оценить характер изменения значений функции. Если положить опцию
filled равной false (или вообще не указывать, то получим не закрашенный график. Напротив, если положить filled=true, то можно использовать опцию coloring, которая позволяет управлять цветами закраски. Например, если указана coloring=[yellow, green], то линии уровня, отвечающие наименьшему значению f, будет желтыми, али- нии уровня, отвечающие наибольшему значению f ‒ зелеными, а все промежуточные линии уровня Maple закрасит в промежуточные цвета. Рис. 4.3: Двумерный график линий уровня функции
 
,
f x Глядя на эти рисунки, можно высказать предположение, что наша функция имеет два экстремума, причем из характера графика, полученного выше, следует, что это точки минимума. Далее продемонстрируем, как можно решить задачу нахождения экстремумов нашей функции аналитически.
3. Применим необходимое условие первого порядка.Для нахождения критических точек функции зададим систему уравнений
 
 
,
0,
,
0 :
f
f
x y
x y
x
y







>
SysEqn:={diff(f(x,y), x)=0, diff(f(x,y), y)=0};
4. Решаем данную систему с помощью команды solve:
>
rez:=solve(SysEqn,{x, Видим, что Maple выдает результат, содержащий функцию
RootOf. Это означает, что аналитические решения системы нельзя выразить в радикалах. В таком случае можно попытаться получить численные, приближенные значения решений с помощью команды evalf. Эта команда служит для принудительного приближенного вычисления результата evalf(rez). Другой способ борьбы с функцией RootOf заключается в том, что в ответ исходной системы искусственно внести неточность, чтобы Maple не пыталась найти точное решение. Это можно сделать, например, так вместо какого-нибудь целого числа в записи уравнений системы, например, числа 0, написать число 0.0.
Maple воспринимает это число как нецелое и автоматически ищет приближенное решение такой системы. Таким образом, нас интересуют следующие координаты (x,y): rez[1]=rez[2]=rez[3]=(0,0); rez[4]=(1,1); rez[5]=(-1,-1);
5. Далее применим условия экстремума второго порядка. Загружаем пакет линейной алгебры linalg и вычисляем Гессеан с помощью команды hessian:
>
with(linalg): MatrixGesse:=hessian(f(x,y), [x,y]);
6. Подставляем в Гессиан координаты стационарных точек с помощью оператора subs. Подставляем точку (0;0):
>
MatrixGesse:=subs(rez[1], hessian(f(x,y), Если rez содержал бы один результат, то мы бы написали
>
MatrixGesse:=subs(rez, hessian(f(x,y), У матрицы Гессе вычисляем главные диагональные миноры.
>
M11:=MatrixGesse[1,1]; M21:=det(MatrixGesse);
:=
SysEqn
{
}
,



4 x
3 2 x
2 y
0



4 y
3 2 x
2 y
0
:=
MatrixGesse







12 x
2 2
-2
-2

12 y
2 2
:=
MatrixGesse






-2.
-2
-2
-2.

Точка (0,0) не является точкой экстремума функции. Также, выяснить положительную или отрицательную определенность матрицы можно при помощи команды definite(A,param), где
param может принимать значения 'positive_def' – положительно определена неотрицательно определенная (A ≥ 0)
, 'negative_def' – отрицательно определенная (A<0), 'negative_semidef' − неположительно определенная (A ≤ 0) . Результатом действия будет константа true – подтверждение, false – отрицание сделанного предположения, Подставляем точку (1;1). У матрицы Гессе вычисляем главные диагональные миноры.
>
MatrixGesse:=subs(rez[4],
hessian(f(x,y),[x,y]));
M12:=MatrixGesse[1,1];
M22:=det(MatrixGesse);
defi-
nite(MatrixGesse,'positive_def');
Т.к. все главные диагональные миноры матрицы Гессе положительны, то точка (1,1) является точка минимума функции. Вычисляем значение функции в данной точке.
>
F:=subs(rez[4],f(x, Подставляем точку (-1;-1).
>
MatrixGesse:=subs(rez[5], hessian(f(x, y), [x,y]));
M13:=MatrixGesse[1,1]; M23:=det(MatrixGesse); defi-
nite(MatrixGesse, 'positive_def');
Т.к. все главные диагональные миноры матрицы Гессе положительны, то точка (-1,-1) точка минимума функции. Вычисляем значение функции в данной точке.
false
false
:=
MatrixGesse






10.
-2
-2 10.
:=
M12
10.
:=
M22
96.
true
:=
F
-2.
:=
MatrixGesse






10.
-2
-2 10.
:=
M13
10.
:=
M23
96.
true

>
F:=subs(rez[5], f(x, Ответ Точки минимума (1,1) (-1,-1), min min
(1,1)
( 1, 1)
2
F
F

  Исходные данные для лабораторной работы Найти точки безусловного экстремума функции
2 2
1 1
2 2
1 2
ax
bx x
cx
dx
ex
extr

 



№ варианта
a
b
c
d
e
1.
3 3
1
-7
-7
2.
4 1
-3
-7 7
3.
-4 8
9
-7 3
4.
-6
-1 8
-5
-9
5.
2
-1
-1 8
8
6.
-7
-8 5
-7
-5
7.
-4 1
9 6
-5
8.
1 2
-8
-3 8
9.
1
-7
-1
-4 8
10.
-7 4
-6
-1
-5
:=
F
-2.

ЛАБОРАТОРНАЯ РАБОТА №5 ЗАДАЧИ НА УСЛОВНЫЙ ЭКСТРЕМУМ Цель работы овладеть навыками решения задач условной оптимизации в пакете MAPLE. Требуется
− изучить теоретический материал
− решить задачу в математическом пакете Maple. Необходимые теоретические сведения Пусть целевая функция
 
f X дважды, а функции ограничений
 
j
g
X ,
1,
j
k

, определяющие множество допустимых точек M , один раз непрерывно дифференцируемы на некотором множестве, содержащем. Требуется исследовать функцию
 
f на экстремум, то есть определить точки
*
X
ее локальных минимумов и максимумов на множестве M :
 
 
*
min
X M
f X
f X


или
 
 
*
max
X M
f X
f X


,
(5.1) где
 


0,
1, ,
j
M
X g
X
j
k Задача (5.1) называется задачей на условный экстремум с ограничениями типа равенств. Функция


 
 
0 0
1
,
,
m
j
j
j
L X
f X
g
X
 называется обобщенной функцией Лагранжа, числа
0

,
1

,...,
m

– множителями Лагранжа,


0 1
,
,
T
m

 Классической функцией Лагранжа


,
L X

называется функция


,1,
L X

, то есть


 
 
1
,
m
j
j
j
L X
f Градиентом функции Лагранжа по X называется вектор- столбец, составленный из ее частных производных первого порядка по
,
1,
i
x i
n

:









0 1
0 0
2 0
,
,
,
,
,
,
,
,
x
n
L X
x
L X
L X
x
L X
x
 
 
 
 Вторым дифференциалом обобщенной (классической) функции Лагранжа


0
,
,
L X
 




,
L X

по X называется функция Таким образом, второй дифференциал функции Лагранжа является квадратичной формой с матрицей Гессе по X


















2 2
2 0
0 0
1 1
1 2
1 2
2 2
0 0
0 0
2 1
2 2
2 2
2 0
0 1
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
n
xx
n
n
n
L X
L X
L X
x x
x x
x x
L X
L X
L X
L
X
x x
x x
x x
L X
L X
x x
x x
 
 
 
 
 
 
 
 
 



 
 
 





 
 
 


 
 


2 0
2
,
,
n
n
L X
x x
 























 Первым дифференциалом ограничения
 
j
g
X называется функция
 
 
1
n
j
j
i
i
i
g
X
dg
X
dx
x





, Ограничение
 
0
j
g
X

называется активным в точке
*
X
, если. Если
 
*
0
j
g
X

, то ограничение называется пассивным. Градиенты ограничений
   
 
1 2
,
,
,
m
g X
g
X
g
X называются линейно независимыми в точке
*
X
, если равенство
 
 
 
*
*
*
1 1
2 2
0
m
m
g
X
g
X
g
X




 




выполняется только при

1 2
0
m
 





. Если существуют числа
1 2
,
,
,
m
 

одновременно неравные нулю, для которых равенство выполняется, то градиенты линейно зависимы. Отметим, что в случае линейной зависимости векторов один из них есть линейная комбинация остальных. Один вектор тоже образует систему векторов, которая является линейно независимой при
 
*
1 0
g
X


и линейно зависимой при
 
*
1 Система векторов, содержащая нулевой вектор, всегда линейно зависима. Если
 
 
 


*
*
*
1 2
,
,
,
m
rankA
rank
g
X
g
X
g
X
m





, то система векторов линейно независима. Если же
rankA m

, то система векторов линейно зависима. Точки
*
X
находятся с помощью необходимых и достаточных условий условного минимума и максимума первого и второго порядка при ограничениях типа равенств. Утверждение 1 (необходимые условия экстремума первого порядка. Пусть
*
X
есть точка локального экстремума в задаче (5.1). Тогда найдутся числа
*
*
*
0 1
,
,
,
k
 

, неравные одновременно нулю, и такие, что выполняются следующие условия
– условие стационарности функции Лагранжа по X

1   2   3   4   5   6   7   8

---

:


*
*
*
0
,
,
0,
1, ;
i
L X
i
n
x
 




(5.2)
– условие допустимости решения
 
*
0
j
g
X

,
1,
j
k

(5.3) Если при этом градиенты
 
 
 
*
*
*
1 2
,
,
,
m
g
X
g
X
g
X



в точке
*
X
линейно независимы (выполняется условие регулярности, то
*
0 Замечания 1: Система (5.2)–(5.3) содержит n + k уравнений с n + k + 1 неизвестными. Точки


*
*
*
*
1 2
,
,...,
T
n
X
x x
x

, удовлетворяющие системе (5.2)-(5.3) при некоторых
*
*
*
0 1
,
,
,
k
 

, называются условно стационарными. Проверка условия регулярности затруднена, так как точка заранее неизвестна. Поэтому, как правило, рассматриваются два случая и
*
0 0


. Если
*
0 0


в (5.2) полагают
*
0 1


. Это эквивалентно делению соотношения (5.2) на
*
0

и заменена. При этом, функция Лагранжа становится классической. В этом случаев системе (5.2)-(5.3) число неизвестных становится равным числу уравнений, и эта система имеет вид


*
*
,
0,
1, ;
i
L X
i
n
x





(5.4)
 
*
0
j
g
X

,
1,
j
k

(5.5) Точка экстремума, удовлетворяющая системе (5.2)-(5.3) при
*
0 0


называется регулярной, а при
*
0 0


– нерегулярной. Случай
*
0 0


отражает вырожденность ограничений. При этом в функции Лагранжа исчезает член, содержащий целевую функцию, а в необходимых условиях экстремума не используется информация, представляемая градиентом целевой функции. Утверждение 2 (необходимые условия условного экстремума второго порядка. Пусть
*
X
– регулярная точка минимума (максимума) в задаче (5.1) и имеется решение системы (5.4)–(5.5). Тогда второй дифференциал классической функции Лагранжа, вычисленный в точке


*
*
,
X

, неотрицателен (неположителен)






2
*
*
2
*
*
,
0,
,
0
d L X
d L X




(5.6) для всех


1 2
,
,
,
T
n
n
dX
dx dx
dx


таких, что
 
 
*
*
1 0
n
j
j
i
i
i
g
X
dg
X
dx
x






,
1,
j
k

(5.7) Утверждение 3 (достаточные условия условного экстремума Пусть имеется точка


*
*
,
X

, удовлетворяющая системе (5.4)-
(5.5). Если в этой точке

---