Документ: ММвСС. Экзаменационные вопросы и ответы, страницы 36-40

41. Безусловная оптимизация. Необходимые и достаточные условия существования экстремума функции нескольких переменных.

Необходимое и достаточное условия существования экстремума функции нескольких переменных

Пусть задана функция нескольких переменных ( ) = ( , , … , ).
							1	2
	Необходимое условие существования локального экстремума
В точке 0	имеет место экстремум тогда, когда она дифференцируема в данной точке и все частные
производные функции в этой точке равны нулю.
			( )		\| =	( )	\| = =	( )	\| 0 = 0


				1	0	2	0
Если условия выполняются, то точка 0					называется стационарной точкой.
	Достаточное условие существования локального экстремума
Теорема 1. Если в точке		первая производная функции равна нулю ′( ) = 0, а вторая производная
	0								0
′′( ) > 0, то функция в точке				имеет локальный минимум, если ′′( ) < 0, то локальный максимум.
0		0							0

Если вторая производная функции в точке 0 равна нулю, то необходимо исследовать производные высших порядков в соответствии со следующей теоремой.

Теорема 2. Если функция одной переменной имеет в точке 0

производные до ( − 1) порядка равными нулю

и производная ( )( ) ≠ 0, то тогда точка :

0

точка минимума, если чётно и ( )( ) > 0

0

{точка максимума, если чётно и

( )(

) < 0

0

точка перегиба, если нечётно

Для анализа поведения функции в точке потребуются некоторые свойства квадратичных функций.

Квадратичная функция (форма):

2

( )

(∆ ) = ′′( )∆ 2 = ∑ ∑

∆ ∆ = ∑

∑

( ) ∆ ∆

=1

Если квадратичная форма:

o

отрицательно определена ( ∆ ≠ 0: (∆ ) < 0),

то в точке 0

имеет место максимум.

o

положительно определена ( ∆ ≠ 0: (∆ ) > 0), то в точке 0

имеет место минимум.

Определитель Гессе (Гессиан):

2( )

…

2( )

|

2

|

1

2

1

det ( ) =

2( )

…

2( )

2

1

2

…

2

|

…

|

2( )

…

2( )

2

1

2

•Квадратичная форма является отрицательно определенной, если собственные значения матрицы отрицательны. Имеет место максимум.

•Квадратичная форма является положительно определенной, если собственные значения матрицы положительны. Имеет место минимум.

•Если собственные значения матрицы имеют разные знаки, то экстремума в данной точке нет.

Собственные значения можно найти как корни уравнения:


	2( )		−		2( )		…		2( )
\|	2										\|
	1			1		2		1
det( ( ) − ) =		2( )		2( )		−	…		2( )		= 0
				2
	2		1	2			…	2
\|		…			…				…		\|
		2( )			2( )		…	2( )		−
								2
			1			2

Теорема4. Пусть для функции = ( , ) в окрестности точки 0( 0, 0) выполняются условия:

•Частные производные первого порядка равны нулю: ′( 0, 0) = 0 и ′( 0, 0) = 0.

•Частные производные второго порядка в определителе Гессе:

det ( , ) = \|	′′	( , )		′′	( , )		\| = ′′ ( ,	) ′′ ( ,	) − ( ′′ ( ,	2
det ( , ) = \|		0	0		0	0	\| = ′′ ( ,	) ′′ ( ,	) − ( ′′ ( ,	))
	′′	( , )		′′	( , )		0 0	0 0	0 0
		0	0		0	0

4 Громницкий В.С. Методы оптимизации. Курс лекций: Учебное пособие.

Тогда:

•Если det ( , ) < 0, то функция = ( , ) в точке 0( 0, 0) не имеет экстремума.

•Если det ( , ) = 0, то функция = ( , ) в точке 0( 0, 0) может иметь или не иметь экстремума (нужны дополнительные исследования).

•Если det ( , ) > 0, то функция = ( , ) в точке 0( 0, 0) имеет экстремум.

Пример №1

Исследовать на экстремум функцию = ( , ) = 3 + 3 − 15 + 2. Вычислим частные производные первого порядка:

′

= 3 2 − 15 ,

′

= 3 2 − 15

Составляем систему:

3 2 − 15 = 0

{3 2 − 15 = 0

Находим два решения – две стационарные точки: 1(0,0) и 2(5,5).

Находим частные производные второго порядка:

′′

= 6 ,

′′ = ′′ = −15,

′′ = 6

Находим определитель Гессе:

2 ( , )

2

6

−15

det ( , ) = | 2 ( , )

2 ( , )| = |−15

6 |

= 36 − 225

2

При = 0, = 0: det = −225 < 0. Экстремума нет.

При = 5, = 5: det = 30 > 0. Экстремум есть.

Находим собственные значения и определяем тип экстремума:

det( ( , )

− ) = |

30 −

−15

= (30 − )

2

− 225 = 0

−15

30 − |

1 = 15, 2 = 45

Собственные значения положительны. Точка (5,5) – точка минимума.

Пример №2

Исследовать на экстремум функцию = ( , ) = 4

+ 4 − 2 − 2.

Вычислим частные производные первого порядка:

′ = 4 3 − 2 ,

′ = 4 3

− 2

Составляем систему:

4 3 − 2 = 0

{4 3 − 2 = 0

Находим девять решений – девять стационарных точек: 1(0,0), 2 (0,

√2

), 3 (0, −

√2

), 4

(

√2

, 0),

2

5 (−

√2

, 0), 6 (−

√2

, −

√2

), 7 (−

√2

,

√2

), 8 (

√2

, −

√2

), 9

(

√2

,

√2

).

2

Находим частные производные второго порядка:

′′ = 12 2 − 2,

′′

= ′′ = 0,

′′ = 12 2 − 2

Находим определитель Гессе:

2 ( , )

2

12 2 − 2

0

= (12 2 − 2)(12 2 − 2)

det ( , ) = | 2 ( , )

2 ( , )| =

|

0

12 2 − 2|

2

1: det = 4 > 0. Экстремум +

2: det = −8 < 0

3: det = −8 < 0

4: det = −8 < 0

5: det = −8 < 0

6: det = 16 > 0. Экстремум +

7: det = 16 > 0. Экстремум +

8: det = 16 > 0. Экстремум +

9: det = 16 > 0. Экстремум +

Находим собственные значения и определяем типы экстремумов:

det( ( ) − ) = |12 2 − 2 −

0

| = (12 2 − 2 − )(12 2 − 2 − ) = 0

0

12 2 − 2 −

Подставляя координаты точек в последнее уравнение (12 2 − 2 − )(12 2 − 2 − ) = 0, получим:1: = −2. Точка максимума.

6, 7, 8, 9: = 4. Точки минимума.

42. Условная оптимизация. Метод множителей Лагранжа.

Математическое программирование – это область математики, разрабатывающая теорию, численные методы решения многомерных задач с ограничениями. В отличие от классической математики, математическое программирование занимается математическими методами решения задач нахождения наилучших вариантов из всех возможных.

Условная оптимизация. Метод множителей Лагранжа

Пусть задана функция нескольких переменных ( ) = (

, … , ).

1

Требуется найти экстремумы ( ) при заданных ограничениях:

( ) =

( , , … ,

)

= 0,

= 1 …

1

2

Необходимые условия существования локального экстремума

Функция Лагранжа:

Ф( , ) = ( ) + ∑

( ) ,

− множители Лагранжа

=1

Если точка является локальным экстремумом и в окрестности этой точки функции ( ) и

( )

0

непрерывно дифференцируемы, то в этой точке выполняются условия:

Ф

=

+ ∑

= 0

=1

Ф

= ( ) = 0

{

I. Достаточные условия существования локального экстремума (из лекций)

Если ( ) и ( ) дважды дифференцируемы в точке

и в этой точке выполняются условия

(Ф′′

( , ) , ) > 0 (мин. )

0

(Ф′′

( , ) , ) < 0 (макс. )

или

0

где Ф′′

( , )

= ′′( ) +

∑

′′( )

0

=1

При всех ненулевых , удовлетворяющих условиям

( ′(

) , ) = 0,

= 1 …

0

То 0

строгий локальный минимум (максимум)

( ) при заданных ограничениях.

II. Достаточные условия существования локального экстремума (из интернета5)

Окаймленный Гессиан:

2Ф( )

2

Ф( )

1

2Ф( )

2

Ф( )

1

2

1

2

2Ф( )

2

Ф( )

Ф =

1

0

1

0

0 )

(

1

( = 1, … , + ) – главный минор матрицы ,

образованный строками и столбцами , + 1, … , + .

= det ,

= 0, при = + 1, … , +

Ф

Теорема 1 (достаточное условие минимума). Пусть в точке 0 ранг матрицы ( ) максимален и эта точка

удовлетворяет необходимым условиям наличия экстремума. Тогда достаточным условием локального минимума в задаче (min) является выполнение неравенств:

(−1) ( ) > , … , (−1) −( ) >

(означает, что все миноры 1 … − имеют знак (−1) .

Теорема 2 (достаточное условие максимума). Пусть в точке 0 ранг матрицы ( ) максимален и эта точка

удовлетворяет необходимым условиям наличия экстремума. Тогда достаточным условием локального максимума в задаче (max) является выполнение неравенств:

(−1) +−1 ( ) > , … , (−1) +−1 −( ) >

(означает, что в последовательности миноров 1 … − есть знакочередование, начиная со знака (−1) .

5 URL: http://meit.mgimo.ru/sites/default/files/Lecture_2_2.pdf

Пример

Мат. модель: ( ) = 4 12 + 20 2 + 6 22, 1 + 2 = 200, 1 ≥ 0, 2 ≥ 0,.

Задача

Минимизировать функцию ( ).

Решение

Перепишем условия в виде ( ) = 0:

200 − ( 1 + 2) = 0

Составим функцию Лагранжа:

Ф( , ) = ( ) + ∑

( ) = 4 2

+ 20

+ 6 2

+

(200 −

− )

=1

1

2

1

2

Составим систему:

Ф′

= 8 1 − 1 = 0

8 − = 0

{Ф′

1

{12 2

− 8 1 = −20 { 1 = 121

= 20 + 12

− = 0

{12

−

= −20

2

1

2

1

+ 2 = 200

2 = 79

200 −

−

= 0

1 + 2 = 200

1

2

Найдём 1 = 8 1 = 968.

Составим окаймленный Гессиан:

Ф′′1

0

−1

8 + 0

0

−1

Ф = ( 0

Ф′′

−1) = ( 0

12 + 0

−1)

2

−1

0

−1

0

− = 2 − 1 = 1. Рассматриваем только 1 = det Ф = −20 < 0. Минимум по достаточному условию.

( ) = 97590

Wolfram Alpha: { 4 1^2 + 20 2 + 6 2^2} ( 1 + 2 = 200) = 97590 ( 1, 2) = (121,79)

43. Условная оптимизация. Условия Каруша-Куна-Таккера.

Выпуклое программирование – раздел нелинейного программирования, совокупность методов решения нелинейных экстремальных задач с выпуклыми целевыми функциями и выпуклыми системами ограничений.

Пусть функция ( ) является выпуклой на некотором промежутке ( , ) и числа q										1	, … , таковы, что
										1
			, … , > 0,			∑ = 1
			1
Тогда каковы бы ни были числа		, … ,	из промежутка ( , ), выполняется неравенство:
1
( + + +				) ≤ (			) + (		) + + ( )
1 1	2 2				1	1	2	2
Т. е.
			(∑ ) ≤ ∑ ( )

Если функция ( ) вогнута (выпукла вверх), то знак в неравенстве меняется на противоположный.

Многие задачи оптимизации можно привести к этой стандартной форме. Например, задача максимизации вогнутой функции может быть переформулирована эквивалентно как задача минимизации выпуклой функции (− ), так что о задаче максимизации вогнутой функции на выпуклом множестве часто говорят как о задаче выпуклого программирования.

Свойства выпуклой функции:

•Дважды дифференцируемая функция выпукла тогда и только тогда, когда её график лежит не ниже касательной, проведенной в любой точке интервала выпуклости;

•Дважды дифференцируемая функция выпукла, если её вторая производная не отрицательна;

•Если ( ) и ( ) выпуклы, то их линейная комбинация тоже выпуклая функция;

•Локальный минимум выпуклой функции является глобальным минимумом;

•Любая стационарная точка выпуклой функции является глобальным экстремумом.

Условия Каруша-Куна-Таккера (ККТ)6

Метод является обобщением метода множителей Лагранжа. В отличие от него, ограничения, накладываемые на переменные, представляют собой не уравнения, а неравенства.

Пусть задана непрерывно дифференцируемая выпуклая функция переменных ( ) = ( 1, … , ). Требуется найти экстремумы ( ) при заданных ограничениях в виде выпуклых функций :

	( ) =	( , … , ) ≤ 0,	≥ 0,	= 1 …
		1

6 URL: https://projecteuclid.org/download/pdf_1/euclid.bsmsp/1200500249

Функция Лагранжа:

Ф( , ) = ( ) + ∑

( ) ,

− множители Лагранжа

=1

Необходимые и достаточные условия существования минимума

Точка при наложенных ограничениях – решение задачи.

Условия из лекции (исправленные)

)

(

,

)

Ф(

,

≤ 0, = 1 …

Ф

≥ 0, = 1 …

)

(

,

)

Ф(

,

= 0, = 1 …

Ф

= 0, = 1 …

≥ 0, = 1 …

Пример

Задача

Найти минимизировать ( , ) = ( − 4)2 + ( − 4)2. Ограничения:

1( ): 2 + ≤ 15 [ограничения задачи]2( ): + 3 3 ≤ 9 [ограничения задачи], ≥ 0 [стандартные ограничения]

Решение

Перепишем условия так, чтобы справа был нуль:

1( ): 2 + − 15 ≤ 02( ): + 3 3 − 9 ≤ 0

Составим функцию Лагранжа:

Ф({ , }, ) = ( , ) + ∑ ( , ) = ( − 4)2 + ( − 4)2 + 1( 2 + − 15) + 2( + 3 3 − 9)

=1

Выписываем условия Каруша-Куна-Таккера:
Ф′	= 2( − 4) + 2 +					2	= 0
			1			2
Ф′	= 2( − 4) + + 9			2	2		= 0
			1	2
2 + − 15 ≤ 0,		≥ 0,	( 2				+ − 15) = 0
		1	1
{ + 3 3 − 9 ≤ 0,		2 ≥ 0,	2( + 3 3 − 9) = 0

Рассмотрим 4 случая (2 случаев для рассмотрения):

1.{ + − = , + − = , > , > , 1( 2 + − 15) = 0, 2( + 3 3 − 9) = 0}. Решая систему, получаем = 3.71378, = 1.20784, 1 = 0.02 ≥ 0, 2 = 0.42379 ≥ 0.

2.{ + − = , + − < , > , = , 1( 2 + − 15) = 0, 2( + 3 3 − 9) = 0}. Корней нет.

3.{ + − < , + − = , = , > , 1( 2 + − 15) = 0, 2( + 3 3 − 9) = 0}. Корней нет.

4.{ + − < , + − < , = , = , 1( 2 + − 15) = 0, 2( + 3 3 − 9) = 0}. Корней нет.

В результате получена единственная точка 1:

= 3.71378027848072, = 1.20783604316766, 1 = 0.02001289364114531, 2 = 0.423792463598923001

Точка удовлетворяет необходимым и достаточным условиям, значит 1 — минимум ( ) для заданных условий.

({ , } | { 1, 2}) = 7.8781

Wolfram Alpha: { ( − 4)2 + ( − 4)2} { 2 + <= 15, + 3 3 <= 9} = 7.8781 ( , ) = (3.7,1.2)

Материал: ММвСС. Экзаменационные вопросы и ответы

Смотрите также: