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

170Глава 12. Многомерная оптимизация с ограничениями

Вэтих условиях направление спуска должно быть направ-

→−

лено не по антиградиенту, а на некоторую точку s , лежащую

в н у т р и (или на границе) допустимой области. Разумно потре-

−→ −→ −→

бовать, чтобы она была как можно ближе к точке X k −tk f (X k), т. е. представляла собой п р о е к ц и ю этой точки на область D

(см. определение проекции точки на множество на с. 21). В нашем
		p						−−→	есть
примере это точка →− . Соответственно вектор движения								k
t	→− f (→−			)		D		X p
			k		на		.
проекция −	k	X

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

Изложение метода начнем с более простого слу-

Линейные ограничения- чая, когда ограничения заданы в форме линей-

равенства

ных р а в е н с т в без условий неотрицательно-

сти переменных, то есть когда множество допу-

стимых решений (планов) представляет собой аффинное множество (см. определение на с. 20). В этом случае оптимизационная задача имеет вид

X )	→	min,		(12.4)
f (→−		→−
→−
AX	= b .
		a T	, где	a
Здесь матрица A составлена из строк →− i				→− i — направля-

ющие векторы (векторы нормалей) гиперплоскостей, определяющих аффинное множество.

Функция Лагранжа для поставленной задачи равна

L(→− →− →− →−	→− − →−
X , Y ) = f (X ) + Y	T (AX b ).

Дифференциальные условия Куна — Таккера в частном случае классической задачи с ограничениями-равенствами согласно (9.35) запишутся в сокращенном виде

12.3.. Метод проектирования градиента								171
	→− L(→− →−			→− →−		→−	= 0;
а, б, в)		X , Y ) =			f (X ) + AT Y			(12.5)
г, д, е)	G (X ) = AX				b = 0.			(12.6)
	→− →−		→− − →−

Геометрический смысл этих условий вполне прозрачен: выражение (12.6) означает, что оптимальный план должен принадлежать допустимому множеству, а равенство (12.5), если его переписать в

→− f (→−		→−	m
			i		a
виде −	X ) = AT Y =				→− i, требует, чтобы в точке оптиму-
			y	i

=1

ма антиградиент целевой функции был равен линейной комбина-

→−

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

Метод описывается следующей релаксационной процедурой.

	X		k		X )
Пусть	→−	k — исходная точка на		→− f (→−		k	— градиент це-
				-м шаге,

левой функции в данной точке. В качестве направления движения

d	берется проекция антиградиента на допустимое множество,
→− k
		d		=		P		X )			P
которая равна		→−	k		−		→− f (→−		k	, где матрица проектирования
определяется выражением (9.4)

P = I − AT (AAT )−1A.

Следующая точка определяется по обычному правилу →− k+1 =

= →− k

→− k, где

X

t > 0

— некоторым образом выбранная длина

X

+ t d

шага.

Данная рекуррентная процедура обладает рядом полезных

свойств.

→− k

→− k

при любом

принадлежит допу-

1. Точка →− k+1

t

X

= X

+ t d

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

→− является возмож-

d

ным (feasible). Для доказательства вычислим

→−

→−

→−

→−

tP

→−

f ) =

AX

k+1

= A(X

k

+ t d

k

) = A(X

k

−

172

Глава 12. Многомерная оптимизация с ограничениями

=

→−

tA

[I

(

AAT

)−

1A

] =

→−

[

A

(

AAT

)(

AAT

)−

1A

]→−

f

=

b

−

−

AT

b

−

t

−

=

→−

t(A

IA)

→−

f

=

→−

t(A

A)

→−

f

→−

b

−

−

b

−

−

=

b .

2. Направление

→− k является понижающим (прогрессив-

d

ным). Рассмотрим одномерную функцию сечения

X

+ t d

)

(12.7)

ϕ(t) = f (→− k

→− k

и вычислим ее производную при t = 0. Дифференцируя сложную функцию и учитывая положительную определенность матрицы

проектирования, имеем

→− k

−→−

→− k)P →− f (→− k

∂t

(t=0

→−

→− k

∂ϕ(t)

(

=

T f (X

) d =

T f (X

X ) 0.

(

Критерий(

окончания поиска устанавливается следующим

утверждением.

3. Если на некотором шаге

→−

= P →− f (→−

) = 0,

(12.8)

d

k

X

k

то

→− k — точка оптимума. Действительно, подставив сюда мат-

X

рицу проектирования, имеем

→− →− ) =

-

I A (AA )− A

→− f (→−

) =

= f (X ) + A

(AA

A f (.

P

f (X

k

−

T

T

1

X

k

→−

→− k

/−

−

→−

→− k

)

0

(12.9)

T

T )

1

X

= 0.

Сравнивая (12.9) с (12.5), видим, что это есть необходимое условие экстремума, в котором вектор множителей Лагранжа равен

→−	=		(AAT	)−	A→− f (→−			).
Y		−		1		X	k		(12.10)

Доказанные свойства приспосабливают градиентный метод

к наличию ограничений в форме линейных равенств. Если длину

−→ −→

шага выбирать по правилу tk = arg min ϕ(t) = f (X k + t d k), то мы получим метод поиска минимума, аналогичный методу наискорейшего спуска в безусловной оптимизации.

12.3.. Метод проектирования градиента

173

Метод Перейдем к случаю, когда ограничения задачи сфорактивного мулированы в виде неравенств (ограничения на ненабора отрицательность включены в общий список):

f (→−

→

min,

f (→−

→

min,

X )

T

X )

→−

i

a

или

→− i

X

,

(12.11)

→−

→−

b

AX

b ,

i = 1, . . . , m,

→− T

где a i обозначает i-ю строку матрицы условий A.

В этом частном случае (ограничения на неотрицательность переменных отсутствуют) условия оптимальности Куна — Таккера имеют вид

			→− →− →−			→− →−		→−	= 0;
а, б, в)				L(X , Y ) =			f (X ) + AT Y			(12.12)
г)	G (X ) = AX				b		0;			(12.13)
	→− →−			→− −	→−
д)	Y (AX			b ) = 0;						(12.14)
	→−		→−	− →−
е)	Y		0.							(12.15)
	→−

Здесь выражение (12.13) по-прежнему означает допустимость оптимальной точки, а равенство (12.14) есть условие дополняющей нежесткости, которое требует, чтобы множители Лагранжа, соответствующие неактивным ограничениям, обращались в нуль. Оно становится очевидным, если его переписать в виде

	m	→−
	y ( a				) = 0.
д)	i	T X	b	i
	i →− i		−
	=1

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

Таким образом, при вычислении множителей Лагранжа и проверке на оптимальность по критерию (12.12) можно учитывать только активные ограничения, считая их строгими равенствами. Задача частично свелась к оптимизации с линейными ограничениями-равенствами, рассмотренной выше.

174Глава 12. Многомерная оптимизация с ограничениями

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

По д г о т о в и т е л ь н ы й э т а п

−→

Выбирается любая допустимая начальная точка X 0. Так как ограничения задачи линейны, то для нахождения точки, принадлежащей допустимой области, можно воспользоваться методом

искусственного базиса в линейном программировании [9, с. 100].

→−

Если b 0, то в качестве начальной может быть взята нулевая точка.

И т е р а ц и я

Шаг 1. Проверка на оптимальность. Для текущей допу-

−→

стимой точки X k определяется список, насчитывающий q актив-

ных ограничений (активный набор)1. Без ограничения общности их можно считать первыми, т. е.

a	T X			= b	, i = 1, . . . , q,
		→−	k
→− i				i
a	T X			< b	, i = q + 1, . . . , m.
		→−	k
→− i				i

Если активные ограничения действительно имеются (q 1),

то составляется матрица Aq	размера q × n, состоящая только из
a T , i = 1, . . . , q		, после чего на ее основе вычис-
активных строк →− i
ляется матрица проектирования
Pq = I − AqT (Aq AqT )−1Aq .
Текущая точка →− k является оптимальной, если выполняются
X

два условия:

1В некоторых публикациях активный набор ограничений называют рабочим

списком.

12.3.. Метод проектирования градиента

175

1) антиградиент представляет собой линейную комбинацию внешних нормалей к активным ограничениям. Это соответствует условию (12.12), которое, как следует из (12.9), превращается в

P

→− f (→−

k

) = 0;

(12.16)

q

X

2) множители Лагранжа, вычисляемые по формуле (12.10), не-

отрицательны:

−→

= (

y

, . . . , y

)T =

(A

AT )

−

1A

→−

→−

)

0.

Y

−

q

f (X

k

(12.17)

1

q

q

q

Если же активный набор пуст (q = 0), т. е. точка

→− k находится

X

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

более простой вид

→− →−

f (X k) = 0.

Шаг 2. Определение направления поиска. Если условия

оптимальности не выполняются, нужно идти к следующей точке

−→

X k+1 с меньшим значением целевой функции. Здесь возможны

различные варианты.

−→

В а р и а н т А. В простейшем варианте точка X k лежит

внутри допустимой области и активные ограничения отсутствуют (q = 0). Тогда направление поиска совпадает с антиградиентом:

		→−	k	=		→− f (→−		k	).
		d			−		X
В а р и а н т Б.	P	→− f (→−				)	= 0
		q			k		. Этот вариант соответствует

−→

ситуации, когда 1 q < n, и точка X k лежит на границе допу-

стимого многогранника, представляющей собой аффинное множество Dq , образованное пересечением q гиперплоскостей, но не в его вершине. Тогда в качестве направления поиска выбирается проекция антиградиента на это аффинное множество:

→−

=

P

→−

→−

).

d

k

−

q

f (X

k

В а р и а н т В.

→− f (→−

k

) = 0

, но хотя бы один из множите-

q

X

P

лей Лагранжа y1, . . . , yq отрицателен. Этот вариант соответствует

176 Глава 12. Многомерная оптимизация с ограничениями

ситуации, когда число гиперплоскостей в активном наборе совпадает с размерностью пространства (q = n), следовательно, аффинное множество, на которое происходит проектирование, имеет размерность 0 и представляет собой точку — вершину допустимого многогранника (см. замечание 3 на с. 24).

Для того чтобы проектирование стало возможным, одну из гиперплоскостей из числа тех, для которых yi < 0, следует удалить из активного набора. Например, это может быть гиперплоскость с

−→

минимальным значением a i yi. Соответствующая строчка удаляется из матрицы Aq , получается матрица Aq−1, определяющая аффинное множество Dq−1 размерности 1 (ребро многогранника). Пересчитывается матрица проектирования

Pq−1 = I − ATq−1(Aq−1ATq−1)−1Aq−1,

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

ента на Dq−1:	d			= P	→−	f (X		).
	→−					→−
			k		q−1		k
Шаг 3. Определение предельной длины поиска. Ко-
гда направление поиска		→− k задано, предстоит определить длину
			d

шага в данном направлении. Как отмечалось выше (см. с. 166), она ограничена величиной T — значением t, при котором луч

X

d

, t > 0

, протыкает изнутри область ограничений.

→− k + t→− k

Для линейных ограничений величина T находится очень про-

сто. Если

i-е ограничение неактивно, т. е. i = q + 1, · · · < m,

то

момент

пересечения прямой

X

+ t d

Ti

−→k

→− k с гиперплоскостью

a

T X = b

a

T

X

+

t d

) =

b

→−

i

(→−

k

→−

k

i,

→− i

определяется решением уравнения →− i

откуда

b

a

T X

−→

Ti =

i −

−→i

k

,

(12.18)

a T

d

−→i −→k

а момент T , когда луч в положительном направлении впервые проткнет неактивные ограничения, равен

T = min max (0, Ti), i = q + 1, . . . , m.	(12.19)
i

12.3.. Метод проектирования градиента

177

Шаг 4. Линейный поиск. Длина шага tk на данной итерации определяется поиском минимума одномерной функции сечения в промежутке [0, T ]:

tk	0 t T f (−→k		−→k	).
	= arg min	X	+ t d

Для сложных целевых функций одномерный поиск осуществляется одним из численных методов, описанных в гл. 10, для самых простых возможно аналитическое решение.

Важным частным случаем является квадратичная целевая

функция

f (X ) = C T X + X T DX ,

→−

→−

→−

→−

→−

X

d

минимум которой по лучу −→k + t→− k может быть найден простым

дифференцированием одномерной функции сечения:

dϕ(t)

X

+ t d

)

=

df (→− k

→− k

= d T c + 2 d T D(X

+ t d

) = 0,

dt

dt

→− k →−

→− k

→− k

→− k

откуда

d T

X )

→−

( c + 2D→−

t =

−

k

→−

k

.

(12.20)

2 d T D d

→− k

→− k

Для того чтобы не выйти за пределы ограничений, длина шага устанавливается равной tk = min(t , T ), где T — предельная дли-

на поиска, вычисленная по формуле (12.19).

Шаг 5. Итерационный шаг. Производится переход к новой

точке по правилу	→− k+1	−→k			−→k
			+ t	k		,
	X	= X			d

затем осуществляется возврат на начало итерации.

Замечание. Для простоты изложения мы опустили некоторые детали, которые следует учесть при реализации рабочего алгоритма для повышения его эффективности. В частности, не рассматривался случай, когда через одну вершину проходит более чем n гиперплоскостей (проблема вырождения). Другая особая ситуация возникает, когда вектор антиградиента в некоторой вершине направлен внутрь допустимой

178 Глава 12. Многомерная оптимизация с ограничениями

области, при этом нет необходимости идти по ребру, а можно сразу двигаться внутрь области по антиградиенту (эта ситуация встретится далее

впримере).

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

f (x1, x2) =

(x1 − 2)2 + (x2 − 1)2 → min,

x1

+x2

2,

x2

1,

−x1

0,

−x2

0.

В данном примере

1

1

0

4

0

1

0 1

→−

−2

1

1

,

→−

2

−

1

0

0 .

D =

,

c

=

−

, A =

b =

0

1

0

−

Геометрическая иллюстрация процесса решения приведена на

рис. 12.7.

П о д г о т о в и т е л ь н ы й э т а п

Поскольку правая часть условий

→−

неотрицательна, в каче-

b

X

0

= (0, 0)T

.

стве начальной точки возьмем →−

И т е р а ц и я

1

X

Ш а г

1. Проверим, какие ограничения являются для точки

0 активными. Для этого вычислим

AX

b = ( 2,

−

1, 0, 0)T

.

→−

→−

0

− →−

−

Нулевые компоненты стоят в позициях 3 и 4, т. е. активны 3-е и 4-е ограничения, их число q = 2. Матрица Aq на данном шаге

12.3.. Метод проектирования градиента

179

составлена из 3-й и 4-й строк матрицы A и равна

Aq =	−1	0 .
	0	−1

Матрица проектирования Pq = I − ATq (Aq ATq )−1Aq , как и следовало ожидать, получилась нулевой2, потому что Aq — квадратная матрица (см. замечание 3 на с. 24).

Рис. 12.7. Иллюстрация к примеру. Ограничения пронумерованы цифрами в скобках

Определим множители Лагранжа. Поскольку матрица Aq квадратная, то их можно вычислить по упрощенной формуле

→−

= (

A

−

1A

→− →−

) =

−

−

1A

→− →−

) =

Y

−

AT )

q

f (X

k

−

(AT )

1A

q

f (X

k

q

q

q

q

=

(AT

)−

→− f (→−

).

−

1

X

k

q

→−

Подставив наши значения, получаем Y = (y1, y2)T = (−4, −2)T . Оба множителя отрицательны, нулевой план неоптимальный.

Ш а г 2. Формально имеет место вариант «В», однако здесь мы сталкиваемся с ситуацией, описанной в замечании к алгоритму (см. с. 177). Вектор антиградиента в этой точке равен

2Подробные численные выкладки опущены ввиду их громоздкости. Предполагается, что их следует делать не вручную, а с помощью какого-либо математического пакета, лучше всего MATLAB.