9893

Итерационные методы оптимизации функций одной переменной

Реферат

Математика и математический анализ

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

Русский

2013-03-18

124 KB

37 чел.

Итерационные методы оптимизации

функций одной переменной

Методы деления интервала

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

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

Для определения интервала, содержащего точку минимума, обычно используют следующую процедуру. Выбирают две стартовые точки x и у такие, что y=x+s.

Затем, если  f(x)>f(y), определяют следующие точки  

xk+1 = xk + s  

до тех пор, пока не будет получено

f(xk) < f(xk+1).

В этом случае полученный интервал [x, xk+1] "накрывает" искомую точку минимума.

Если же f(x) < f(y), то выбирается противоположное направление. Точки строятся по правилу  

xk+1 = xk - s  

до тех пор, пока не будет получено  

f(xk) < f(xk+1).

Основной проблемой при применении описанной процедуры является правильный выбор величины s. Во многих прикладных задачах переменная изменяется в пределах многих степеней десятки (например, от 0,001 до 10000). Тогда при неправильном выборе величины s минимизация может потребовать слишком больших затрат (при очень малом s - на "накрытие" точки минимума, а при большом - на последующее за "накрытием" сужение отрезка до требуемой точности).

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

xk+1 = x0 + 2ks.

После того, как точка минимума была накрыта, нижняя граница интервала определяется тем же самым процессом, но с изменением знака перед s и в обратном направлении. Иногда такой процесс используют не только для "накрытия" точки минимума, но и для ее отыскания.

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

Метод бисекций

Этот метод позволяет на каждом шаге уменьшать вдвое длину интервала, содержащего минимум, причем значения целевой функции вычисляются с этой целью в двух определенных точках. Если выполнено n вычислений целевой функции, то длину интервала можно уменьшить в 2(n-3)/2 раза.  

Сначала разбивается исходный интервал (a0,b0).

Берется середина интервала

с0 = (a0+b0)/2,

затем две точки

e0 = (a0+c0)/2 и  d0 = (c0+b0)/2,

что дает пять точек, удаленных друг от друга на одно и то же расстояние

0 = (b0 - a0)/4.

С учетом унимодальности легко видеть, что всегда можно исключить два из четырех подынтервалов (поскольку точка минимума не может в них содержаться) и что остаются только два смежных подынтервала (a1,c1) и (c1,b1).  

Таким образом, все сводится к той же задаче, но уже на отрезке (a1,b1), длина которого в два раза меньше, чем у исходного.

На следующем шаге понадобится только два дополнительных вычисления целевой функции в точках e1=(a1+c1)/2 и d1=(c1+b1)/2 и т.д.

Глобальная сходимость метода бисекций с очевидностью следует из самого определения этого метода.


Поиск методом Фибоначчи

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

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

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

Пусть , , . Эти значения фиксированы, если известны .

Если находится в интервале , то:

1) если , то новым интервалом неопределенности будет длиной ;

2) если , то новым интервалом неопределенности будет длиной .

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

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

Числа Фибоначчи определяются следующим образом:

  ,

то есть

Если начальный интервал имеет длину , - точность вычисления значения функции, то конечный интервал неопределенности будет равен

  ,

то есть уменьшится в раз (пренебрегая ) и это наилучший гарантированный результат.

Отметим, что в начале поиска, когда известны только a и b, необходимо правильно установить первую внутреннюю точку. Она размещается на расстоянии от любого конца интервала

  ,

то есть тоже определяется с помощью чисел Фибоначчи.

Поиск методом "золотого сечения"

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

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

 

Поиск методом "золотого сечения" является предельным случаем поиска Фибоначчи и при достаточно больших n дает результат, лишь на 17% худший. Зато не требует начального задания количества вычислений функции.

Интерполяционные методы

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

Метод квадратичной интерполяции

Если известны значения функции в трех точках , , , равные , , , то функция может быть аппроксимирована квадратичной функцией (x)=Ax2+Bx+C, где A, B, C определяются из системы уравнений

 A + B + C = ,

A + B + C = ,

A + B + C = ,

то есть из системы трех линейных уравнений с тремя неизвестными.

Так как квадратичная функция (x) имеет минимум в точке -B/2A, если A>0, то точка минимума может быть аппроксимирована значением

  .

Опишем алгоритм. Пусть - унимодальная функция одной переменной, A - начальная аппроксимация положения минимума, длина шага H является величиной того же порядка, что и расстояние от точки A до истинного минимума (условие, которое не просто удовлетворить).

Алгоритм квадратичной интерполяции:

1. Вычислить f(A), f(A+H).

2. Если f(A)<f(A+H), то взять в качестве третьей точки A-H и вычислить f(A-H). В противном случае взять точку A+2H и вычислить f(A+2H).

3. Используя эти три точки, найти аппроксимацию точки минимума и вычислить f().

4. Если разность между f() и предыдущим наименьшим значением функции меньше заданной точности, то процедура заканчивается.

5. Если процедура не завершилась на шаге 4, то точка с наибольшим значением отбрасывается и выполняется переход на шаг 3. Но если, оставив точку с наибольшим значением, мы определим конечные границы интервала, в котором лежит минимум, то следует действительно оставить эту точку, отбросить другую и вернуться на шаг 3.

   

 

 

 В примере на рисунке 2 оставляем , а не , хотя x1 и дает наибольшее значение функции.

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

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

Метод кубической интерполяции

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

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

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

Пусть минимизируется функция на прямой , то есть функция

 

.

Предполагаем, что известны следующие значения:

.

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

Если выбрать p=0 (для простоты), то уравнения, определяющие a, b, c, d, выглядят так:

 

Эти уравнения имеют решение:

 

Стационарные точки кубического полинома являются решением уравнения

 

Точкой минимума кубического полинома является

,      (*)

Как уже отмечалось, это все выполняется при =0. Выбор q осуществляется из следующих соображений.

Если < 0, то следует выбирать q>0, то есть сделать шаг в направлении убывания функции (h). В противном случае q<0.  Значение q должно быть таким, чтобы интервал (0, q) содержал минимум. Это будет верно, если (q)>(p) или >0 (даже при (q)<(p)). Если ни одно из этих условий не выполнено, то надо удвоить q, повторяя это до тех пор, пока полученный интервал не будет содержать минимум.

Остается задача определения начальной величины q. Значение q, которое было бы одинаково приемлемо для всех задач, выбрать весьма сложно. Дэвидон, Флетчер и Пауэлл предложили выбирать q следующим образом:

, где - оценка наименьшего значения (h), = const (2 или 1).

Алгоритм кубической интерполяции.

1. Найти и .

2. Проверить, выполняется ли условие <0. Если не выполняется, производить поиск в направлении - , иначе - в направлении . Выбрать q в соответствии с рекомендациями (при этом необходимо "угадать" ).

3. Вычислить

4. Если или , то интервал, содержащий минимум, найден. Иначе положить q = 2q и перейти к 3.

5. Использовать выражение (*) для аппроксимации точки минимума на интервале (0, q) значением r.

6. Если , где - заданная точность, то остановиться.

7. Вернуться на шаг 5, используя интервал (0, r), если >0, либо используя интервал (r, q), если < 0.

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


Итерационный метод
regula falsi

Хорошо известный метод секущих отыскания нуля функции первоначально назывался методом regula falsi или regula falsorum. Этот метод правильно предсказывает положение нуля функции, если она зависит линейно от своего аргумента. Если даны две точки a и b и значения функции в них, то формула предсказания положения нуля функции имеет вид:

 c = a - f(a)  .

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

 c = a – f’ (a) .

Если f'(с)0, то процедура может быть продолжена итеративно с использованием уменьшенного интервала [a,c], если f'(c) и f'(b) имеют одинаковый знак, или [c,b], если f'(c) и f'(a) имеют одинаковый знак. Если f'(a) и f'(b) имеют одинаковый знак, то точка c должна лежать вне отрезка [a,b]. Если f'(c) имеет опять тот же знак, то c заменяет ту точку, которая дает наибольшее значение производной. Если f'(c) имеет другой знак, то можно продолжать процедуру regula falsi итеративно до тех пор, пока не будет получена точка с нулевой (или достаточно малой) производной.

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

Итерационный метод Ньютона-Рафсона

Интерполяционная формула Ньютона для улучшения приближенного решения уравнения f(x)=0

   xk+1 = xkf(xk)/f'(xk) 

использует только одну точку, но требует оценки значения функции и ее производной. Если функция линейна по x, то ноль функции будет указан точно, в противном случае будет получено только улучшенное значение и процесс должен быть повторен. Как и в предыдущем случае эта рекуррентная формула может быть применена для поиска нуля производной, то есть для определения точки минимума самой функции. Соответствующая итерационная формула, называемая также правилом Ньютона-Рафсона, имеет вид:

   xk+1 = xkf'(xk)/f''(xk).

Если целевая функция не является квадратичной, то понадобится несколько итераций до тех пор, пока не будет удовлетворен критерий останова.

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

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

- не различаются точки минимумов, максимумов и перегибов. Уже стартовая точка должна выбираться как можно ближе к искомому минимуму;

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

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


f(x)

    Рис. 2. Выбор границ интервала

x1

x2

x3

x4

x


 

А также другие работы, которые могут Вас заинтересовать

44764. Предприятие как субъект и объект предпринимательской деятельности 57.38 KB
  Функционирование предприятий в условиях рынка предполагает поиск и разработку каждым из них собственного пути развития. Чтобы не только удержаться, но и развиваться в рынке, предприятие должно улучшать состояние своей экономики
44765. Банковский маркетинг, Краткий конспект лекций 99.59 KB
  Основные понятия банковского маркетинга. Роль маркетинга в банковской деятельности. Концепция банковской технологии маркетинга. Банковская маркетинговая стратегия. Постановка маркетинговой работы в коммерческом банке. Банковская конкуренция. Маркетинг депозитарной деятельности банка. Маркетинг кредитного банковского рынка...
44766. Проект доготовочного цеха блинной на 50 мест в г.Омске 1.04 MB
  Качество обслуживания оказывает непосредственное влияние на результаты хозяйственной деятельности предприятий общественного питания. Повышения качества обслуживания способствует увеличению количества потребителей, росту товарооборота, повышению рентабельности предприятий.
44767. Электроснабжение участка токарного цеха 5.73 MB
  Сегодня на предприятии в трех цехах трудится около полутора тысяч человек - токарей, кузнецов, слесарей, электрогазосварщиков, электриков, электромонтеров, и многих других, которым приходится знать и ремонтировать самое разное горнодобывающее и металлургическое оборудование.
44768. Анализ потребительских свойств и качеств темного пива 486.5 KB
  Пиво — один из древнейших напитков в мире. Пиво известно со времен Древнего Египта (многие считают, что пшеницу и ячмень там начали культивировать для приготовления пива, а изготовление хлеба стало побочным эффектом). В ходе археологических раскопок в Египте был найден самый древний рецепт пива. В Римской империи пиво не пользовалось популярностью, здесь предпочтение отдавалось вину
44769. Изучение ассортимента, конкурентоспособности, показатели качества чая, реализуемого Иркутским Облпотребсоюзом 725 KB
  Древняя китайская мудрость гласит: Лучше обойтись три дня без еды, чем один день без чая. В этой стране чай употребляют более 5 тысяч лет. По сравнению с Китаем, Россия имеет с этим напитком лишь шапочное знакомство 300 лет. Но даже за это время чаепитие стало национальной русской традицией
44770. Изучение ассортимента и качества пряностей, реализуемых в розничном торговом предприятии г. Москвы 289 KB
  Пряностями являются разные части растений со специфическим ароматом, разной степенью жгучести и вкуса. Эти растения относятся более чем к 30 различным ботаническим семействам. Это сухие корни, семена или кора душистых растений. Они могут употребляться в целом либо измельченном виде
44771. Особенностями приготовления блюд немецкой кухни 178.5 KB
  Целью выполнения курсовой работы является ознакомление с особенностями приготовления блюд немецкой кухни, закрепление и углубление знаний будущего инженера, способного не только технически грамотно владеть существующими технологическими процессами, но и совершенствовать их и создавать новые, обеспечивающие повышение качества продукции и эффективность производства.
44772. Анализ технологии приготовления вторых горячих блюд из рыбы 1.85 MB
  Обитатели глубин содержат необходимые нашему организму витамины (особенно А и D), жиры, белки (мясо рыб содержит 18% белков). Белки мяса рыб легче усваиваются организмом человека, чем белки мяса животных. Ценной составной частью рыб, особенно океанических, является жир. Рыбий жир характеризуется высоким содержанием непредельных жирных кислот