Поиск минимума унимодальной функции путем сокращения интервала неопределенности

Задача минимизации одномерной унимодальной функции Q(х), определенной на интервале [а, b], связана с поиском оптимального решения х*:

Q(x*)= min Q(x). (3.1)

Из свойства унимодальности функции Q (х) следует, что с возрастанием переменной х функция Q (х) строго убывает при х ≤ х* и строго возрастает при х ≥ х*, т. е. унимодальная функция не должна иметь горизонтальных участков («плато»), хотя может быть не дифференцируемой, разрывной, неопределенной в некоторых точках и т. д. В начале поиска положение точки х* на интервале [а, b] неизвестно. Путем проведения в точках рассматриваемого интервала N испытаний требуется локализовать оптимальное решение х* в интервале [aN, bN] меньшей длины, чем исходный. При этом предполагается, что каждое испытание, связанное с вычислением значения функции Q (х), может быть выполнено без ошибки, либо последняя настолько мала, что ею можно пренебречь. В дальнейшем интервал [aN, bN] будем называть апостериорным интервалом неопределенности в отличие от исходного интервала [а, b], называемого априорным интервалом неопределенности.

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

ak ≤ ak+1 ≤ bk+1 ≤ bk (3-2)
и ak ≤ ak+1 или bk+1 < bk.

Длина l текущего интервала неопределенности [аk+1, bk+1] как видно из рис. 3.1, зависит от расположения в интервале |ak,bk| точек испытаний x1k, x2k, выбор которых определяется конкретным методом
поиска Fi. Тогда наилучший метод F* из некоторой совокупности рассматриваемых методов сокращения интервала неопределенности АF должен обеспечивать минимальное значение длины апостериорного интервала неопределенности после проведения N испытаний для самой «наихудшей» функции Q (х) из класса унимодальных функций КQ

l(F*)= min max |bN — aN| (3.3)

Такой подход к выбору наилучшего метода F* минимизации одномерных унимодальных функций Q (х), определенных на интервале [а, b], называется минимаксным подходом (принципом гарантированного результата).



Рис. 3.1. Уменьшение априорного интервала неопределенности [ak, bk] путем проведения двух испытаний в точках x1k, x2k

Согласно экстремальной задаче (3.3) на каждом k-м шаге поиска точки испытаний x1k, x2k должны выбираться таким образом, чтобы наибольшая длина интервала неопределенности [ak+1, bk+1] была как можно меньше:

min max {x2k — ak, bk — x1k}

при условии, что

ak ≤ x1k ≤ x2k ≤ bk

Решением задачи (3.4) является пара точек, расположенных симметрично относительно середины интервала неопределенности [ak, bk]:

x1k = ((ak + bk) — δ)/2, x2k = ((ak + bk) + δ)/2. (3.5)

Здесь δ > 0 — минимально допустимое различие между точками испытаний x1k и x2k, при котором возможно точно определить знак разности [Q (x1k) — Q (x2k)], т. е. параметр δ имеет такое значение, что если |x1k — x2k| > δ, то Q (x1k) = Q (x2k) только в том случае, когда x1k и x2k лежат по разные стороны от оптимального решения х*.

Метод поиска F1, реализующий процедуру выбора точек испытаний по формуле (3.5), называется методом деления пополам (методом последовательного дихотомичевкого поиска). Согласно этому методу на каждом шаге поиска пара испытаний, разнесенных между собой на величину δ, проводится в середине текущего интервала неопределенности |ak, bk|. По значениям функции Q (х), полученным в этих точках, одна половина исследуемого интервала в силу унимодальности минимизируемой функции исключается из дальнейшего рассмотрения. В середине оставшейся части интервала неопределенности вновь делается пара испытаний и т. д. После проведения (N/2) пар испытаний для длины апостериорного интервала неопределенности получаем выражение:

lN (F1) = (b — δ)/2N/2. (3.6)

Недостатком этого метода является то, что на каждом шаге поиска приходится проводить два испытания x1k и x2k. Причем информация о значениях функции в этих точках Q (x1k) и Q (x2k) на (k + 1)-м
шаге полностью игнорируется. Потребуем, чтобы информация об одном из проведенных на k-ш шаге испытаний (Q (x1k) или Q (x2k)) сохранялась на (k + 1)-м шаге, что позволит проводить в текущем интервале неопределенности [ak+1, bk+1 только одно новое испытание.

Из рис. 3.1 видно, что для выполнения этого условия необходимо, чтобы при Q (x1k) < Q (x2k) точка x1k совпадала с точкой x2k+1, а при
Q (x1k) > Q (x2k) точка x2k — с точкой x1k+1 то же время потребуем, чтобы положительное свойство метода деления пополам, связанное Q обеспечением на каждом шаге поиска минимального значения длины наибольшего возможного интервала неопределенности, сохранялось.

Из (3.5) следует, что для выполнения этого требования необходимо выбирать точки x1k, x2k на интервале [ak, bk] эквидистантно от обоих его
концов, соответственно в подынтервалах [ak, (ak + bk)/2] и [(ak + bk)/2, bk]:

x1k — ak = bk — x2k;

ak ≤ x1k ≤ (ak + bk)/2; (3.7)

k + bk)/2 ≤ x2k ≤ bk.

Нетрудно видеть, что условия (3.7) выполняются, если точки испытаний x1k, x2k∈[аk, bk] вычисляются по формулам:

x1k = аk + tk (bk — ak), (3.8)

x2k = ak + (1 — tk)(bk — ak). (3.9)

где

0 ≤ tk ≤ 1/2. (3.10)

При этом длина интервала неопределенности [ak+1, bk+1] не зависит от вида функции Q (х) и имеет следующую величину:

bk+1 — ak+1 = x2k — ak = bk — x1k = (1 — tk) (bk — ak). (3.11)


Оставить комментарий





Статистика

Рейтинг@Mail.ru