книги / Математические методы принятия решений

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

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

Рассмотрим некоторые примеры перехода от задачи математи­ ческого программирования к задаче безусловной минимизации ме­ тодом внутренней точки.

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

f(x ) = Х \ + Х 2

при ограничениях

gi(x) = - x ] + х 2 ^ 0 ,

д2(х) = £ 1 ^ 0.

Р е ш е н и е . Построим логарифмическую штрафную функцию

L(x, г) = £ 1 + х 2 - г	1п(—х\ + x 2) — r In Х\.
Определим точки минимума	L(x, г) аналитически, так как

L(x, г) дифференцируема в рассматриваемой области. Для нахож­ дения xi(r) и £2(г) получим систему уравнений

дх\	—х] + х2 х\
дх2	—х] + х2
Отсюда найдем	-1 ± V T T 8f

£i(r) =

Рис. 5.14. Графическое решение задачи математического програм­ мирования методом внутренней точки

(здесь оставим только знак -h, так как х\ ^ 0),

х 2( г ) = (-1 + VTT8F)2 + г. 16

Заметим, что значения x i(r) и х2(г) удовлетворяют условию положительной определенности матрицы V 2L. Пусть г последо­ вательно принимает значения 1,0; 0,5; 0,25; 0,1. Соответственно получим последовательности значений

х\(г) = 0,50; 0,309; 0,183; 0,085;

х2(г)= 1 ,2 5 ; 0,595; 0,283; 0,107,

сходящиеся при г —> 0 к точке (0,0). Графическое решение данной задачи представлено на рис. 5.14.

В общем случае в задачах (при слабых условиях регулярно­ сти) существует последователь­ ность безусловных локальных минимумов, сходящаяся к каждо­ му из условных локальных мини­ мумов.

Рассмотрим еще пример ре­ шения задачи линейного про­ граммирования методом внутрен­ ней точки.

Пример. Минимизировать х\ при условии <7i(х) = х\ > 0.

Р е ш е н и е . Построим логарифмическую штрафную функцию

L(x, r) = x 1 — г In x i.

Для существования минимума должно выполняться необходимое

условие	dL _	dL_ _	j _ Л _ Q
	dx1	дх\	xi
Откуда получаем xi(r) = г.
d}L	г
Из условия	= ^2 > 0 следует, что для г < 1 безусловный ми­

нимум будет при х(г) = г.

§ 5.9. Методы внешней точки для решения задачи математического программирования

Попытаемся приблизиться к оптимальной точке из недопусти­ мой области. По аналогии с методами внутренней точки надо вы­ брать функцию 0(д(х)) так, чтобы каждая из функций Т(х, tk) = = f(x) + tkO(g(x)) имела конечный минимум (при каждом tk > 0). Это достигается, если для любой неограниченной последователь­ ности значений tk функция tkO(g(x)) стремится к +оо быстрее, чем f(x) стремится к —оо. Поэтому {i^} —возрастающая неогра­ ниченная последовательность положительных чисел, или tk = 1 /гк, если 0 < Гк < 1.

Преобразуем достаточные условия локального минимума задачи математического программирования следующим образом:

1) рассмотрим ограничения в ослабленной форме:

д%{х)^-г, г = 1,2, . . . , т , г > 0 ;	(5.26)
2) преобразуем условие дополняющей нежесткости u*gi{x*) = 0
так, чтобы оно имело смысл для отрицательных	значений дг(х)

и сводилось к исходному условию при г —►0 (это означает, что щ(х*) = 0 при gi(x*) Ф 0; если gi(x*) = 0, то щ(х*) принимает лю­ бые значения), т. е.

	щ(г) = -	min{0; &(ж(г))}.	(5.27)
Отсюда если	г > 0 мало,	х(г) удовлетворяет условию (5.26)
и gi(x(r)) ф 0 для	некоторых	г, то щ = 0 и lim и(г) = щ(х*) = 0.
		г—>0

Если gi(x(r)) < 0, то lim (—min{0, gi(x(r))}) = 0, так как из неравен- г—>0

ства (5.26) следует, что х(г) при г —►0 принадлежит допустимой

области. В силу (5.26) gi(x(r)) ^ —г, а из равенства (5.27) вытекает,
что lim щ{г)г = 0, поэтому lim щ{г)д^х{г)) = 0.
г—*0	г—>0

Условие дополняющей нежесткости в данном случае выполня­ ется в пределе при г —» 0 (из соотношения (5.27) следует, что щ ^ 0, г = 1,2, ...,ш ) .

Аналогично преобразуют другие достаточные условия:

Щ ( г ) ^ 0, г =1,2, ...,тп,

in
V /(x (r)) - 1 J ]	Ui(r)Vgi(x(r)) = О, t = - ,	(5.28)
i =	1
и для каждого вектора у,	для которого yrV g i(x (r)) = 0	при всех

i е D* = {г | и* > 0}, справедливо неравенство

Подставляя (5.27) в равенство (5.28), получим

1

V/(æ (r)) + 2 7 min{°; 9 i(x (r))}V g i{x {r)) = 0. i= 1

Опять непосредственной проверкой убеждаемся в том, что функ­ ция, для которой выполняются приведенные достаточные условия существования точки минимума, имеет вид

m

T(x(r)) = f(x) + 2 2^ (m in(°’ 9 i(x (r))})2

Это и есть функция, минимизируемая методом внешней точки. В нее могут входить ограничения и в виде неравенств, и в виде равенств. Можно доказать, что все необходимые условия миниму­ ма этой функции выполняются, например V 2T есть положительно определенная матрица. Причем для ограничений-неравенств имеют место соотношения

(min{0; gi(x(r))})2 = £î-_j£îl

Если среди ограничений в задаче математического программи­ рования есть ограничения-равенства hj{x) = 0, j = 1,2,..., то мож­ но записать

gji(x) = hj(x) ^ 0, gj2(x) = —hj(x) ^ 0, откуда gji = - g j2, или

I j pbi-lgjilj2 + j~- g j i - | - g 3ilj2) = £я = h2M r))

Рассмотрим пример применения метода внешней точки для ре­ шения задачи математического программирования.

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

f(x) = - x \Х2

при ограничениях

gi(x) = - x i - x l + 1 ^ 0 , g2(x) = x i +Х 2 ~^0 .

Р е ш е н и е . Составим функцию штрафа для метода внешней точки:

Т ( х , г ) = —х \ х 2 + (-*.-^ +l-|-*.-*i +l|)2 +{ x x+ X 2 - \ x , + x t f

	от		от
Из необходимых условий экстремума ^— = 0,				= 0 определим
последовательности значений х\	и х 2, сходящиеся к решению.
	Зададим		последовательность
	значений г: 1,0; 0,5; 1/3; 0,1;
	получим	соответствующие			по­
	следовательности			значений х\(г):
	0,89; 0,77;	0,73;		0,67; х 2(г): 0,64;
	0,62; 0,61; 0,58.
	Последовательность значений
	х \(г) сходится к 2/3, а последова­
	тельность значений х2(г) — к \/3 /3
	(рис. 5.15).
	Метод внутренней точки и ме­
ние задачи математического про­	тод внешней		точки основаны		на
граммирования методом внеш­	разных принципах: в первом слу­
ней точки	чае штрафной		член препятствует

нарушению ограничений, во втором — он предотвращает блуждание точек слишком далеко от допустимой области.

§ 5.10. Комбинированный метод внутренней и внешней точек

Введем параметры г и t = 1/г и рассмотрим комбинированную функцию

У(х, г, 0 = f{x) + s(r)L(x) + p(t)T(x),

где s(r) — функция от г, г —*• 0, для метода внутренней точки; Ь(х) — функция штрафа для метода внутренней точки; p(t) — функция от t,

t —» оо, для метода внешней точки; Т{х) — функция штрафа для ме­ тода внешней точки; f(x) — целевая функция задачи математическо­ го программирования.

Покажем на примере, как применяется комбинированная функ­ ция V ( x , r ,t ) для решения задачи математического программиро­ вания.

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

f(x ) = In х\	-	хг
при следующих ограничениях:
g(x) = xi -	1 ^	О,
h(x) = ж, + х\ —4 = 0,	или X2 = 4 — XI .

Р е ш е н и е . Построим комбинированную функцию

V(x, г, t) = In xi — Х2 — г ln(a;i —1) + г		’(æf + х\ —4)'
/(*)	s(r)L(x)	№Т(х)

С помощью этой комбинированной функции мы избежали исполь­ зования модулей \д(х)\, которые появляются в методе внешней точ­ ки. Из необходимых условий существования минимума функции

V(x, г, t) имеем

dV	1	г	1/_2
дх\	х\	я, —1 + '~‘'	v“4

^ - = - 1 + 4 х2Г~1(х] + Х2 —4) = 0.

0X2

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

4г 1(я 1 + ^2 —4) = ^ - =

y / 4 - x

	Зададим	последовательность	значе­	Рис. 5.16. Графическое
				решение	задачи матема­
	ний для г:	1,0; 1/4; 1/16; 1/64;	1/256,
				тического	программиро­
	и получим соответствующие ей последо­			вания с помощью комби­
	вательности значений:			нированного метода

xi (г):	1,553;	1,159;	1,040;	1,010;	1,002,
х2(г):	1,334;	1,641;	1,711;	1,727;	1,731,

V:-0,2648; -1,0285; -1,4693; -1,6447; -1,7048.

Последовательности значений х\ и х 2 сходятся к оптималь­ ному решению (1, -\/3). Графическое решение задачи математи­ ческого программирования комбинированным методом приведено на рис. 5.16.

§ 5.11. Метод проекции градиента

Известны и другие методы безусловной оптимизации для ре­ шения задач математического программирования. Одним из таких методов является метод проекции градиента (МПГ). Метод бази­ руется на методе градиентного спуска безусловной оптимизации; МПГ — численный метод условной оптимизации для нелинейных задач. Рассмотрим задачу

m in{/(x)} при х е D,

(5.29)

где D —замкнутое выпуклое множество в Rn, /(х ) — дифференци­ руемая функция на D.

Проекцией точки а на множество D называется точка апр, бли­ жайшая к а среди всех точек D, т. е. апр является решением задачи

проектирования:

ср(х) = ||х —о||2 —►min, x e D .

(5.30)

Свойства проекции точки на множество D определяются следу­ ющими леммами и теоремой.

Лемма 1. Пусть D —замкнутое выпуклое множество в Rn . Тогда:

1) проекция апр любой точки а е Rn существует и единственна; 2) точка х является проекцией точки а на множество D

(х = апр) в том и только в том случае, если

(х — а, а —х) ^ 0 при всех х е D;

3) для любых точек a i, а2 Е Rn справедливо неравенство

||а 1пр — ° 2 п р || ^ | | o i — O2 II»

т. е. оператор проектирования обладает свойством нерастяжения.

Д о к а з а т е л ь с т в о . 1) Функция ф(ж) является строго выпук­ лой, поэтому решение задачи (5.30) существует и единственно.

2) На выпуклом множестве и при выпуклой функции ф(ж), если ж* — локальное решение задачи (5.29), должно выполняться условие

	(фх(ж*), х — х*) ^ 0,		же D.
Производная ф'(ж ) равна 2(х — а), т. е. 2(х* — а, а — х*) ^ 0.
3) В силу утверждения 2) имеем
(&1пр Оь Û2np Ûinp) ^ 0, (û2np			Û2, Oinp ~ Û2np) ^	0*
Суммируя эти неравенства, получим
(^lnp	Û1	&2пр "Ь ®2» ®2пр	0]Пр) ^ О,
откуда в силу неравенства Коши—Буняковского имеем
||0 1пр — Û2np|P ^	(û2np ~	û lnp» а 2 ~ a i) ^	||a lnp — ®2прЦ ||°1	— Û2||-

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

Лемма 2. Пусть множество D выпукло и замкнуто, функ­ ция /(ж) выпукла на D u дифференцируема в точке х* е D. Тогда х* является решением задачи (5.29) в том и только в том случае, если

X*=(x*-0Lf'(x*))пр

при произвольном a > 0.

Д о к а з а т е л ь с т в о . Согласно утверждению 2) леммы 1 приве­ денное равенство эквивалентно условию

(ж* - (х* - a / V ) ) , х - х*) > 0 V x e D .

Поэтому

( / '( ж * ) , х - ж * ) ^ 0 Vxe D.

Это неравенство является условием того, что х* — решение за­ дачи (5.29). Лемма доказана.

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

точек

x k+l= x k -<xkf ( x k), fc = 0 ,1 ,2 , ...

в методе проекции градиента на каждой к-й итерации требуется производить операцию проецирования точки на множество D, т. е.

решать задачу (5.30) при

а= х к - akf'( x k).

Вкачестве очередной точки приближения к решению зада­ чи (5.29) выбирается точка

x k+l= ( x k - a kf ( x k))np, к = 0 ,1 ,2 , ...

(5.31)

Сходимость последовательности (5.31) к решению задачи (5.29) вытекает из следующей теоремы.

Теорема. Пусть множество D выпукло и замкнуто, функция /(х (6)) строго выпукла на D при 0 > 0 и дифференцируема на D , причем ее градиент удовлетворяет условию Липшица:

|| f i x ) - f ' ( x l)\\ ^ М\\х - х 1 1|, х, х 16 D.

Тогда последовательность, генерируемая по правилу (5.31), где х° — произвольная точка из D, a ctk = а е (0 ,40/М 2), сходится к реше­ нию х * задачи (5.29) со скоростью геометрической прогрессии:

\\xk+' - x * \ \ ^ q \ \ x k -x*\\,

где q = V I - 49а + а2М 2 е (0,1). Доказательство этой теоремы не приводится.

Конкретных рекомендаций для выбора константы 6 не суще­ ствует, поэтому значения а выбирают опытным путем. В общем случае на каждой итерации необходимо решать задачу (5.30). Однако для некоторых видов множеств D удается получить явную формулу для проекций.

1) Если D —шар: D = { х е R” | ||х —х ° | | 2 ^ г}, то

о	а — х °
Опр — X	-jj	л|7 т .
	||а -х ° ||

2) Если D —координатный параллелепипед:

D = {х е Mn|6j ^ Xj ^ Cj, j = 1,2, ... , n},

то

bj,	если	dj < bj,
a j пр — û j,	если	by ^ Qj ^ Cy,

если a j > C j.

3)Если D — неотрицательный ортант:

D = {х е Rn | Xj ^ 0, j = 1,2,..., п},

то

опр = (m ax{0,ai}; ...; т а х { 0 ,о п}).

4) Если D — гиперплоскость: D = {х е Мп | (р, х) = (3}, р Ф 0, то

a np = a + ( p - ( p , a ) ) | | j 5 .

5) Если D — полупространство: £>= {xeR n |(p ,x )^p } , рФ 0, то

anp = a + max{0; р - (р, а)}

6) Если D — аффинное множество: D = (х е Rn | Ах = Ь}, стро­ ки матрицы А линейно независимы, то

опр = о - АТ(ААТ)~1(Аа - Ь).

Если множество D задается сложной системой равенств и нера­ венств, то метод проекции градиента практически не применим, в этом случае задача (5.30) не проще исходной задачи.

Пример. Решить задачу математического программирования:

/(х ) = х] —2xi —Х2 ~* min

при X, + х\ ^ 4.

Здесь множество D — круг радиуса г = 2 с центром в начале ко­ ординат хо = (0,0). Последовательность точек в методе проекции градиента задается формулой

	Q	Ci	X		(5.32)
	а"Р=Х ~	||а — х°|| г,
где х° = (0 ,0)т — нулевое приближение. Пусть					= а = 0,1. Вычис­
лим производные:
df(x)	дКх) _	дН0,0) _		2	df(0,0)
дх\ = 2xi - 2,	дХ2	5	x i	’	дх2

тогда согласно соотношению (5.32) определим точку а 1 = (0,2; 0,1),