8.3. МАКСИМИЗАЦИЯ ВОГНУТОЙ ФУНКЦИИ СУБОПТИМИЗАЦИЕЙ НА МНОГООБРАЗИЯХ

Метод, представленный в этом параграфе, предназначен для задачи (8.1) с вогнутой функцией Этот метод сводит исходную задачу к решению подзадач, каждая из которых содержит лишь некоторые из ограничений задачи (8.1), и сходимость достигается после того, как алгоритм решает конечное число этих подзадач. Однако сам алгоритм не является конечным процессом, так как может оказаться, что решать подзадачи за конечное число итераций невозможно. Частный случай, когда возможна конечная сходимость, рассмотрен в следующей главе.

Мотивировка. Для того чтобы понять идею, на которой основан метод, рассмотрим задачу (8.1) с вогнутой непрерывно дифференцируемой функцией и допустим, что оптимальная точка. Напишем условия Куна—Ааккера для этой задачи в специальной форме. Сначала определим Гаким образом, представляет собой множество индексов, для которых соответствующие компоненты точки х равны нулю.

Ьсли пользоваться обозначением то условия Куна — Таккера принимают вид: существуют допустимая точка х, множители неограниченные по знаку и такие, что (условие Куна —

Таккера 2)

и (условие Куна — Таккера 3)

Напомним (упр. 2.13), что при линейных ограничениях условие регулярности выполняется автоматически. Более того, так как вогнута, то условия Куна — Таккера являются также достаточными.

Исключение неравенств. Теперь допустим, что мы рассматриваем тесно связанную с (8.1) задачу

Для простоты предположим, что решение задачи (8.39) единственно. Тогда условия Куна — Таккера, показывающие, что х — оптимальная точка для задачи (8.39), могут быть записаны следующим образом.

Существует допустимая точка не ограниченные по знаку множители и также неограниченные по знаку такие, что (условие Куна — Таккера 2)

и (условие Куна — Таккера 3)

Благодаря вогнутости как и выше, условия Куна — Таккера как необходимы, так и достаточны.

Анализ условий Куна — Таккера обнаруживает, что точка — оптимальная для задачи (8.1), также

оптимальна для задачи (8.39). По предположению задача (8.39) имеет единственное решение. Следовательно, х является единственным решением задачи (8.39). Таким образом, приходим к следующему выводу: решая задачу (8.39), мы тем самым решаем задачу (8.1).

Основное значение этого результата заключается в следующем. Если можно выделить ограничения, активные в окончательном решении задачи (8.1), то в результате решения более простой задачи (8.39) определится решение задачи (8.1). Метод оптимизации, который сейчас будет рассматриваться, основан именно на этом подходе и представляет собой адаптивный метод для определения ограничений, активных в оптимальной точке. Метод эффективен, если задачи типа (8.39) решаются легко (упр. 8.8). Один такой случай, когда — квадратичная функция, обсуждается в следующей главе.

Многообразия. Задача (8.39) имеет форму максимизации на множестве решений системы линейных уравнений. Множество решений системы линейных уравнений является (лшейным) многообразием. Таким образом, задача (8.39) представляет собой задачу максимизации на многообразии.

Рассмотрим многообразия более подробно. В гл. 6 было отмечено, что многообразие подобно линейному подпространству за исключением того, что в отличие от подпространства многообразие не обязательно содержит начало координат. Примеры многообразий в включают само точку и гиперплоскость. В нашем рассмотрении важна размерность многообразия. В терминах решений систем линейных уравнений размерность многообразия представляет собой наибольшее число линейно независимых векторов, которые могут быть помещены в множество решений. Например, размерность равна гиперплоскость имеет размерность тогда как размерность точки равна нулю. Кроме того, предположим, что дана матрица В размером строки которой линейно независимы. Тогда многообразие, т. е. множество решений системы

имеет размерность . В вырожденном случае, когда размерность равна Ясно, что добавление к (8.42) линейно независимого уравнения уменьшает размерность многообразия.

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

определяя оптимальную точку

Если окажется допустимой для задачи (8.1), то переходим к и полагаем Если окажется еще и оптимальной для (8.1), то решение найдено. В случае, когда не является оптимальной по методу, который будет описан ниже, строится новая задача, и процедура продолжается.

Теперь предположим, что не является допустимой точкой для (8.1). Тогда из перемещаемся прямо по направлению к до достижения граничной точки. Эта граничная точка принимается за Кроме того, так как вогнута, удовлетворяет также соотношению где Это следует из того, что благодаря вогнутости при движении от значение функции возрастает.

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

где В — некоторое подмножество целых чисел Следует обратить внимание на то, что тогда задача (8.39) может быть сформулирована как

Единственность. Здесь также требуется свойство единственности. Предположим, что у является оптимальной точкой для задачи

Для этой задачи часть условий Куна — Таккера имеет вид

где Можем переписать (8.45) в виде

Здесь выражена как линейная комбинация строк матрицы Л и единичных координатных векторов Напомним, что единичный координатный вектор состоит из нулей, за исключением одной единицы в позиции.

Теперь можно определить свойство единственности. Точка у обладает свойством единственности, если может быть выражена в виде единственной линейной комбинации строк А и единичных координатных векторов . В практике свойство единственности имеется почти всегда. После этих замечаний сформулируем следующую лемму.

Лемма 8.2. Пусть у является оптимальной точкой для задачи

и пусть у обладает свойством единственности. Полагая, что соотношение

представляет собой часть условий Куна—Таккера для задачи (8.47), предположим, что для некоторого Тогда, если у является оптимальной точкой для

где (т. е. множество В без ), то

Доказательство. Отметим, что так как то у удовлетворяет условиям Куна — Таккера для задачи при , так как условия Куна — Таккера являются достаточными для вогнутой и линейных ограничений, то у является оптимальной точкой для задачи (8.50).

На основе свойства единственности не могут существовать величины и и которые удовлетворяют (8.48) с Поэтому в точке у условия Куна — Таккера для задачи

не удовлетворяются и у не является оптимальной точкой для задачи (8.51).

Полагая, что у — оптимальная точка для задачи (8.51), получаем Но вследствие того, что задача (8.49) имеет более слабые ограничения, чем задача (8.51),

Лемма доказана.

Замечание. Короче говоря, лемма утверждает, что если у оптимальна для задачи (8.47) с то ослаблением «жесткого» ограничения можно достигнуть более высокого значения

Теперь дадим строгую формулировку алгоритма максимизации вогнутой функции с помощью субоптимизации на многообразии.

Формулировка алгоритма. Пусть дана точка допустимая для задачи (8.1). Полагаем Переход к шагу 1 с

Шаг 1. Определить который решает задачу

Случай — допустимая точка для задачи (8.1). При помощи множителей Куна — Таккера для задачи (8.53) определяется

Если 0, то происходит останов; является оптимальной точкой для задачи (8.1). Если то определяются Производится замена на и переход к шагу 1.

Случай не является допустимой. Пусть ближайшая к допустимая точка на отрезке между Полагаем Происходит замена на и переход к шагу 1.

Доказательство сходимости за конечное число шагов. Очевидно, что если алгоритм завершает поиск, то у должна быть оптимальной точкой, так как условия Куна—Таккера удовлетворяются.

Покажем, что это завершение поиска должцо произойти после конечного числа итераций. Предположения, которые требуются при этом, заключаются в том, что должна быть вогнутой и непрерывно дифференцируемой и все задачи (8.53) должны иметь решения, которые обладают свойством единственности.

Сначала покажем, что всякий раз, когда реализуется случай 1 и поиск не завершен, целевая функция на следующем шаге должна строго возрасти. В частности, пусть допустимая, но не оптимальная точка, так что Будет показано, что также является допустимой точкой, то и справедливость неравенства вытекает из леммы 8.2. Если не является допустимой, то по лемме

Но вследствие вогнутости ее значение в любой точке между больше, чем в точке Значит, (Здесь мы предполагаем, что нет вырожденности и

Таким образом, доказано, что в случае 1

Теперь мы можем показать, что случай 1 может иметь место лишь конечное число раз. Если реализуется случай 1, то принимается равным решению данной подзадачи. Но целевая функция монотонно возрастает, и из-за условия (8.54) эта подзадача уже не может встретиться. А благодаря специфической форме подзадачи их имеется лишь конечное число. Следовательно, случай 1 без завершения поиска может реализоваться лишь конечное число раз.

Чтобы доказать искомый результат, нам необходимо теперь лишь установить, что случай 2 может произойти последовательно, без прерывания случаем 1 не более чем конечное число раз. Тогда, поскольку случай 1 реализуется лишь конечное число раз, после конечного числа шагов поиск будет завершен.

Предположим, что имеет место случай 2. так что точка не является допустимой. Весь отрезок прямой между точками входит в многообразие . Значит, также находится в Но в точке для некоторого новое переменное

Таким образом, размерность многообразия меньше, чем размерность так как добавлено по крайней мере одно новое ограничение, именно

Мы показали, что всякий раз, когда реализуется случай 2, размерность многообразия, используемого в

следующей подзадаче, уменьшается. Если случай 2 реализуется подряд достаточное число раз, то это может привести к многообразию нулевой размерности. Но такое многообразие представляет собой точку, например Подзадача максимизации на многообразии, состоящем из одной точки имеет решение Однако вследствие того, что допустимая точка, это случай 1. Поэтому после не более чем конечного числа повторений случая 2 должен наступить случай 1. Таким образом, после конечного числа повторений случая 2 наступает случай 1, а случай 1 без завершения поиска может реализоваться лишь конечное число раз; значит, после конечного числа шагов поиск должен завершиться.

Геометрическая интерпретация. Геометрически в процедуре оптимизации на многообразии мы двигаемся по направлению к точке, которая оптимизирует целевую функцию на многообразии. Если оптимальная точка многообразия допустима, но не является оптимальной для задачи (8.1), то в качестве новой точки берется оптимальная точка многообразия и рассматривается многообразие с размерностью, на единицу большей, так как опускается требование где Если оптимальная точка многообразия окажется недопустимой, в качестве новой точки берется ближайшая к оптимальной точке многообразия допустимая точка, лежащая на отрезке прямой между предыдущей точкой и точкой, оптимальной на многообразии. В новой точке дополнительно одна компонента х становится равной нулю, например Присоединяя это ограничение к предыдущему многообразию, получаем новое многообразие и двигаемся к точке, оптимальной в этом новом многообразии. Таким образом, процедура продолжается.

Упражнения

(см. скан)

(кликните для просмотра скана)

(см. скан)

Примечания и ссылки

§ 8.1. Этот алгоритм был предложен Франком и Вольфом, хотя доказательство с помощью теоремы сходимости является новым.

§ 8.2. Выпуклый симплексный метод был предложен Зангвиллом (1967g), а возможность его декомпозиции, так же как и его применимости ко многим матрицам специального вида, была обнаружена Рутенбергом. Выпуклый симплексный метод связан с алгоритмом, разработанным Вольфом (см. Вольф (1962); Лермитт и Бессиер; Фор и Хьюард. См. также Розен (1960) и Бил (1955)).

§ 8.3. Изложение основано на работе Зангвилла (1967h). Упр. 8 дает краткое введение к вопросу обобщенной обратной матрицы (см. Пенроуз). Обобщенная обратная матрица представляет собой распространение понятия обратной матрицы на матрицы, которые не имеют обратных в обычном смысле.

Дополнительные замечания

В частных случаях задачи максимизации функции при линейных ограничениях упрощаются. Такое упрощение имеет место для сепарабельных целевых функций (см. Чарис и Лемке; или Миллеп).

К упрощениям приводят также сетевые формулировки (см. Бил (1959), Хью и Зангвилл (1966b)),