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

Метод последовательного перебора.

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

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

(1).

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

(2).

где, ,, а число определяется условием .

Теорема 1.

Метод последовательного перебора (2) решает задачу (1) на классе .

Описание метода.

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

Для решения поставленной задачи разобьем на отрезков, ,;. Вычислим значения функции () в очках разбиения и найдем. Далее сравним полученное значение с величиной, чтобы не выйти за границы отрезка, на котором ищется минимум функции. Если выполняется условие, то переходим к следующему шагу поиска минимума функции. Как только это условие перестанет выполняться, возьмем в качестве последней проверяемой точки. После этого выберем в качестве приближений для точного значения точки минимума и точного значения минимума функции значения и, где значение выбирается соответствующим номеру шага, на котором найдено приближенное минимальное значение точки минимума [2].

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

Метод последовательного перебора, аналогичный методу (2), можно предложить и для некоторых других классов функций. Остановимся на классе функций, дважды. дифференцируемых на отрезке, у которых, где — некоторая фиксированная константа. Обозначим этот класс функций через. Заметим, что если, то, и следовательно, монотонно убывает на. Это значит, что тогда функция достигает своей нижней грани при или. Таким образом, задача минимизации функций из класса в случае решается просто. Поэтому имеет смысл рассматривать класс при .

Тогда для решения задачи минимизации первого типа на классе функций можно предложить следующий метод последовательного перебора.

(2).

где,, , а число определяется условием [2].

Теорема2.2.

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

. (2.4).

В худшем случае (например, если) может оказаться, что, , и тогда метод (2.3) переходит в метод равномерного перебора с шагом. Если же при некоторых (например, для), то методом (3) удается получить неравенство (4), вообще говоря, при меньшем, чем методом равномерного перебора. Недостатком метода (3) является требование знания константы .

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

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

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

Ищется значение, а также приближенные значения локальных минимумов и глобального минимума с погрешностями, не превышающими заданного положительного числа. Ищутся также приближенные значения точек локального минимума и точки глобального минимума с погрешностями, не превышающими заданного положительного числа. Если на имеется множество точек локального минимума, то нам годится любая из них. То же относится и к точке глобального минимума [20].

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

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

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

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

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

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

. (5).

Таким образом, при каждом сгущении сетки число увеличивается в 3 раза. Узлы очередной сетки вычисляются по обычным формулам:

, (6).

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

Будем считать, что на функция предположительно является унимодальной, если.

. (6).

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

(и) или (и) или.

(и). (7).

Будем считать, что на функция предположительно является унимодальной, если.

. (8).

Условия (6) и (8) получаются из необходимых для унимодальности функции на отрезках и условий:

.

.

Условия (7) получаются из необходимых для унимодальности функции на отрезке условий:

.

.

Здесь использованы полиномиальные формулы численного дифференцирования 1 порядка точности. В условиях (8) требуется, чтобы хотя бы одно из неравенств было строгим. Это необходимо, чтобы исключить отрезки на которых функция является постоянной. При формулировке условий (8) фигурируют два отрезка. Поэтому условия предположительной унимодальности функции (6) — (8) будем называть двухзвенными условиями первого порядка.

При нахождении очередного (-го) отрезка, на котором выполняются условия (6) или (7) или (8), на нём применяется модифицированный метод золотого сечения, с помощью которого определяются приближенное значение точки локального минимума функции и приближенное значение локального минимума этой функции с погрешностями, не превышающими и, соответственно. Условия (6) — (8) позволяют выявить все окрестности внутренних точек локального минимума функции на отрезке, ширина которых не меньше, а также окрестности граничных точек локального минимума функции, ширина которых не меньше. С ростом значения и уменьшением, условия (6) — (8) будут выявлять окрестности всё более и более узких локальных минимумов и при достаточно большом значении (маленьком значении) будут выявлены окрестности всех точек локального минимума функции, на которых функция является унимодальной. А далее методом золотого сечения получатся приближенные значения точек локального минимума и локальных минимумов с погрешностями и, соответственно. Параллельно вычисляются количество обнаруженных локальных минимумов, приближенные значения глобального минимума и точка глобального минимума ().

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

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

Чтобы сформулировать условия выбора начального значения заметим, что если.

(9).

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

(10).

при выполнении которого следует выдать сообщение о необходимости уменьшения значения. Здесь — целая часть вещественного числа. Начальное значение будем выбирать меньшим, чем и таким, чтобы после третьего сгущения сетки значение ещё не достигало, а после четвёртого сгущения значение становилось больше :

. (11).

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