6.9. МИНИМИЗАЦИЯ НЕГЛАДКИХ ФУНКЦИЙ
Обобщенный градиентний метод
Как известно, градиентний метод основан на предположении непрерывной дифференцируемости целевой функции 
. Для минимизации негладких функций его применить невозможно. Вместе с тем, целевые функции, не имеющие непрерывных частных производных, весьма часто возникают в задачах исследования операций. Поэтому проблема оптимизации негладких функций является черезвычайно актуальной.
Рассмотрим, например, динамическую задачу управления запасами.
Пусть какое-то предприятие планирует свою работу на 
месяцев. Обозначим через 
план производства продукта в 
-м месяце: 
- фактический объем производства продукта в -м месяце: 
- остаток запаса продукта к концу -го месяца. Поскольку планы производства каждого месяца неодинаковы, то предприятие может изготовить часть продукции преждевременно для покрытия плана следующего месяца и хранить ее в виде запасов.
Пусть 
- удельные затраты по хранению единицы продукта в -м месяце: 
- функция производственных затрат, связанных с сокращением или расширением производства:
(6.9.1)
Необходимо найти такие объемы производства и запасов в каждом месяце 
, для которых
(6.9.2)
при условиях
(6.9.3)
Эта задача является частным случаем общей минимаксной задачи 
поскольку 
может быть представлена в виде
. (6.9.4)
Введя вспомогательные переменные 
, данную задачу можно привести к следующему виду:
. (6.9.5)
Для минимизации негладких выпуклых (или квазивыпуклых) функций вводится понятия субградиента (или обобщенного градиента) [56].
|
|
называется обобщенным градиентом, или субградиентом функции в точке 
, если для любого 
выполняется неравенство
. (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. Если при 
, 
, а 
, то найдется такая подпоследовательность 
последовательности 
, что 
при 
.
|
- произвольная константа такая, что 
для всех 
. По определению операции проектирования и на основании условий теоремы имеем 
Рассмотрим некоторое достаточно малое 
. При каждом 
возможны два случая:
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) при 
или 
.
Пример 6.11. Пусть 
, где функции 
выпуклы по 
. Тогда 
,
где 
- правая и левая производные функции .
Пример 6.12. При решении задач теории игр зачастую приходится решать задачу об отыскании минимакса [36]:
(6.9.18)
при условии, что 
Допустим, что функция 
при каждом 
является выпуклой по и существует 
такое, что
,
и при каждом известен обобщенный градиент 
функции по переменным . Тогда
. (6.9.19)
Доказательство. Так как функция при каждом выпукла (вниз), то 
.
Пример 6.13. Рассмотрим задачу о наилучшем Чебышевском приближении. Необходимо найти такой 
для которого
. (6.9.20)
Пусть максимум в (6.2.20) достигается при 
, т.е.
.
Функции 
выпуклы; в этом случае субградиент равен 
.
Используя (6.9.20), получим
(6.9.21)
Пример 6.14. Для задачи динамического планирования и управления запасами, сформулированной выше, целевая функция имеет вид
, (6.9.22)
где 
.
|
|
,
где 
(6.9.23)
(6.9.24)
Пример 6.15
Минимизировать 
. (6.9.25)
Очевидно, можно представить в виде
. (6.9.26)
Тогда, используя (6.9.19), получаем
|
|
(6.9.27)
