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. Если
при
,
, а
, то найдется такая подпоследовательность
последовательности
, что
при
.



Доказательство. Пусть

- произвольная константа такая, что

для всех

. По определению операции проектирования и на основании условий теоремы имеем
Рассмотрим некоторое достаточно малое
. При каждом
возможны два случая:
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)