Главная  Методы условной оптимизации 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [ 34 ] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

из теории н практики применения квазнньютоновской схемы к большим задачам читатель найдет в работах Тойнта (1978, 1979), Денниса и Шнабеля (1979), Тапы (1980), Пауэлла (1981).

Метод численного дифференцирования вдоль специально подбираемых конечно-разностных векторов впервые был использован Кертисом, Пауэллом и Раддом (1974). Они предложили его как средство эффективной организации поиска решения больших систем нелинейных уравнений. Применение этого метода в задачах минимизации рассматривалось Гиллом и Мюрреем (1973а). Различные формы метода, эксплуатирующие симметрию, представлены в ра-бсяе Пауэлла и Тойнта (1979). Обсуждение способов перестановки строк и столбцов разреженной матрицы произюдных, позволяющих получать желаемые структуры заполненности, содержится в работе Колемана и Море (1980).

Когда матрица Гессе разрежена, но имеет плотные факторы Холесского, можно прибегнуть к ее приближенному (частичному) разложению, генерируемому по обычным формулам. Оно пригодно для расчета направления поиска (см. Тапа (1980)) и может быть использовано для улучшения обусловленности матрицы системы в усеченном методе Ньютона.

Авторами линейного мегода сопряженных градиентов являются Хестенс и Штифель (1952). Для задач мниимизацин нелинейных функций он обобщен Флетчером и Ривсом (1964). Теоретическая эквивалентность мегода сопряженных градиентов и BFGS-метода для квадратичных функций доказана Назаретом (1979). Современный обзор различных версий метода сопряженных фадакнтов можно найти в работах Гилла и Мюррея (1979а), Флетчера (1980) и Хестен-са (1980а).

Диксон (1975) и Назарет (1977) предложили методы, которые в квадратичном случае генерируют сопряженные направления независимо от того, точно илн приближенно решаются подзадачи одномерной минимизации. Однако нх методы обладают серьезным недостатком: для произвольной нелинейной функции они могут порождать направления, вдоль которых она юзрастает. Здесь уместно отметить, что точный одномерный поиск практически не требуется и в обычном методе сопряженных градиентов. Хотя предположение о точной одномерной минимизации существенно используется для их теоретического обоснования, на практике хорошо реализованный приближенный поиск дает сравнимые, а иногда н лучшие результаты (см. Гилл и Мюррей (1979а)).

Фсрмула (4.93) метода сопряженных градиентов с произвольным начальным направлением была предложена Билом (1972) и популяризована Пауэллом (1977а). Авторами квазиньютоновских методов с ограниченной памятью являются Перри (1977) н Шанно (1978). Бакли (1978), Назарет (1979) и Носедал (1980) использовали для построения алгоритмов такого сорта связь между BFGS-мето-дом и традиционным методом сопряженных градиентов.

Одной из первых публикаций по методам улучшения обусловленности jrHHefiHbix систем уравнений является работа Аксельсона (1974). Подробности раз.1нчных методов, гголученных нз несколько иных соображений, приводятся у Конкуса, Голуба н ОЛирн (1976). О том, как использовать квазиньютоновские формулы для улучшения обусловленности в традиционном методе сопряженных градиентов, можно прочес"гь в работе Назарета и Носсдала (1978). Идея диагонального масгитабнровання с квазнньютоновской аппроксимацией принадлежит Гиллу и Мюррею (1979а).

Применение линейного метода сопряжетшых градиентов для приближенного решения ньютоновской системы обсуждалось в предыдущем ра.чделе в неявном предположении, что матрица Гессе положительно определена. ОЛири (1980а), Гилл, Мюррей и Нэш (1981) разработали модификащш этого метода, которые гюдойдут для случаев, когда это предположение не выполнено. Авторами усеченного метода Ньютона, использующего в качестве направлений спуска промежуточные векторы линейного мегода сопряженных градиентов, являются Дембо и Штайхауг (1980). Они предложили и cxe.\iy автоматического выбора числа итераций поиска решения ньютоновской системы, теоретически гарантирующую сверхлиней-иую сходимость основного алгоритма. Целесообразность применения в усеченном методе Ньютона техники улучшения обусловленности впервые была отмечена Гиллом, Мюрреем и Нэшем (1981).

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



ГЛАВА S

ЗАДАЧИ С ЛИНЕЙНЫМИ ОГРАНИЧЕНИЯМИ

Забросить к.ш1 от дома и уйти Не как изгнанник, что бредет без смысла Но выбирая свай маршрут разумно. Меняя скорость, если склон сменился.

У. X. Оден, «The Journeys (1928J

В данной главе рассматривается техника решения задач оптимизации при ограничениях типа линейных равенств нли неравенсгв. Речь пойдет только о задачах с гладкими целевыми функциями. Будут приведены методы, в полной мере использующие специфш<у линейных ограничений и получающиеся комбинированием приемов безусловной минимизации и вычислтггельной линейной алгебры. Существенная роль отводится в них множителям Лагранжа (см. разд. 3.3). Что же касается негладких задач с линейными ограничениями, то их можно решать, например, по схеме, изложенной в разд. 6.2.2.2.

Как и прежде, основное внимание мы уделим методам, в эффективности которых убедились иа собственном опыте. Иные методы даны лишь постольку, поскольку это способствует пониманию каких-то вещей либо служит основой для последующих построений. Ссылки на литературу вынесены в замечания, которыми завершается каждый раздел. Там же указаны имена авторов представленных схем и результатов.

5.1. МЕТОДЫ ПОИСКА МИНИМУМА ПРИ ОГРАНИЧЕНИЯХ-РАВЕНСТВАХ

В этом разделе мы займемся задачей минимизации гладкой функции на множестве, заданном набором линейных равенств: LEP иайти min F (к)

при ограничениях Ах=Ъ. Здесь Л есть (х п-матрица, i-я строка которой составлена коэффициентами (-го ограничения. В дальнейшем считается, что / не превосходит п и что ранг А равен /, т. е. ее строки линейно независимы. С практической точки зрентш это предположение вполне естественно: линейная зав1к:имость ограниченш"! LEP означала бы, что либо оии не совместны, либо среди них есть лишние, которые можно отбросить, не изменив решения. (Хоро-

шая программа оптимизации при линейных ограничениях должна начинать с проверки независимости равенств и исключения лишних, если таковые найдутся.) Относительно целевой функщш F будем предполагать, что она дважды непрерывно Д1[фференци-руе.ма, ограничена снизу на допустимом множестве и что ее минимум на нем достигается в конечной точке.

Необходимые условия оптимальности для LEP были получены в разд. 3.3.1. Они формируются так: если л?"-решение LEP, то найдется мepный вектор множителей Лагранжа >.•, такой, что

g() = ATX. (5.1)

Введя матрицу Z, составленную из векторов базиса подпространства, ортогонального строкам А, это равенство можно заме-

нить эквивалентным

(5.2)

Кроме того, из нсти х* следует положительная полу-

определенность м ... G(x*)Z. Напомним, что вектор Z"g(x) принято называть спроектированным градиентом функции F в х, а матрицу ZC (х) Z-ее спроектированной матрицей Гессе.

5.1.1. ПРИНЦИП ОРГАНИЗАЦИИ АЛГОРИТМОВ

5.1.1.1. Влияние линейных ограничений-равенств. Как уже

было отмечено в разд. 3.3.1, результатом подчинения «-мерного вектора переменных i линейно независимым ограничениям-равенствам будет сокращение размерности допустимого множества до п - t. Чтобы убедиться в этом, рассмотрим подпространство, натянутое на строки А, н его ортогональное дополнение. Через Y обозначим матрицу, столбцы которой образуют базис первого (например, можно взять Y- А), а через Z-матртщу из базисных векторов второго. Тогда любой п-мерный вектор х можно однозначно представить линейной комбинацией столбцов V и Z, т~ е. для любого х однозначно определятся -мерный Ху и (п-i)-мерный х, такие, что x = Vxy-{-Zx2.

Пусть теперь х-допустимый вектор задачи LEP. Для него имеем

Ax=A(Yxr-\-Zx2)~b,

а так как AZ = Q, отсюда получим

АУху = Ь. (5.3)

Поскольку матрица AV невырождена, это равенство фиксирует Ху, т. е. из всех допустимых х составляющая Ху будет одной и той же. Отличаться же оии будут то.пько (п-0-мерными составляющими значение которых ничем не ограничены. Стало



быть, размерность допустимого множества задачи LEP действительно равна п-/, причем, решив систему (5.3), построив матрицу Z и заменив аргумент х его разложением по столбцам V и Z с Ху, найденным нз (5.3), мы можем свести LEP к (п-/)-мерной задаче безусловной минимизации по х.

Пример 5.1. Рассмотрим множество, заданное единственным ограничением

х,-Ьх,-Ьх.=3.

В данном случае Лс=(1 1 1). Матрицу Y возьмем равной Л", а одной из возможных Z будет

--3---3

2=1 ±{1- -=fi. (5.4)

в 6 ,

Подставив А и выбранную Y в (5.3), получим Зху = 3, т. е. Ху = 1. Соответственно множество всех допустимых точек определится формулой

3+yj 6

з-Кз 6

3±V± 6

где Xz-двумерный вектор.

5.1.1.2. Модельная схема. Наиболее эффективные алгоритмы решения задачи LF.P работают по принципу генерирования последовательности допустимых точек с монотонно убывающими значениями целевой функции. Их практичность обусловлена простагой описания для LEP возможных перемещений. Чтобы шаг р пз какой-нибудь допустимой гочкн этой задачи не нарушил ее ограничений, необходимо н достаточно ортогональности р строкам А. Значит, имея текущее допустимое приближение Хд, направление поиска следует искать среди векторов рц, удовлетворяющих условию

Лрд = 0. (5.5)

Если Z - матрица, составленная из векторов базиса подпространства, ортогонального строкам Л, то можно утверждать, что (5.5) выполнится тогда и только тогда, когда рд будет линейной комбинацией столбцов Z, т. е. справедливо соотношение эквивалентности

Лр,=о<=>р,=гр, (5.6)

где Рг есть (п-/)-ыерный вектор. Равенстю справа и служит конструктивным описанием всех возможных для LEP направлений в .любой допустимой точке.

Используя (5.6), легко сформулировать аналог модельной схемы безусловной минимизации нз разд. 4.3.1, предназначенный для LEP:

Алгоритм LE {модельная схема решения LEP). Имея допустимую начальную точку х,, и сделав присвоение /г.-О, надо выполнить следующие действия:

LE1. [Проверка соблюдения условий останова,] Проверить, выполняются ли в Хд условия останова. Еслн выполняются, вычисления прекратить и взять Хд в качестве искомого решения.

LE2. [Расчет допустимого направления поиска.) Вычислить ненулевой (/г-/)-мерный вектор р и направление поиска

p,=Zp. (5.7)

LE3. [Расчет длины шага.] Вычислить положительное число а,, (длину шага), обеспечивающее неравенство

/(Хд-ЬЗДХ (Хд).

LE4. [Пересчетприближения.) ПоложитьХ(+,..-ХдЧ-адРд, k-k+l и вернуться к шагу LE1.

Поскольку допустимость рд из (5.7) гарантирована прн любом Pz, выбор pz, позволяющего удовлетворить условию спуска на шаге LE3, осуществляется из соображений, аналогичных испо.ль-зуемым в процедурах безусловной минимизации. В частности, при ненулевом Zg вектор Рг подбирают так, чтобы было glZp <0, т. е, чтобы (1)ормула (5.7) давала направ.11енне спуска. Что же касается способов определения а, то они просто те же, что и для случая без ограничений: так как допустимым будет любой шаг вдоль рд, никаких модификаций здесь не нужно.

Ниже мы займемся вопросом, как получать «хорошие» направления поиска для задачи LEP, вычисляя р на основе методов гл. 4. Адаптация этих методов к LEP затруднений не вызывает, и побеспокоиться надо только об одном: фюрмулы не должны опираться на те свойства задач безусловной минимизации, которых нет у LEP. К примеру, конструируя метод поиска безусловного минимума, разумно предполагать, что матрица Гессе целевой функции F положительно определена - ведь в большинстве случаев в окрестности решения так оно и будет. При решении задачи LEP это пред-по.ложенне было бы неоправданным, поскольку матрица Гессе ее целевой функции, вообще говоря, знаконеопределеиа даже в точке опти.мума.



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [ 34 ] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

0.0011