3.2 Условия оптимальности в задаче (3.2)
К оглавлению1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1617 18
Условия оптимальности в задаче (3.2) представляют собой формулировку условий Куна-Таккера для этой задачи. Будем рассматривать следующую форму записи условий Куна-Таккера для задачи выпуклого программирования:
(3.2.1) |
В нашем случае получим:
(3.2.2) |
Здесь Ai- столбцы матрицы A длины m, Di столбцы матрицы D длины n, Lk - строки матрицы A длины n, ej - n-мерные столбцы единичной матрицы. Здесь и далее xi - компоненты оптимального вектора задачи x, lk и Dk - множители Лагранжа условий Куна-Таккера. Запишем систему 3.2.2 в более обобщенной форме:
(3.2.3)
|
где составные столбцы P0, ... Pm+2n каждый длиной m+n являются столбцами блочной матрицы P, имеющей следующий вид:
(3.2.4) |
В таком виде условия Куна-Таккера (3.2.3) можно записать в еще более простом виде:
(3.2.5)
|
Поскольку рассматриваемая нами задача является задачей выпуклого программирования, указанные условия существования минимума являются одновременно необходимыми и достаточными. Доказательство указанных условий можно найти в [1,2].
Условия оптимальности в задаче (3.2) представляют собой формулировку условий Куна-Таккера для этой задачи. Будем рассматривать следующую форму записи условий Куна-Таккера для задачи выпуклого программирования:
(3.2.1) |
В нашем случае получим:
(3.2.2) |
Здесь Ai- столбцы матрицы A длины m, Di столбцы матрицы D длины n, Lk - строки матрицы A длины n, ej - n-мерные столбцы единичной матрицы. Здесь и далее xi - компоненты оптимального вектора задачи x, lk и Dk - множители Лагранжа условий Куна-Таккера. Запишем систему 3.2.2 в более обобщенной форме:
(3.2.3)
|
где составные столбцы P0, ... Pm+2n каждый длиной m+n являются столбцами блочной матрицы P, имеющей следующий вид:
(3.2.4) |
В таком виде условия Куна-Таккера (3.2.3) можно записать в еще более простом виде:
(3.2.5)
|
Поскольку рассматриваемая нами задача является задачей выпуклого программирования, указанные условия существования минимума являются одновременно необходимыми и достаточными. Доказательство указанных условий можно найти в [1,2].