Метод субоптимизации на многообразиях. Выпуклый случай
Для решения задачи (3.1.2) предлагается использовать метод
субоптимизации на многообразиях. Вначале рассмотрим основные идеи, приводящие к методу субоптимизации в случае задачи выпуклого программирования общего вида.
Рассмотрим задачу выпуклого программирования с линейными ограничениями, состоящую в минимизации выпуклой функции f(x)
на множестве L
, задаваемом ограничениями типа равенств.
|
|
(3.4.1) |
Предположим, что задача имеет единственное решение, т.е минимум целевой функции достигается в единственной оптимальной точке x
*
. В этом случае задаче (3.4.1) эквивалентна задача:
|
|
(3.4.2) |
Эквивалентность этих двух задач является следствием единственности решения. Переход к задаче (3.4.2) называется выделением активных ограничений, т.е. вместо условия неотрицательности всех переменных, мы переходим к условию равенства нулю всех компонент, решения, индексы которых не принадлежат множеству Á
(x*).
Предположим, что для задачи (3.4.2) нахождение оптимального решения существенно проще, чем для исходной задачи (3.4.1). В этом случае, перебирая каким-либо образом всевозможные множества индексов Á
k
, являющиеся подмножествами полного набора индексов {1,..n}
, и решая для каждого из них задачу (3.4.2), используя Á
k
вместо Á
*
, определить искомое множество индексов Á
*
.
Предположим также, что задача (3.4.2) обладает свойством
единственности, т.е система векторов {L1, .. Lm
, ej
(
j
Î
Á
(x*)}
- линейно независима. В случае нарушения свойства единственности задача поиска оптимального вектора задачи (3.4.2) усложняется, и в дальнейшем этот случай рассматриваться не будет.
Алгоритм перебора множеств индексов Á
k
основан на следующей лемме.
Основная лемма
:
Пусть x
*
является оптимальной точкой задачи:
|
|
(3.4.3) |
где X
Á
- линейное многообразие, определяемое следующим образом:
|
|
(3.4.4) |
Предположим, что задача (3.4.3) с условием (3.4.4) обладает свойством единственности, и среди D
j
, удовлетворяющих условиям Куна-Таккера существует отрицательное D
j
0
, т.е.
|
|
(3.4.5) |
Пусть Á
'
- множество индексов, полученное из Á
вычитанием индекса j
0
:
|
|
(3.4.6) |
Тогда, если x
*
' - оптимальный вектор задачи
|
|
(3.4.7) |
то справедливо неравенство:
|
f(x*')<f(x*) |
(3.4.8) |
Доказательство.
Так как в силу выполнения соотношения (3.4.6) и определения множеств X
Á
и X
Á
'
вытекает, что X
Á
'
É X
Á
то имеет место неравенство f(
x
*
')
£
f(
x
*
)
. Следовательно для доказательства соотношения (3.4.8) достаточно показать, что f(
x
*
')
¹
f(
x
*
)
.
Предположим, что это не так. Тогда точка x
*
является оптимальной для задач (3.4.3) и (3.4.7), и удовлетворяет условиям Куна-Таккера в обоих задачах:
|
|
(3.4.9) |
|
|
(3.4.10) |
Добавим в правую часть равенства (3.4.10) член 0
ej
0
. Поскольку, по предположению (3.4.5) леммы коэффициент D
j
0
отличен от нуля, получаем разложение вектора градиента функции f
по системе векторов {L1, .. Lm
, ej
(
j
Î
Á
(x*)}.
Получаем противоречие с условием единственности, а стало быть, и с условием основной леммы.
Доказанная лемма указывает направление перебора множеств индексов Á
k
(а стало быть и многообразий), уменьшающее значение целевой функции f
(
x
).
Из доказанной леммы вытекает
