Сопряжение направленное

Основной недостаток названных и аналогичных им методов — экспоненциальный рост числа итераций с увеличением размерности задачи. Поэтому в общем случае для оптимизации ХТС более эффективными оказываются метод многогранника и метод сопряженных направлений. [c.204]

Изложение метода начнем с определения сопряженных направлений. Говорят, что два вектора х, у R представляют сопряженные направления относительно симметричной положительно определенной матрицы А размерностью пХп, если [c.206]

Следовательно, для каждой квадратной симметричной положительно определенной матрицы существует не менее одного множества сопряженных направлений. Сопряженные направления относительно А можно конструировать, исходя из линейно независимых векторов tt , U-,. .., и в R на основе метода ортогонализации. Если = и [c.206]

Доказано, что если используются сопряженные направления, то любая квадратичная функция п переменных, имеющая точный минимум, может быть минимизирована за п шагов (по одному в каждом из сопряженных направлений). Более того, порядок использования этих направлений несущественен. [c.207]

Рис. У.8. Сопряженные направления относитель но

Рис. v.9. Геометрическая интерпретация метода сопряженных направлений.

Методы переменной метрики. Движение к экстремуму целевой функции по сопряженным направлениям позволяет существенно ускорить поиск, поэтому в работах, посвященных развитию методов оптимизации, значительное внимание уделяется улучшению выбора сопряженных направлений. Особенно эффективен поиск сопряженных направлений с одновременным накоплением информации [c.210]

В методах, которые рассмотрены в этой главе, используются свойства квадратичной аппроксимации минимизируемой функции, однако они не требуют вычисления матрицы вторых производных. Мы здесь обсудим два тина методов — методы сопряженных направлений и методы переменной метрики (квазиньютоновские методы). Последнее название обусловлено следующими причинами. [c.33]

Свойства и методы сопряженных направлений [c.35]

Свойства сопряженных направлений Пусть имеется квадратичная форма [c.35]

Определение сопряженных направлений. Ненулевые векторы (направления) [c.36]

В соответствии со свойством (И,25) сопряженных направлений получим, что сумма, стоящая в правой части этого соотношения, будем равна нулю отсюда и следует соотношение (11,34). [c.38]

Пусть построены п сопряженных направлений (11,20). Согласно доказанному, эти векторы линейно независимы. Следовательно, они образуют базис в п-мерном пространстве и любой вектор, в частности, вектор может быть выражен линейно через них [29, с. 581 [c.38]

Пусть теперь построены га сопряженных направлений Рн Рп-1 И найдена точка х на последнем направлении. Поскольку векторы р ,. линейно независимы, они об- [c.39]

Умножим скалярно данное соотношение на вектор ру. Тогда, принимая во внимание свойства (11,21), (11,22) сопряженных направлений п применяя (11,41), получим [c.40]

Построение алгоритмов минимизации, использующих свойства сопряженных направлений. Здесь мы рассмотрим только алгоритмы, требующие нахождения оптимальной точки на каждом направлении. [c.40]

Перейдем теперь к вопросам минимизации неквадратичных функций. Так как понятие сопряженности направлений опиралось на свойство квадратичности функций, само это понятие в случае произвольных функций становится неопределенным. Можно было бы формально по определению считать направления сопряженными, если они удовлетворяли бы соотношениям (11,24)—(11,26). Но подобное допущение оказалось бы малополезным, поскольку в общем случае из соотношений [c.41]

Фактически все алгоритмы, использующие свойства сопряженных направлений, при применении к неквадратичным функциям строят последовательности направлений, удовлетворяющих условиям (11,24). Для простоты изложения направления, удовлетворяющие указанным условиям в случае неквадратичных функций, мы вслед за работой [30, с. 123] будем называть с о п р я - [c.41]

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

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

Конечно, при применении алгоритмов, использующих свойства сопряженных направлений, для минимизации произвольных функций мы теряем основное свойство — возможность нахождения минимума функции за п шагов. В связи с этим возникает следующая проблема. [c.42]

Методы сопряженных направлений [c.43]

Здесь рассмотрен ряд алгоритмов построения сопряженных направлений. Как было показано выше, для построения сопряженных направлений достаточно построить векторы р , удовлетворяющие условиям (11,24). В соответствии с (П,24) на -ом шаге (г < и) вектор Р1 должен быть ортогонален I векторам [c.43]

На основе описанного построения сопряженных направлений можно получить ряд алгоритмов. Прежде чем перейти к их подробному описанию, заметим, что для неквадратичных функций может не выполняться линейная независимость уо,. . ., Нетрудно показать, что линейная зависимость этих векторов приводит к равенству е,- = О, если определяется с помощью процесса ортогонализации, или к Р,-.]Уг i=0, если р, находится из (П,60), (11,64). [c.45]

Пусть Ро, Р1,. . ., Рп-1 — сопряженные направления, которые генерирует алгоритм I 2, Вп градиенты функций в оптимальных точках на поисковых направлениях. Сначала докажем вспомогательное утверждение [c.47]

Итак, формула (11,81) с коэффициентами у,, определяемыми посредством (11,82), (11,83), генерирует последовательность векторов сопряженных направлений рд,. . ., Рп 1- Поскольку векторы р находятся с точностью до скалярной величины, векторы р,-(коллинеарные векторам р,) можно считать векторами р и переписать форм лы (11,81), (11,82) следующим образом [c.48]

Выра кение (11,84) со значениями 7,, определяемыми из соотношений (11,83), (11,85)—(11,87), дает группу методов сопряженного градиента. Для квадратичных функций эти соотношения эквивалентны. Итерационный процесс (П,84) с различным способом вычисленными коэффициентами у,- дает одну и ту же последовательность сопряженных направлений и, следовательно, 1+1 = + а,Рг генерирует одну и ту же последовательность точек. Для нахождения минимума требуется не более п направлений. [c.48]

Здесь рассмотрены методы минимизации квадратичных функций (И,9), которые наряду с построением сопряженных направлений позволяют после конечного числа шагов найти матрицу, обратную к гессиану, т. е. матрицу А . Пусть на каждой итерации вектор р, определяется из соотношения (1,41). При этом векторы и,- будем строить таким образом, чтобы направления (11,20) были сопряженными, а матрицу Я,- размерности п X п находить так, чтобы на ге-ом шаге она равнялась матрице А . При этом примем, что метод обеспечивает построение ненулевых векторов р (г = О, [c.62]

Действительно, пусть построены п сопряженных направлений ро) -1 Рп- - Положим г = и в (11,118), тогда Я У = р5 (11,120) [c.62]

Определение векторов . Для сопряжения направлений р , получаемых с помощью формул (1,41), (11,118), векторы на каждой итерации необходимо подбирать таким образом, чтобы выполнялись равенства (11,31). [c.63]

Рассмотренные выше методы переменной метрики предполагают нахождение точного минимума функции на каждом направлении поиска. Однако поиск с высокой точностью минимума на каждом направлении связан с вычислением значений функции в достаточно большом числе точек, что приводит к значительному увеличению затрат времени ЭВМ на решение задачи. Поэтому в последнее время был развит ряд поисковых методов, не требующих точного линейного поиска. Упомянутые методы можно разделить на две группы. К первой относятся методы, в которых, несмотря на отсутствие точной одномерной минимизации, минимум квадратичной функции достигается за конечное число шагов. Ко второй группе относятся методы, не обладающие указанным свойством. Здесь рассмотрен только один представитель последней группы методов (см. с. 113). Основное же внимание уделено первой группе методов, которую удобно разбить на две подгруппы методы сопряженных направлений без точного линейного поиска и квазиньютоновские методы без точного линейного поиска. [c.102]

Методы сопряженных направлений без точного линейного поиска [c.103]

Идея этих методов состоит в следующем. Пусть / (х) — квадратичная функция (11,9). Для итерационного процесса Х1+т = х, + + а,/),- при произвольных с помощью того или иного метода конструируются п сопряженных направлений ро, р ,. . ., Рп-1-Затем, используя формулу (11,42), в которой коэффициенты Р определяются соотношениями (11,46), делается шаг (будем называть его завершающим ). Как было показано (см. с. 39), в результате этого шага находится точный минимум функции / (ж). Такая итерационная процедура может быть записана следующим образом [c.103]

Остановимся теперь на способе построения сопряженных направлений, не требующих точного линейного поиска. Из описанных ранее методов можно применить процесс построения сопряженных направлений, использующий процесс ортогонализации Грамма — Шмидта (11,66), (11,67), (11,69) или тождественный ему процесс с проекционной матрицей (11,60), (11,64). [c.104]

Другой способ [64] состоит в построении сопряженных направлений но системе п линейно независимых векторов. Еще один способ дается процедурой [65] [c.104]

Следовательно, посредством данного метода сопряженные направления строятся без точного линейного поиска. Поскольку для алгоритмов (11,265), (11,272), (11,174) справедливо (11,119), то Н п = рА я дополнительный шаг (11,271) дает искомое решение. Методы с точным линейным поиском могут привести к минимуму за число итераций А с и. В этом случае = О и, значит, [c.109]

Наконец, остановимся на методе [72], который можно было бы отнести к методам сопряженных направлений без точного линейного поиска. Но для удобства изложения рассмотрим его здесь — это модификация метода сопряженного градиента, не предполагающая одномерный поиск. [c.111]

Следовательно, если мы установим соотношения между gf и X и XI, то получим возможность генерировать те же сопряженные направления, что и (11,265), (11,283), (11,85) и находить точку минимума квадратичной функции за конечное число шагов Итак, при = О имеем Ро = — и о = о о- Тогда [c.111]

Наконец, может быть использована процедура завершающего шага. Кроме того, можно применить другие способы построения сопряженных направлений. Алгоритм, использующий сопряженные направления, которые построены по системе линейно независимых векторов, предложен в работе [64], а алгоритм, использующий (11,268) —(11,269) — в статье [65]. В работе [71] приведен алгоритм, который через каждые п итераций процесса (11,262), (11,281), (11,282) осуществляет параболическую интерполяцию вдоль следующих направлений [c.112]

Рассмотрим методы [24, 76], которые генерируют сопряженные направления. Приведем в начале несколько вспомогательных утверждений [c.122]

Рп — сопряженные направления. Тогда точка Х1 + х = Х1 +а,р,, где — оптимальная точка на направлении р , является точкой минимума в многообразии М [х- , р , р , ,р,), проходящем через точку х- и параллельном векторам р , р ,. . ., р . Действительно, в силу (11,37) имеем [c.122]

Определить новое сопряженное направление = х +1 — [c.123]

В соответствии с (11,26) величина (р , г/,) отлична от нуля, отсюда С = 0. Поскольку I было взято произвольно, все = О (1 = О, 1,. . ., 7г — 1), и мы пришли к противоречию, а следова-тельно, векторы р ,. . р линейно независимы. Подчеркнем, что вывод о линейной независимости векторов (11,20) суш ественно использует факт положительной определенности матрицы А-Конечность числа направлений поиска при использовании сопряженных направлений. Докажем вначале, что в точках смены направлений х,- выполняется соотношение [c.38]

В связи с этим может быть предложен следующий алгоритм. На каждой итерации (11,262) = 0, 1,...,п — 1 направленияр,-определяются с помощью формулы (1,41), в которой Я удовлетворяет уравнению (11,118), а вектор у,- — соотношениям (11,124), причем конкретно вектор у,- можно взять в виде (11,132), (11,137), (11,139). Следующая точка на п-ом шаге находится с помощью формулы (11,271). В самом деле, выполнение соотношения (11,124) обеспечивает сопряженность поисковых направлений, а как было показано (см. с. 37), сопряженные направления являются линейно независимыми. Отсюда на п-ож шаге данный алгоритм позволит получить обратную матрицу А . [c.107]

Справочник химика 21

Химия и химическая технология