6.9. МИНИМИЗАЦИЯ НЕГЛАДКИХ ФУНКЦИЙ

Обобщенный градиентний метод

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

Рассмотрим, например, динамическую задачу управления запасами.

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

Пусть – удельные затраты по хранению единицы продукта в -м месяце: – функция производственных затрат, связанных с сокращением или расширением производства:

(6.9.1)

Необходимо найти такие объемы производства и запасов в каждом месяце , для которых

(6.9.2)

при условиях

(6.9.3)

Эта задача является частным случаем общей минимаксной задачи поскольку может быть представлена в виде

. (6.9.4)

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

. (6.9.5)

Для минимизации негладких выпуклых (или квазивыпуклых) функций вводится понятия субградиента (или обобщенного градиента) [56].

Определение 6.5. Вектор называется обобщенным градиентом, или субградиентом функции в точке , если для любого выполняется неравенство

. (6.9.6)

Если дифференцируема в точке , то субградиент совпадает с градиентом .

Дадим геометрическую интерпретацию субградиента. Для этого рассмотрим сначала гладкую функцию (рис. 6.20, а).

Градиент непрерывно дифференцируемой выпуклой функции направлен вдоль вектора нормали по линиям уровня .

Субградиент выпуклой функции, не имеющей в точке непрерывных производных, направлен вдоль вектора нормали к опорной гиперплоскости уровня, и также имеет направление внешней нормали (рис. 6.20, б). Обозначим через множество субградиентов в точке . Это множество является выпуклым и замкнутым. На понятии субградиента основан метод обобщенных градиентов (МОГ), впервые предложенный Н. З. Шором [56].

Пусть требуется найти . Пусть – начальная точка. В соответствии с методом ОГ поиск осуществляется согласно следующему рекуррентному соотношению:

, (6.9.7)

где – величина шага; – нормирующий множитель;

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

Возникает вопрос о сходимости метода ОГ. Если выбирать из условий

а) при ; б) , (6.9.8)

будет обеспечена сходимость метода , т.е.

Рассмотрим теперь более общую задачу:

минимизировать

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

В этом случае используется метод проекции градиентов [56]

, (6.9.9)

где – проекция градиента на допустимую область , оператор проектирования удовлетворяет следующим условиям:

а) ; б) . (6.9.10)

Рассмотрим частный случай, когда =1, и пусть – множество точек минимума функции , которые принадлежат допустимой области решений .

Пусть для минимизации используется метод проекции обобщенных градиентов вида

. (6.9.11)

Справедлива следующая теорема [56].

Теорема 6.6. Если при , , а , то найдется такая подпоследовательность последовательности , что при .

(6.9.12)

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

Рассмотрим некоторое достаточно малое . При каждом возможны два случая:

1), (6.9.13)

2). (6.9.14)

Покажем, что не существует такого , что при будет выполнятся (6.9.13). Действительно, если бы это имело место, то при

, (6.9.15)

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

Так как , то отсюда следует, что для любого найдется такая последовательность и такое , что при всех

и тем более

, (6.9.16)

или ,

Откуда .

Итак, теорема доказана.

Пример 6.10. Пусть – выпуклая функция скалярного аргумента . Тогда

, (6.9.17)

где – производные справа и слева от точки , т.е. .

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