Добавил:

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

Вуз:

Томский Государственный Университет

Предмет:

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

Файл:

Методы оптимизации и исследование операций для бакалавров информатики. Часть 2

.pdf

Скачиваний:

187

Добавлен:

26.03.2016

Размер:

7.81 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 56 / 276 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 > Следующая >>>

50	Глава 9.		Теория выпуклого программирования
							X )	. Получим
Возьмем левое неравенство и сократим его на f (→−								. Получим
	m			m		→−
	y g (→−					→−
			X )	i		(X ).		(9.27)
	i	i		i	i			(9.27)
	i=1			=1

Так как yi 0, а неравенство должно выполняться для всех

yi 0, то

(−→ ) 0 gi X ,

−→

т. е. X — план задачи. В частности, (9.27) должно выполняться для yi = 0, т. е.

	m
0	y g (−→ )
	i	X .
	i i	X .
	=1

Но

→−

yi gi(X ) 0.

i=1 0 0

Отсюда немедленно следует, что

(−→ ) = 0 yi gi X .

i=1

−→

Покажем, что X — оптимальный план. Возьмем правое неравенство:

→−

f (→−

−→

(X )

f (X ) +

(X ).

i=1

— план, то

X )

Отсюда, если →−

(→−

yi gi(→−

X )

9.5. Дифференциальные условия Куна — Таккера					51
X	X	)	f (X ),	следовательно, план
То есть для любого плана →−	f (→−		→−	следовательно, план
→− оптимальный.
X

Замечание. Более подробное исследование, которое мы опускаем, показывает, что условие Слейтера является необходимым только для н е л и н е й н ы х ограничений. Для линейных ограничений теорема справедлива без этого условия.

9.5.Дифференциальные условия Куна — Таккера и их геометрическая интерпретация

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

жить, что они являются гладкими, т. е. непрерывно дифференци-

→− →−

руемыми, то условие седловой точки функции Лагранжа L(X , Y ) на неотрицательном октанте можно представить в дифференциальной форме.

Минимизация L по переменным xj при xj 0 приводит, как мы видели, рассматривая «полуклассический» случай оптимизации, к трем условиям для каждого j = 1, . . . , n. Аналогичные условия получаются для каждого i = 1, . . . , m при максимизации L по множителям Лагранжа yi при условии yi 0, однако знаки производных при переходе от минимизации к максимизации следует сменить на обратные.

В совокупности получится шесть симметричных дифференциальных условий Куна — Таккера, которые являются необходимыми и достаточными условиями минимума для общей задачи выпуклого программирования (9.1):

Глава 9. Теория выпуклого программирования

→− →−

X , Y )

а)

∂L(X , Y )

г)

∂L(→− →−

∂xj

∂yi

б)

∂L(→− →−

= 0,

д)

X , Y )

= 0,

(9.28)

X , Y )

yi ∂L(→− →−

∂xj

∂yi

в) xj 0,

е) yi 0,

j = 1, . . . , n,

i = 1, . . . , m.

Равенства «б» и «д» обычно называют условиями дополняющей нежесткости (complementary slackness conditions).

В векторной форме условия «а»–«в» приобретают компакт-

ный вид
	→− L(→− →−				0,
а)			X , Y )		0,
а)
	→−	→− L(→− →−				(9.28 )
б)	X T			X , Y ) = 0,		(9.28 )
б)	→−
в)	→−		0,
	X		0,

a условия «г»–«е», учитывая линейность функции Лагранжа по переменным yi, иногда удобнее использовать в равнозначной покоординатной записи:

г)	gi(→−				0,
			X )
д)	y		X ) = 0,
		igi(→−				(9.28 )
е)	yi		0,

i = 1, . . . , m.
Для того чтобы компактно записать условия «г»–«е», введем
обозначение вектор-функции:
→− (→− ) =				1(→−		.
				.
			g	X )
				.
G X			gm(→−

X )

9.5. Дифференциальные условия Куна — Таккера

Тогда (9.28 ) перепишется в эквивалентном векторном виде

г)

→− →−

д)

(X )

→−

→− →−

(9.29)

е)

T G (X ) = 0,

→−

Геометрическая

Условия Куна — Таккера имеют простую

и наглядную геометрическую интерпрета-

интерпретация

цию.

Напомним еще раз общую задачу выпуклого программирова-

ния (9.1)

f (→−

→

min,

X )

gi(→−

0, i = 1, . . . , m,

−→

X )

и функцию Лагранжа для нее (9.18)

L(→− →−

→−

i i

X , Y ) = f (X ) +

(X ).

y g

= (x

, . . . , x )T

Итак, пусть →−

— оптимальный план, →−

= (y1 , . . . , ym)T — соответствующий ему вектор оптимальных множителей Лагранжа.

Представим градиент функции Лагранжа в точке →− в виде

разложения по координатным векторам:

, Y ) =

(X ) =

f (X ) + y

v e .

→− L(→−

→−

→− →−

−→

j −→j

i i

j=1

Здесь

j — координата градиента, а

= (0, . . . , 0, 1, 0, . . . , 0)T ,

→− j

где единица стоит на j-м месте, — единичный координатный вектор (орт).

Глава 9.

Теория выпуклого программирования

Выразим отсюда антиградиент

ц е л е в о й

функции в

точке →−

→− f (→−

→−

−

) =

) +

v (

(9.30)

−→− j

j=1

C учетом введенных обозначений условия Куна — Таккера (9.28)–(9.28 ) приобретают вид

а) vj 0,

б) xj vj = 0,

в) xj 0, j = 1, . . . , n,

−→

г) gi(X ) 0,

−→

д) yi gi(X ) = 0,

е) yi 0,

i = 1, . . . , m.

Рассматривая их, прежде всего заметим, что условия «в» и
«г» очевидны: они требуют, чтобы оптимальный план	→−	удовле-
	X

творял всем ограничениям задачи, т. е. находился в допустимой области.

Для интерпретации остальных условий напомним, что некоторое ограничение является активным для конкретного плана, если соответствующее нестрогое неравенство превращается в равенство, то есть если данный план попадает на границу допустимой

области.	→−	может активизировать ограничения
В нашей задаче план	→−	может активизировать ограничения
	X

по двум причинам: либо он попадает на границу, заданную од-

−→

ной или несколькими функциями gi(X ) = 0, либо он попадает на

границу неотрицательного октанта, при этом одна или несколько

координат xj нулевые. В связи с этим для оптимального плана

→−

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

M (→−

→−

) =

) = 0

{

}

N (→−

}

) =

{

= 0

Условия дополняющей нежесткости «д» и «б» означают, что для н е а к т и в н ы х (пассивных) ограничений соответствующие

9.5. Дифференциальные условия Куна — Таккера

им yi и vj равны нулю:

→− ) → gi(→−

)

→ i

= 0;

(9.31)

i / M (X

j / N (→−

)

→

= 0.

(9.32)

x >

С учетом этого в выражении (9.30) суммирование по всем индексам можно заменить суммированием по индексам активных ограничений, так как остальные слагаемые, соответствующие неактивным ограничениям, равны нулю. Таким образом, условия «д» и «б» эквиваленты следующему выражению:

→− →−

y →− g (→− ) +

f (X

i i

(

−

i M (→−

→−

−→− j

(9.33)

)

j N (X

)

Оставшиеся два условия «а» и «е» требуют неотрицательности входящих в разложение коэффициентов vj и yi .

Для того чтобы увидеть в выражении (9.33) наглядный гео-

g	X )			X
X ) = 0				X
метрический смысл, заметим, что вектор →−	i(→−	представляет
собой внешнюю нормаль к ограничению gi(→−			в точке	→−	,

−→−

а вектор e j также можно понимать как внешнюю нормаль к координатной прямой xj = 0.

Подводя итог, получаем следующую интерпретацию условий Куна — Таккера для задачи выпуклого программирования.

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

Из этой интерпретации следует и геометрический смысл множителей Лагранжа yi: они представляют собой коэффициенты разложения антиградиента по векторам внешних нормалей к активным ограничениям. Если некоторое ограничение неактивно,

56	Глава 9. Теория выпуклого программирования

то, как следует из (9.31), соответствующий ему множитель равен нулю.

П р и м е р 1. Для иллюстрации рассмотрим простую задачу выпуклого программирования с двумя переменными :

f (x1, x2) = (x1 − 2)2 + (x2 − 2)2 → min,

x21 + x22 4,

x2 x1, x2 1,

x1, x2 0.

Рис. 9.14. Минимизация квадратичной функции двух неотрицательных переменных с тремя ограничениями-неравенствами

Как видно из рис. 9.14, допустимое множество (множество

планов) в этой задаче представляет собой криволинейную трапе-

−→

цию, оптимальный план X 1 находится в правом верхнем ее углу.

9.5. Дифференциальные условия Куна — Таккера

Координаты этой точки находятся из решения системы уравнений

! x2	= 1,	= 4,
x2	+ x2	= 4,
1	2

откуда x

= √

, x

= 1, f (x

, x )

1.0718.

≈

Для записи условий Куна — Таккера приведем ограничения к

каноническому виду:

g1(x1, x2) = x12 + x22 − 4 0,

g2(x1, x2) = −x1 + x2 0,

g3(x1, x2) = x2 − 1 0.

) =

1, 3 ,

Активные ограничения исследуемой точки: M (→−

{

}

) =

N (→−

Градиенты целевой и ограничивающих функций в

этой точке:

2(x1

2√

f (X ) =

f (X

) =

−→−

− 2)

−→−

−2

→−

−2(x2

→−

−

2x1

2√

(X ) =

) =

→−

2x2

→−

→− g3

(X ) =

→−

g (X

) =

→−

3 →−

Коэффициенты разложения антиградиента по нормалям к активным ограничениям находятся из системы уравнений

y1 2

√

2√

3 + y3

3 ,

1 =

−2

откуда

2√

− 3

12 − 4√

y1 =

= 0.1547 > 0,

y3 =

= 1.6906 > 0.

Глава 9.

Теория выпуклого программирования

Они неотрицательны, на рис. 9.14 это хорошо видно, следователь-

но, план −→ действительно оптимальный.

П р и м е р 2. В качестве контрпримера рассмотрим заведо-

= (2, 0)T

, расположенную в правом

мо неоптимальную точку −→1

нижнем углу множества планов.

Множества активных ограничений для нее: M (−→1) = {1},

) = 2 .

N (−→

{ }

Антиградиент и нормали в данной точке:

) =

g (X

) =

−→

−−→f (−→1

−→1

−−→2

−

Коэффициенты разложения по нормалям к активным ограниче-

ниям находятся из системы уравнений

y1 0 + v2 01

= 4 ,

−

откуда y1 = 0, v2 = −4. Коэффициенты разложения неположи-

тельны, план неоптимальный.

Замечание.

Кроме геометрической, условия оптимальности Ку-

на — Таккера имеют простую и наглядную физическую интерпре-

тацию. Представим себе шарик (рис. 9.15), скатывающийся под дей-

X )

−→f (−→

, которую мы интерпретируем как силу тяже-

ствием силы −

сти,

по

поверхности,

образованной гладкими ограничениями

X )

gi(−→

Согласно Третьему закону Ньютона, на шарик

действуют силы реакции поверхностей, которых

он данный момент касается (т. е. активных огра-

ничений). Эти силы ортогональны поверхностям

X )

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

gi(−→

стало быть, противоположны внешним нормалям

−→g

X )

(−→

Шарик достигнет минимума и остановится в

стационарной точке, где сумма всех сил, действу-

Рис. 9.15.

ющих на него, равна нулю:

) = 0,

) y

−→f (−→

−

−→

−

−→

−

= 0, j = 1, . . . , n.

9.6.. Частные случаи

т. е. там, где вектор антиградиента будет уравновешен равнодействующей сил реакции активных ограничений. При этом коэффициенты разложения y1 , y2 0.

9.6. Частные случаи

Если задача выпуклого программирования имеет общий вид

f (x1, . . . , xn) → min,

gi(x1, . . . , xn) 0, i = 1, . . . , m, x1, . . . xn 0, j = 1, . . . , n,

то для нее требуются все шесть, точнее 3m + 3n условий Куна—

Таккера (9.28):

X , Y )

∂L(→− →−

а)

X , Y )

г)

∂L(→− →−

∂xj

∂yi

б)

∂L(→− →−

= 0,

д)

X , Y )

= 0,

X , Y )

yi ∂L(→− →−

∂xj

∂yi

в) xj 0,

е) yi 0,

j = 1, . . . , n,

i = 1, . . . , m.

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

1. Неограниченность переменных по знаку. Пусть некоторые переменные xj неограничены по знаку: −∞ < xj < ∞. В таком случае д л я э т и х п е р е м е н н ы х условия «а», «б», «в» минимума функции Лагранжа по xj в неотрицательном октанте заменяются на одно классическое условие минимума на всей числовой оси

→− →−

∂L(X , Y )

∂xj

<<< < Предыдущая 1 2 3 4 56 / 276 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 > Следующая >>>

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

#
30.05.2015337.94 Кб84методичка, задачи микро.pdf
#
08.08.2019142.85 Кб3Методичка.Контрольная.Задачи..doc
#
11.11.2019401.41 Кб2Методичка_Микро_Лит_ТГУ.doc
#
26.11.2019506.88 Кб14Методологические проблемы клинической психологи...doc
#
02.05.2019118.27 Кб2Методы обучения рисованию в России.doc
#
26.03.20167.81 Mб187Методы оптимизации и исследование операций для бакалавров информатики. Часть 2.pdf
#
03.09.201979.36 Кб2методы проведения маркетинговых исследований.doc
#
30.05.201598.82 Кб26Методы психологии развития.doc
#
12.11.20191.96 Mб32МЕТОДЫ_РЕШЕНИЯ_ЗНЛП.doc
#
14.09.201935.16 Кб5Микробиология на госы.docx
#
10.11.2019233.98 Кб2Микроэкономика Лекции Г..А. Тарунина.doc