Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






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



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

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

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

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

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

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

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

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

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

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

а) если f(x0-hf(x0f(x0+h), то начальный интервал неопределённости определён: [a0, b0]=[x0-h, x0+h];

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

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

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

а) если f(x0-hf(x0f(x0+h), то D=h, a0=x0, x1=x0+h;

б) если f(x0-hf(x0f(x0+h), то D=-h, b0=x0, x1=x0-h, k=1

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

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

а) если f(xk+1)<f(xk) и D=h, то a0=xk;



если f(xk+1)<f(xk) и D=-h, то b0=xk;

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

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

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


 

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

2.0. Вычислить значение функции в точках x0-h=-1, x0=0, x0+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, a0=x0=0, x1=x0+h=1, k=1.

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

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

5.2. Найдём следующую точку x3=x2+22D=7;

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

2. Найдём точки xi=a0+i =1+i =1+0,5i вычислений функции: x1=1,5, x2=2, x3=2,5, x4=3, x5=3,5, x6=4, x7=4,5, x8=5, x9=5,5, x10=6, x11=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. В точке x4=3 функция принимает наименьшее значение: f(3)=5»minf(x).

Ответ: fmin(xf(3)=5.


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!