Lektsii_po_teorii_lineynogo_programmirovania

верхние {(x,µ) | µ ≥ h(x) ≡	x,b	− β},
и вертикальные {(x,µ) | h(x) ≡	x,b	− β ≤ 0}.

Однако ни одно нижнее полупространство не может участвовать в образовании надграфика, так как они ограничивают множество относительно оси ординат сверху, а надграфик сам неограничен сверху. Содержащие надграфик верхние полупространства как раз отвечают неравенству h(x) ≤ f(x), пересечение таких надграфиков афинных функций и является поточечной верхней гранью всех этих функций h(x).

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

Действительно,	пусть		есть
V ={(x,µ) | H (x) = x,b − β ≤ 0}		–	вертикальное

полупространство, содержащее надграфик f и пусть некоторая точка (x0 ,µ0 ) V , то есть H (x0 ) > 0 . Покажем, что найдется такое верхнее полупространство {(x,µ) | h(x) = x,b − β ≤ µ}, которое также содержит

надграфик f и не содержит точку (x0 ,µ0 ),h(x0 ) > µ0 ,

тогда вычеркивание полупространства V не увеличит объема пересечения полупространств. Во-первых, хотя

бы	одно		верхнее	полупространство
			l	в формировании
{(x, µ) | h(x) =		x,b	− β ≤ µ} участвует

надграфика f ведь этот надграфик ограничен снизу, т.к. функция f собственная.

11

Теперь мы имеем для любого x из Df : H (x) ≤ 0 и

h(x) ≤ f (x) . Значит, λH (x) + h(x) ≤ f (x) для любого λ ≥ 0 (это верно и для тех x, в которых значения f бесконечны, т.к. тогда f = +∞). Подберем λ0 так, чтобы в точке x0

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

λ0 H (x0 ) +h(x0 ) > µ0 ,

и потом положим h(x) ≡ λ0 H (x) +h(x) .

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

множество F*, состоящее из	всех пар	таких
(x*,µ*) n+1, что функции	h(x) ≡ x, x *	− µ *
мажорируются функцией f(x)
F* ≡{(x*,µ*) | h(x) = x, x * − µ* ≤ f (x)}.

Выписанное неравенство выполняется при всех x тогда и только тогда, когда µ* ≥sup{x, x * − f (x) | x Rn },

( Df =Rn) Таким образом	x
	F* является надграфиком
функции f * (x) ≡sup{x, x *	− f (x)}.
x

Определение 2. Функция f* : Rn→R называется

сопряженной	к	функции	f,	а	отображение
(x, f (x)) →(x*, f * (x*)) называется				преобразованием

Лежандра. Будем обозначать его .

Теорема 3. Пусть
f : Rn → R,	f С1 ,
f – строго выпуклая:
λ (0,1) ,	x, y Rn
12

f(λx + (1 − λ) y) < λf (x) + (1 − λ) f ( y)

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

Тогда f * (x*) = (Df )−1 (x*), x * − f ((Df )−1 (x)) .

Доказательство. Условие кофинитности означает, что

для любого x* Rn			множество
w(x*) ≡{x | x, x *			− f (x) ≥ 0}ограничено.
На ограниченном множестве w(x*) супремум
функции	x, x * − f (x)				превращается в максимум и
благодаря строгой выпуклости функции f достигается в
единственной точке. Так как						f C1 ,	эта	точка
максимума находится из условия обращения в нуль
производной.		− f (x)]|x=x			То			есть
0 = Dx [ x, x *					= x * −Df (x−)) . Как мы уже
				0	разрешимо относительно x0
получили,	это	уравнение
при любом x* Rn. Значит, область значения Df есть все
Rn и Df	отображает			Rn	на Rn	взаимно	однозначно
x0 = (Df )−1 (x*) и
f * (x*) = x0 , x *			− f (x0 ) = (Df )−1(x*), x *				− f ((Df )−1 (x*))
					.			□
Таким образом, мы получили другое определение
преобразования Лежандра:
	: (x, f (x)) →(x*, f * (x*)) , x* = Df (x) ,
	f * (x*) =< x*, x > − f (x) |x=(Df )−1(x*) .
Теорема 4. Пусть f – выпуклая функция. Тогда f*
является	замкнутой			выпуклой		функцией,		которая
					13

является собственной тогда и только тогда, когда f – собственная и f * = (cl f ) *, f ** = cl f .

Доказательство. Выпуклые несобственные функции – это только f (x) ≡ −∞ или f (x) ≡ +∞. Очевидно, что

эти функции взаимно сопряжены. Пусть теперь f – выпуклая собственная функция

f * (x*) = sup[ x, x * − f (x)].

x

Рассмотрим множество

F* ={(x*,µ*) | h(x) ≡< x, x* > −µ ≤ f (x), x}.

Оно задано нестрогим неравенством, выдерживающим предельный переход по (x*j ,µ*j ) → (x*,µ*), поэтому

замкнуто.	(x* ,µ* ) и				(x* ,µ* )
F* – выпуклое: если									таковы, что
	1	1				2	2
< x, x* > −µ* ≤ f (x) и < x, x*			> −µ*			≤ f (x) ,			то такое же
1		2			2
					*	*		*	*
				x1		+ x2	,	µ1	+ µ2		. В то
неравенство выполняется и для						2			2

же время очевидно

F* ={(x*,µ*) | µ* ≥< x, x* > − f (x), x}={(x*,µ*) | µ* ≥ f * (x)}

.

то есть

f * (x*) = inf {µ*| (x*,µ*) F *}.

µ*

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

Заметим, что F и F определяют одно и то же

множество своих опорных плоскостей, причем F является пересечением только верхних полупространств, определяемых этими опорными плоскостями (см.

14

доказательство теоремы 2). А это однозначно определяет F*, то есть f * = (cl f ) *.

Воспользуемся теоремой 2

f (x) =sup{h(x) | h(x) = x, x * −µ*}=

h≤ f

= sup {h(x) | h(x) = x, x * −µ* ≤ f (x)}=

(x*,µ*)

=sup x, x *

x*

= sup x, x * x*

sup[ x, x *

+	sup		=
		(−µ*)
	µ*, x,x* −µ*≤ f (x)
	inf
−		µ(x)		=
sup( y,x* − f ( y))≤µ( x)
	y

− f * (x*)]= f **(x) .

x*

□

Следствие. Преобразование Лежандра осуществляет взаимно однозначное соответствие множества всех замкнутых выпуклых функций на себя.

Теорема 5. Преобразование Лежандра осуществляет взаимно однозначное соответствие на себя и

подмножества	замкнутых	выпуклых	функций,
неотрицательных и обращающихся в нуль в нуле.
Доказательство.	f (x) = inf [f (x) − x,0 ]=
inf
x	x

= −sup[ x,0 − f (x)]= − f *(0) .

x

15

Если f (x) ≥ 0 и f (0) = 0, то 0 = inf f (x) = − f * (0) , т.е.

x

f * (0) = 0. Обратно, inf f * (x) = − f (0) = 0 , значит,

x

f * (x*) ≥ 0 .

□

Рассмотрим множество W пар функций {( f (x), g( y)}, удовлетворяющих неравенству

x, y ≤ f (x) + g( y)

и пусть ( f0 (x), g0 ( y)) наилучшие из них, то есть если

f (x) ≤ f0 (x) , g( y) ≤ g0 ( y) и ( f , g) W , то необходимо f = f0 , g = g0 . Предыдущие теоремы дают

такое

Следствие: множество {( f , f *)} есть множество

наилучших пар замкнутых выпуклых функций: для любых x, x* и любой собственной выпуклой функции f справедливо

x, x * ≤ f (x) + f * (x*) – неравенство Фенхеля. Функции, связанные преобразованием Лежандра

, называются двойственными. Приведем примеры пар двойственных функций.

Пример 2.	x * ln x * −x*, x* > 0
f (x) = ex , f * (x*) =	0,	x* = 0
		x* < 0
	+ ∞,
f (x) =| x |2 / 2 ,	f * (x*) =| x*|2 / 2,
	16

					1	− ln x,	x > 0
	f (x) =		−
					2
							x ≤ 0
			+ ∞,
				1	− ln(−x*),		x* < 0,
	f * (x*) =	−
				2
							x* ≥ 0.
		+ ∞,
	то есть f * (x*) = f (−x*).
	Заметим, что		f (x) =| x |2 / 2				– это самый узкий

инвариантный относительно преобразования Лежандра класс, состоящий только из одной функции.

До сих пор мы рассматривали выпуклые функции, определенные на всем пространстве Rn. Если же область определения C собственной выпуклой функции f есть часть Rn, C Rn то, очевидно, C – необходимо выпуклое множество. Введем индикаторную функцию множества

C:

0, x C, δ(x | C) =

+ ∞, x ≠ C.

Пусть f – замкнутая, а δ заменим замкнутой, положив δ(x | C) = δ(x | C ).

		f (x),	x
				C			– замкнутая
Тогда f (x) + δ(x | C ) ≡			x
		+ ∞,			C

выпуклая собственная функция с областью определения Rn и к ней применима описанная выше теория преобразования Лежандра.

17

Задача.	Найти		(δ|C)				и	показать,	что
(δ| C) = δ* (x*| C) = sup{x, x *							| x C}. Эта функция
				x
называется опорной функцией множества C. Нарисовать
δ* (x*) для C ={x | (x				−1)2	+ (x	2	−1)2 ≤1} R2.
		1
Теорема 6. So(b) – выпуклая функция.
Доказательство. Пусть b α = α b'+(1-α )b'', α (0,1),
	So(b') ≡< c, x'o> = min < c, x'>, Ax' ≤b'.
So(b'') ≡< c, x''o> = min < c, x''>, Ax'' ≤b''.
Положим	x α =	α xo'+(1-α )xo''.					Имеем Ax α ≤ b α		и
< c, x α > = α < c, x'o>+(1- α )< c, x''o> = α So(b') +
+ (1- α ) So(b'').		min <c, x> ≤ <c, x α > ≤ α So(b') +
А тогда So(b α )=

Ax≤bα

+ (1- α ) So(b'').

□

18

4. Определение двойственной задачи с помощью преобразования Лежандра

Определение 3. Двойственной задачей к Зо называется такая задача линейного программирования

(Зо)*: arg max <y,b>=?

(на некоторой области определения Ω R-m , являющейся выпуклым многогранником), для которой

< yopt, b > = Sо(b), где yopt= arg max <y,b>, у Ω.

Задача. Показать, что двойственная задача однозначно определена, если b>0.

Теорема 7 (Вычисление задачи, двойственной к Зо). (Зо)*: arg max <y,b>=? ATy=c, y ≤ 0 .

Доказательство. Применим преобразование Лежандра к функции Sо(b) ≡min {<c,x> | Ax ≤b}.

Sо*(y) ≡ max [<y,b>-Sо(b)] =

b

= max [<y,b>- min {<c,x> | Ax ≤b}] =

bх

=max [<y,b>+ max {-<c,x> | Ax ≤b}] =

bх

=max {<y,b>-<c,x> | Ax ≤b} =

b,x

= max max {<y,b>-<c,x> | Ax ≤b} = max I(b)

x

b

x

Если у≤0, то максимальное по b значение будет при b минимальном (допустимом), т.е. при b=Ax. Поэтому максимум по b будет равен [< y, Ax > − < c, x >]. Если у>0,

то, т.к. на b нет ограничений сверху, максимум по b будет равен + ∞).

19

Поэтому max I(b) =

		x
max	[< y, Ax > − < c, x >] при			y ≤ 0 и
x		+ ∞, при y > 0
S*(y)	=	max I(b)=	max < AT y − c, x >, если у ≤ 0
			x	+ ∞, иначе	=
		x
0,если у ≤ 0 и АТ = с,
+ ∞,если у ≤ 0 и АТ			≠ с,
	+ ∞, если у > 0

S**(b) = max [<y,b> - S*(y)] = max {<y,b> | ATy=c,y ≤0}.

y y

Таким образом, получаем двойственную к Зо

задачу

(Зо)*: arg max <y,b>=? ATy=c, y ≤0.

Замечание. Задачу (Зо)* можно превратить в

каноническую задачу

Зк': arg max <y',-b>=? ATy'=-c, y' ≥0. (yopt ≡- yopt').

Определение 4. Для задач канонической и нормальной (и другим) двойственными называются те, которые являются двойственными к общим задачам, эквивалентным первоначально поставленным.

Теорема 8. Задача, двойственная к двойственной, совпадает с первоначальной.

Доказательство. Пусть сначала была дана общая задача

Зо: arg min <c,x>=?, Ax ≤b.

Двойственная задача имеет вид

(Зо)*: arg max <y,b>=? ATy=c, y ≤0.

20