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

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

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

Теорема

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

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

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

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

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

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

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

а) б)

Рис. 6.49 Графические иллюстрации к теореме

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

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

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

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

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

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

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

f(х₀ - |D|) ³ f(х₀) £ f(х₀+ |D|)

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

f(х₀ - |D|) £ f(х₀) ³ f(х₀+ |D|)

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

Пример

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

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

f(х₀) = f(30) = 4900

f(х₀+ |D|) = f(35) = 4225

f(х₀ - |D|) = f(25) = 5625

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

откуда х*>35.

х₃ = х₂ + 2²D = 65, f(65) = 1225 < f(х₂),

откуда х*>45.

х₄ = х₃ + 2³D = 105 f(105) = 25 < f(х₃),

откуда х*>65.

х₅ = х₄ + 2⁴D = 185, f(185) = 7225 > f(х₄)

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

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

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

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

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

Шаг 3. Сравнить f(х₁₎ и f(х_m).

(1) Если f(х₁₎ < f(х_m), исключить интервал (x_m, b), положив b=Х_т.

Средней точкой нового интервала поиска становится точка х₁. Сле­довательно, необходимо положить x_m = х₁. Перейти к шагу 5.

(2) Если f(х₁₎ ³ f(х_m) перейти к шагу 4.

Шаг 4. Сравнить f(х₂₎ и f(х_m).

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

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

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

Замечания

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

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

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

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

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

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

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

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

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

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

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

Рис. 6.51 Симметрия золотого сечения интервала

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

,

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