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

Будем полагать, что в точке x имеется хотя бы одно активное ограничивающее уравнение g(x) = 0 , при этом точка x лежит на

границе допустимой области. В противном случае нет проблем с выбором направления – это антиградиент.

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

Если ограничивающее уравнение линейно, то «лучшее» направление S получается проекцией вектора – f ( x ) на

многообразие, характеризуемое линейным ограничивающим уравнением(рис. 1.28).

− f ( x )

g(x) = 0

уменьшение f (x)

x

X − допустимая область

Рис. 1.28. Проекция антиградиента на активное ограничение

Если активное ограничивающее уравнение является нелинейным, проблема выбора направления становится сложнее. Помимо условия < f (x), S >< 0 (движение в сторону уменьшения

f (x) ), должно удовлетворяться условие < g(x), S >< 0 (движение

всторону уменьшения g(x) ), где g(x) – активное

ограничивающее неравенство (рис. 1.29).

Возможными являются направления S , для которых < g(x), S >< 0 (при условии выпуклости g(x) ).

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

81

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

g(x)

x

Касательная плоскость к g(x) = 0

g(x) = 0

S S

X (g(x))

Рис. 1.29. Выбор возможных направлений при нелинейном ограничивающем уравнении

Возможное и приемлемое направление S получается путем решения следующей вспомогательной задачи условной оптимизации: найти max{ϕ(σ, S) = σ} при ограничениях:

< gi (x), S > +σ ≤ 0, i Iε ;

<f (x), S > +σ ≤ 0 .

<S, S >=1 .

В данной задаче Iε = {i : −ε ≤ gi (x) ≤ 0; 0 < ε <<1}, т.е. множество Iε включает в себя индексы «почти активных»

ограничений, значения которых находятся в ε-близости от границы

( − εi ≤ gi (x) ≤ 0 ).

Очевидно, если полученное в результате решения вспомогательной задачи максимальное значение σ > 0 , то смещение в направлении S приводит к уменьшению значения функции f (x) , что следует из второго условия в ограничениях

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

82

следующим: −1 ≤ s j ≤1, j =1, n , s j – элемент вектора направления

S. Таким образом, вспомогательная задача становиться задачей линейного программирования, для решения которой существуют конечно-шаговые методы (симплекс-методы). Неизвестными параметрами в этой задаче линейного программирования являются σ, и элементы вектора S ( s1 , s2 , …, sn ).

Рассмотрим один из алгоритмов метода возможных направлений.

В качестве начального приближения x0 может быть выбрана любая точка множества X , а ε0 выбирают из интервала (0, 1].

Пусть в результате k-й итерации вычислены xk и εk . Опишем k +1 итерацию.

1.Решить вспомогательную задачу и вычислить σk ≥ 0 и Sk (если Iε пусто, т.е. xk – внутренняя точка, то Sk совпадает с антиградиентом).

2.Если σk ≥ εk , то перейти к вычислению величины шага λk .

задачу с ε = 0 . Если σ*k = 0 , то процесс поиска точки минимума

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

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

проекция точки yk на допустимое множество X (рис. 1.30). После этого надо осуществлять спуск вдоль полученного направления. Выпуклость множества X гарантирует, что такое направление Sk является возможным. Проекция точки y k на множество – ближайшая к y k точка этого множества.

Рис. 1.30. Определение направления в методе проекции градиента

84

Итак, метод проекции градиента состоит в вычислении

различные варианты метода проекции градиента (можно использовать одномерную минимизацию и т.д.).

Прекращения процесса является условие pk = xk , которое является необходимым и достаточным условием того, что точка xk

– точка минимума (доказывается с помощью специальной теоремы).

Например, pk = xk , если f ( xk ) = 0 , так как тогда yk = xk , и нет перемещения из точки xk . Аналогичная ситуация возникает,

если xk лежит на границе и градиент ортогонален границе допустимой области (рис. 1.31).

− f ( x )

Рис. 1.31. Направление градиента совпадает с направлением градиента к границе допустимой области

Для того чтобы найти проекцию точки yk на множество X , необходимо решить задачу минимизации квадратичной функции yk − x 2 на множестве X (т.е. x X ) – тем самым будет найдена ближайшая к yk точка множества X . В общем случае эта задача

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

множество X представляет собой шар или параллелепипед в E n ,

85