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

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

Причем если в задаче линейного программирования вспомогательная функция fL (x) неограничена для текущего xk (такое возможно, несмотря на то, что исходная задача имеет решение), то можно для получения точки yk ограничиться несколькими шагами симплекс-метода в сторону убывания функции fL (x) .

Существуют различные способы выбора шага λk в методе условного градиента. Рассмотрим некоторые из них.

1. Величина шага λk может выбираться из условий: 0 ≤ λk ≤1;

ϕ(λk ) = min f (xk + λSk ).

λ

Очевидно, что такая задача может быть решена каким-либо методом одномерной минимизации.

2.Можно задавать λk =1 и проверять условие монотонного убывания функции f (x) при переходе от точки xk к точке xk+1 , а именно: f (xk+1 ) < f (xk ) . Если это условие не выполняется, то необходимо дробить шаг λk до тех пор, пока не выполнится условие монотонности.

3.Величина шага определяется из условия λk = αi0 , где i0 –

минимальный номер среди номеров i ≥ 0 , удовлетворяющих условию

f (xk ) − f (xk + αi Sk ) ≥ αi ε η(xk ) .

Здесь α, ε – параметры метода, 0 < α <1; 0 < ε <1 . Величина η(xk ) является минимумом линейной функции fL (x) , т.е.

Необходимо отметить, что величина η(xk ) в условии выбора параметра шага берется по модулю, так как η(xk ) ≤ 0 . Это следует из того, что при x = xk вспомогательная линейная функция f L (x) x=xk = 0 , следовательно, значение η(xk ) , обеспечивающее

минимальное значение fL (x) , меньше или равно нулю.

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

Процесс вычислений заканчивается в точке xk , если η(xk ) = 0 . Это может случиться, например, если f (xk ) = 0 . Из этого условия следует, что если

Последнее, видимо, является необходимым и достаточным (для выпуклой функции достаточным) условием того, чтобы точка xk являлась минимумом функции f (x) на множестве X (тоже

выпуклом).

Это условие является обобщением условия стационарностиf (x k ) = 0 для задачи минимизации функций на множествах.

Проиллюстрируем условие < f (x k ), x − xk > ≥ 0 графически

(рис. 1.34).

x

x

xk

f (xk )

Рис. 1.34. Графическая интерпретация скалярного произведения

< f (x k ), x − xk > ≥ 0

92

Оно означает, что угол между градиентом в точке xk и любым вектором x − xk для всех точек x X должен быть острым. Однако, если точка xk лежит внутри области X , то этого не может быть. Следовательно, условие (1.18) справедливо, только в случае:

f (x k ) = 0 .

Если точка xk лежит на границе области, то минимум в этой точке достигается лишь тогда, когда антиградиент перпендикулярен границе и направлен из области X (рис. 1.35).

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

В этом случае углы между градиентом и любым вектором (x − xk ) будут острыми (рис. 1.35, а).

Если антиградиент отклоняется от данного направления, то найдутся точки x , для которых эти углы будут тупыми (рис. 1.33, б).

Геометрический смысл метода условного градиента поясняет рис. 1.36.

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

Пример. Найти min f (x) при ограничении

i=1

93

Линииуровня функции fL =< f (xk ), x − xk > ортогональны f (xk )

Линииуровня < f (x0 ), x −x0 >=const

Рис. 1.36. Геометрический смысл метода условного градиента

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

~

r в n-мерном пространстве с центром в точке x .

Вспомогательная задача для метода условного градиента формулируется следующим образам.

Определить точку yk , являющуюся решением задачи. Найти

1.4.7. Метод линеаризации

Пусть требуется найти min f (x) при ограничениях

gi (x) ≤ 0, i =1, m .

94

Заменим в точке xk функцию f (x) и все ограничения gi (x) на

линейные путем линеаризации:

f L (x) =< f (xk ), x − xk >;

gi (xk )+ < g(xk ), x − xk >≤ 0, i =1, m.

В результате получим задачу линейного программирования: найти

min {f L (x) =< f (xk ), x − xk >}

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

gi (xk )+ < g(xk ), x − xk >≤ 0, i =1, m.

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

уходило слишком далеко от xk , оставаясь в такой окрестности xk ,

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

при ограничениях:

gi (xk )+ < g(xk ), x − xk >≤ 0, i =1, m ,

где параметр βk > 0 .

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

95