Eng | Rus | Ukr
Исследование операций
24.12.2008

<< prev | ^up^ | next >>

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) при  или .

Пример 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)

<< prev | ^up^ | next >>

 
     
  Copyright © 2002-2004