Основы теории оптимизации (стр. 16 )

Так както поиск завершен и (сравните с результатом решения предыдущего примера).

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

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

Один из путей такого более эффективного поиска точки х* указывает свойство 3 унимодальных функций.

Пусть Сравнить значения f(x) в точках х1 и х2 (пробных точках), можно сократить отрезок поиска точки х*, перейдя к отрезку [а;х1], если или к отрезку [х1;b], если(рис. 1).

Рис. 1. Уменьшение отрезка поиска точки минимума методами

исключения отрезков

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

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

1. Метод дихотомии (первый метод деления отрезка пополам)

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

В этом методе точки х1 и х2 располагаются близко к середине очередного отрезка [a;b], т. е.

(1)

где δ > 0 - малое число. При этом отношение длин нового и исходного отрезков

близко к 1/2, этим и объясняется название метода.

Отметим, что для любых точек х1 и х2 величина τ > 1/2, поэтому указанный выбор пробных точек объясняется стремлением обеспечить максимально возможное относительное уменьшение отрезка на каждой итерации поиска х* .

В конце вычислений по методу дихотомии в качестве приближенного значения х* берут середину последнего из найденных отрезков [a;b], убедившись предварительно, что достигнуто неравенство

Опишем алгоритм метода деления отрезка пополам.

Шаг 1. Определить х1 и х2 по формулам (1). Вычислить f(х1) и f(х2).

Шаг 2. Сравнить f(х1) и f(х2). Если f(х1) ≤ f(х2), то перейти к отрезку [а; х2], положив b = х2, иначе - к отрезку [х1;b], положив а = х1.

Шаг 3. Найти достигнутую точность Если εп > ε, то перейти к следующей итерации, вернувшись к шагу 1. Если εп ≤ ε , то завершить поиск х*, перейдя к шагу 4.

Шаг 4. Положить

Замечание:

1. Число δ из (1) выбирается на интервале (0; 2ε) с учетом следующих соображений:

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

б) при чрезмерно малом δ сравнение значений f(x) в точках х1 и х2, отличающихся на величину δ, становиться затруднительным. Поэтому выбор δ должен быть согласован с точностью определения f(x) и с количеством верных десятичных знаков при задании аргумента х.

2. Число п итераций метода дихотомии, необходимое для определения точки х* с точностью ε, определяется неравенством

(2)

Обозначим длину исходного отрезка [ а,b ] через ∆0. Длина отрезка, полученного после первой итерации, будет после второй итерации после третьей и т. д.

Таким образом, в результате п итераций длина отрезка поиска точки х* станет

При этом будет достигнута точность определения точки минимума Находя п из условия

(3)

получаем неравенство (2).

Величина δ может быть выбрана достаточно малой, поэтому, пренебрегая ею в (2), получаем На каждой итерации метода дихотомии вычисляются два значения f(x). Поэтому после N вычислений f(x) производится n = N/2 итераций и достигается точность определения x*.

(4)

Пример. Метод деления отрезка пополам.

Решить задачу, приведенную в двух предыдущих примерах:

Выберем δ=0,02.

Итерация 1

Шаг1 .

Шаг 2. f(x1)> f(x2), поэтому полагаем а = х1 = 0,49.

Шаг 3. т. е. переходим к следующей итерации.

Результат вычисления на остальных итерациях записаны в табл. 1

Таблица 1

Таким образом,

(сравнить с результатами решения двух предыдущих примеров).

Пусть дана функция F(x). Необходимо найти , доставляющий минимум (или максимум) функции F(x) на интервале [a, b] с заданной точностью ε, т. е. найти

Запишем словесный алгоритм метода.

1) На каждом шаге процесса поиска делим отрезок [a, b] пополам, x=(a+b)/2 - координата середины отрезка [a, b].

2) Вычисляем значение функции F(x) в окрестности ±ε вычисленной точки x, т. е.

3) Сравниваем F1 и F2 и отбрасываем одну из половинок отрезка [a, b] (рис. 2).

Рис. 2.  Поиск экстремума функции F(x) методом дихотомии

При поиске минимума:

Если F1<F2, то отбрасываем отрезок [x, b], тогда b=x. (рис. 2,а)

Иначе отбрасываем отрезок [a, x], тогда a=x. (рис.2,б)

При поиске максимума:

Если F1<F2, то отбрасываем отрезок [a, x], тогда a=x.

Иначе отбрасываем отрезок [x, b], тогда b=x.

4) Деление отрезка [a, b] продолжается, пока его длина не станет меньше заданной точности ε, т. е.

Схема алгоритма метода дихотомии представлена на рис 3.

Рис. 3.  Схема алгоритма метода дихотомии

На рис 3: c- константа,