3.4. Метод субоптимизации на многообразиях. Выпуклый случай.

                Для решения задачи (3.1.2) предлагается использовать метод

субоптимизации на многообразиях. Вначале рассмотрим основные идеи, приводящие к методу субоптимизации в случае задачи выпуклого программирования общего вида.

                Рассмотрим задачу выпуклого программирования с линейными ограничениями, состоящую в минимизации выпуклой функции f(x) на множестве L, задаваемом ограничениями типа равенств.

                Предположим, что задача имеет единственное решение, т.е минимум целевой функции достигается в единственной оптимальной точке x*. В этом случае задаче (3.4.1) эквивалентна задача:

                Эквивалентность этих двух задач является следствием единственности решения. Переход к задаче (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* является оптимальной точкой задачи:

                где XÁ - линейное многообразие, определяемое следующим образом:

                Предположим, что задача (3.4.3) с условием (3.4.4) обладает свойством единственности, и среди Dj, удовлетворяющих условиям Куна-Таккера существует отрицательное Dj0, т.е.

                Пусть Á '  - множество индексов, полученное из Á  вычитанием индекса j0:

 Тогда, если x*' - оптимальный вектор задачи

то справедливо неравенство:

Доказательство.

                Так как в силу выполнения соотношения (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.10) член 0ej0. Поскольку, по предположению (3.4.5) леммы коэффициент Dj0 отличен от нуля, получаем разложение вектора градиента функции f по системе векторов {L1, .. Lm, ej (jÎ Á(x*)}. Получаем противоречие с условием единственности, а стало быть, и с условием основной леммы.

                Доказанная лемма указывает направление перебора множеств индексов Ák (а стало быть и многообразий), уменьшающее значение целевой функции f(x).

                Из доказанной леммы вытекает

                Алгоритм поиска оптимального вектора

                Общий вид алгоритма метода субоптимизации для задачи выпуклого программирования приведен на рис. 1. Ниже приводятся описания блоков алгоритма, изображенных на этом рисунке.

                Блок 1. Определяется допустимая начальная точка x1 для исходной задачи. Это может быть точка, получаемая с помощью алгоритма построения начального базиса линейного симплекс-метода, или же решение в некотором смысле близкой линейной задачи. Предполагается Á1=Á(x1), k=1.

                Блок 2. Находится оптимальный вектор x*k для задачи

                Если x*k оказывается допустимой для исходной задачи (3.4.1), совершается переход к блоку 3, в противном случае осуществляется переход к блоку 4.

                Блок 3. Вычисляется значение

                Если

                то в силу выполнения условий Куна-Таккера для исходной задачи (3.4.1) точка x*k является оптимальной точкой задачи (3.4.1) и работа алгоритма заканчивается.

                Если

                то предполагаем

                и происходит переход к блоку 2.

Блок 4. Поскольку оптимальная точка вспомогательной задачи оказалась недопустимой для исходной, выбираем в качестве новой начальной точки ближайшую к ней точку, допустимую для исходной задачи (3.4.1), и лежащую на прямой, соединяющей оптимальные точки вспомогательной задачи, т.е.

                Далее полагаем Ák+1=Á(xk+1), заменяем k на k+1, и переходим к блоку 2.

                Таким образом построен итерационный процесс, позволяющий осуществить направленный перебор множеств индексов Á k, позволяющий найти оптимальный вектор исходной задачи. Сходимость процедуры будет рассмотрена позже.

                Для решения задачи (3.1.2) предлагается использовать метод

субоптимизации на многообразиях. Вначале рассмотрим основные идеи, приводящие к методу субоптимизации в случае задачи выпуклого программирования общего вида.

                Рассмотрим задачу выпуклого программирования с линейными ограничениями, состоящую в минимизации выпуклой функции f(x) на множестве L, задаваемом ограничениями типа равенств.

                Предположим, что задача имеет единственное решение, т.е минимум целевой функции достигается в единственной оптимальной точке x*. В этом случае задаче (3.4.1) эквивалентна задача:

                Эквивалентность этих двух задач является следствием единственности решения. Переход к задаче (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* является оптимальной точкой задачи:

                где XÁ - линейное многообразие, определяемое следующим образом:

                Предположим, что задача (3.4.3) с условием (3.4.4) обладает свойством единственности, и среди Dj, удовлетворяющих условиям Куна-Таккера существует отрицательное Dj0, т.е.

                Пусть Á '  - множество индексов, полученное из Á  вычитанием индекса j0:

 Тогда, если x*' - оптимальный вектор задачи

то справедливо неравенство:

Доказательство.

                Так как в силу выполнения соотношения (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.10) член 0ej0. Поскольку, по предположению (3.4.5) леммы коэффициент Dj0 отличен от нуля, получаем разложение вектора градиента функции f по системе векторов {L1, .. Lm, ej (jÎ Á(x*)}. Получаем противоречие с условием единственности, а стало быть, и с условием основной леммы.

                Доказанная лемма указывает направление перебора множеств индексов Ák (а стало быть и многообразий), уменьшающее значение целевой функции f(x).

                Из доказанной леммы вытекает

                Алгоритм поиска оптимального вектора

                Общий вид алгоритма метода субоптимизации для задачи выпуклого программирования приведен на рис. 1. Ниже приводятся описания блоков алгоритма, изображенных на этом рисунке.

                Блок 1. Определяется допустимая начальная точка x1 для исходной задачи. Это может быть точка, получаемая с помощью алгоритма построения начального базиса линейного симплекс-метода, или же решение в некотором смысле близкой линейной задачи. Предполагается Á1=Á(x1), k=1.

                Блок 2. Находится оптимальный вектор x*k для задачи

                Если x*k оказывается допустимой для исходной задачи (3.4.1), совершается переход к блоку 3, в противном случае осуществляется переход к блоку 4.

                Блок 3. Вычисляется значение

                Если

                то в силу выполнения условий Куна-Таккера для исходной задачи (3.4.1) точка x*k является оптимальной точкой задачи (3.4.1) и работа алгоритма заканчивается.

                Если

                то предполагаем

                и происходит переход к блоку 2.

Блок 4. Поскольку оптимальная точка вспомогательной задачи оказалась недопустимой для исходной, выбираем в качестве новой начальной точки ближайшую к ней точку, допустимую для исходной задачи (3.4.1), и лежащую на прямой, соединяющей оптимальные точки вспомогательной задачи, т.е.

                Далее полагаем Ák+1=Á(xk+1), заменяем k на k+1, и переходим к блоку 2.

                Таким образом построен итерационный процесс, позволяющий осуществить направленный перебор множеств индексов Á k, позволяющий найти оптимальный вектор исходной задачи. Сходимость процедуры будет рассмотрена позже.