Методы нулевого порядка одномерной минимизации

Общие положения

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

Функция f(x) называется унимодулярной на интервале [a, b], если она достигает глобального минимума на [a, b] в единственной точке x*, причём слева от x* функция строго убывает, а справа - строго возрастает.

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

Для любого метода одномерной оптимизации необходимо задание начального интервала L₀=[a₀, b₀], в котором лежит точка минимума. Интервал L₀ называется начальным интервалом неопределённости.

Для выбора начального интервала неопределённости можно применить, например, алгоритм Свенна, идея которого заключается в следующем:

Берутся равноотстоящие друг от друга на некоторый шаг h три точки x₀-h, x₀, x₀+h и сравниваются значения f в этих точках. Если f(x₀-h)³f(x₀)£f(x₀+h), то в качестве начального интервала неопределённости берётся отрезок [x₀-h, x₀+h]. Если f(x₀-h)£f(x₀)≥f(x₀+h), то функция на этом отрезке противоречит определению унимодулярности, и таковой не является. Тогда берутся другие три точки и процедура повторяется. Если же на отрезке [x₀-h, x₀+h] функция монотонна, то наращиваем отрезок в сторону убывания с определённым шагом D до тех пор, пока значение функции в очередном конце отрезка не превысит значения на предыдущем. Это будет означать, что локальный минимум функции достигается на полученном отрезке. Более подробно:

1. Задать произвольно следующие параметры: x₀ - некоторую точку, h>0 - величину шага. Положить k=0.

2. Вычислить значение функции в точках x₀-h, x₀, x₀+h.

3. Проверить условие окончания:

а) если f(x₀-h)³f(x₀)£f(x₀+h), то начальный интервал неопределённости определён: [a₀, b₀]=[x₀-h, x₀+h];

б) если f(x₀-h)£f(x₀)³f(x₀+h), то функция не является унимодулярной, и требуемый интервал не может быть найден. Требуется задать другую x₀.

в) если условие окончания не выполняется, то перейти к шагу 4.

4. Определить величину D:

а) если f(x₀-h)³f(x₀)³f(x₀+h), то D=h, a₀=x₀, x₁=x₀+h;

б) если f(x₀-h)£f(x₀)£f(x₀+h), то D=-h, b₀=x₀, x₁=x₀-h, k=1

5. Найти следующую точку x_k+1=x_k+2^kD;

6. Проверить условие убывания функции:

а) если f(x_k+1)<f(x_k) и D=h, то a₀=x_k;

если f(x_k+1)<f(x_k) и D=-h, то b₀=x_k;

в обоих случаях положить k=k+1 и перейти к шагу 5);

б) если f(x_k+1)³f(x_k), то процедура завершается. При D=h положить b₀=x_k+1, а при D=-h положить a₀=x_k+1. В результате имеем [a₀, b₀] - искомый интервал неопределённости.

Пример I. Найти методом Свенна начальный интервал неопределённости для решения задачи f(x)=x²-6x+14®min при x₀=0, h=1.

Решение. 1. Положим k=0.

2.0. Вычислить значение функции в точках x₀-h=-1, x₀=0, x₀+h=1:

f(-1)=21, f(0)=14, f(1)=9.

3.0. Так как f(-1)>f(0)>f(1)=9, то условие окончания не выполняется.

4.0. Полагаем D=h=1, a₀=x₀=0, x₁=x₀+h=1, k=1.

5.1. Найдём следующую точку x₂=x₁+2D=3.

6.1. Проверим условие убывания функции. Так как f(x₂)=5<f(x₁)=9 и D=h, то a₀=x₁=1. Положим k=2.

5.2. Найдём следующую точку x₃=x₂+2²D=7;

6.2. Проверим условие убывания функции. Так как f(x₃)=21>5=f(x₂) то поиск завершён: правая граница b₀=7.

Ответ: [1; 7] - начальный интервал неопределённости.

Существуют две принципиально различные стратегии выбора точек, в которых производится вычисление значений функции. Это - параллельная и последовательная стратегии. В первой стратегии все точки задаются заранее, до начала вычислений. Во второй стратегии точки выбираются последовательно в процессе поиска с учётом результатов предыдущих вычислений. Эта стратегия поиска включает в себя следующие три этапа:

1. Выбор начального интервала неопределённости.

2. Уменьшение интервала неопределённости.

3. Проверка условия окончания. Поиск заканчивается, когда длина текущего интервала неопределённости [a_k, b_k] оказывается меньше заданной величины e.

Ниже мы рассматриваем два метода нулевого порядка. Один относится к параллельным, другой - к последовательным стратегиям.

Метод равномерного поиска

Метод относится к параллельным стратегиям и заключается в следующем:

1. Задаётся начальный интервал неопределённости L₀=[a₀, b₀] и количество N вычислений функции.

2. L₀ разбивается на N+1 равных интервалов точками x_i=a₀+i вычисления функции.

3. Вычисляются значения функции в найденных точках: f(x_i), i=1, 2, …, N.

4. Среди точек x_i, i=1, 2, …, N находится точка x^* такая, в которой функция принимает наименьшее значение: f(x_k)= .

Пример II. Решить задачу

f(x)=x²-6x+14®min

методом равномерного поиска.

Решение. 1. Задаём начальный интервал неопределённости L₀=[1; 7] (см. решение примера I) и количество N=11 вычислений функции.

2. Найдём точки x_i=a₀+i =1+i =1+0,5i вычислений функции: x₁=1,5, x₂=2, x₃=2,5, x₄=3, x₅=3,5, x₆=4, x₇=4,5, x₈=5, x₉=5,5, x₁₀=6, x₁₁=6,5.

3. Вычислим значения функции в найденных точках: f(1,5)=7,25, f(2)=6, f(2,5)=5,25, f(3)=5, f(3,5)=5,25, f(4)=6, f(4,5)=7,25, f(5)=9, f(5,5)=11,25, f(6)=14, f(6,5)=17,25,

4. В точке x₄=3 функция принимает наименьшее значение: f(3)=5»minf(x).

Ответ: f_min(x)»f(3)=5.