- •Содержание
- •Предисловие
- •Глава I. Нелинейное программирование: экстремумы функций нескольких переменных
- •§1. Классические методы оптимизации
- •1.1. Безусловный экстремум функции одной переменной
- •1.2. Условный экстремум функции одной переменной
- •1.3. Безусловный экстремум функций двух переменных
- •2.1. Необходимые и достаточные условия
- •1.4. Упражнения.
- •§2. Безусловный экстремум функций нескольких переменных
- •§3. Условный экстремум функций нескольких переменных
- •3.1. Основные определения и факты
- •3.2. Условный экстремум при ограничениях типа равенств
- •3.3. Условный экстремум при ограничениях типа неравенств
- •3.4. Условный экстремум при смешанных ограничениях
- •3.5. Понятие о методах штрафных функций
- •Глава II. Численные методы нелинейного программирования
- •§1. Общие положения
- •1.1. Постановка проблемы
- •1.2. Общие принципы.
- •§2. Методы нулевого порядка одномерной минимизации
- •2.1. Общие положения
- •2.2. Метод равномерного поиска
- •2.3. Метод деления интервала пополам
- •§3. Методы первого и второго порядка
- •3.1. Метод градиентного спуска с постоянным шагом
- •3.2. Метод Ньютона
- •§4. Элементы численных методов задачи условной оптимизации выпуклого программирования
- •4.2. Постановка задачи выпуклого программирования.
- •4.3. Численные методы на основе метода штрафных функций
- •4.4. Метод проекции градиента.
- •Приложение 1. Варианты индивидуальных заданий
- •Задание нп-1
- •Задание нп-2
- •Задание нп-3
- •Задание нп-4
- •Задание нп-5
- •Задание нп-6
- •Задание нп-7
- •Задание нп-8
3.2. Условный экстремум при ограничениях типа равенств
В этом случае утверждения, 3.1.1, 3.1.2, 3.1.4 принимают следующую редакцию, соответственно:
3.2.1. Пусть X*Rп точка локального минимума (максимума) функции f(X) на множестве М={X|i(X)=0, i=1, 2, …, m}. Тогда существуют числа , , …, , не равные одновременно нулю и такие, что выполняются условия:
условия стационарности обобщённой функции Лагранжа по X:
=0, j=1, 2, …, n; (3.2.1.a)
условие допустимости решения:
i(X*)=0, i=1, 2, …, n; (3.2.1.б)
Если при этом градиенты 1(X*), 2(X*), …, m(X*) в точке X* линейно независимы, то ≠0.
При решении задач, как правило, рассматривают два случая: =0 и ≠0. В последнем случае в системе (3.2.1.а) полагают =1, при котором функция Лагранжа становится классической, система (2.2.1) принимает вид
=0,
j=1,
2, …, n, (3.2.2.a)
i(X*)=0, i=1, 2, …, n. (3.2.2.б)
3.2.2. Пусть X*Rп регулярная точка локального минимума (максимума) функции f(X) на множестве М и имеется решение (X*, *) системы (3.2.1). Тогда второй дифференциал классической функции Лагранжа, вычисленный в точке (X*, *), неотрицателен (неположителен):
d2L(X*, *)0 (d2L(X*, *)0) (3.2.3.а)
для всех таких dxRп, что
di(X*)=
=0
(i=1,
2, …, m). (3.2.3.б)
3.2.3. Пусть (X*, *) точка, которая является решением системы (3.2.1). Если в этой точке полный дифференциал второго порядка классической функции Лагранжа, положителен (отрицателен)
d2L(X*, *)>0 (d2L(X*, *)<0)
для всех таких dxRп, что
di(X*)= =0 (i=1, 2, …, m),
то точка X* является точкой локального минимума (максимума) задачи.
Таким образом, для того, чтобы исследовать функцию на условный экстремум с ограничениями типа равенства (то есть найти для функции точки условных экстремумов, определить их характер и вычислить значения функции в этих точках), достаточно:
Составить обобщённую функцию Лагранжа:
L(X, 0, )=0f(X)+
Составить систему:
(3.2.1)
Решить систему (3.2.1) для двух случаев:
а) 0=0;
б) 0=1.
В результате находятся условно-стационарные точки X*.
Для условно стационарных точек X*, полученных в пункте 3, проверить достаточные условия экстремума. Для этого можно, в силу Замечания в пункте 2.1, применить критерии типа Сильвестра к функции d2L(X*, *), или проверить это непосредственно, выразив из системы (3.2.3.б) любые m дифференциалов через остальные nm и подставив их в d2L(X*, *). Если d2L(X*, *)>0 при ненулевых dx, то точка X* является точкой условного минимума, а если d2L(X*, *)<0, то точкой условного максимума. Если достаточные условия не выполняются, то проверяются необходимые условия второго порядка. Если они выполняются, то требуется дополнительные исследования; если нет, то точка X* не является точкой условного экстремума.
Вычислить значения функции в точках условного экстремума.
При проверке достаточных условий в условно-стационарных точках (при 0=1) более эффективно воспользоваться непосредственной проверкой.
Пример I. Исследовать на условный экстремум функцию:
f(X)=x1+x2extr
.
Решение.
Действуем по вышеприведённой схеме. В
нашем случае 1(Х)=
(Х)=
Составим обобщённую функцию Лагранжа:
L(X,
0,
)=0(x1+x2)+1(
).
Составим систему (3.2.1). Имеем
=0+21x1,
=0+21x2.
Поэтому
(3.2.4)
Решаем систему для двух случаев:
а) 0=0.
Имеем 1≠0, так как по 3.2.1 в точке локального экстремума X* не все 0 и 1 равны нулю. Тогда x1=0 и x2=0. Но тогда (X*)≠0, то есть X*=(0, 0) не удовлетворяет ограничению задачи. Значит, условно-стационарных точек при 0=0 нет.
б) 0=1.
(3.2.4)
Из
первых двух уравнений системы получаем
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(X)=21
и 2(X)=4
.
При 1=
,
то есть для точки X1=(2,
2), имеем 1(X1)=
<0
и 2(X1)=
>0.
Это означает, что в точке (X1,
1)=(2,
2,
)
d2L
отрицательно определена, и X1
точка регулярного условного локального
максимума. При 1=
имеем 1(X2)=
>0
и 2(X2)=
>0,
и в точке (X2,
2)=(2,
2,
)
d2L
положительно определена, и X2
точка регулярного условного локального
минимума.
Способ 2. Имеем d=2x1dx1+2x2dx2. Выразим из d=0 dx2 через dx1:
2(2)dx1+2(2)dx2=0 4dx14dx2=0 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.
Ответ: X1=(2, 2) точка регулярного условного локального максимума, fmax=4, X2=(2, 2) точка регулярного условного локального минимума, fmin=f(X2)=4.
Пример II. Исследовать на условный экстремум функцию:
f(X)=x1x2extr
.
Решение. Имеем 1(Х)=(Х)= Так как (Х)=(2x1, 2x2)≠0 для всех хM, то условие регулярности выполнено, то есть 0≠0 и можно считать 0=1. Далее действуем по схеме.
Составим функцию Лагранжа:
L(X, )=(x1x2)+1( ).
Составим систему (3.2.1). Имеем =x2+21x1, =x1+21x2. Поэтому
Решаем полученную систему. Выразим из второго уравнения системы x1 через x2 (x1=21x2) и подставим его в первое уравнение:
x2+21(21x2)=0 x2(14 )=0.
Заметим, что x20, так как в противном случае x1=0, то есть x1=x2=0, что не удовлетворяет третьему уравнению. Поэтому
x2(14
)=0
14
1=
,
откуда
x1=
x2,
подставляя которое в третье уравнение
системы, приходим к уравнению
,
то есть x1=
2,
откуда x2=
2.
При этом знаки у x1
и x2
не зависят от того, 1=
или 1=
.
Таким образом, решением системы являются
четыре точки: (X1,
1)=(2,
2,
),
(X2,
2)=(2,
2,
),
(X3,
3)=(2,
2,
),
(X4,
4)=(2,
2,
).
Проверим достаточные условия экстремума в найденных точках.
Имеем
= =21, = =1.
Способ
1. Имеем H(X)=
,
1(X)=21,
2(X)=4
1.
Тогда 1(X1)=1(X2)=2
=1<0,
2(X1)=2(X2)=4
1=0,
то есть 1<0
и 2=0,
и для точек X1
и X2
достаточные условия второго порядка
не выполнены, в то время, как необходимые
условия второго порядка выполнены.
Аналогично, 1(X3)=1(X4)=1>0
и 2(X3)=2(X4)=0.
Таким образом, этот способ не даёт ответа
на вопрос об экстремальности
условно-стационарных точек.
Способ 2. Имеем d2L=21d +2dx1dx2+21d . Так как d=2x1dx1+2x2dx2, то d=0 dx2=dx1, и d2L=41d 2d . Тогда
d2L(
)=d2L(
)=4d
<0
при dx1≠0
Поэтому точки X1 и X2 точки регулярного условного локального максимума.
Далее,
d2L(
)=d2L(
)=4
d
2d
=0.
Это означает, что достаточное условие
условного экстремума в точках X3
и X4
не выполняется, в то время, как выполняется
необходимое условие второго порядка.
Поэтому требуется дополнительное
исследование. Например, заметим, что
функция f(X)=x1x2
непрерывна везде, в том числе и во
множестве {(x1,
x2)|
}.
Поэтому она достигает на этом множестве
своих экстремумов, в том числе минимумов.
В этих точках (где достигается условный
минимум) обязательно выполняется
необходимое условие. Следовательно, X3
и X4
точки условного минимума.
Вычислим значение функции в точках условного максимума и в точках условного минимума:
fmax=f(X1)=f(X2)=(2)(2)=4, fmin=f(X3)=f(X4)=(2)( 2)=4
Ответ: X1=(2, 2) и X2=(2, 2) точки регулярного условного локального максимума, fmax=4; X3=(2, 2) и X2=(2, 2) точки регулярного условного локального минимума, fmin=4.
