12.3. МЕТОД БАРЬЕРОВ

Как было отмечено, сущность метода барьеров заключается в барьерной функции Однако чтобы изучить барьерную функцию, мы должны определить некоторые понятия. Внутренней частью допустимой области является множество

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

Очевидно, что состоит из и ее границы. Определение барьерной функции. Для любого определим непрерывную функцию такую, что

б) при приближении х к границе допустимой области

Условие (б) иначе можно перефразировать так: если где для всех и если для некоторого

то

Нример функции В был приведен в

Отметим, что так как незамкнутое множество, то мы можем найти подпоследовательность

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

Теперь определим для функцию

Мы предполагаем, что непрерывна, тогда непрерывна на

Подзадача. Метод барьеров требует решения следующей подзадачи для

Сейчас мы покажем, что максимизирующая точка действительно существует; тогда вместо операции может быть использована операция Здесь трудность заключается в том, что если даже компактно, то все равно не является компактным множеством, поэтому мы не можем применить результаты гл. 8. Вместо этого мы должны привлечь определение

Предположим, что

Тогда согласно определению существует такая последовательность что

Поскольку принадлежит то в. силу компактности существует сходящаяся подпоследовательность с предельной точкой

где

Вначале предположим, что тогда благодаря непрерывности

т. e. — точка максимума.

Теперь допустим, что не принадлежит а находится на границе Тогда

Но равенство (12.37) не может иметь места, так как а из свойства (б) барьерной функции

Полученное противоречие означает, что не может находиться на границе Следовательно, обязательно и мы можем в (12.35) заменить операцию операцией

Алгоритм метода барьеров. Теперь будет сформулирован метод барьеров. Пусть дана такая последовательность что По некоторой точке существование которой предполагается, определяется

И вообще, исходя из точки определяем в которой достигается Как было отмечено в § 12.1, мы можем выполнить максимизацию при наличии ограничений: методом решения задачи без ограничений, отправляясь из точки Кроме того, для всех

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

(12.1), то в любой окрестности х существует точка Это последнее предположение требует, чтобы х не была изолированной от точек, входящих в

Для доказательства сходимости нам следует вначале сформулировать следующую лемму, доказательство которой аналогично доказательству леммы 12.1 и оставляется в качестве упр. 10.

Сходимость метода барьеров будет установлена применением теоремы сходимости С. Мы определяем алгоритм последовательностью а точку х будем называть подходящей, если она будет решением задачи (12.1). Условие 1а выполняется, так как все точки х входят в допустимое множество, а согласно (12.38), если — оптимальная точка задачи (12.1), то все последующие за ней точки также являются решениями задачи (12.11).

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

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

По предположению мы можем найти точку столь близкую к х, что справедливо

Кроме того, поскольку определена и конечна. Используя тот факт, что мы можем выбрать столь большим, скажем чтобы иметь

Тогда

При этом, так как , то из выражения (12.44) вытекает, что

Этим подтверждается выполнение условия 26, и значит процедура удовлетворяет теореме сходимости С.

Следствие 12.2.1. (упр. 5).

12.3.1. Вогнутая двойственность для метода барьеров

Предположим, что

непрерывно дифференцируемы и вогнуты. Тогда, вследствие того, вогнута для (упр.

6), функция

вогнута на Так как максимизирует то справедливо

Теперь определим

Тогда для фуикции Лагранжа справедливы соотношения

и

где последнее равенство следует из (12.46).

Двойственная задача. Двойственная задача из гл. 2 благодаря вогнутости и принимает вид

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

Границы погрешностей. Из теории двойственности известно, что функция

является верхней границей для Более того, так как — допустимая точка, решение задачи, то

Отсюда видно, что

можно рассматривать как член, выражающий погрешность, поскольку его величина служит границей для разности между

Из следствия 12.2.1 и эта погрешность в пределе стремится к нулю.

Упражнения

(см. скан)

(см. скан)

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

Обсуждение метода штрафных функций взято из работы Зангвилла (1967а), а обсуждение метода барьеров можно найти в работе Фиакко и в совместной работе Фиакко и Маккормика (1964а). Эти методы и особенно метод барьеров были подробно анализированы Фиакко и Маккормиком (см. Фиакко и Маккормик (1963), (1964в) (1966а), ;(1965Ь), (,1966)).

Первые упоминания о методах штрафных функций и барьеров относятся, по крайней мере, к 1943 г.; см. Курант. Другие родственные подходы могут быть найдены у Белтрами и Мак Гилла; Батлера и Мартина; Кэррола (1959), (1961); Кемпа; Фриша; Гольдштейна и Криоке; Петршиковокого; Псшенталья; и Стонга.