Материал: Бородакий Нелинейное программирование в современных задачах оптимизации 2011

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

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

Рассмотрим пример явного определения проекции точки на множестве X . В качестве области X будем рассматривать

замкнутый шар радиуса r с центром в точке O в пространстве E n . Как известно, уравнение шара имеет вид

∑xi2 = r 2 ;

i=1

тогда допустимая область X описывается неравенством

∑xi2 ≤ r 2 .

i=1

Пусть y – некоторая точка, для которой надо найти проекцию p на поверхность шара. Очевидно, что данная задача эквивалентна задаче минимизации функции

φ(x) = y − x 2; x X ,

при этом
при этом	p = arg min φ(x) .
	x X

Данную задачу можно записать в виде: найти

min ∑( yi − xi )2

i=1

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

∑xi2 ≤ r 2 .

i=1

Решение этой вспомогательной задачи находиться в явном виде:

	если
y,	если
	ry
p =	ry
	n
	∑yi2
	i=1
	i=1

∑yi2 ≤ r2 ;

i=1

, если ∑yi2 > r2 .

i=1

x = f (xk ) . В

1.4.5. Метод проекции градиента при линейных ограничениях

Будем полагать, что ограничивающие уравнения линейны, т.е. имеют вид:

Ax −b ≤ 0 ,

где A – матрица ( m ×n ); b – m-мерный вектор.

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

Предположим,	что при заданном			x X	грань, содержащая x ,
определяется уравнением
		gi (x) = 0, i I ,
где I ={i1 , i2 ,…, i p } , p < m .
Предположим,	что	любая	подматрица		размерности ( p ×n)
матрицы A имеет ранг		p , и пусть AI – подматрица, составленная
из p строк	матрицы		A ,	соответствующих активным

ограничениям. Тогда можно предложить следующий алгоритм поиска минимума функции f (x) при линейных ограничениях.

Алгоритм (один шаг, после того как найдена точка xk X ).

1. Вычислить проекцию градиента на грань, содержащую xk по

формуле
	т	т	−1
x = I n	− AI	(AI AI	)	AI f (xk ) ,
						(AI AIт )−1
где In – единичная	матрица		(n ×n) .		Матрица	(AI AIт )−1
существует, так как по условию задачи ранг матрицы						AI равен
числу строк в ней.
Если xk лежит внутри X ,		то множество I			пусто, в квадратных

скобках остается одна единичная матрица In и

этом случае данный метод оказывается обычным градиентным методом.

2. Если

x ≠ 0 ,

то найти

λдоп ,

такое, что

λдоп

x определяет

максимальное перемещение в направлении

− x , которое может

быть сделано,

не выходя за пределы X ;

λдоп

может быть найдено

путем решения задачи

λдоп = max{λ:

(xk − λ

xk X }.

После этого найти λ* как

решение

задачи

одномерной

оптимизации:

min f (x

− λ

λ* = arg

0≤λ≤λдоп

и вычислить xk +1 = xk − λ* xk .

Если

λ* < λдоп ,

то совокупность

активных

ограничивающих

уравнений остается без изменений.

Если λ* = λдоп , то граница области X будет достигнута и новое

ограничивающее

уравнение

станет

активным. Тогда, если

g j (xk+1) =0 ,

j I , то надо включить в I

это

j , определить новую

матрицу AI

и вернуться к шагу 1.

Если

x = 0 , то необходимо вычислить вектор μ (размерности

p ) исходя из соотношения

= ( A A т )−1

A f (x

) .

Если

все

компоненты

μi

≤ 0 ,

i =

то

оптимально

1, p

( xk = x* ), и процесс вычисления прекращается.

В противном случае исключить из AI

строку, соответствующую

наибольшей положительной компоненте вектора μ ,

и вернуться к

шагу 1.

Дело в том, что компоненты вектора

эквивалентны

множителям Лагранжа, и точка xk

является оптимальной точкой в

том случае, когда все μi ≤ 0 .

Однако, если некоторые компоненты вектора μ положительны,


то функция f (x)	может уменьшаться		в том случае если
перемещение от xk	осуществляется в направлении уменьшения
gi (x) , т.е. в направлении, где		gi (x) < 0 .	При этом ограничение
gi (x) становится неактивным, i		исключается из I .
Это можно проиллюстрировать рис.1.32:

f (x )

x
− f ( x )	x
	x

Рис. 1.32. Особенности метода проекции градиента

Алгоритм работает так, что проекции градиентов, расположенных симметрично относительно грани, одинаковы (рис. 1.33).

f ( x )

g ( x ) = 0

2	−	f ( x )

Рис. 1.33. Пояснения к использованию метода проекции градиента.

Следовательно, если f ( x ) ≠ 0 , то ситуация, когда x = 0 , может возникнуть в двух случаях:

вслучае 1 точка x является точкой оптимума, следовательно, вычисления необходимо прекратить;

вслучае 2, как видно из рис. 1.33, антиградиент направлен внутрь области X , следовательно, его проектировать на грань не нужно.

Когда согласно алгоритму из AI будет убрана строка, соответствующая ограничению gi (x) = 0 , в формуле для проекции

останется In и получится, что

x = f ( x ) , т.е. направление

поиска будет направлено внутрь области X в сторону убывания функции.

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

Идея метода условного градиента состоит в выборе направления спуска на основе линеаризации функции f (x) относительно

текущей точки xk . В результате линеаризации получаем линейную функцию fL (x) вида:

f L (x) = f (xk ) + f (xk )(x − xk ) .

Пусть yk – точка, обеспечивающая минимум функции fL (x) на множестве X . Тогда направление Sk поиска экстремума исходной функции f (x) на множестве X можно определить следующим образом:

Sk = yk − xk ,

при этом основная итерационная формула имеет стандартный вид:

xk +1 = xk + λk Sk .

Таким образом, для определения направления Sk необходимо решить задачу минимизации линейной функции fL (x) на

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

Источник: https://studfile.net/preview/16708738/

Смотрите также:



_1966(~1
_Антонян Ю.М., Сексуальные преступления. Чикатило и другие
_РГР № 1 (2)
- Габариты и масса 27
'Образ–Я' и его развитие средствами диалога
"Логистическая технология JIT"
"Особенности правовой системы Российской Федерации" по дисциплине "Теория государства и права"
«Анализ ликвидности и платежеспособности предприятия» (на материалах ОАО Московская кондитерская фабрика «Красный Октябрь»)