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 вектор xj имеет компоненты {
} ; функции fj(xj),
предполагаются непрерывно дифференцированными, а их частные производные удовлетворяют условию Липшица. Кроме того, предполагается, что функции fj(xj) - в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)
Нетрудно убедиться , что функции 
, 
и 
являются выпуклыми по переменным xi, .
Запишем двойственную задачу для макрозадачи (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)-й итерации.
