Этап установления границ интервала

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

 

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

 

Свойства функций одной переменной

Согласно наиболее простому определению, функция f(х) представляет собой правило, которое позволяет каждому значению х поставить в соответствие единственное значение у=f(х). В этом случае х носит название независимой переменной, а у — за висимой переменной. Рассмотрим множество SÌR, где R — множество всех действительных чисел. Мы можем определить соответствие (или преобразование), с помощью которого каждой точке хÎ S приписывается единственное числовое значение. Такое соответствие называется скалярной функцией f, определенной на множестве S.

Когда множество S=R, мы имеем дело со всюду определенной функцией одной переменной. Если S есть некоторое подмножество множества R, то функция f определена в ограниченной области. Например,

f(х)=х³+2х²—х+3для всех х Î R

есть всюду определенная функция, тогда как функция

f(х)=х³+2х²—х+3для всех х Î R= {х|—5≤ х ≤5}

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

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

 

Например, если мы строим график функции, которая измеряет затраты на сообщение некоторой системе количества тепла, равного 1 БТЕ (Британская тепловая единица; 1 БТЕ = 252 кал,— Прим. перев.), при различных температурах системы, то в результате получаем кусочно-непрерывную кривую, изображенную на рис. 2.1. Затраты описываются разрывной функцией температуры системы; однако температура системы может принимать все значения в диапазоне от 200 до 3000 градусов по шкале Фаренгейта.

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

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

1) сумма или произведение непрерывных функций является непрерывной функцией;

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

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

 

 

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

Монотонные функции. Функция f(х) является монотонной (как при возрастании, так и при убывании), если для двух произвольных точек х₁ и х₂, таких, что х₁≤ х₂, выполняется одно из следующих неравенств:

f(х₁) ≤ f (х₂) (монотонно возрастающая функция),

f(х₁) ≥ f (х₂) (монотонно убывающая функция).

На рис. 2.3 представлен график монотонно возрастающей функции, а на рис. 2.4 — график монотонно убывающей функции. Заметим, что монотонная функция не обязательно должна быть непрерывной. На рис. 2.5 изображен график функции, которая монотонно убывает при х≤0 и монотонно возрастает при х≥0. Функция достигает своего минимума в точке х=х* (начале координат) и монотонна по обе стороны от точки минимума. Такие функции называются унимодальными.

Определение

Функция f(х) является унимодальной на отрезке а≤х≤b в том и только том случае, если она монотонна по обе стороны от единственной на рассматриваемом интервале оптимальной точки х*. Другими словами, если х*— единственная точка минимума f(x) на отрезке а≤х≤b, то f(х) оказывается унимодальной на данном интервале тогда и только тогда, когда для точек х₁и х₂

из x*≤x₁≤x₂ следует, что f(x*)≤f(x₁)≤f(x₂),

и

из x*≥x₁≥x₂следует, что f(x*)≤f(x₁)≤f(x₂).

 

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

Критерии оптимальности

 

При анализе оптимизационных задач, как правило, возникают два общих вопроса.

1. Вопрос анализа «в статике». Как определить, представляет ли данная точка х* оптимальное решение задачи?

2. Вопрос анализа «в динамике». Если х* не является точкой оптимума, то какая последовательность действий приводит к получению оптимального решения?

В этом разделе основное внимание уделяется решению вопроса анализа «в статике», а именно построению множества критериев оптимальности, позволяющих определить, является ли данное ре­шение оптимальным.

Определения

Функция f(x), определенная на множестве S, достигает своего глобального минимума в точке х** Î S том и только том случае, если

Функция f(x), определенная на множестве S, имеет локальный ми­нимум (относительный минимум) в точке x* Î S в том и только том случае, если

т.е если существует e > 0, такое, что для всех х, удовлетворяющих условию ïх-х*ï <e, выполняется неравенство f(x*) ≤ f(x)

Замечания

1. Аналогичные определения глобального максимума и локаль­ного максимума можно получить путем замены знака неравенства на противоположный.

2. Если функция обладает свойством унимодальности, то ло­кальный минимум автоматически является глобальным минимумом.

 

 

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

На рис. 2.7 точка х₁— точка глобального максимума, х₂ — точка локального минимума, х₃ — точка локального максимума, х₄ — точка глобального минимума, а х₅можно рассматривать и как точку локального минимума, и как точку локального максимума.

Идентификация оптимумов в случае фун­кции одной переменной. Предположим, что функция f(x) одной переменной х определена на открытом интервале (a, b) и n-кратно дифференцируема на этом интервале. Если х*— внут­ренняя точка интервала, то теорема Тейлора позволяет записать изменение функции f при переходе от точки х* к точке (х*+e) в следующем виде:

где через О_n+1(e) обозначена сумма членов, в которых степень e равна (n+1) и выше. Если х*— локальный минимум функции f на (а, b), то по определению должна существовать e-окрестность точки х*, такая, что для всех х из этой окрестности выполняется нера­венство

f(x) ³ f(x*)                                                                      (2.2)

Из неравенства (2.2) следует, что

При достаточно малом e первое слагаемое доминирует над осталь­ными, а так как e можно выбрать и положительным, и отрицатель­ным, то неравенство (2.3) будет выполняться только в том случае, если:

                                                                  (2.4)

Рассуждая аналогичным образом, нетрудно установить, что нера­венство (2.3) будет справедливым только тогда, когда

                                                                (2.5)

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

Теорема 2.1

Необходимые условия того, что х* является точкой локального минимума (максимума) дважды дифференцируемой функции f на открытом интервале (а, b), выражаются следующими соотношениями:

Эти условия являются необходимыми, т. е. в случае, когда они не выполняются, точка х* неможет быть точкой локального минимума (максимума). С другой сторо­ны, если эти условия выполня­ются, мы не имеем гарантии, что х* является точкой локаль­ного минимума (максимума). Рассмотрим, например, функцию f(x)=x³, график которой пред­ставлен на рис. 2.8. Эта функ­ция удовлетворяет необходимым условиям наличия как локаль­ного минимума, так и локаль­ного максимума в начале коор­динат, однако не имеет ни мак­симума, ни минимума при х*=0.

Определения

Стационарной точкой называется точка х*, в которой

Если стационарная точка не соответствует локальному оптиму­му (минимуму или максимуму), то она является точкой перегиба, или седловой точкой.

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

Теорема 2.2

Пусть в точке х* первые (п—1) производные функции обращаются в нуль, а производная порядка п отлична от нуля.

(1) Если п — нечетное, то х*— точка перегиба.

(2) Если п — четное, то х*— точка локального оптимума.

Кроме того,

(а) если эта производная положительная, то х*— точка локаль­ного минимума;

(б) если эта производная отрицательная, то х*— точка локаль­ного максимума.

Доказательство

Утверждение теоремы нетрудно доказать с помощью разложения в ряд Тейлора, представленного равенством (2.1). Поскольку поря­док первой отличной от нуля производной равен п, формулу (2.1) можно переписать в следующем виде:

Если п — нечетное число, то правая часть (2.6) может принимать как положительные, так и отрицательные значения в зависимости от того, является ли величина e положительной или отрицательной. Это означает, что в зависимости от знака e разность f(x*+e) - f (x*) либо положительная, либо отрицательная. Следовательно, функция не достигает в точке х* своего минимального или максимального значения, т. е. х*— точка перегиба.

Далее рассмотрим случай, когда п — четное число. При этом ве­личина eⁿ всегда положительная, а знак правой части (2.6) опреде­ляется первым слагаемым, если e— достаточно малая величина. Таким образом, если величина (dⁿf /dxⁿ )ï_x=x* положительная, то f(x*+e)- f (х*)>0 и точка х* соответствует локальному минимуму. Аналогичные рассуждения нетрудно провести также и для локаль­ного максимума.

Для того чтобы применить теорему 2.2 к функции f(x)=x³, гра­фик которой изображен на рис. 2.8, вычислим

Так как порядок первой отличной от нуля производной равен 3 (нечетное число), точка х=0является точкой перегиба.

Замечание

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

Эта функция непрерывна во всех точках действительной оси, но не­дифференцируема при х=2. Функция достигает максимума в точке х=2, которая не является стационарной в соответствии с данным выше определением.

Пример 2.1

Рассмотрим функцию

определенную на всей действительной оси. Первая производная этой функции равна

df /dx =30х^{5 +} 180х⁴+ 330х³— 180х² = 30х² (х—1) (х—2) (х—3).

Ясно, что первая производная обращается в нуль в точках х = 0, 1, 2, 3, и, следовательно, эти точки можно классифицировать как стационарные. Вторая производная функции равна

Вычислив значения второй производной в четырех точках х = 0, 1, 2, 3, получим

 

x	f(x)	d2f /dx2
0	36	0
1	27,5	60
2	44	-120
3	5,5	540

 

Отсюда следует вывод, что х=1, 3 — точки локальных минимумов, а х=2— точка локального максимума. Чтобы идентифицировать точку х=0, вычислим третью производную

Так как эта производная отлична от нуля и имеет нечетный порядок, то точка х=0является не точкой оптимума, а точкой перегиба.

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

Максимизировать f(x) при ограничении а ≤ x ≤ b,

где а и b — установленные границы изменения значений перемен­ной х.

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

Шаг 1. Приравнять df/dx=0и найти все стационарные точки.

Шаг 2. Выбрать все стационарные точки, которые располо­жены в интервале [а, b]. Обозначим эти точки через x₁, х₂, . . . , х_N.

Проверку наличия локального оптимума следует проводить только на множестве указанных точек, дополненном точками а и b.

Шаг 3. Найти наибольшее значение f(x) из множества f(а), f(b), f(x₁), . . . , f(x_N). Это значение соответствует глобальному максимуму.

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

Пример 2.2

Максимизировать f(x)= - x³+Зх²+9х+10 на интервале -2≤ х ≤4.Имеем

Решая это уравнение, получаем две стационарные точки х=3и x= -1, которые расположены внутри заданного интервала.

Для того чтобы найти глобальный максимум, вычислим значения f(x) в точках х = 3, - 1, - 2 и 4:

Таким образом, точка х =3соответствует максимальному значению f на интервале [—2, 4].

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

Пример 2.3

Исследуем свойства функции

При х≤1 имеем f"(х)≤0, и, следовательно, функция является вог­нутой в указанной области. Если же х³ 1то f"(x)³0, т. е. функ­ция является выпуклой в этой области.

Заметим, что функция имеет две стационарные точки х= -¹/₂ и x= ⁵/₂. Поскольку f"(-¹/₂)<0, функция обладает локальным мак­симумом при х= -¹/₂. В точке x= ⁵/₂ вторая производная f"(⁵/₂)>0, и, следовательно, функция достигает в этой точке локального ми­нимума. Если ограничить допустимую область неравенством х≤1, то f(x) имеет глобальный максимум при х= -¹/₂, так как f(x) — вогнутая функция (в данной области) и х= -¹/₂ — точка локаль­ного максимума. Аналогично если ограничить допустимую область неравенством х³1, то f(x) достигает глобального минимума при х= ⁵/₂. Однако если переменная х изменяется на всей действительной оси от -∞ до +∞, то функция f(x) не имеет конечного глобального максимума или минимума.

Пример 2.4. Задача управления запасами

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

В рамках этой модели спрос предполагается постоянным и рав­ным l, единиц товара в год. Частое пополнение запасов нецелесооб­разно, так как стоимость выполнения одного заказа составляет К долл. независимо от его размера. Первоначальная стоимость еди­ницы товара равна с долл. Хранение излишних запасов также не­целесообразно, поскольку стоимость хранения единицы товара от­лична от нуля и составляет h долл. в год. Для того чтобы упростить задачу, предположим, что спрос удовлетворяется немедленно (т. е. задолженные заказы отсутствуют), а пополнение осуществляется сразу же, как только запасы иссякают.

Рис. 2.9 иллюстрирует изменение объема запасов с течением времени. В точке А объем запасов равен В; затем объем запасов начинает уменьшаться со скоростью lединиц товара в единицу вре­мени и достигает нулевого значения в точке С. В это время посту­пает новая партия товара, и объем запасов восстанавливается.

Треугольник ABC представляет один цикл управления запасами, который повторяется во времени. Задача заключается в том, чтобы определить оптимальный размер заказа В и продолжительностьинтервала времени между заказами С — А. Обозначим соответ­ствующие переменные через Q и Т.

Поскольку Т есть величина промежутка времени, в течение ко­торого при скорости расходования lистощается запас Q, имеем T=Q/l. Таким образом, задача сводится к нахождению оптималь­ного значения Q. Заметим, что когда Q мало, переменная Т также принимает малое значение. При этом частота заказов велика, что обусловливает большие затраты на выполнение заказов и относи­тельно малые издержки хранения запасов. С другой стороны, нали­чие большого объема запасов (Q велико) приводит к увеличению затрат на хранение запасов и одновременно к снижению издержек, связанных с выполнением заказов на товары. Одна из основных задач управления запасами состоит в определении оптимального значе­ния Q, которому соответствует минимум суммы полных годовых затрат.

Получим аналитическое выражение для функции полных годо­вых затрат (затраты/цикл x количество циклов/год).

Примечание. Затраты на хранение запасов в течение цикла рав­ны затратам на хранение Q/2 единиц товара в течение интервала времени Т.

Таким образом, подлежащая минимизации функция полных затрат есть

Отсюда следует, что f(Q) — выпуклая функция и если существует положительное значение Q*, такое, что f(Q*)=0, то Q* минимизи­рует f(Q).

При этом Т*— интервал времени между заказами = l. Величина Q* известна в теории управления запасами как наиболее экономичный размер заказа.

Методы исключения интервалов

В разд. 2.2 рассматривался вопрос анализа «в статике», который заключается в том, чтобы определить, является ли данное решение оптимальным. Для этого были построены необходимые и достаточ­ные условия оптимальности решения. Далее мы переходим к изу­чению вопроса анализа «в динамике», связанного с нахождением оп­тимального решения. С этой целью ниже рассматривается ряд одно­мерных методов поиска, ориентированных на нахождение точки оптимума внутри заданного интервала. Методы поиска, которые позволяют определить оптимум функции одной переменной путем последовательного исключения подынтервалов и, следовательно, путем уменьшения интервала поиска, носят название методов исключения интервалов.

В разд. 2.1 было дано определение унимодальной функции. Уни­модальность функций является исключительно важным свойством. Фактически все одномерные методы поиска, используемые на прак­тике, основаны на предположении, что исследуемая функция в до­пустимой области по крайней мере обладает свойством унимодаль­ности. Полезность этого свойства определяется тем фактом, что для унимодальной функции f(x) сравнение значений f(x) в двух различ­ных точках интервала поиска позволяет определить, в каком из заданных двумя указанными точками подынтервалов точка опти­мума отсутствует.

Теорема 2.3

Пусть функция f унимодальна на замкнутом интервале а ≤ x ≤ b, а ее минимум достигается в точке х*. Рассмотрим точки x₁ и х₂,. расположенные в интервале таким образом, что а<x₁<x₂<b. Сравнивая значения функции в точках x₁и х₂, можно сделать сле­дующие выводы.

1. Если f(x₁)>f(x₂), то точка минимума f(x) не лежит в интерва­ле (а, х₁), т. е. х* Î (х₁, b) (рис. 2.10).

2. Если f(x₁)<f(x₂), то точка минимума не лежит в интервале: (х₂, b), т. е. х*Î (a, x₂ )(см. рис. 2.10).

Доказательство

Рассмотрим случай, когда f(x₁)>f(x₂). Пусть утверждение тео­ремы неверно, т. е. a≤ х*≤ х₁. Поскольку х*— точка минимума, то по определению f(х*)≤f (х) для всех х Î (a, b). Получаем двойное неравенство

f(x*)≤f(x₁)>f(x₂) при x*<x₁<x₂.

Это неравенство не может выполняться, так как унимодальная функ­ция f (x) должна быть монотонной по обе стороны от точки х*. Таким образом, получено противоречие, доказывающее утверждение тео­ремы. Аналогичные рассуждения справедливы также в случае, когда f(x_l)<f(x₂).

Примечание. Если f(x_l)=f(x₂), то можно исключить оба крайних интервала (а, х₁) и (х₂, b); при этом точка минимума должна распо­лагаться в интервале (x_l , x₂).

Согласно теореме 2.3, которую иногда называют правилом ис­ключения интервалов, можно реализовать процедуру поиска, позво­ляющую найти точку оптимума путем последовательного исключе­ния частей исходного ограниченного интервала. Поиск завершается, когда оставшийся подынтервал уменьшается до достаточно малых размеров. Заметим, что правило исключения интервалов устраняет необходимость полного перебора всех допустимых точек. Несом­ненным достоинством поисковых методов такого рода является то, что они основаны лишь на вычислении значений функций. При этом не требуется, чтобы исследуемые функции были дифференцируемы; более того, допустимы случаи, когда функцию нельзя даже записать в аналитическом виде. Единственным требованием является воз­можность определения значений функции f(х) в заданных точках х с помощью прямых расчетов или имитационных экспериментов. Вообще в процессе применения рассматриваемых методов поиска можно выделить два этапа:

этап установления границ интервала, на котором реализуется процедура поиска границ достаточно широкого интервала, содер­жащего точку оптимума;

этап уменьшения интервала, на котором реализуется конечная последовательность преобразований исходного интервала с тем, чтобы уменьшить его длину до заранее установленной величины,

Этап установления границ интервала

На этом этапе сначала выбирается исходная точка, а затем на основе правила исключения строится относительно широкий интер­вал, содержащий точку оптимума. Обычно поиск граничных точек такого интервала проводится с помощью эвристических методов поиска, хотя в ряде случаев можно также использовать методы, экстраполяции. В соответствии с одним из эвристических методов, который был предложен Свенном [1], (k+1)-я пробная точка опре­деляется по рекуррентной формуле

где х₀— произвольно выбранная начальная точка, Δ — подбирае­мая некоторым способом величина шага. Знак Δ определяется путем сравнения значений f(x₀), f(x₀+|Δ|) и f(x₀— |Δ|). Если

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

то точка минимума лежит между х₀—|Δ| и х₀+|Δ| и поиск гранич­ных точек завершен. Случай, когда

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

Пример 2.5

Рассмотрим задачу минимизации функции f(х)=(100—х)² при заданной начальной точке х₀=30и величине шага |Δ|=5.

Знак Δ определяется на основе сравнения значений

Так как

то величина Δ должна быть положительной, а координата точки минимума х* должна быть больше 30. Имеем x₁=x₀+Δ=35. Далее х₂=х₁+2Δ=45, f(45)=3025<f(x₁),

следовательно, х*<185. Таким образом, шесть шагов вычислений x* позволили выявить интервал 65£x*£185, в котором располо­жена точка х*. Заметим, что эффективность поиска граничных точек непосредственно зависит от величины шага Δ. Если Δ велико, то получаем грубые оценки координат граничных точек, и построен­ный интервал оказывается весьма широким. С другой стороны, если Δ мало, для определения граничных точек может потребоваться достаточно большой объем вычислений.

Этап уменьшения интервала

 

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

Метод деления интервала пополам. Рас­сматриваемый метод позволяет исключать в точности половину интервала на каждой итерации. Иногда этот метод называют трех­точечным поиском на равных интервалах,поскольку его реализация основана на выборе трех пробных точек, равномерно распределен­ных в интервале поиска. Ниже приводится описание основных шагов поисковой процедуры, ориентированной на нахождение точки ми­нимума функции f(x) в интервале (а, b).

Шаг 1. Положить х_т=(а+b)/2и L=b—а. Вычислить значе­ние f(x_m).

Ш а г 2. Положить x₁=a+L/4 и х₂=b—L/4. Заметим, что точ­ки x₁, x_m и х₂делят интервал (a, b) на четыре равные части. Вычис­лить значения f(x₁) и f(x₂).

Ш а г 3. Сравнить f(x₁) и f(x_m).

(1) Если f(x₁)<f(x_m), исключить интервал (х_т, b), положив b=х_т. Средней точкой нового интервала поиска становится точка х₁. Сле­довательно, необходимо положить х_т=х₁.

Перейти к шагу 5.

(2) Если f(x₁)>f(x_m), перейти к шагу 4.

Ш а г 4. Сравнить f(x₂) и f(x_m).

(1) Если f(x₂)<f(x_m), исключить интервал (а, х_т), положив а=х_т. Так как средней точкой нового интервала становится точка х₂положить х_т=х₂. Перейти к шагу 5.

(2) Если f(x₂)³f(x_m), исключить интервалы (a, x₁) и (х₂, b). Поло­жить a=x₁ и b=х₂. Заметим, что х_т продолжает оставаться средней точкой нового интервала. Перейти к шагу 5.

Ш а г 5. Вычислить L=b—а. Если величина |L|мала, закон­чить поиск. В противном случае вернуться к шагу 2.

Замечания

1. На каждой итерации алгоритма исключается в точности по­ловина интервала поиска.

2. Средняя точка последовательно получаемых интервалов всег­да совпадает с одной из пробных точек x₁, x₂или х_т, найденных на предыдущей итерации. Следовательно, на каждой итерации тре­буется не более двух вычислений значения функции.

3. Если проведено п вычислений значения функции, то длина полученного интервала составляет (1/2)^n/2 величины исходного интервала.

4. В работе [2] показано, что из всех методов поиска на равных интервалах (двухточечный, трехточечный, четырехточечный и т. д.) трехточечный поиск, или метод деления интервала пополам, отли­чается наибольшей эффективностью.

Пример 2.6. Метод деления интервала пополам

Минимизировать f(х)=(100—x)² в интервале 60£ x £150. Здесь a=60, b=150 и L=150-60=90.

Таким образом, исключаются интервалы (60; 82,5) и (127,5; 150). Длина интервала поиска уменьшается с 90 до 45.

Итерация 2

Таким образом, интервал неопределенности равен (93,75; 116,25)

Итерация 3

а=93,75 b=116,25, х_т=105,

L = 116,25—93,75=22,5,

x₁=99,375, х₂=110,625,

f(x₁)=0,39<f(105)=25.

Таким образом, исключается интервал (105; 116,25). Новый ин­тервал неопределенности равен (93,75; 105), его средняя точка есть 99,375 (точка х₁на итерации 3). Отметим, что за три итерации (шесть вычислений значения функции) исходный интервал поиска длины 90 уменьшился до величины (90)(1/2)³=11,25.

Поиск с помощью метода золотого сече­ния. Из проведенного выше обсуждения методов исключения ин­тервалов и минимаксных стратегий поиска можно сделать следую­щие выводы.

1. Если количество пробных точек принимается равным двум, то их следует размещать на одинаковых расстояниях от середины интервала.

 

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

3. На каждой итерации процедуры поиска должно вычисляться только одно значение функции в получаемой точке.

Руководствуясь этими выводами, рассмотрим симметричное рас­положение двух пробных точек на исходном интервале единичной длины, которое показано на рис. 2.11. (Выбор единичного интервала обусловлен соображениями удобства.) Пробные точки отстоят от граничных точек интервала на расстоянии t. При таком симметрич­ном расположении точек длина остающегося после исключения ин­тервала всегда равна t независимо от того, какое из значений функ­ции в пробных точках оказывается меньшим. Предположим, что исключается правый подынтервал. На рис. 2.12 показано, что оставшийся подынтервал длины t содержит одну пробную точку, расположенную на расстоянии (1—t) от левой граничной точки.

Для того чтобы симметрия поискового образца сохранялась, расстояние (1-t) должно составлять t-ю часть длины интервала (которая равна t). При таком выборе t следующая подобная точка размещается на расстоянии, равной t-й части длины интервала, от правой граничной точки интервала (рис.2.13)

Рис. 2.12. Интервалы, полученные методом золотого сечения

 

Отсюда следует, что при выборе t в соответствии с условием 1-t =t² симметрия поискового образца, показанного на рис. 2.11, сохраняется при переходе к уменьшенному интервалу, который изображен на рис. 2.13. Решая это квадратное уравнение, получаем

откуда положительное решение t=0,61803… . Схема поиска, при которой пробные точки делят интервал в этом отношении, известна

под названием поиска с помощью метода золотого сечения. Заметим, что после первых двух вычислений значений функции каждое по­следующее вычисление позволяет исключить подынтервал, величина которого составляет (1—t)-ю долю от длины интервала поиска. Следовательно, если исходный интервал имеет единичную длину, то величина интервала, полученного в результате N вычислений зна­чений функции, равна t^N-1. Можно показать, что поиск с помощью метода золотого сечения является асимптотически наиболее эффек­тивным способом реализации минимаксной стратегии поиска.

 

---

Дата добавления: 2018-06-01; просмотров: 709; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!