Повышение эффективности унимодального поиска за счет дополнительной информации о минимизируемой функции

Без потери общности предположим, что решается задача минимизации унимодальной функции Q (х), определенной на единичном интервале [0, 1], во внутренней точке ξ которого имеется информация о численном значении функции Q (ξ). В этом случае применение процедур сокращения интервала неопределенности позволяет получить после проведения N испытаний апостериорный интервал неопределенности [aN, bN], длина которого определяется следующим выражением:

lN(ξ) = bN — aN = max ((1-ξ)/uN, ξ/uN-1), 0 ≤ ξ ≤ 1/2; (3.61)

lN(ξ) = bN — aN = max ((1-ξ)/uN-1, ξ/uN), 1/2 < ξ ≤ 1; (3.62)

Соотношение (3.62) получается из (3.61) по симметрии:

lN(1-ξ) = lN(ξ) для 1/2 ≤ ξ ≤ 1.

В связи о этим докажем справедливость только выражения (3.61).

При N = 1 испытание в точке

ξ1 = {1/2, если ξ ≠ 1/2;
1/2 + δ — в противном случае}

позволяет получить апостериорный интервал неопределенности

l1 (ξ) = max (1 — ξ, ξ)

что и подтверждает справедливость (3 61).

Пусть соотношение (3.61) имеет место при (N — 1)-м числе испытаний Докажем его справедливость для N испытаний, предположив, что

0 ≤ ξ ≤ uN-1/uN+1.

Покажем, что в атом случае

lN(ξ) ≥ (1 — ξ)/uN. (3.63)

Пусть на отрезке [ξ, 1] задана произвольная унимодальная функция Q (x). Доопределим ее следующим образом:

Q*(x) = Q(ξ) — x + ξ при 0 < x ≤ ξ Q*(x) = Q(x) при ξ ≤ x ≤ 1

Нетрудно видеть, что построенная функция Q*(х) является унимодальной и ее минимум совпадает с точкой минимума функции Q (х). Допустим от противного, что неравенство (3.63) не выполняется, т. е. для функции Q (х), определенной на отрезке [0, 1], существует процедура поиска F, которая позволяет получить апостериорный интервал неопределенности

lN(F) < (1 - ξ)/uN

С другой стороны, для унимодальной функции Q*(x), как было показано ранее, наилучшим является метод Фибоначчи, который гарантирует получение после N испытаний наименьшего допустимого апостериорного интервала неопределенности не меньше чем 1/uN, что больше чем (1 — ξ)/uN. Следовательно, мы пришли к противоречию, что и доказывает справедливость неравенства (3.63). Установим теперь справедливость противоположного неравенства

lN(ξ) ≤ (1 — ξ)/uN

Первое испытание будем проводить по методу Фибоначчи, предположив, что а = ξ, b = 1 и число испытаний равно (N — 1), в точке

ξ1 = ξ + (1 — ξ)/uN-2/uN. (3.65)

Если Q (ξ1) ≤ Q (ξ), то х*∈[ξ, 1] и так как ξ1 выбрано по, методу Фибоначчи, то после N испытаний получим

lN(ξ) = (1 — ξ)/uN.

Если Q(ξ1) > Q(ξ), то необходимо рассмотреть следующие три случая.

Случай 1.

ξ/ξ1 ≤ uN-2/uN

Точка минимума х* принадлежит интервалу [0, ξ1], в котором необходимо провести (N — 1) испытание. В связи с тем, что оценки (3.60) справедливы для (N — 1)-го испытания, можем записать, что

lN(ξ) = ξ1lN-1(ξ) = ξ1(1 — ξ)/uN-1.

Записав полученное соотношение для нормированного значения ξ/ξ1 и подставив выражения (ξ1 — ξ) из (3.65), получим

lN(ξ) = (1 — ξ)/uN uN-2/uN-1. (3.66)

Так как uN-2/uN-1 < 1, то из (3.66) следует справедливость неравенства (3.64). Случай 2. uN-2/uN < ξ/ξ1 ≤ 1/2. Из соотношения (3.65) можем записать

ξ/ξ1 = 1/(1 + (1 — ξ)/ξ uN-2/uN),

что должно быть меньше 1/2 или

(1 + (1 — ξ)/ξ uN-2/uN) > 2

Отсюда следует, что (1 — ξ)/uN ≥ ξ/uN-2. (3.67)

Точка минимума х* принадлежит интервалу [0, ξ1], для которого после «проведения (N — 1)-го испытания согласно (3.60) получаем для нормированного значения ξ/ξ1 выражение

lN(ξ) = ξ1lN-1(ξ) = ξ/uN-2

так как ξ < 1/2. Отсюда, с учетом (3.67), следует справедливость неравенства (3.64). Случай 3:

1/2 < ξ/ξ1 ≤ uN-1/uN

По симметрии можем записать

lN (ξ)= ξ1(1 — ξ) = ξ1lN-1(1 — ξ).

Для нормированного значения ξ/ξ1 после проведения (N — 1)-го испытания согласно (3.60) получаем

lN(ξ) = (ξ1 — ξ)/uN-2

Подставляя сюда (ξ1 — ξ) из выражения (3.65), можем записать

lN(ξ) = (1 — ξ)/uN.

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

lN(ξ) = (1 — ξ)/uN.

Аналогично доказывается выполнение соотношения (3.60) при
uN-1/uN+1 < ξ ≤ 1/2 для N испытаний при условии, что оно справедливо для (N - 1)-го испытания. Из (3.60) следует, что при ξ = 0 и ξ = 1 (в случае, когда дополнительная информация о значении функции Q (х) относится к одному из концов априорного интервала неопределенности) длина апостериорпого интервала неопределенности [аN, bN] совпадает с оценкой, гарантируемой методом Фибоначчи:

lN (0) = lN (1) = lN (F2) = 1/uN.

В общем случае дополнительная информация о значениях унимодальной функции Q (х) на обоих концах априорного интервала неопределенности Q (0) и Q (1) не позволяет получить оценку lN (ξ) лучше, чем она гарантируется методом Фибоначчи, т. е. эта информация является избыточной.

Предположим от противного, что существует процедура сокращения интервала неопределенности F, использующая информацию о значениях Q (0) и Q (1) которая позволяет получить апостериорный интервал неопределенности, длина которого меньше оценки, гарантируемой методом Фибоначчи:

lN(F) < lN(F2). (3.68)

Построим для произвольной унимодальной функции Q (х) ее нижнюю оценку.

Q*(x) = Q(0) для x = 0;
Q*(x) = Q(x) — max(Q((0), Q(1)) для 0 < x <1 Q*(x) = Q(1) для x = 1;

Нетрудно видеть, что для построенной функции Q (х) справедливо неравенство (3.68), т. е. течка ее минимума x* может быть локализована с помощью метода F в апостериорном интервале неопределенности, длина которого не больше lN(F2). С другой стороны, согласно построению функция Q (х) является унимодальной и ее минимум совпадает с точкой минимума функции Q (х), но для последней наилучшим является метод Фибоначчи F2, который гарантирует выполнение условия:

lN(F2) < lN(F).

Полученное неравенство противоречит допущению (3.68), что позволяет сделать вывод о том, что длина апостериорного интервала неопределенности [aN, bN] для произвольной унимодальной функции Q (х) зависит от длины априорного интервала неопределенности [a, b] и числа проведенных испытаний N, но не зависит от информации о значениях функции Q (а) и Q(b), вычисленных на концах интервала неопределенности.

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

Предположим, что рассматриваемый класс унимодальных функций включает только функции Q (х), которые удовлетворяют условию Липшица с известной константой L:

|Q(x1 — Q(x2)| ≤ L|x1 — x2| для x1, x2 ∈ [a, b]. (3 69)

Для непрерывных функций Q (х)∈С1 константа Липшица равна максимальному значению первой производной от этой функции

L = max |∂Q/∂x|

а для выпуклых функций Q (х) она может быть определена из выражения:

L = max {|Q'(a+0)|, |Q'(b-0)|},

где

Q'(a+0) = [Q(a + Δ) — Q(a)]/Δ;
Q'(b-0) = [Q(b) — Q(b — Δ)]/Δ;

Рассмотрим алгоритм, относящийся к классу методов сокращения интервала неопределенности. Основная идея этого алгоритма заключается в том, что на k-м шаге поиска с помощью известной константы Липшица Щ строятся ломаные, позволяющие получить текущий интервал неопределенности [ak‘, bk‘] меньших размеров, чем при помощи метода Фибоначчи.

Геометрическая иллюстрация-процедуры сокращения длины текущего интервала неопределенности с помощью построения отрезков прямых в углом наклона, равным константе Липшица L, приведена на рис. 3.6.



Рис. 3.6. Сокращение длины текущего интервала неопределенности с помощью построения отрезков прямых с углом наклона, равным константе Липшица L

Здесь показана ситуация, которая имеет место после проведения k испытаний:

Q(xk) = min Q(xi);
аk < xk < bk; (3.70)
Q (ak) > Q (xk) < Q (bk).

Из рис. 3.6 видно, что проведение через точки с координатами (ak, Q (ak)), (xk, Q (xk)) и (bk, Q (bk)), отрезков прямых с тангенсами углов наклона к оси х, равными L и (- L), позволяет выделить интервал неопределенности [ak‘, bk‘], который получается путем пересечения построенных ломаных с прямой Q (х) = Q (xk) = const. (Для метода Фибоначчи в рассмотренной ситуации (3.70) интервал неопределенности равен отрезку [ak, bk]). Нетрудно видеть, что унимодальная функция Q (х), удовлетворяющая условию (3.69), обладает следующими свойствами:

график функции Q (х) на интервале [ak, bk] располагается не ниже построенных ломаных, так как для любых значений xk из условия Липшица (3.69) следует неравенство

Q(x) ≥ (Q(k) — L|x — xk|);

точка минимума х* функции Q (х) принадлежит интервалу [ak‘, bk‘], что позволяет исключить из дальнейшего рассмотрения подынтервалы [аk, аk‘] и [bk‘, bk‘] длина текущего интервала неопределенности [ak‘, bk‘] зависит от константы Липшица L и убывает с уменьшением ее значения.

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

I. Функция Q (х) не вычислена еще ни в одной точке. Интервал неопределенности [ak‘, bk‘] совпадает с исходным интервалом неопределенности [а, b].

II. Среди вычисленных значений Q (х) оказалось два одинаковых (рис. 3.7, а). Тогда концы интервала неопределенности [ak‘, bk‘] совпадают с точками, где получились эти значения.

III. Функция Q (х) вычислена лишь в одной точке xk (рис. 3.7, б). Интервал неопределенности [ak‘, bk‘] совпадает с исходным интервалом [аk, bk].

IV. Среди k вычисленных значений Q (х) имеется минимальное Q (xk), слева и справа от которого есть точки ak, bk, в которых значения функции Q (х) больше Q (xk) (рис. 3.6). Этот общий случай приведен в стандартной форме на рис. 3.7, в. Интервал неопределенности [ak‘, bk‘] определяется из соотношений:

Q (ak) — L (ak‘ — ak) = Q(xk),
Q (bk) — L(bk — bk‘) = Q(xk).

V. Между точкой xk и одним из концов исходного интервала [xk, b] нет точек, где функция Q (х) вычислялась.

Если это подынтервал [xk, b] (рис. 3.7, г), тогда конец интервала неопределенности bk‘ совпадает с точкой bk, а начало аk‘ определяется из соотношения:

Q (ak) — L (ak‘ — ak) = Q(xk).

Если испытания не проводились в подынтервале [a, xk] (рис. 3.7, д), то ak‘ = a, a bk‘ определяется из соотношения:

Q (bk) — L(bk— bk‘) = Q(xk).

На рис. 3.7 показаны рассмотренные типовые ситуации, причем справа приведены их стандартные формы, полученные при помощи замены переменных:

t = (х — аk‘)/(bk‘ — аk‘),
z = 2 [Q (х) — Q (xk)]/L,
ξ = (xk — аk‘)/(bk‘ — ak‘).

Эти преобразования позволяют свести интервал неопределенности [ak‘, bk‘] к интервалу единичной длины [0, 1], а испытание в точке (xk, Q (xk)) преобразовать в точку о координатами (ξ, 0). Теперь для каждой из пяти ситуаций (рис. 3.7) и любого целого числа m оставшихся вычислений функции Q(x) необходимо указать процедуру определения точки хm (ξ) ∈ [0, 1], в которой требуется провести очередное испытание.



Рис. 3.7. Типовые ситуации и их стандартные формы определения интервала неопределенности [ak‘, bk‘] в алгоритме F4

Для ситуаций I и II потребуем, чтобы рассматриваемый метод F* совпадал с методом Фибоначчи. Тогда, приняв ξ = 0 или ξ = 1, точку очередного испытания хm(ξ) будем выбирать по одной из формул алгоритма F2:

хm(0) = um-1/um+1 или хm(1) = um/um+1.

В остальных трех ситуациях (III—V) для интервала неопределенности [0, 1] имеется дополнительная информация о значении функции Q (х) во внутренней точке ξ. В этом случае для получения наименьшего значения апостериорного интервала неопределенности lm (ξ) точка очередного испытания хm(ξ) должна определяться из выражения (3.65):

xm(ξ) = ξ + (1 — ξ)um-2/um при 0 < ξ < 1/2; xm(ξ) = ξum-1/um при 1/2 < ξ < 1; где m = N-1, N - 2, ..., 1.

Окончательно стратегия поиска минимума унимодальной функции Q (х), определенной на интервале [а, b], по алгоритму F4 сводится к следующей последовательности действий.

1. На первом шаге поиска (k = 1) принимается m = N; аk = а; bk = b и ξ = 0.
2. Для ситуации 1 определяется точка очередного испытания хm(ξ) = um-1/um+1.
3. Вычисляется значение функции Q (х) в точке

xi = ak + (bk — ak)xm (ξ);

4. Обрабатываются результаты проведенных k испытаний:

Q (xk) = min Q(xj);

5. Определяется одна из четырех типовых ситуаций II—V; с помощью константы Липшица L строятся ломаные, проходящие через точки (ak, Q (ak)), (xk, Q (xk)) и (bk, Q(bk)), и находится текущий интервал неопределенности [ak‘, bk‘], содержащий точку минимума х*.

6. Определяются параметр ξ = (xk — ak‘)/(bk — ak‘) и число оставшихся испытаний m = m — 1. Если m = 1, то переходят к п. 8. В противном случае выполняется п. 7.

7. Вычисляется точка очередного испытания

хm(ξ) = ξ + (1 — ξ)um-2/um, если 0 ≤ ξ ≤ 1/2;
хm(ξ) = ξum-1/um — в противном случае

и вся процедура повторяется с п. 3.
8. Находится апостериорный интервал неопределенности [аN, bN].

Для этого последнее N-е испытание проводится в точке

xi = ak‘ + (bk‘ — аk‘)ξ1,

Рассмотренный алгоритм F4 является обобщением метода Фибоначчи на класс унимодальных функций с известной константой Липшица L. Поэтому при L → ∞ он просто совпадает с алгоритмом. Однако для любой промежуточной ситуации учет конечного значения L уменьшает текущий интервал неопределенности [k, bk] да значения [аk‘, bk‘], что позволяет получить при одном и том же числе испытаний N более точную оценку апостериорного интервала неопределенности [aN, bN] содержащего точку минимума х*. Алгоритм F4 отличается от алгоритма F2 тем, что на каждом шаге решение о том, какой подынтервал исключить из дальнейшего рассмотрения делается по информации не только о значении числа оставшихся испытаний т, но и по информации о значении параметра ξ. Этот параметр позволяет адаптировать алгоритм поиска к особенностям минимизируемой функции Q (х).

Для примера, приведенного на рис. 3.2, стратегия выбора точек испытаний по алгоритму F4 приведена в табл. 3.2. Из таблицы видно, что учет константы Липшица (здесь L = 6) позволяет уменьшить апостериорный интервал неопределенности по сравнению с методом Фибоначчи при одном и том же числе допустимых испытаний (N = 5) больше чем в два раза.


Таблица 3.2


Комментарии запрещены.





Статистика

Рейтинг@Mail.ru