10.5. МЕТОД ДЕКОМПОЗИЦИИ НА ОСНОВЕ агрегирования в ЗАДАЧАХ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Задача квадратичного программирования

Рассмотрим теперь метод декомпозиции на основе агрегирования для блочных задач квадратичного программирования. Такие задачи можно получить из (10.4.55)-(10.4.58) путем введения в целевую функцию квадратичных членов и имеют следующий вид :

        максимизировать      (10.5.1)

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

                             (10.5.2)

 при  при                         (10.5.3)

 .                          (10.5.4)

Матрицы  по предположению симметричны и им соответствуют отрицательно определенные квадратичные формы. Для задачи (10.5.1)-(10.5.4) рассмотрим двойственную задачу в виде :

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

      (10.5.5)

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

           (10.5.6)

 при  при               (10.5.7)

 ; ; ; ; .       (10.5.8)

Введем задачу в агрегированных переменных для (10.5.1)-(10.5.4). Для этого, как и обычно, подставим  в (10.5.1)-(10.5.4), считая весовые коэффициенты фиксированными. Получим задачу:

                 максимизировать    (10.5.9)

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

; ;                     (10.5.10)

;                                 (10.5.11)

;                                 (10.5.12)

где к обозначениям (10.4.55) добавлено следующее:

 .

Нетрудно убедиться , что матрица  также симметрична и ей соответствует отрицательно определенная квадратичная форма. Двойственная задача к задаче (10.5.9)-(10.5.12) имеет вид:

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

             (10.5.13)

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

;         (10.5.14)

;;;;;; .     (10.5.15)

Пусть { } – оптимальное решение задачи (10.5.13)-(10.5.15), которое предполагается единственным. Сформулируем задачи для отдельных блоков, то есть при фиксированных j ( ):

максимизировать

       (10.5.16)

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

 ; ,                         (10.5.17)

 при  при .                (10.5.18)

Двойственные задачи для блочных задач (10.5.16)-(10.5.18) записываются в виде:

            минимизировать     (10.5.19)

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

 ; , (10.5.20)

 при  при .           (10.5.21)

Сформулируем критерий оптимальности промежуточного решения.

Пусть при некоторых весовых коэффициентах  получено оптимальное решение  макрозадачи (10.5.9)-(10.5.12) и единственным двойственным оценкам  соответствуют оптимальные решения для отдельных блоков (10.5.16)-(10.5.18). Тогда справедлива следующая теорема (52).

Теорема 10.8. Достаточным условием оптимальности дезагрегированного решения  для задачи (10.5.1)-(10.5.4) является выполнение равенства

     (10.5.22)

Если задача (10.5.1)-(10.5.4) разрешима, а { } неоптимально для нее, то в соотношении (10.5.22) знак “=” заменяется на знак “>”.

Доказательство 10.8 проводится аналогично схеме доказательства теоремы 10.7.

Задача выпуклого программирования

Обобщим метод декомпозиции на основе агрегирования переменных для блочных сепарабельних задач выпуклого программирования (общая задача выпуклого программирования рассмотрена в гл.5).

Пусть имеется задача вида:

              максимизировать (10.5.23)

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

; ,,            (10.5.24)

;,                              (10.5.25)

;,                              (10.5.26)

где при каждом фиксированном j вектор x_j имеет компоненты { } ; функции f_j(x_j), предполагаются непрерывно дифференцированными, а их частные производные удовлетворяют условию Липшица. Кроме того, предполагается, что функции f_j(x_j) – вoгнуты, а  - выпуклы.

Тогда двойственная задача для задачи (10.5.23) имеет вид:

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

        (10.5.27)

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

при                           (10.5.28)

    (10.5.29)

                                           при  ; ; ;

 0 ; ; .

Вводя агрегированные переменные ,  и весовые коэффициенты агрегирования при фиксированных , приходим к задаче в агрегированных переменных:

                                (10.5.30)

;;                      (10.5.31)

;;                              (10.5.32)

 ; .                              (10.5.33)

где для удобства обозначено

              (10.5.34)

Нетрудно убедиться , что функции , и  являются выпуклыми по переменным x_i, .

Запишем двойственную задачу для макрозадачи (10.5.30)-(10.5.33):

     (10.5.35)

  (10.5.36)

где  и  - множители Лагранжа.

Пусть при некоторых весовых коэффициентах получены оптимальные множители Лагранжа { }, для задачи (10.5.35), (10.5.36). Рассмотрим блочные задачи при каждом фиксированном j ( ):

 ,              (10.5.37)

 ; ; ;                 (10.5.38)

Двойственные задачи для блочных задач записываются в виде

,           (10.5.39)

 ,          (10.5.40)

 ,          (10.5.41)

 ; ;

Предположим, что задача (10.5.23)-(10.5.26) имеет решение и для нее выполняется условие Слейтера (см.гл.5). Тогда это же условие выполняется и для блочных задач (10.5.37) по ограничениям (10.5.38). То же самое предполагается выполненным и для макрозадачи (10.5.30) для ограничений (10.5.31), (10.5.32), если весовые коэффициенты удовлетворяют условиям

 ; ; .

Рассмотрим критерий оптимальности промежуточного решения для итеративного процесса. Пусть при некоторых значениях  получено решение задачи  задачи в агрегированных переменных (10.5.30)-(10.5.33) и { }- единственные оптимальные множители Лагранжа, которым соответствуют решения { }, ,  блочных задач (10.5.37), (10.5.38).

Тогда справедливо следующее утверждение [52].

Теорема 10.9. Достаточным условием оптимальности дезагрегированного решения{ } для задачи (10.5.23)—(10.5.26) является выполнение равенства:

 .       (10.5.42)

Если же решение { } неоптимально для задачи (10.5.23)-(10.5.26), то в соотношении (10.5.42) знак “=” заменяется на “>”.

Доказательство. Дезагрегированное решение  допустимо к задаче (10.5.23)-(10.5.26), что устанавливается непосредственной проверкой. Значение целевой функции (10.5.23) для этого решения есть . Пусть , , - оптимальные решения двойственных задач (10.5.39)-(10.5.41). Тогда набор { } удовлетворяет условиям (10.5.28) и (10.5.29) двойственной задачи, что следует из (10.5.40), (10.5.41) и (10.5.36). Иными словами, вектор ,  является решением задачи о максимизации функционала (10.5.27) при фиксированных множителях Лагранжа { }, { }, равных { }, и . Поскольку между значениями ц.ф. двойственной и прямой задач выполняется неравенство вида , то

 .          (10.5.43)

При этом равенство в (10.5.43) обеспечивает оптимальность дезагрегированного решения  для задачи (10.5.23)-(10.5.26). При условии разрешимости этой задачи и неоптимальности { } для нее соотношение (10.5.43) выполняется как строгое неравенство.

Второе слагаемое левой части неравенства (10.5.43) равняется нулю в силу теоремы Куна-Таккера (условие дополняющей нежесткости в применении к блочным задачам). Отсюда и следует справедливость теоремы 10.9.

Таким образом, общий итеративный метод решения блочных задач ЛП на основе агрегирования, рассмотренный в разделе 10.4, обобщается и на задачи квадратичного и выпуклого программирования.

Описание алгоритма декомпозиции на основе агрегування
для задач квадратичного программирования

Пусть задана блочная задача квадратичного программирования вида (10.5.1)-(10.5.4).

Предварительный этап

Зададимся начальными коэффициентами агрегирования (0), , и запишем задачу квадратичного программирования в агрегированных переменных (10.5.9)-(10.5.12).

Находим решение задачи (10.5.9)-(10.5.12) { } и { }.

Запишем двойственную задачу (10.5.13)-(10.5.15) и находим ее оптимальное решение { }.

Решаем блочные задачи (10.5.16)-(10.5.18) для всех j и находим их оптимальные решения { }, а также величину ц.ф. .

Проверяем признак оптимальности (10.5.22) для найденных значений { }, { }. Если (10.5.22) выполняется как строгое равенство, то { } – оптимальные решения. Иначе, если знак в этом соотношении “>”, то переходим к k-й итерации.

k-я итерация. Пусть уже проведены (k-1) итераций, в результате чего найдены { (k-1)}, { (k-1)}.

Формируем весовые коэффициенты :

 .

Ищем

на n-мерном гиперкубе , ( ) и находим оптимальные значения (k).

Вычисляем , , .

Записываем и решаем задачу в агрегированных переменных (10.5.9)-(10.5.12) для новых значений коэффициентов  и находим ее решения (k), , а также вычисляем .

Запишем двойственную задачу для агрегированной задачи (10.5.13)-(10.5.15) и находим ее оптимальное решение { }, { (k)}.

Для найденных значений { (k)},  формируем и решаем задачи для отдельных блоков (10.5.16)-(10.5.18) и находим их решения { (k)}.

Проверяем условие оптимальности (10.5.22) для текущего решения { }. Если (10.5.22) выполняется как строгое равенство, то конец, { } – оптимальное решение, иначе переходим к (k+1)-й итерации.