Методы наискорейшего спуска и спуска по координатам даже для квадратичной функции требуют бесконечного числа итераций. Однако можно построить такие направления спуска, что для квадратичной функции
- (3.12)
- (где r есть n-мерный вектор) с симметричной положительно определенной матрицей А процесс спуска сойдется точно к минимуму за конечное число шагов.
Положительно определенная матрица позволяет ввести норму вектора следующим образом:
Определение (3.13) означает, что под скалярным произведением двух векторов x и у теперь подразумевается величина (х, Ау). Векторы, ортогональные в смысле этого скалярного произведения
(х, Ау) = 0 (3.14)
называют сопряженными (по отношению к данной матрице А).
На этом основана большая группа методов: сопряженных градиентов, сопряженных направлений, параллельных касательных и другие.
Для квадратичной функции они применяются с одинаковым успехом. На произвольные функции наиболее хорошо обобщается метод сопряженных направлений, у которого детали алгоритма тщательно отобраны.
Сначала рассмотрим, как применяется этот метод к квадратичной форме (3.12). Для этого нам потребуются некоторые свойства сопряженных векторов.
Пусть имеется некоторая система попарно сопряженных векторов х i . Нормируем каждый из этих векторов в смысле нормы (3.14), тогда соотношения между ними примут вид
Докажем, что взаимно сопряженные векторы линейно-независимы. Из равенства
что противоречит положительной определенности матрицы. Это противоречие доказывает наше утверждение. Значит, система n-сопряженных векторов является базисом в n-мерном пространстве. Для данной матрицы имеется бесчисленное множество базисов, состоящих из взаимно сопряженных векторов.
Пусть нашли некоторый спряженный базис х i , 1 in. Выберем произвольную точку r 0 . Любое движение из этой точки можно разложить по сопряженному базису
Подставляя это выражение в правую часть формулы (3.12), преобразуем ее с учетом сопряженности базиса (3.15) к следующему виду:
Последняя сумма состоит из членов, каждый из которых соответствует только одной компоненте суммы (3.16). Это означает, что движение по одному из сопряженных направлений х i меняет только один член суммы (3.17), не затрагивая остальных.
Совершим из точки r 0 поочередные спуски до минимума по каждому из сопряженных направлений x i . Каждый спуск минимизирует свой член суммы (3.17), так что минимум квадратичной функции точно достигается после выполнения одного цикла спусков, то есть за конечное число действий.
Сопряженный базис можно построить способом параллельных касательных плоскостей.
Пусть некоторая прямая параллельна вектору х, а квадратичная функция достигает на этой прямой минимального значения в точке r 0 . Подставим уравнение этой прямой r = r 0 + бx в выражение (3.12) и потребуем выполнения условия минимума функции
ц(б) = Ф(r 0) + б 2 + б (x, 2Аr 0 + b),
и положим (dц/dб) б-0 = 0. Отсюда следует уравнение, которому удовлетворяет точка минимума:
(х, 2Аr 0 + b) = 0. (3.18)
Пусть на какой-нибудь другой прямой, параллельно первой, функция принимает минимальное значение в точке r 1 ;тогда аналогично найдем (х, 2Аr 1 + b) = 0. Вычитая это равенство из (3.18), получим
(х, А(r 1 r 0)) = 0. (3.19)
Следовательно, направление, соединяющее точки минимума на двух параллельных прямых, сопряжено направлению этих прямых.
Таким образом, всегда можно построить вектор, сопряженный произвольному заданному вектору х. Для этого достаточно провести две прямые, параллельные х, и найти на каждой прямой минимум квадратичной формы (3.12). Вектор r 1 r 0 , соединяющий эти минимумы, сопряжен х. Заметим, что прямая касается линии уровня в той точке, где функция на данной прямой принимает минимальное значение; с этим связано название способа.
Пусть имеются две параллельные m-мерные плоскости, порожденные системой сопряженных векторов х i , 1 imn. Пусть квадратичная функция достигает своего минимального значения на этих плоскостях соответственно в точках r 0 и r 1 . Аналогичными рассуждениями можно доказать, что вектор r 1 r 0 , соединяющий точки минимума, сопряжен всем векторам х i . Следовательно, если задана неполная система сопряженных векторов х i , то этим способом всегда можно построить вектор r 1 r 0 , сопряженный всем векторам этой системы.
Рассмотрим один цикл процесса построения сопряженного базиса. Пусть уже построен базис, в котором последние m векторов взаимно сопряжены, а первые n-m векторов не сопряжены последним. Найдем минимум квадратичной функции (3.12) в какой-нибудь m-мерной плоскости, порожденной последними mвекторами базиса. Поскольку эти векторы взаимно сопряжены, то для этого достаточно произвольно выбрать точку r 0 и сделать из нее спуск поочередно по каждому из этих направлений (до минимума). Точку минимума в этой плоскости обозначим через r 1 .
Теперь из точки r 1 сделаем поочередный спуск по первым n - m векторам базиса. Этот спуск выведет траекторию из первой плоскости и приведет ее в некоторую точку r 2 . Из точки r 2 снова совершим по последним m направлениям спуск, который приведет в точку r 3 . Этот спуск означает точное нахождение минимума во второй плоскости, параллельной первой плоскости. Следовательно, направление r 3 - r 1 сопряжено последним m векторам базиса.
Если одно из несопряженных направлений в базисе заменить направлением r 3 - r 1 , то в новом базисе уже m + 1 направление будет взаимно сопряжено.
Начнем расчет циклов с произвольного базиса; для него можно считать, что m=1. Описанный процесс за один цикл увеличивает на единицу число сопряженных векторов в базисе. Значит, за n - 1 цикл все векторы базиса станут сопряженными, и следующий цикл приведет траекторию в точку минимума квадратичной функции (3.12).
Хотя понятие сопряженного базиса определено только для квадратичной функции, описанный выше процесс построен так, что его можно формально применять для произвольной функции. Разумеется, что при этом находить минимум вдоль направления надо методом парабол, не используя нигде формул, связанных с конкретным видом квадратичной функции (3.12).
В малой окрестности минимума приращение достаточно гладкой функции обычно представило в виде симметричной положительно определенной квадратичной формы типа (3.2). Если бы это представление было точным, то метод сопряженных направлений сходился бы за конечное число шагов. Но представление приближенно, поэтому число шагов будет бесконечным; зато сходимость этого метода вблизи минимума будет квадратичной.
Благодаря квадратичной сходимости метод сопряженных направлений позволяет находить минимум с высокой точностью. Методы с линейной сходимостью обычно определяют экстремальные значения координат менее точно.
Метод сопряженных направлений является, по-видимому, наиболее эффективным методом спуска. Он неплохо работает и при вырожденном минимуме, и при разрешимых оврагах, и при наличии слабо наклонных участков рельефа - «плато», и при большом числе переменных - до двух десятков.
СОПРЯЖЕННЫЕ НАПРАВЛЕНИЯ
Пара направлений, исходящих из точки Рповерхности Sи таких, что содержащие их прямые являются сопряженными диаметрами индикатрисы Дюпена поверхности Sвточке Р. Для того чтобы направления (du : dv ), вточке Рповерхности Sбыли С. н., необходимо и достаточно выполнения условия
где L, М и N - коэффициенты второй квадратичной формы поверхности S, вычисленные в точке Р. Примеры: асимптотические направления, главные направления.
Лит.
: Погорелов А. В., Дифференциальная , 5 изд., М., 1969.
Е. В. Шикин.
Математическая энциклопедия. - М.: Советская энциклопедия . И. М. Виноградов . 1977-1985 .
Смотреть что такое "СОПРЯЖЕННЫЕ НАПРАВЛЕНИЯ" в других словарях:
Раздел геометрии, в к ром изучаются геометрич. образы, в первую очередь кривые и поверхности, методами математич. анализа. Обычно в Д. г. изучаются свойства кривых и поверхностей в малом, т. е. свойства сколь угодно малых их кусков. Кроме того, в … Математическая энциклопедия
1) Сумма квадратов длин сопряженных полудиаметров эллипса есть величина постоянная, равная сумме квадратов длин его полуосей. 2) Площадь описанного вокруг эллипса параллелограмма, стороны к рого имеют сопряженные направления, постоянна и равна… … Математическая энциклопедия
Направ ление на регулярной поверхности, в к ром кривизна нормального сечения поверхности равна нулю. Для того чтобы направление в точке Рбыло А. н., необходимо и достаточно выполнение условия: где внутренние координаты на поверхности, а L, М и N… … Математическая энциклопедия
Численные методы раздел вычислительной математики, посвященный математич. описанию и исследованию процессов численного решения задач линейной алгебры. Среди задач Л. а. наибольшее значение имеют две: решение системы линейных алгебраич. уравнений… … Математическая энциклопедия
Сеть линий на поверхности, образованная двумя семействами линий такими, что в каждой точке поверхности линии сети различных семейств имеют сопряженные направления. Если координатная сеть является С. с., то коэффициент М второй квадратичной формы… … Математическая энциклопедия
СО 34.21.308-2005: Гидротехника. Основные понятия. Термины и определения - Терминология СО 34.21.308 2005: Гидротехника. Основные понятия. Термины и определения: 3.10.28 аванпорт: Ограниченная волнозащитными дамбами акватория в верхнем бьефе гидроузла, снабженная причальными устройствами и предназначенная для размещения … Словарь-справочник терминов нормативно-технической документации
I I. История развития железных дорог. Ж. дорога, в том виде, в каком она существует теперь, изобретена не сразу. Три элемента, ее составляющие, рельсовый путь, перевозочные средства и двигательная сила прошли каждый отдельную стадию развития,… … Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона
Заработная плата - (Wages) Важнейшее средство повышения заинтересованности работников Участие трудящихся в доле вновь созданных материальных и духовных благ Содержание Содержание. > заработная плата - это важнейшее средство повышения заинтересованности… … Энциклопедия инвестора
Диверсификация - (Diversification) Диверсификация это инвестиционный подход направленный на снижение финансовых рынков Понятие, основные методы и цели диверсификации производства, бизнеса и финансовых рисков на валютных, фондовых и сырьевых рынках Содержание… … Энциклопедия инвестора
XIII. Дела внутренние (1866—1871). 4 го апреля 1866 года, в четвертом часу дня, Император Александр, после обычной прогулки в Летнем саду, садился в коляску, когда неизвестный человек выстрелил в него из пистолета. В эту минуту, стоявший в… … Большая биографическая энциклопедия
Шаг 1. Задать начальную точку х (0) и систему N линейно независимых направлений; возможен случай, когда s (i) = e (i) i = 1, 2, 3,..., N.
Шаг 2. Минимизировать f(x) при последовательном движении по (N +1) направлениям; при этом полученная ранее точка минимума берется в качестве исходной, а направление s (N) используется как при первом, так и последнем поиске.
Шаг 3. Определить новое сопряженное направление с помощью обобщенного свойства параллельного подпространства.
Ш а г 4. Заменить s (l) на s (2) и т. д. Заменить s (N) сопряженным направлением. Перейти к шагу 2.
Для того чтобы применить изложенный метод на практике, его необходимо дополнить процедурами проверки сходимости и линейной независимости системы направлений. Проверка линейной независимости особенно важна в тех случаях, когда функция f(x) не является квадратичной .
Из способа построения алгоритма следует, что в случае, когда целевая функция квадратична и обладает минимумом, точка минимума находится в результате реализации N циклов, включающих шаги 2, 3 и 4, где N - количество переменных. Если же функция не является квадратичной, то требуется более чем N циклов. Вместе с тем можно дать строгое доказательство того, что при некотором предположении метод Пауэлла сходится к точке локального минимума с суперлинейной скоростью (см. данное ниже определение).
Скорость сходимости. Рассматриваемый метод позволяет построить последовательность точек х (k) , которая сходится к решению x*. Метод называется сходящимся, если неравенство
≤ 1, где (3.39)
= x – х* , (3.40)
выполняется на каждой итерации. Поскольку при расчетах обычно оперируют конечными десятичными дробями, даже самый эффективный алгоритм требует проведения бесконечной последовательности итераций. Поэтому в первую очередь интерес представляют асимптотические свойства сходимости изучаемых методов. Будем говорить, что алгоритм обладает сходимостью порядка r (см. ), если
, (3.41)
где С - постоянная величина. Из формулы (3.39) следует, что при r = 1имеет место неравенство С ≤ 1. Если r = 1или r = 2, то алгоритм характеризуется линейной или квадратичной скоростью сходимости соответственно. При r = 1и С = 0 алгоритм характеризуется суперлинейной скоростью сходимости.
Пример 3.6. Метод сопряженных направлений Пауэлла
Найти точку минимума функции
f(x) = 2x + 4x x – 10x x + x ,
если задана начальная точка х (0) = T , в которой f (x (0)) = 314.
Шаг 1. s (1) = T , s (2) = T .
Шаг 2. (а) Найдем такое значение λ, при котором
f (x (0) + λs (2)) → min.
Получим: λ* - 0,81, откуда
x (l) = T - 0,81 T = T , f (x (l)) = 250.
(б) Найдем такое значение λ, при котором f (x (1) + λs (1)) → min.
λ* = – 3,26, x (2) = T , f (x (2)) = 1.10.
(в) Найдем такое значение λ, при котором f (x (2) + λs (2)) → min.
λ* = – 0.098, x (3) = T , f (x (3)) = 0.72.
Шаг 3. Положим s (3) = х (3) - x (1) = [-3.26,-0.098] T . После нормировки получим
s (3) = = [– 0,99955, – 0,03] T .
Положим s (1) = s (2) , s (2) = s (3) и перейдем к шагу 2 алгоритма.
Шаг 4. Найдем такое значение λ, при котором f (x (3) + λs (2)) → min.
λ* = – 0.734, x (4) = T , f (x (4)) = – 2,86.
Примечание. Если бы f(x) была квадратичной функцией, то полученная точка являлась бы решением задачи (если пренебречь ошибкой округления). В данном случае итерации следует продолжить до получения решения.
Направления поиска, полученные в процессе реализации метода, показаны на рис. 3.13.
Результаты вычислительных экспериментов позволяют утверждать, что метод Пауэлла (дополненный процедурой проверки линейной зависимости направлений) отличается по меньшей мере столь же высокой надежностью, как и другие методы прямого поиска, и в ряде случаев является значительно более эффективным. Поэтому проблема выбора алгоритма прямого поиска часто (и обоснованно) разрешается в пользу метода Пауэлла.
Здесь заканчивается рассмотрение методов прямого поиска решений в задачах безусловной оптимизации. В следующем разделе описываются методы, основанные на использовании производных.
Градиентные методы
В предыдущем разделе рассматривались методы, позволяющие получить решение задачи на основе использования только значений целевой функции. Важность прямых методов несомненна, поскольку в ряде практических инженерных задач информация о значениях целевой функции является единственной надежной информацией, которой располагает исследователь.
f(x) = 2x + 4x x – 10x x + x
Рис. 3.13. Решение задачи из примера 3.6 по методу сопряженных направлений Пауэлла.
С другой стороны, при использовании даже самых эффективных прямых методов для получения решения иногда требуется чрезвычайно большое количество вычислений значений функции. Это обстоятельство наряду с совершенно естественным стремлением реализовать возможности нахождения стационарных точек [т. е. точек, удовлетворяющих необходимому условию первого порядка (3.15а)] приводит к необходимости рассмотрения методов, основанных на использовании градиента целевой функции. Указанные методы носят итеративный характер так как компоненты градиента оказываются нелинейными функциями управляемых переменных.
Далее везде предполагается, что f(х), f(x) и f(x) существуют и непрерывны. Методы с использованием как первых, так и вторых производных рассматриваются лишь кратко и главным образом в их связи с более полезными методами. Особое внимание уделяется подробному изложению методов сопряженных градиентов, в основе которых лежит введенное выше понятие сопряженности направлений, и так называемых квазиньютоновских методов, которые аналогичны методу Ньютона, но используют лишь информацию о первых производных. Предполагается, что компоненты градиента могут быть записаны в аналитическом виде или с достаточно высокой точностью вычислены при помощи численных методов. Кроме того, рассматриваются способы численной аппроксимации градиентов." Все описываемые методы основаны на итерационной процедуре реализуемой в соответствии с формулой
x = x + α s (x ) (3.42)
где x - текущее приближение к решению х*; α - параметр характеризующий длину шага; s (x ) = s - направление поиска в N-мерном пространстве управляемых переменных x i , i = 1, 2, 3,..., N .Способ определения s(x) и α на каждой итерации связан с особенностями применяемого метода. Обычно выбор α осуществляется путем решения задачи минимизации f(x) в направлении s (x ). Поэтому при реализации изучаемых методов необходимо использовать эффективные алгоритмы одномерной минимизации.
3.3.1. Метод Коши
Предположим, что в некоторой точке пространства управляемых переменных требуется определить направление наискорейшего локального спуска, т. е. наибольшего локального уменьшения целевой функции. Как и ранее, разложим целевую функцию в окрестности точки в ряд Тейлора
f(x) = f ()+ f() ∆x+ … (3.43)
и отбросим члены второго порядка и выше. Нетрудно видеть, что локальное уменьшение целевой функции определяется вторым слагаемым, так как значение f () фиксировано. Наибольшее уменьшение f ассоциируется с выбором такого направления в (3.42), которому соответствует наибольшая отрицательная величина скалярного произведения, фигурирующего в качестве второго слагаемого разложения. Из свойства скалярного произведения следует, что указанный выбор обеспечивается при
s () = – f(), (3.44)
и второе слагаемое примет вид
–α f () f ().
Рассмотренный случай соответствует наискорейшему локальному спуску. Поэтому в основе простейшего градиентного метода лежит формула
x = x – α f (x ), (3.45)
где α - заданный положительный параметр. Метод обладает двумя недостатками: во-первых, возникает необходимость выбора подходящего значения α, и, во-вторых, методу свойственна медленная сходимость к точке минимума вследствие малости f в окрестности этой точки.
Таким образом, целесообразно определять значение α на каждой итерации
x = x – α f (x ), (3.46)
Значение α вычисляется путем решения задачи минимизации f (x (k +1)) вдоль направления f (x ) с помощью того или иного метода одномерного поиска. Рассматриваемый градиентный метод носит название метода наискорейшего спуска, или метода Коши, поскольку Коши первым использовал аналогичный алгоритм для решения систем линейных уравнений.
Поиск вдоль прямой в соответствии с формулой (3.46) обеспечивает более высокую надежность метода Коши по сравнению с простейшим градиентным методом, однако скорость его сходимости при решении ряда практических задач остается недопустимо низкой. Это вполне объяснимо, поскольку изменения переменных непосредственно зависят от величины градиента, которая стремится к нулю в окрестности точки минимума, и отсутствует механизм ускорения движения к точке минимума на последних итерациях. Одно из главных преимуществ метода Коши связано с его устойчивостью. Метод обладает важным свойством, которое заключается в том, что при достаточно малой длине шага итерации обеспечивают выполнение неравенства
f (x ) ≤ f (x ). (3.47)
С учетом этого свойства заметим, что метод Коши, как правило, позволяет существенно уменьшить значение целевой функции при движении из точек, расположенных на значительных расстояниях от точки минимума, и поэтому часто используется при реализации градиентных методов в качестве начальной процедуры. Наконец, на примере метода Коши можно продемонстрировать отдельные приемы, которые используются при реализации различных градиентных алгоритмов.
Пример 3.7. Метод Коши
Рассмотрим функцию
f(x) = 8x + 4x x + 5x
и используем метод Коши для решения задачи ее минимизации.
Решение. Прежде всего вычислим компоненты градиента
= 16x + 4x , = 10x + 4x .
Для того чтобы применить метод наискорейшего спуска, зададим начальное приближение
x (0) = T
и с помощью формулы (3.46) построим новое приближение
x = x -α f (x )
f (x) = 8x + 4x x + 5x
Рис. 3.14. Итерации по методу Коши с использованием метода квадратичной интерполяции.
Таблица 3.1. Результаты вычислений по методу Коши
| k | x | x | f(x ) |
| 1 | -1.2403 | 2.1181 | 24.2300 |
| 2 | 0.1441 | 0.1447 | 0.3540 |
| 3 | -0.0181 | 0.0309 | 0.0052 |
| 4 | 0.0021 | 0.0021 | 0.0000 |
Выберем α таким образом, чтобы f (x (1)) → min.; α = 0,056. Следовательно, x (1) = [– 1,20, 2.16] T Далее найдем точку
x = x – α f (x ),
вычислив градиент в точке x и проведя поиск вдоль прямой.
В таблице 3.1 представлены данные, полученные при проведении итераций на основе одномерного поиска по методу квадратичной интерполяции . Последовательность полученных точек изображена на рис. 3.14.
Несмотря на то что метод Коши не имеет большого практического значения, он реализует важнейшие шаги большинства градиентных методов. Блок-схема алгоритма Коши приведена на рис. 3.15. Заметим, что работа алгоритма завершается, когда модуль градиента или модуль вектора ∆x становится достаточно малым.
Рис. 3.15. Блок-схема метода Коши.
3.3.2. Метод Ньютона
Нетрудно видеть, что в методе Коши применяется «наилучшая» локальная стратегия поиска с использованием градиента. Однако* движение в направлении, противоположном градиенту, приводит в точку минимума лишь в том случае, когда линии уровня функции f представляют собой окружности. Таким образом, направление, противоположное градиенту, вообще говоря, не может служить приемлемым глобальным направлением поиска точек оптимума нелинейных функций. Метод Коши основывается на последовательной линейной аппроксимации целевой функции и требует вычисления значений функции и ее первых производных на каждой итерации. Для того чтобы построить более общую стратегию поиска, следует привлечь информацию о вторых производных целевой функции.
Опять разложим целевую функцию в ряд Тейлора
f(x)=f(x )+ f(x ) ∆x+½∆x f(x )∆x+O(∆x³).
Отбрасывая все члены разложения третьего порядка и выше, получим квадратичную аппроксимацию f(x):
(x; x ) = f(x ) + f(x ) T ∆x + ½∆x f(x )∆x, (3.48)
где (x; x ) - аппроксимирующая функция переменной х, построенная в точке x . На основе квадратичной аппроксимации функции f(х) сформируем последовательность итераций таким образом, чтобы во вновь получаемой точке x градиент аппроксимирующей функции обращался в нуль. Имеем
(x; x ) = + f(x )+ f(x ) = 0, (3.49)
Высокая скорость сходимости метода Ньютона обусловлена тем, что он минимизирует квадратичную функцию
Где А – симметрическая положительно определенная матрица размера nxn , за один шаг. Квазиньютоновские методы позволяют найти минимум квадратичной функции за шагов. На стремлении минимизировать квадратичную функцию за конечно число шагов основана идея метода сопряженных направлений. Точнее говоря, в методах сопряженных направлений требуется найти направлениятакие, что последовательностьодномерных минимизаций вдоль этих направлений приводит к отысканию минимума функции 2.1, т. е.при любом, где
Оказывается, что указаным свойством обладает система взаимно сопряженных относительно матрицы А направлений
Пусть А – симетрическая положительно определенная матрица размера .
Определение 2.1. Векторы (направления) иназываются сопряженными (относительно матрицы А), если они отличны от нуля и. Векторы (направления)называются взаимно сопряженными (относительно матрицы А), если все они отличны от нуля и. (2.3)
Лемма 3.1. Пусть векторы являются взаимно сопряженными. Тогда они линейно независимы.
Доказательство.
Пусть это неверно, т. е.
при некотором.
Тогда
,
что возможно только при,
так как матрица А положительно определена.
Полученное противоречие доказывает
лемму.
Рассмотрим задачу минимизации на R n функции 2.1. Будем решать ее методом 2.2. Если векторы , взаимно сопряжены, то метод 3.2 можно назвать методом сопряженных направлений. Однако обычно это название употребляется лишь для тех методов, в которых именно стремление добится условия взаимной сопряженности определяет выбор направлений. К выполнению того же самого условия может привести и реализация совершенно новой идеи.
Теорема 3.1. Если векторы h k в методе 2.2 взаимно сопряжены, k =0,1,…, m -1 , то для функции f , заданой формулой 2.1,
,
(2.4)
где – линейное подпространство, натянутое на указанные векторы.
Доказательство. С учетом 2.2 и определения 2.1 имеем
(2.5)
Используя это равенство, получаем
(2.6)
Следствие. Если векторы h k в методе 2.2 взаимно сопряженны, k =0,1,…, n -1 , то для функции f , заданной формулой 2.1, и произвольной точки
Таким образом, метод 2.2 позволяет найти точку минимума квадратичной функции 2.1 не более чем за n шагов.
2.2. Метод сопряженных направлений нулевого порядка.
Алгоритм состоит из последовательности циклов, k -й из которых определяется начальной точкой t 0 (k ) и направлениями минимизации p 0 (k ), p 1 (k ), …, p n -1 (k ) . На нулевом цикле в качестве t 0 (0), выбирается произвольная точка , в качествеp 0 (0), p 1 (k ), …, p n -1 (k ) – направления координатных осей.
Очередной k -й цикл состоит в последовательном решении одномерных задач
Тем самым определяется шаг из точки в точку
где итаковы, что
После завершения k -го цикланачальная точка и направления минимизации (k +1) -го цикла определяются по формулам
Критерием остановки может служить выполнение неравенства , где– заранее выбраное малое положительное число.
Теорема 3.2. Если векторы в методе 2.5-2.7 отличны от нуля, то для функцииf , заданой формулой 2.1
Доказательство. Учитывая следствие из теоремы 3.1, достаточно показать, что векторы взаимно сопряжены. Пусть. Предположив, что векторывзаимно сопряжены, докажем, что векторсопряжен с векторами.
Заметим, что и, стало быть, точкаt n (k ) , согласно формулам 2.5, получена из точки t n - k (k ) с помощью последовательности одномерных минимизаций вдоль направлений . Это, в силу теоремы 2.1, означает, что
Аналогично, точка t 0 (k ) получена из точки t n - k +1 (k ) помощью последовательности одномерных минимизаций вдоль тех же направлений, и поэтому
Доказываемое утверждение теперь непосредственно следует с леммы 2.2 так как .
Предположение теоремы 2.2 о том, что отличны от нуля, выполняется далеко не всегда. Система векторовможет при некоторомk оказатся линейно зависимой (или «почти» линейно зависимой), в результате чего метод может не обеспечить отыскание минимума даже квадратичной функции.
Опишем модификацию метода 2.5-2.7, приводящую к эффективному алгоритму минимизации.
После завершения k -го цикла проверяется выполнение неравенств . Если хотя бы одно с них выполнено, то производится остановка. В противном случае проверяется выполнение неравенства
,
(2.16)
Если оно выполнено, то направления минимизации (k +1) -го цикла остаются прежними, т. е.
Если нет, то направления минимизации (k +1) -го цикла определяется по формулам
В обоих случаях начальная точка (k +1) -го цикла вычисляется так, же как и в исходном алгоритме.
Подобные документы
Рассмотрение эффективности применения методов штрафов, безусловной оптимизации, сопряженных направлений и наискорейшего градиентного спуска для решения задачи поиска экстремума (максимума) функции нескольких переменных при наличии ограничения равенства.
контрольная работа , добавлен 16.08.2010
Анализ теорем сопряженных функторов. Естественное преобразование как семейство морфизмов. Характеристика свойств рефлективных подкатегорий. Знакомство с универсальными стрелками. Рассмотрение особенностей метода построения сопряженных функторов.
курсовая работа , добавлен 27.01.2013
Методика преобразования вращения и ее значение в решении алгебраических систем уравнений. Получение результирующей матрицы. Ортогональные преобразования отражением. Итерационные методы с минимизацией невязки. Решение методом сопряженных направлений.
реферат , добавлен 14.08.2009
Методы решения систем линейных алгебраических уравнений, их характеристика и отличительные черты, особенности и сферы применения. Структура метода ортогонализации и метода сопряженных градиентов, их разновидности и условия, этапы практической реализации.
курсовая работа , добавлен 01.10.2009
Численные методы поиска безусловного экстремума. Задачи безусловной минимизации. Расчет минимума функции методом покоординатного спуска. Решение задач линейного программирования графическим и симплексным методом. Работа с программой MathCAD.
курсовая работа , добавлен 30.04.2011
Формирование функции Лагранжа, условия Куна и Таккера. Численные методы оптимизации и блок-схемы. Применение методов штрафных функций, внешней точки, покоординатного спуска, сопряженных градиентов для сведения задач условной оптимизации к безусловной.
курсовая работа , добавлен 27.11.2012
Математическая модель задачи. Решение транспортной задачи методом потенциалов. Значение целевой функции. Система, состоящая из 7 уравнений с 8-ю неизвестными. Решение задач графическим методом. Выделение полуплоскости, соответствующей неравенству.
контрольная работа , добавлен 12.06.2011
Методы нахождения минимума функции одной переменной и функции многих переменных. Разработка программного обеспечения вычисления локального минимума функции Химмельблау методом покоординатного спуска. Поиск минимума функции методом золотого сечения.
курсовая работа , добавлен 12.10.2009
Решение систем линейных алгебраических уравнений методом простой итерации. Полиномиальная интерполяция функции методом Ньютона с разделенными разностями. Среднеквадратическое приближение функции. Численное интегрирование функций методом Гаусса.
курсовая работа , добавлен 14.04.2009
Основные сведения о симплекс-методе, оценка его роли и значения в линейном программировании. Геометрическая интерпретация и алгебраический смысл. Отыскание максимума и минимума линейной функции, особые случаи. Решение задачи матричным симплекс-методом.