jadan (1)

= zoj − z0k zsj. zsk

и,поскольку ведущий элемент zsk всегда положителен,получаем

1			m	zik
		ak −				(83)
as =			=1, i=s		ai.
	zsk			zsk
		i
Далее,так как
	m

aj = zijai, 0 ≤ j ≤ n,

i=1

то,подставляя(83),приходим к следующему представлению векторов a0, . . ., an в новом базисе.

aj =

m

zijai + zsjas =

i=1, i=s

m

1

m

zik

= i=1, i=s

zijai + zsj

zsk

ak

i=1, i=s zsk ai

=

m

zik

−zsj

=

i=1, i=s

zij

− zsk

zsj

ai +

ak.

zsk

Для элементов нулевой строки имеем

m

z0j = cB, B−1aj − cj = cizij − cj, 0 ≤ j ≤ n.

i=1

Поэтому

z¯0j

= m

= im=1, = im=1,

i=1

= m

i=1

i=s ciz¯ij + ckz¯kj − cj =

i

zik

zsj

k

j

i=s c

zij − zsk zsj

+

c

j−

c

=

zsk

i

zik

zsj

k

c

zij − zsk zsj +

c

− c

=

zsk

−

− i=1

−

zsk

cizij

cj

m

cizik

ck

zsj

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

1.4.5.Выбор начальной угловой точки

.

Для нахождения начальной угловой точки применяются несколько способов.Одним из распространенных является

Метод искуственного базиса.Считаем,что b ≥ 0m.Если же для какой-либо компоненты bi вектора правой части b выполняется неравенство bi < 0, то , умножая одновременно i-ую строку матрицы A и i-ую компоненту вектора b на −1, приходим

46

к выполнению нужного неравенства.Строится вспомогательная задача
min	m=1 yi,	(84)
Ax + yi = b,

x ≥ 0n, y ≥ 0m.

Пространство переменных в этой задаче расширяется по сравнению с исходной за-

дачей(73).В качестве начальной угловой точки берется точка

	x	=	0n	.
	y		b

Если b > 0m,то данная угловая точка невырожденна.

Далее вспомогательная задача(84)решается симплекс-методом.Пусть найдено ее решение и пусть x и y соответственно первая и вторая компоненты векторов x и y в решении . Обозначим

				m
			i
		µ =			yi .
				=1
Возможны две ситуации.
1) µ		= 0, т . еy. = 0m. В этом случае x			угловая точка в исходной задаче .
2) µ		> 0, т . е . для хотя бы одной компоненты вектораy					выполняется yi > 0. В
этом случае допустимое множество X в исходной задаче(73)должно быть пустым.
Действительно,если X = , то найдется x X.Но тогда точка
					x
		x	=			.
		y			0m

будет решением вспомогательной задачи и в ней значение целевой функции равно нулю.

С использованием метода искуственного базиса реализуется двухфазовый симплексметод решения задачи линейного программирования.Первая фаза состоит из решения вспомогательной задачи.Вторая фаза заключается в решении исходной задачи линейного программирования(73)из найденной угловой точки.Искуственная переменная при этом отбрасывается.

М-метод. В данном методе объединяются оба этапа нахождения начальной уг - ловой точки и последующего решения исходной задачи.

Пусть M достаточно большая положительная переменная и пусть , по прежне -

му, b ≥ 0m.Составляется так называемая M-задача:
min c, x + M	im=1 yi	,
Ax + y =		(85)
	b,
x ≥ 0n, y ≥ 0m.

Утверждение7. Пусть исходная задача линейного программирования(73)раз-

47

решима.Тогда найдется такое число M ≥ 0, что для всех M > M в любом реше - нии [x , y ] задачи(85)точка x будет оптимальной для исходной задачи(73).При этом y = 0m.

Встаем вопрос,как выбирать константу M в(85)?Можно показать,что если взять в качестве M величину M = max1≤i≤m ui , где u оптимальное решение задачи(84),двойственной к(73),то утверждение7оказывается справедливым.

1.4.6.Модифицированный симплекс-метод

.

В обычном симплекс-методе работают с симплекс-таблицей Z.Ее элементы преобразуются по формулам(81),(82).В модифицированном симплекс-методе работают с матрицей базиса B, точнее , с обратной к ней матрицейB−1. Объясняется это тем , что для того,чтобы получить информацию о всех величинах,связанных с текущей угловой точкой,достаточно только знать матрицу B−1.Действительно,имея B−1, легко находим разложения всех столбцов матрицы A по текущему базису,а также величины

	u = B−1 T cB, ∆k = u, ak − ck, xB = B−1.
Поэтому хранится	только матрица B	1, а новая матрица Bø−1	, соответствующая
		−

новой угловой точке xø,вычисляется по старой матрице B−1 с использованием рекур - рентных соотношений,подобных(81), (82).

Пусть и ø соответственно базисы старой и новой угловых точек:

B B

ø

B = [a1, . . . , as, as+1, . . . am] , B = [a1, . . . , ak, as+1, . . . am] .

Пусть,кроме того,

−1 ø−1 ø ≤ ≤

B = [βij] , B = βij , 1 i, j m.

Формулы пересчета имеют следующий вид:

ø

βij

	zik
= βij −			βsj, i = s,
	zsk
ø	1
βsj =		zsk		βsj

Справедливость этих формул проверяется путем умножения матрицы ø на матрицу

B

ø−1.

B

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

48

1.5.Методы минимизации на множествах простой структуры

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

1.5.1.Метод проекции градиента
Пусть требуется найти	(86)
f = min f(x),
x X

где X выпуклое замкнутое множество в Rn, f(x) дифференцируемая функция , определенная на некоторой области,содержащей множество X.Про такую задачу иногда говорят,что она является задачей с прямым ограничением,подчеркивая тем самым,что множество X здесь рассматривается как единое целое без уточнения его функционального описания.

Обозначим через X X множество оптимальных решений в задаче(86).Если x X ,то в силу необходимых условий минимума( ??) данная точка должна быть стационарной,т.е.быть решением вариационного неравенства с градиентным отображением fx(x),:

fx(x ), x − x ≥ 0 x X.

(87)

В задаче безусловной минимизации , когдаX = Rn,одним из основных методов решения был метод градиентного спуска,в котором строилась последовательность точек {xk} согласно следующей рекуррентной схеме

xk+1 = xk − αkfx(xk), k = 0, 1, . . . ,

(88)

где αk шаг спуска,определяемый по какому-либо правилу точной или приближенной одномерной минимизации.Однако,если X отлично от всего пространства Rn, то непосредственное применение градиентного метода затруднено,например,из-за возможного выхода точек за пределы множества X.

Рассмотрим теперь метод решения задачи(86),в котором все точки итеративного процесса принадлежат множеству X. В нем сочетаются идеи метода градиентного спуска и проектирования,поэтому он и получил название метода проекции градиен-

та.

В методе проекции градиента , как и в методе градиентного спуска , начальная точка x0 задается,причем x0 X,а последующие точки вместо(88)вычисляются

по рекуррентной схеме

xk+1 = πX (xk − αkfx(xk)) k = 0, 1, . . . ,

(89)

49

где πX(a) проекции точки a на множество X. Таким образом , вся последователь - ность {xk} оказывается принадлежащей допустимому множеству X. Шаг αk в (89) выбирается по одной из модификаций процедур одномерного поиска,обсуждаемых ниже.

Лемма3. Пусть x решение задачи (86). Пусть , кроме того X, выпуклое замкнутое множество.Тогда

x = πX (x − αfx(x ))

(90)

для любого α > 0.

Доказательство. На основании необходимых условий минимума дифференцируемой функции на выпуклом замкнутом множестве X, если x X решение задачи,то эта точка должна быть стационарной,т.е.для нее выполняется неравен-

ство(87).

Умножим неравенство(87)на α > 0 и перепишем в виде

x − (x − αfx(x )) , x − x ≥ 0 x X, α > 0.

Отсюда на основании утверждения ?? заключаем,что точка x является проекцией точки x − αfx(x ) на множество X. Таким образом , имеет место равенство (90).

Заметим,что если f(x) выпуклая дифференцируема функция,то опять же в силу утверждения ?? выполнение равенства(90)является не только необходимым, но и достаточным,для того,чтобы точка x X была решением задачи(86).

Обсудим вопрос о выборе шага αk в итеративном процессе (89). Возможно несколь - ко подходов,упомянем только три из них.

1)Правило постоянного шага.Согласно этому правилу шаг αk выбирается заранее,равным достаточно малой положительной величине.

2)Правило одномерной минимизации. Обозначим

φk(α) = f (xk(α)) , xk(α) = πX (xk − αfx(xk)) .

Согласно данному правилу шаг αk является решением задачи

φk(αk) = min φk(α).

α>0

3) Правило приближенной минимизации на отрезке [0, αˆ], где αˆ > 0 некоторый заданный максимально возможный шаг.Для приближенной минимизации может применяться правило Армихо,в котором путем дробления начального шага α = αˆ, добиваются выполнения неравенства:

f (xk(α)) − f(xk) ≤ ε fx(xk), xk(α) − xk ,

(91)

где 0 < ε < 1.Если неравенство(91)при данном α не выполняется,то его уменьшают, умножая на коэффициент 0 < θ < 1.

50

Предположим,что градиент функции f(x) удовлетворяет условию Липшица:

fx(x) − fx(y) ≤ L x − y x, y X,

(92)

и рассмотрим вопрос о сходимости итеративного процесса (89) в том случае , когда шаг αk берется постоянным,удовлетворяющим условию:

	0 < αk <	1	,	(93)
		L + c

где c > 0 любое положительное число .

Теорема8. Пусть X выпуклое замкнутое множество и f(x) дифференци - руемая функция,градиент которой удовлетворяет условию Липшица(92).Пусть, кроме того,начальная точка x0 X такова,что множество

˜ { ≤ }

X(x0) = x X : f(x) f(x0)

компактное,а шаг αk берется постоянным и таким,что выполняется неравенство (93).Тогда последовательность {xk}, генерируемая методом проекции градиента , имеет предельные точки,которые являются стационарной точками в задаче(86). Если f(x) выпуклая функция , то каждая стационарная точкаx есть решение задачи(86).

Доказательство. Для проекции a¯ X точки a Rn на множество X согласно (16)выполняется неравенство

a¯ − a, x − a¯ ≥ 0 x X.
Беря в нем a¯ = xk+1, a = xk − αkfx(xk), x = xk, приходим к	(94)
xk+1 − (xk − αkfx(xk)) , xk − xk+1 ≥ 0.
Обозначим sk = xk+1 − xk.Неравенство(94)при этих обозначениях перепишется
как
sk + αkfx(xk), sk ≤ 0
или	(95)
sk 2 + αk fx(xk), sk ≤ 0.

Представим f основании(92)

f(xk+1)

(xk+1) как f(xk+1) = f(xk) + fx(˜xk), sk , где x˜k [xk, xk+1

= f(xk) + fx(xk), sk + fx(˜xk) − fx(xk), sk ≤
≤ f(xk) + fx(xk), sk + L x˜k −2 xk sk ≤
≤	f(xk) + fx1(xk), sk + L sk =	1	sk 2
=	f(xk) + αk− [ sk 2 + αk fx(xk), sk ] + L − αk−

]. Тогда на

.

Отсюда с учетом(95)и(93)получаем

f(xk+1) − f(xk) ≤ L − α−1 sk 2 ≤ −c sk 2. (96)

k

51

Имеем для этой подпоследовательности

j→∞

lim

На основании неравенства(96)и ограниченности непрерывной функции f(x) на

компактном множестве ˜ заключаем,что

X(x0)

lim (f(xk+1) − f(xk)) = 0,

k→∞

а также

lim sk = lim xk+1 − xk = 0.

k→∞ k→∞

Так как последовательность { } принадлежит компактному множеству ˜ , xk X(x0)

существует сходящаяся подпоследовательность xkj }.Пусть xkj = x .

skj = πX xkj − αkj fx(xkj ) − xkj → 0.

Поэтому в силу непрерывности оператора проектирования

πX (x − αfx(x )) = x ,

где α равняется постоянному шагу, α = αk.

Согласно утверждению ??, если x является проекцией точки x − αfx(x ) на множество X, то имеет место неравенство :

x − (x − αfx(x )), x − x ≥ 0 x X.
Таким образом,	(97)
fx(x ), x − x ≥ 0 x X,

т.е.точка x является стационарной.

Если f(x) выпуклая функция,то условие(97)достаточно для того,чтобы точка x была бы решением задачи(16).

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

1.Пусть f(x) выпуклая функция.Тогда для любого xk справедливо неравенство

C f(xk) − f ≤ k ,

где C > 0.Выполнение данного неравенства означает сверхлинейную скорость сходимости метода по функционалу.

2.Предположим теперь,что f(x) сильно выпуклая функция с константой θ. Предположим также,что шаг αk берется постоянным из интервала (0, 4θ/L2). Тогда

xk+1 − x ≤ C xk − x ,

52

где 0 < C < 1.Данное неравенство означает,то метод проекции градиента с постоянным шагом сходится к точке минимума сильно выпуклой функции на X с линейной скоростью.

3.Если x точка строгого мнимума функции f(x) на X, т . е . для некоторого γ > 0 выполняется

f(x) − f(x ) ≥ γ x − x x X,

то можно показать,что метод находит решение задачи за конечное число шагов. Чтобы уменьшить количество проектирований,наряду с основной схемой метода

проекции градиента рассматривают ее модификацию

xk+1 = xk + λksk,	sk = πX (xk − αkfx(xk)) .	(98)
Здесь αk то же самое,что и в основной схеме,а λk выбирается из условия
λk = arg min f (xk + λsk)
или из условия	0≤λ≤1
λk = arg	min f (xk + λsk) ,
0≤λ≤λ

где λ максимальное значение параметра λ, для которого xk + λsk X. Схему (98)

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

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

1.5.2.Метод условного градиента

Рассмотрим другой метод решения задачи(86),получивший название метода условного градиента.Метод относится к классу методов спуска и основан на идее линеаризации целевой функции.

Предположим,что в задаче(86)множество X является выпуклым компактом. Предполагаем также,что f(x) дифференцируемая функция.Итеративный процесс в методе описывается следующим рекуррентным соотношением

xk+1 = xk + αksk,											(99)
где sk = x¯k − xk и точка x¯k есть решение вспомогательной задачи											(100)
x X		f	x	(x	k	), x	−	x	k	.
min

Шаг αk определяется из решения одномерной задачи минимизации

αk = arg min f(xk + αsk),

0≤α≤1

53

что соответствует наискорейшему спуску.Возможно также приближенное решение этой задачи,например,с использованием правила Армихо.О направлении sk говорят как об условном антиградиенте.

Обратим внимание,что вспомогательная задача(100)эквивалентна задачи минимизации линейного приближения целевой функции,так как,если точка x¯k есть

решение(100),то эта же точка будет и решением задачи
min f	(x),	f	(x) = f(x		) +	f (x	), x	−	x	k	,
x X k		k		k		x k
				fx(xk), x на X.
как,впрочем,и точкой минимума функции

Обозначим через ηk = fx(xk), sk минимальное значение целевой функции во вспомогательной задаче(100).Понятно,что всегда ηk ≤ 0. Возможны два случая :

1) ηk = 0. Тогда

fx(xk), x − xk ≥ 0 x X.

Выполнение данного неравенства означает,что xk является стационарной точкой в задаче(86).

2) ηk < 0. Тогда из fx(xk), sk < 0 следует,что возможно движение вдоль направления sk с уменьшением значения целевой функции f(x).

Предположим сначала,что шаг αk выбирается по правилу Армихо:
f(xk + αksk) − f(xk) ≤ αkεηk,	(101)

где 0 < ε < 1.

Теорема9. Пусть X выпуклый компакт и f(x) дифференцируемая функ - ция,градиент которой удовлетворяет на X условию Липшица

fx(x) − fx(y) ≤ L x − y x, y X.

Пусть,кроме того,шаг αk выбирается путем дробления начального шага,равного единице,по правилу Армихо(101).Тогда для любого начального x0 X метод условного градиента порождает последовательность точек {xk}, которая имеет предельные точки и любая предельная точка x является стационарной для задачи (86).Если f(x) выпуклая функция на X, то x решение задачи (86).

Доказательство. Обозначим

2(ε − 1)ηk

α¯k = L sk 2 .

Если на k-ой итерации выполняется неравенство(101),то аналогично тому,как это делается в методе градиентного спуска с правилом Армихо выбора шага,можно показать,что αk ≤ α¯k.Поэтому,производя дробление шага,начиная с единичного шага,мы в принципе можем столкнуться с двумя случаями.В первом случае будем получать,что αk = 1 (это соответствует тому,что неравенство(101)выполняется при

54

αk = 1).Во втором случае αk < 1,т.е.произведено хотя бы одно дробление.Но это возможно только при α¯k < 1,и мы дроблением шага добиваемся выполнения(101)а, следовательно,и выполнения неравенства αk ≤ α¯k.Но тогда обязательно αk ≥ θα¯k, где 0 < θ < 1 параметр дробления шага в правиле Армихо . Таким образом , всегда

min{1, θα¯k} ≤ αk ≤ 1.

Пусть последовательность {xk} бесконечная.Имеем {xk} X и f(xk+1) < f(xk). Множество X компактное,функция f(x) непрерывная.Поэтому существуют пределы:

klim [f(xk+1) − f(xk)] = 0,
→∞
и	(102)
lim (αkηk) = 0.
k→∞

Шаг αk, как уже отмечалось , на каждой итерации удовлетворяет неравенству (101), в котором величина α¯k зависит от ηk и sk.

Из компактности множества X следует,что можно указать константу C > 0, для которой sk ≤ C на каждой итерации.Отсюда получаем,что

α¯	≥		2(ε − 1)ηk		.
k			LC2
Обозначим		2θ(1 − ε)
δ =				> 0.
			LC2
Имеем либо αk = 1, либо αk ≥ −δηk > 0, поэтому из (102)						(103)
	lim ηk = 0.
	k→∞
Так как ηk минимальное значение функции fx(xk), x − xk на X, то						(104)
ηk ≤ fx(xk), x − xk x X.

Последовательность {xk} принадлежит компактному множеству X,и,стало быть, имеет предельные точки.Пусть xkj → x X. Для этих kj согласно(104)выполняются неравенства

ηkj ≤ fx(xkj ), x − xkj x X.
Отсюда,переходя к пределу,получаем с учетом(103)
fx(x ), x − x ≥ 0 x X,	(105)

т.е. x является стационарной точкой для задачи(86).

Если f(x) выпуклая функция,то условие(105)достаточно для того,чтобы точка x была решением задачи(86).

Сделаем несколько замечаний.

55