ЛЕКЦИЯ 11

ЛЕКЦИЯ 11

МЕТОДЫ РЕШЕНИЯ ЗАДАЧ СТОХАСТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

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

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

Втех случаях, в которых удается получить явную запись эквивалентной задачи в виде простой линейной, кусочнолинейной или выпуклой задачи, целесообразно применять следующие методы:

метод проекции градиента,

метод условного градиента,

метод модифицированных функций Лагранжа (метод

множителей),

двойственные методы,

метод штрафных функций,

метод Келли (метод отсекающих плоскостей) и т.д.

В остальных случаях необходимо прибегать к таким методам, как:

метод проекции субградиентов,

метод проекции стохастических субградиентов,

приближенные методы анализа	стохастического
программирования и т.д.

1 Методы выпуклого программирования для решения задач условной оптимизации

1.1 Метод проекции градиента

Рассмотрим метод проекции градиента для решения задачи следующего вида:

f (x) min,	x X,	(1)
где X - замкнутое выпуклое множество в		R n , f (x)-
дифференцируемая функция на X .

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

Рассмотрим вначале свойства проекции точки a Rn на множество X Rn .

Определение. Проекцией точки a Rn	на множество
X Rn называется точка a X такая, что

X

x X : X a ax a ,

т.е. точка, ближайшая к a среди всех точек из X.

Если

a Rn , то X a X ,

если же a X , и X - открыто, то проекция X a не существует.

Можно показать, что X a является решением следующей задачи проектирования:

X

a

x a

2

min, x X.

(2)

Лемма 1 Пусть X замкнутое выпуклое подмножество в

R n .

Тогда

1.Проекция X a любой точки a Rn существует и единственна;

2.Точка x является проекцией точки a на множество Xx X a в том и только в том случае, если

x a, x x 0 x X.

(3)

3. Для всех точек a1, a2 Rn справедливо неравенство

X a1 X a2

a1 a2

,

(4)

т.е.

оператор

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

обладает

свойством

нерастяжения расстояний.

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

Пусть x* X является оптимальным решением задачи

(1)

Лемма 2. Пусть множество X выпукло и замкнуто,

функция f (x) выпукла на X и дифференцируема	в	точке
x* X . Тогда x* X является решением задачи (1)	в	том и
только в том случае, если
x* X x * f x * ,		(5)
при произвольном 0.

Теперь рассмотрим алгоритм метода проекции градиента и его сходимость. В методе проекции градиента в качестве очередной точки приближения к решению задачи (1)

выбирается проекция точки на множество X той точки, которая получается по градиентному методу:

x(k 1) X x(k) kf x(k) , где k 0,1,2,...

(6)

Коэффициенты k 0 можно выбирать различными способами.

Рассмотрим теорему о сходимости метода проекции градиента с априорным выбором коэффициентов k , то есть

последовательность k

выбирают заранее, до начала

вычислений (например, k

c k 1, где k=0,1,2,...).

Теорема 1. Пусть множество X выпукло и замкнуто,

функция

f (x) сильно

выпукла с

константой

0 и

дифференцируема на X, причем ее градиент удовлетворяет

условию Липшица:

M

x x

X.

(7)

f x f x

, x, x

Тогда последовательность x(k) , генерируемая по формуле

x(k 1)

X x(k) kf x(k) ,k 0,1,2,...

где x(0) произвольная точка из X, а

k

0, 4 M2 ,

сходится к решению x * задачи (1)

со

скоростью

геометрической прогрессии:

x(k 1) x *

q

x(k) x *

,

(8)

0,1 .

где q

1 4 2M2

Замечание: В рассмотренном методе на каждой k-ой итерации требуется производить операцию проектирования точки на множество X, то есть решать задачу вида (2) при

ax(k) kf x(k) .

Внекоторых частных случаях удается указать явный вид

проекции, например, если множество X шар, координатный параллелепипед, полупространство, гиперплоскость, аффинное множество.

Однако, если X задается с помощью более или менее сложной системы равенств и неравенств, то метод проекции градиента практически неприменим, так как задача (2) оказывается не проще исходной.

В некоторых задачах константы M, из теоремы 1 обычно неизвестны, что затрудняет отыскание .

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

.

Пример 1. Решить методом проекции градиента:

f x x3x	2		2x22
1			x1
1 x1	5
X			.

5 x2 2

min,

x X

(9)

(10)

Решение. Задачу (9)-(10) решим методом проекции градиента, используя соотношение (6).

	Выберем начальное приближение x(0) 2, 2 .								Пусть шаг
	k , k 0,1,2,... в выражении (6)	k равен					1	.	Критерий
						2
	останова выберем следующий:			x(k 1) x(k)		, k 0,1,2,...,
	где 0.1.
	Итерация 1. В соответствии с выражением					(6)
	определяем

	(1)	~(1)		(0)		1			(0)
x		X x	X x					f x		.
						2

	~(1)		1	~(1)		1
	x1	2		24 2 13, x2	2			8	4 8.
			2			2
		~(1)		(13, 8) выходит за пределы области X.
	Точка x

Так как множество X- координатный параллелепипед, то можно указать явный вид проекции точки на множествоХ.

Можно показать, что если

X x R n : b j x j c j , j 1,..., n -

координатный параллелепипед, то a Rn :

b j , a j b j ,X a j a j , b j a j c j ,

c j , a j c j.

В нашем случае x1(1) 5, x(21) 5.

Вычисляем f x(1) 635,f x(0) 20.

Так как

f x(1) f x(0) ,

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

x(1) x(0) 7.62 0.1.

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

Итерация 2. В соответствии с выражением (6) определяем

	(2)	~(2)		(1)		1
x		X x	X x
						2

~(2)	~(2)	69.5.
x1	191.5, x2

~

Точка x(2) выходит за пределы области

(1)

f x .

X.

Значит, x1(2) 5, x(22) 5.

Проверяем критерий останова:

x(2) x(1)

0.

Критерий останова выполняется, значит, процесс вычислений закончен.

Пример 2. Решить методом проекции градиента:

f x x2		2x		1	x	2	min,	(11)
	1						x X
X x2			2 .
	x2							(12)
1		2

	Решение. Задачу	(11)-	(12)	решим методом
	проекции градиента, используя соотношение			(6).
	Выберем начальное приближение x(0)		0,0 .
	Пусть шаг k , k 0,1,2,... в выражении			(6) k равен	1	.
					2

Критерий останова выберем следующий:

x(k 1) x(k) , k 0,1,2,..., где 0.1.

Итерация 1. В соответствии с выражением определяем

	(1)	~(1)		(0)		1			(0)
x		X x	X x					f x		.
						2

	~(1)		1		~(1)		1			1
	x1	0		2 1, x2		0			1		.
			2				2			2
				~(1)	попадает в область X, то
	Так как точка x

Так как

(6)

(1)~(1) .

xx

f x(1) f x(0) ,

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

x(1) x(0) 1.118 0.1.

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

Итерация 2. В соответствии с выражением										(6)
определяем
	(2)	~(2)		(1)		1			(1)
x		X x	X x					f x		.
						2