mo-crib-03

26. Теорема Куна-Таккера, доказательство достаточности.

	(1)	f (				) → min
				x
		~
	(2)		(x) £ 0, i = 1, m
		gi

задача выпуклого программирования т е и ~ явл выпуклыми

(1),(2) , . . f (x) _ _ g (x) .

функциями.

Условие регулярности Слейтера

x X (является внутренней точкой Х) и для неё выполняется ограничение:

~ £ =

gi (x) 0, i 1, m n-мерный объем (Х)

~

f (x), gi (x), i = 1, m - являются выпуклыми функциями.

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

n

~

(3) F (x, λ ) =

(x),

f (x) ¹ ∑λi gi

i=1

Теорема

Для того чтобы x * являлся оптимальным вектором задачи (1),(2) необходимо и достаточно: $λ * ³ 0 ,для которой λ ³ 0 выполняется след. соотношение

(4) f (x * , λ ) £ f (x * , λ * ) £ f (x, λ * ) ,т.е. f (x * , λ * ) -седловая точка функции Логранжа (3)в ней достигается min f (x, λ ) по x и max по среди " _ λ ³ 0

Док-во: Достаточность

Считается, что (4) выполняется для " _ λ ³ 0 . И покажем, что x * является решением з.(1)-

(2).

*

* ~

*

* ~

D £

f (x

(x

) £ f (x) + ∑

(x)

) + ∑λi gi

λi gi

i

i

D =

*

~

*

), "λ ³ 0 ___(5)

f (x

) + ∑λgi (x

i

*

~

*

) £ 0, i

= 1, m

выполняеться _ и _ λi λi

gi (x

(·)x * Î X

Является допустимым решением задачи (1)-(2).

Левое (∆) выполняется и при λi						= 0
* ~		*	) = 0
∑ Ai gi (x
i						* ~
							(x)
С учетом этого P (П) : f (x) + ∑λi gi
					i	{{
						³0 £0
						{
						£0

f (x * ) £ f (x) для "x Î X x * точка глобального min, т.е. оптим-я.

27. Теорема Куна-Таккера, доказательство необходимости.

	(1)	f (				) → min
				x
		~
	(2)		(x) £ 0, i = 1, m
		gi

задача выпуклого программирования т е ~ явл выпуклыми

(1),(2) , . . f (x) _ и _ g (x) .

функциями.

Условие регулярности Слейтера

x X (является внутренней точкой Х) и для неё выполняется ограничение:

~ =

gi (x) 0, i 1, m n-мерный объем (Х)

~

f (x), gi (x), i = 1, m - являются выпуклыми функциями.

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

n

~

(3) F (x, λ ) =

(x),

f (x) ¹ ∑λi gi

i=1

Теорема

Для того чтобы x * являлся оптимальным вектором задачи (1),(2) необходимо и достаточно: $λ * ³ 0 ,для которой λ ³ 0 выполняется след. соотношение

(4) f (x * , λ ) £ f (x * , λ * ) £ f (x, λ * ) ,т.е. f (x * , λ * ) -седловая точка функции Логранжа (3)в ней достигается min f (x, λ ) по x и max по среди " _ λ ³ 0

Док-во: Необходимость

Считаем, что x * является оптимальным решением задачи (1)-(2),необходимо найти: λ * ³ 0 , при котором выполняется (4)

Построим 2 вспомогательных множества точек:

		y0	′
			³ f	(x)
М (1) = {		(1) } y1	~
			³ g1	(x)				,		Î E n }
	y								x
		i...........

	~
						(x)
			ym ³ g m
			y0 f (		* )
				x
	M (2) = {		(2) } y1 0			};
		y
	......

ym 0

M (1) , M ( 2) выпуклые множества, неперсек-ся для них м. построить гипер пл-ть вида:

(V , y) = C, C = const

Разделяющую эти множества, для которой применительно к M (1) , M ( 2) :

(6) V T × y (1) ³ V T × y (2)

P (6) применительно к V ¹ 0 ; т.к. компонент y (2) не ограничено снизу и м. принимать

неограниченно большие значения V ³ 0

|| (6) справедливо и для нестрогого разделения M (1) , M ( 2)

f (

)

f (

* )

x

x

~

(1)

g1

(x)

(2)

=

0

Пусть y

=

, y

.....

.......

~

0

g m

(x)

Подставим в (6) и получим:

m

~

*

), "x Î X (7)

V0 f (x) + ∑Vi gi (x) ³ V0 f (x

i=1

V0 ¹ 0, очевидно.

Допустим, что это не так, т.е. V0 = 0 , тогда из (7) что

m	~	(x) ³ 0, "x Î X ,но этого не может быть, т.к. V	³ 0,V	¹ 0 , т.е. хотя бы один
∑Vi gi

i=1

компонент Vi 0 , но при этом в Х есть хотя б одна x , в котором по условию Слейтера:

~	(x) 0, i = 1, m
gi

Значит наше предположение не верно Vo ¹ 0 ,а именно Vo 0

λ*i

=

Vi

, i =

1, m

Vo

Тогда (7): V0

m

* ~

*

(8)

f (x) + ∑

(x) ³ f (x

), "x Î X

λi

gi

i=1

Азначит оно справедливо и для (·)x * , т.е.

m

*

)

+

* ~

*

)

*

* ~

*

) ³ 0;

(9) f (x

∑λi

gi

(x

³ f (x

); ∑λi gi

(x

{123

i=1 ≤0

≤0

m

* ~

*

= 0;

)

(10) ∑λi

gi

(x

i=1

(11)f (x * , λ * ) = f (x * ) , выполняется частично

P (8) с учетом (11) можем записать f (x, λ * ) ³ f (x * ) (12)

Разумеется, справедлива запись

*

*

m

~

*

(D) : f (x

) ³

f (x

(x

) (13)

) + ∑λi gi

i=1

Запишем (13) с учетом (11): (14) f (x * , λ * ) ³ f (x * , λ )

Объединим (12) и (14):

f (x * , λ ) £ f (x * , λ * ) f (x, λ * )

28. Развитие и обобщение метода Лагранжа, общая теорема математического программирования.

Развитие метода

f (

) ® min

(1)

x

~

(x) = 0, "i = 1, m (2)

gi

x j ³ 0, j = 1, n

(3)

f

~

(x), gi (x) являются выпуклыми непрерывно дифференцируемыми функциями.

Найдем набор необходимых условий для того, чтобы (x * ) являлась оптимальным планом задания (1) ÷ (3), а (x * , λ* ) седловой (×) функции Лагранжа.

P "компонента _ x *

1) x*j 0 к любому такому компоненту мы можем применять малые вариации увеличения и уменьшения применительно к f (x * , λ * )

¶f (x * , λ * ) =

0 (необходимое условие)

¶x j

2)

x*j = 0 можем только увеличить значение при анализе функции Лагранжа. Тогда

необходимое условие:

¶f (

* ,

* ) ³ 0

λ

x

¶x j

Окончательно весь набор необходимых условий:

*

*

*

m

~

*

, λ

(4)

¶f (x

)

=

¶f (x

)

+ ∑λ*i

¶gi (x

)

³ 0, j =

1, n

¶x j

¶x j

¶x j

i=1

(5)¶f (x * , λ * ) = 0, j = 1, n

¶x j

(6)x j ³ 0, j = 1, n

¶f (

* ,

* )

λ

~

x

*

(7)

) = 0, i

= 1, m

¶λ j

= gi (x

Обобщение метода

Задача вида:

f (

) ® min

x

~

Выпуклые gi (x) £ 0, j = 1, m

x j ³ 0, j = 1, m

Найдем набор необходимых условий:

Добавим yi ³ 0, i = 1, m , тогда получим (1), (2), (3) из «Развития метода» и применим к зад.

Условия (4) ÷ (7) из «Развития метода».

m

~

m

(x) + ∑λi yi ® min

f (x, λ , y) = f (x) + ∑λi gi

i=1

i=1

¶f (

* ,

* ,

* ) ³ 0, j =

λ

x

y

(1)

1, n

¶x j

× ¶f (

* ,

* ,

* ) = 0, j =

λ

(2)

x*j

x

y

1, n

¶x j

x*j

³ 0, j =

(3)

1, n

¶f (

* ,

* ,

* )

λ

x

y

*

(4)

³ 0, i = 1, m

¶y j

= λi

yi* × ¶f (

* ,

* ,

* ) = 0, i =

λ

x

y

(5)

1, m

¶y j

yi*

³ 0, i =

(6)

1, m

¶f (

* ,

* ,

* )

λ

~

x

y

*

*

(7)

(x

¶λ j

= gi

) + yi = 0

Из (4) следует, что λ*i

³ 0 для "i =

1, m

Из (5) следует, что в (.) (x * , λ * ) расширенная функция.

Из (5) следует, что y * , λ* = 0, i = 1, m; f (x * , λ * , y * ) = f (x * , λ * ) числено

		~			*
	В (7) заметим		(x			) выразим из предыдущего пункта:
		gi

¶f (

* , λ

* )

~

x

*

=

), i = 1, m;

( x

¶λi

g i

y i* ³ 0, i =

1, m

Таким образом

¶f (

* ,

* ) £ 0, i =

(9)

λ

x

1, m

¶λi

Тогда (9) с учетом (5) дает

¶f (

* , λ

* )

*

x

= 0, i

= 1, m (10)

λi ×

¶λi

Окончательно объединим (1),(2),(3),(8),(9),(10) получаем набор окончательных условий для седловой точки:

¶f (

* )

λ

x

³ 0

¶

x

*

*

, λ

¶f (x

)

*

×

= 0

x

¶

x

*

³ 0

x

¶f (

* , λ

* )

x

£ 0

¶λ

*× ¶f (

* ,

λ

* )

x

λ

= 0

¶λ

*

λ

³ 0

ОТМП

Для того, чтобы точка x * ³ 0 являлась (.) глобального экстремума функции на множестве ограничений (2),(3), т.е. на выпуклом множестве, необходимо, чтобы $λ* ³ 0 , при котором выполняются необходимые условия:

1)	Для [f (					) ® min]
				x
	f	¢(			* ,			* ) ³ 0
							λ
			x
	x

(x * , f

¢(x * , λ* )) = 0, x * ³ 0

x

¢

f

(x * , λ* ) £ 0

λ

(

* , f

¢

(

* ,

* )) = 0,

* ³ 0

λ

λ

λ

x

λ

2)

2) Для [f (

) ® max]

x

f

¢(

* ,

* ) £ 0

λ

x

x

(x * , f

¢(x * , λ* )) = 0, x * ³ 0

x

¢

f

(x * , λ* ) ³ 0

λ

(λ* , fλ¢ (x * , λ* )) = 0, λ* ³ 0

|| Если функция и множество строго выпуклые эти условия достаточные.

29. Общая теорема математического программирования, условия оптимальности для задач квадратичного программирования.

ОТМП

Для того, чтобы точка x * ³ 0 являлась (.) глобального экстремума функции на множестве ограничений (2),(3), т.е. на выпуклом множестве, необходимо, чтобы $λ * ³ 0 , при котором выполняются необходимые условия:

1)

Для [ f (

) ® min]

x

f

¢(

* ,

* ) ³ 0

λ

x

x

*

*

*

*

, λ

x¢(x

)) = 0, x

³ 0

(x

, f

f

¢

(

* ) £ 0

* , λ

x

λ

(

*

, f

¢

(

* ,

* )) = 0,

* ³ 0

λ

λ

λ

x

λ

2)

2) Для [ f (

) ® max]

x

f

¢(

* ,

* ) £ 0

λ

x

x

*

*

*

*

, λ

x¢(x

)) = 0, x

³ 0

(x

, f

f

¢

(

* ) ³ 0

* , λ

x

λ

(

*

, f

¢

(

* ,

* )) = 0,

* ³ 0

λ

λ

λ

x

λ

|| Если функция и множество строго выпуклые эти условия достаточные.

Условия для задач квадратичного программирования.

		m
f (		) = ∑c j x j	+ (d11 x12 + d 22 x22 + ... + d nn xn2 + 2d12 x1 x2 + 2d13 x1 x3 + ... + 2d n−1,n xn−1 xn ) ® max
	x
		j =1
			n
			∑ aij x j = bi , i =		1, m
			j =1
			x j ³ 0, j =
				1, n

f (x) строго вогнута.

Тогда, на выпуклом множестве для такой f (x) ОТМП является достаточным условием:

с

b

x

1

1

1

с2

b2

x2

с =

, b =

, x =

, Am×n

..

..

..

cn

bm

xn

d

d

... d

11

12

1n

d

21

d 22

... d 2n

D =

..................

d n2

d n1

... d nn

Запишем з. в векторном виде:

T

T

f (x) = c

x + x

Dx ® max

= b

Ax

x ³ 0

Функция Лагранжа для f (x) :

f (x, λ ) = c T x + x T Dx + λ T (b - Ax)

Запишем f (x) с использованием матрицы Гессе:

f (x) = c T x + 1 x T Hx

2

Применим ОТМП к функции Лагранжа:

(1) ¶f (x * , λ * ) = c + 2Dx * - AT λ * £ 0

¶x

(2) x * × ¶f (x * , λ * ) = 0

¶x

(3)x * ³ 0

(4)Ax * = b

Добавляем в левую часть (1) дополнит. перемен-еV ³ 0 , тогда получим:

(5)c + 2Dx * - AT λ * + V * = 0

(6)V * = -c - 2Dx * + AT λ * ³ 0

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

2Dx

* - AT

λ

* + V

= -

c

*T

×V = 0

x

* = b

Ax

*

³ 0,V ³ 0

x

Если для такой задачи существуют вектора x 0, λ 0,V 0 , то исходная задача разрешима.

30. Метод Била.

T

T

f (x) = c

x + x

Dx ® max

= b

квадратичная форма

Ax

x ³ 0

Х - выпуклое множество. f (x) - вогнутая функция.

Алгоритм начинает работу от 1ДБР исх. зад.

Пусть мы нашли такое 1ДБР, т.е. т БП выразили через остальные xm+1 , xm+2 ,...., xn - НБП и получили:

x

= ...

1

= ...

x2

БП

........

= ...

xm

x j ³ 0, j = 1, n

f (

) = (c

+ c

x

+ c

x

+ ... + c

x

) ×1 + (c

+ c

x

+ c

x

+ ... +

x

0,m+1

m+1

0,m+2

m+2

m+1,0

m+1,m+1

m+1

m+1

m+2

0,0

0,n

n

+ cm+1,n xn )xm+1 + ... + (cn,0 + cn,m+1 xm+1 + ... + cn,n xn )xn ® max

∂f (

) £ 0, i =

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

x

(!)

1, m

¶xi

	1	¶f (		) = ch,0 ; f (		) = c0,0 - должныполучить
			x
					x
	2
		¶xh
	¬ cij = c ji

Допустим, что c0,m+1 0 , тогда если мы увеличим xm+1 и вводить V в очередной базис, то f (x) будет возрастать.

// В обычном симплекс-алгоритме мы бы V увел., пока к-л БП обратилось в «не существует», но здесь возможно что

1∂f (x) обратиться в «не существует» раньше какой либо БП и тогда при продолжении

2¶xm+1

увеличения скобка с xm+1 станет принимать отрицательные значения f (x) будет убывать, что недопустимо.

При исполнении симплекс-алгоритма, может возникнуть ситуация, что:

	1	∂f (		)
xh ,			x		= 0
	2	¶xh

В этом случае вводим новую переменную, неограниченную знаком:

		1		∂f (		)
u1	=				x
				¶xh
	2
xh	= ...

В начале очередной итерации НБП будут все прежние, за исключением xh и +переменная u1 ; а БП будут прежние + xh

Поскольку u1 неограниченна по знаку, то если:

1) ∂f (

) 0 то значение u

x

надо увеличить

¶u1

1

∂f (

) = 0

При этом f (

) будет возрастать. u увеличивать необходимо до тех пор, пока

x

x

1

¶u1

2) ∂f (

) 0 то значение u

∂f (

) = 0 . При этом значение f (

) будет

x

надо уменьшать, пока

x

x

¶u1

¶u1

1

также возрастать.

¶f

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

равны «не существует», то проводим анализ

по всем ui

¶ui

∂f (

) (по НБП)

x

¶xh

Если все ∂f (

) £ 0 , то мы получим max значение

x

f (

) :

x

¶xh

f (x) = 10x1 - x12 + 2x1 x2 - 2x22 ® max x1 + 2x2 £ 10

x1 + x2 £ 6 x1 , x2 ³ 0