Добавил:

ivanov666 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Национальный исследовательский ядерный университет (МИФИ)

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

Кудрявтсев Методы оптимизатсии 2015

.pdf

Скачиваний:

Добавлен:

12.11.2022

Размер:

1.51 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 67 / 147 8 9 10 11 12 13 14 > Следующая >>>

2.3Условная оптимизация функций многих переменных

2.3.1 Основные понятия и определения

Постановка задачи

, , … ,

Пусть задана функция n

действительных переменных

(2.14)

определенная на множестве

которая представляет из себя

функцию цели (функцию

качества). Требуется найти

дос-

j k

при ограниче-

тавляющий максимум (минимум) данной функции

ниях вида:

0, @

0, … , @

т.е. имеется

0, … ,

p ограничений заданных в виде равенств и m-p огра-

его легко переписать в виде

0, то

ничений, заданных в виде неравенств. Как было отмечено ранее,

если какое-либо ограничение представлено в виде

, , … ,

, @ , , … ,

, , , … , ,

Функции

общем случае нелинейны. В отличие от задач линейного программирования для задач нелинейного программирования не существует универсального метода решения.

В методах оптимизации с ограничениями используются понятия

выпуклых и вогнутых функций.

назы-

Функция

определенная на выпуклом множестве

вается выпуклой вверх, если для любой пары точек

произвольного

| 1

выполняется неравенство

Если

A 1 |

| A 1 |

называется вогнутой (выпуклой вниз).

то функция|

A 1 |

| A 1 | ,

Нетрудно установить,

что если

функции

выпуклы (вогнуты) на множестве

, то

функция

, , … ,

также выпукла (вогнута), если | 0, 1, Š .

Обобщенный алгоритм поиска условного экстремума

1.Поиск всехkстационарных точек функции на выпуклом множестве .

2.Исследование точек границы, с отысканием тех из них, где достигает максимума.

3.Непосредственным сравнением точек, найденных в п. 1 и 2, определяют точку абсолютного максимума.

Следует отметить, что такой подход может применяться только в простых случаях, при небольшом числе ограничений.

2.3.2 Метод множителей Лагранжа

Метод неопределенных множителей Лагранжа позволяет оты-

скивать максимум (минимум) функции при ограничениях равенст-

вах. Основная идея метода заключается в переходе от задачи ус-

ловной оптимизации к задаче поиска безусловного экстремума

специально построенной функции Лагранжа.

Рассмотрим задачу поиска минимума функции цели при огра-

ничениях равенствах:

, , … ,

‹ min

@ , , … ,

, , … ,

(2.15)

…

цию

λ , λ

, … , λ

Предположим, что

все функции дифференцируемы. Введем m

, , … ,

переменных

(множителей Лагранжа) и составим функ-

Лагранжа:

, , … , , λ , λ , … , λ

или в

, , … ,

A ∑

, , … ,

(2.16)

F , Λ

! A

Λ · y!,

векторной форме

Λ λ , λ , … , λ

y @ , @ , … , @

(

∑

λ @

(

( ( 9

· y!

– векторы,

где

(

—(скалярное

произведение.

, , … ,

Покажем, что для решения задачи (2.15) т.е. для отыскания точ-

ки

, обеспечивающей минимум функции

, , … ,

, λ , … , λ

(2.17)

необходимо решить систему нелинейных уравнений относительно

неизвестных

8(+ > ,DE> -

8(+ >

(2.18)

Для доказательства

предположим, что функции

0, 1, .

градиенты

имеют непрерывные производные первого порядка, а , @

, @ , … , @

Žx@

; p@

Žx@

; P ; p@

•

Žx@

линейно независимы.

, , … ,

Представим, что из уравнений ограничений можно явно выра-

•

• , … , •

зить переменные

через

, т.е.

В этом случае задачу условной минимизации можно свести к

Для

, •

, … , •

‹ min.

безусловной:

нять ее нулю и решить

, •

, … , • ,

нахождения стационарных точек необходимо найти произ-

водную сложной функции

прирав-

‘

‘•

x !

‘•

‘

A x

‘

A x

‘

A P A x

‘

уравнение

Для ограничений можно записать

‘•

‘@

‘•

x@!

‘•

1, .

‘

A x

‘

A x

‘

A P A x

‘

Данные уравнения могут]быть· T записаны0, в матричной форме (2.19)

где							P						1
				8		8			8				1
				8		8			8
	]			8		8			8		;	T	FG
	]										;	T	FG
				8$		8$			8$					FG
				8$		8$			8$
		Ž					’			Ž				F
		Ž		•		•	’		•	Ž				F		.
		Ž		8		8	P		8	Ž				F	Ž	.
			8$		8$		P	8$					Ž •		Ž
				8		8	P	8				\| .
Поскольку		]			\|p , p@		, p@ , … p@					\| .
Матрицу A можно записать в векторной форме:
												9
	вектор				не нулевой, то для получения ненулевого
				уравнения (2.19) требуется, чтобы определи-
решения матричного T

тель матрицы был равен нулю, т.е. строки матрицы должны быть

p A / p@ A / p@ A P A / p@ 0,

линейно зависимы, а именно должно выполняться соотношение:

причем коэффициенты

не должны быть равны ну-

лю одновременно.

/ , / , / , … , /

Так как по условию

линейно независимые, то

коэффициент

не

может равняться нулю (так как в противном

, p@ , … , p@

должны бы быть

остальные коэффициенты

случае все

равными нулю, а это противоречит

требованию линейной зависи-

/ , / , … , /

, полу-

мости

строк матрицы A). Разделив данное уравнение на

чим:

p A λ p@ A λ p@ A P A λ p@ 0,

(2.20)

, 1,

—

где

точка решения системы (2.19).

Таким образом, для решения задачи минимизации с ограниче-
1,
ниями (2.15) должны существовать такие коэффициенты
	, которые одновременно не обращаются в нуль, и						выполня-
	, которые одновременно не обращаются в нуль, и							“		,
ется соотношение (2.20).		F , Λ! A Λ · y								(
Если теперь ввести функцию									и Λ
Если теперь ввести функцию								, то, вы-
числяя частные производные этой			функции от ее аргументов
числяя частные производные этой				(	(	(
		64

и приравнивая их нулю, получим уравнения (2.20) и (2.15). В самом деле

HI+J>

, Λ -

HM)J>

HP )J>

N O

N Q N O

L 0,

S L 1, U,

L P )J> * L 0,

V L 1, W.

Из всего вышесказанного следует теорема Лагранжа.

имеют непрерывные частные

, @

, @ , … , @

Задана задача (2.15) нахождения минимума функции при огра-

ничениях

равенствах.

Все

функции

производные на множестве

. Пусть

существует точка

в которой достигается

относительный экстре-

Если ранг матрицы

мум задачи (2.15).

, … , λ

равен m, то существуют m

λ , λ

в точке

чисел

, не все од-

новременно равные нулю, для которых справедливо соотношение
		p A ∑ λ @ 0.								(2.21)
Алгоритм метода неопределенных множителей Лагранжа:
		(				(8(+(
			F , Λ! A			Λ · y!.
1. Составление функции Лагранжа								0,	1,
8(+ >,DE>-							8	0,	1,
							E>
2. Нахождение частных производных							>,D-			и
		0, 1, .
3.		0, 1, .
8C			xF ,	(
				(
				Λ!
	Решение системы уравнений
			x		0,		1, ,
					65

		xF ,	(
		xF ,	Λ!
				0,	1, .
				0,	1, .

4. Исследование	решения системы точек					на минимум.
4. Исследование		xλ				на минимум.

2.3.3Пример использования метода неопределенных множителей Лагранжа

Найти минимум целевой функции
при ограничениях ,						A ! ” min
							2 0,
			,
Составим	функцию Лагранжа						2 0.
			,
, , , λ , λ					λ			2 λ 2 .
Дифференцируя		функцию		, , , λ , λ					по переменным

, , !, λ , λ и приравнивая полученные выражения нулю, полу-

			λ	0
чим следующую систему уравнений:
	$		λ λ 0
				0

	#		λ
	#			2 0
		! 1;
Из первого и третьего	уравнения следует
Из первого и третьего	!			2 0.
данную систему, находим					λ

λ 2 . Решая

2.3.4Поиск условного экстремума при ограничениях– неравенствах. Теорема Куна-Такера

Рассмотрим задачу поиска минимума функции цели при огра- ничениях–неравенствах: , , … , ‹ min

& , , … ,

( 0

(2.22)

, , … ,

( 0

…

, , … , ( 0.

если оно

, , … ,

Ограничение

называется активным в точке

выполняется как строгое равенство, т.е.

Рассмотрим случай линейных ограничений, т.е.

Здесь

–

*µ +

( 0,

- 1, .

, , … ,

можно представить как

µ(

вектор постоянных коэффициентов размерности n, а

обозначает скалярное произведение векторов

и .

µ( Представляя приведенное выражение в

другом виде, нетрудно

µ(

заметить, что ограничения задаются неравенствами вида

. Допус-

и каждое ограничение

определяет полупространство в

*µ / + ,

- 1, .

µ(

m полупространств, причем

тимая область задается пересечением

Заметим, что

0, .

гиперплоскости, определяемой

вектор

является

нормалью

Пусть

µ(

внутрь

допустимой

области.

уравнением

и направлен

является точкой минимума задачи (2.22). Обозначим

Для любой точки

–

0&.

множество индексов активных ограничений как

так как

*µ

находящейся внутри допустимой области

/ 0

( 0;

- 2 3,

ограничений,

справедливо выражение

Если

–

µ(

;

векторы

являются однонаправленными.

в силу того, что

/ 0

точка минимума функции, то

однонаправленными.

градиент направлен в сторону максимального воз-

растания функции, и, следовательно,

являются

*µ

/ 0,

- 1, .,

Таким образом, имеем очень важные неравентства:

Для дальнейших

/ 0.

(2.23)

преобразований воспользуемся леммой Фаркаша

(

A – матрица размерности m x n,

– вектор размерности

Пусть

–

вектор размерности

Тогда имеет

решение только одна из

(

систем:

4λ +,

λ / 0, λ 2 5 ,

4 ( 0,

, + / 0

2 5 .

1)T *

(2.24)

(

(2.25)

(

0 ]

a ] 0 a, 0

Доказательство. Пусть система*

(1) имеет решение, т.е. сущест-

вует

, а

, то

]λ

a, ]λ! a ], λ!

. Под-

. Предположим, что

λ 0 a ] 0

a, 0,

ставим вместо

выражение

, получим

. Но так

как

y( , 0

получим(

т.е.(

противоречие(

с ус-

(

ловием

. Следовательно,

если система (1) имеет решение,

(

то система ((2) его не имеет.

˜с: с ]λ, λ 0š

]λ ›

. По теореме об

Пусть теперь система (1) не имеет решения. Рассмотрим замк-

f i

Так как

и(

нутое выпуклое множество

то

Š, ! G α

отделимости выпуклого( (

множества.

точ(-

Š, с

0 i

ки,( которая ему не принадлежит, существуют вектор

и число

такие, что

α 0

Š, ! G α G 0

Š, с

Š, ]λ! Š ], λ!

. По условию нулевой

(

λ 0

. С другой стороны,

значит

(

Так(как

], λ! α

] 0

выполнение(

обеспечивается

при

шим,(

то

условия(

. Следовательно,

T – решение

(системы

(2).

Вернемся к

анализу неравенств (2.23). Первые

m неравенств

*µ

можно представить в матрично-векторной форме:

*µ

/ 0 или

*µ , *µ , … , *µ

/ 0.

(

перепишем ] |µ( , µ( , … , µ(

, а

также

Вводя

обозначения

*µ

] 0,

неравенства (2.21) в виде

a 0.

В соответствии с леммой

Фаркаша система (2.25) не выполняет-

(

ся и, следовательно, должна иметь решение система (2.24), т.е.

|µ(

]λ ,

λ 0

, µ(

, … , µ(

· λ

Используя введенные

обозначения, получим

(

или

(

∑Y

∑Y λ p .

(2.26)

шется в виде

0 при

f –

, то выражение (2.26) запи-

Если принять, что

∑

Кроме того,

аналогичном (2.21):

(2.27)

так как

при

∑

,λа

справедливо соотношение

–

f – λ

(2.28)

при

Таким образом, если ввести целевую функцию, аналогичную

функции Лагранжа, то можно записать

A λ

и решение задачи (2.22) сводится к решению системы уравнений:



pž			0,
pž	p A λ p		0,


	0,
λ	0,	λ 0,	1, .
При решении данной системы может случиться так, что в случае

λ 0, 1,

произвольных функций в задаче (2.22) не будет существовать таких

, для которых были бы справедливы полученные

уравнения (2.27) и (2.28). Поэтому на функции необходимо наложить определенные ограничения, которые называют условиями регулярности ограничений.

Требования к условиям регулярности ограничений сформулиро-
производные на		, 1,
ваны в теореме Куна-Такера.				k
Пусть функции		69
			имеют			непрерывные частные
	открытом множестве				, содержащем точку .

Если является решением задачи (2.22), где , 1, удов-

летворяют условию регулярности в виде линейной независимости

, λ

, … , λ

векторов-градиентов

, то существуют такие неотрицатель-

ные множители

Лагранжа

, что

9 λ

- 1, ..

/ 0,

Если определить функцию Лагранжа как

(

F , Λ! A λ

(

F , Λ! 0,

то теорему Куна-Такера можно записать в виде

(

p F , Λ!

(

F , Λ! λ

Доказательство.

1, .

ности точки

A ŸT

Разложим целевую функцию

в ряд Тейлора в окрест-

Пусть

–

ŸT

A Ÿp

T A Ÿ

0 при –

что

множество

активных

ограничений,

учитывая,

A ŸT

A Ÿp

T A

Ÿp

T A

, получим

T ? 0,

¡p

Нетрудно видеть, что система неравенств

(2.29)

для не-

несовместна, так как в

противном случае при малом

Ÿ G 0

которого

A ŸT ?

получили бы

A ŸT 0,

–,

что противоречит

предположению об оптимальности точки

<<< < Предыдущая 1 2 3 4 5 67 / 147 8 9 10 11 12 13 14 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
12.11.20222.92 Mб1Кувяткина Международные стандарты учета и отчетности 2012.pdf
#
12.11.202210.45 Mб26Кудинова Практическиы курс аглиыского языка для студентов международник Ч.1 2014.pdf
#
12.11.202210.79 Mб22Кудинова Практическиы курс англиыского языка для студентов международник Ч.2 2014.pdf
#
12.11.202212.14 Mб30Кудинова Практическиы курс англиыского языка для студентов международник Ч.3 2014.pdf
#
12.11.202210.38 Mб15Кудинова Практическиы курс англиыского языка для студентов международник Ч.4 2014.pdf
#
12.11.20221.51 Mб12Кудрявтсев Методы оптимизатсии 2015.pdf
#
12.11.20221.39 Mб7Кузмина, Что такое ядерная медецина 20112.pdf
#
12.11.2022688.18 Кб5Кушин Методы регистратсии излучениы 2015.pdf
#
12.11.20222.76 Mб9Лабораторный практикум Атомная физика.pdf
#
12.11.20221.65 Mб2Лабораторный практикум Конструкционные материалы ядерных реакторов.pdf
#
12.11.20224.42 Mб4Лабораторный практикум курса общей физики. Раздел Атомная физика.pdf