Метод золотого сечения

Содержание. Введение. … 4 стр. I. Методы одномерной оптимизации… 6 стр. II. Метод золотого сечения … 7 стр. Заключение. Сравнение методов одномерного поиска . 10 стр. Приложение Приложение 1. Листинг программы… 11 стр. Приложение 2. Результат работы программы………… 12 стр. Список используемых источников… 13 стр. Введение.

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

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

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

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

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

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

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

которой соответствует наименьшая величина (преимущество такого выбора в том, что, во-первых, сохраняется гарантия получить реальную длину интервала неопределенности, не превышающую , и во-вторых, эта гарантированная длина минимальна). Обозначив рассматриваемый минимум как , получим Величина определяет единственную стратегию, называемую минимаксной. Всякое отклонение от нее приведет лишь к опасности ухудшения результат будущего поиска.

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

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

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

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

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

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

равна  независимо от того, какие из значений функции в пробных точках оказались меньшим. Предположим, что исключается правый подынтервал. На рис 1.2 показано, что оставшийся подынтервал длины  содержит одну пробную точку, расположенную на расстоянии (1-) от левой граничной точки. Отношение длин отрезков определяется правилом золотого сечения: Решая это квадратное уравнение, получаем откуда положительное решение =0.61803….

Таким образом, деление интервала неопределенности в этом отношении позволяют уменьшить его в раза. Начиная с , приходят в конце концов к интервалу неопределенности: Алгоритм поиска с помощью данного метода выглядит следующим образом. Шаг 1. Положить x0=a, x3=b. Шаг 2. Положить x1=x0+t1∙(x3-x0). Вычислить значение φ(x1). Шаг 3. Положить x2=x0+t2•(x3-x0).

Вычислить значение φ (x2). Шаг 4. Сравнить φ(x2) и φ(x1). Если φ(x1)> φ(x2), исключить интервал (x0, x1), положив x0=x1. Перейти к шагу 5. Если φ(x1)< φ (x2), исключить интервал (x2, x3), положив x3=x2. Перейти к шагу 5. Шаг 5. Сравнить длину интервала с заданной точностью : . Если неравенство выполняется, то перейти к шагу 4.

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

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

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

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

не существует универсального алгоритма, который позволял бы решать любые задачи. Решая сложные задачи оптимизации, следует пользоваться разными методами, так как это позволяет увеличить долю удачных решений. Относительная точность вычисления точки оптимума Методы оптимизации перебора дихотомии трихотомии золотого сечения Фибоначчи 0,1 11 5-8 8 6 6 0,01 101 8-14 20 11 11 0,001 1001 11-20 32 15 15 0,0001 10001 15-28 42 20 20

Приложение. Приложение № 1. Листинг программы. Программа запрашивает интервал неопределенности и требуемую точность вычисления. Результатом работы программы является вывод координаты точки экстремума функции и значение функции в этой точке. program ZolotoeSechenie; const t1=0.382; const t2=0.618; var i: integer; Eps, a,b,x0,x1,x2,x3,x: real; function f(x:real):real; begin f:=2*x*x-ln(x); end; begin writeln ('Поиск экстремума функции одной переменной методом золотого сечения'); writeln ('Введите интервал неопределенности');

readln (a, b); writeln ('Введите требуемую точность'); readln (Eps); x0:=a; x3:=b; i:=0; while abs (x3-x0) > Eps do begin inc(i); x1:=x0+t1*(x3-x0); x2:=x0+t2*(x3-x0); if f(x1)>f(x2) then x0:=x1; if f(x1)

сечения Введите интервал неопределенности 0 10 Введите требуемую точность 0.0001 Значение функции в точке экстремума f( 5.0002792383E-01)= 1.1931471837E+00 Количество итераций 24 Поиск экстремума функции одной переменно методом золотого сечения Введите интервал неопределенности 0 4 Введите требуемую точность 0.01 Значение функции в точке экстремума f( 5.018330E-01)= 1.1931471806E+00

Количество итераций 32 Поиск экстремума функции одной переменно методом золотого сечения Введите интервал неопределенности 0 4 Введите требуемую точность 0.0001 Значение функции в точке экстремума f( 4.9999405402E-01)= 1.1931471807E+00 Количество итераций 23 Используемая литература. 1. Дегтярев Ю.И. Методы оптимизации. М.: Советское радио,

1980. 2. Карманов В.Г. Математическое программирование. М.: ФИЗМАТЛИТ, 2001. 3. Полак Э. Численные методы оптимизации. М.: Мир, 1974. 4. Шуп Т.П. Решение инженерных задач на ЭВМ: Практическое руководство. М.: Мир, 1982.