Численное решение задачи оптимизации управления

Предположим, что функционал (6) обладает особенностями: 1) имеет только один минимум (локальный, он же и абсолютный) на интервале определения k; 2) может не удовлетворять требованиям непрерывности и существования производной на интервале определения k. Функции, удовлетворяющие этим требованиям, называются унимодальными. Поиск минимума унимодальных функций может проводиться методом перебора, методом дихотомии, методом золотого сечения и методом чисел Фибоначчи [4]. Методы перечислены в порядке увеличения эффективности поиска. Таким образом, метод чисел Фибоначчи является самым эффективным. Поэтому поиск минимума функционала (6) будем проводить этим методом.

Реализация метода связана с использованием последовательности целых чисел, открытой итальянским математиком Леонардом Пизанским (Фибоначчи) в на­чале XIII века. Обозначим унимодальную целевую функцию через z = z (x). Необходимо найти точку х * при которой целевая функция z имеет минимум: z *= z (x *)= z (x). При этом считаем, что х лежит в интервале [0, 1], поскольку любой другой интервал легко приводится к интервалу [0, 1].

Чтобы проследить за ходом развития схемы поиска х *, z *, предположим, что в нашем распо­ряжении имеется N экспериментов. Оценим ситуацию, которая возникает после того, как проведён N –1 эксперимент и остаётся выбрать последнее значе­ние х = x_N. К этому моменту гарантированная длина интервала неопределённости становится равной L_{N –1}, а сам интервал содержит точку х_{N –1} (рис.3), причём среди всех величин z_q (q = ), полученных в пред­шествующих экспериментах, наибольшей является имен­но z_{N –1}. Положение х_{N –1} на отрезке L_{N –1} зависит от то­го, какой метод поиска была реализована на предыдущих шагах.

Длина конечного интервала неопределенности будет определяться не только выбираемым х_N, но и уже имею­щимся х_{N –1}. Очевидно, результат поиска окажется наи­лучшим тогда, когда х_{N –1} распо­ложится на расстоянии ε/2 от середины L_{N –1} (рис.3) (в этом случае достаточно разместить точку х_N симме­трично х_{N –1} и найти L_N =(L_{N –1}+ε)/2 независимо от того, в каком отношении находятся z_N и z_{N –1}). Таким образом, первым требованием к исследуемой схеме явля­ется следующее: после проведения N –1 экспериментов точка х_{N –1} должна занять на L_{N –1} положение, указан­ное на рис.3.

Рис.3. Рис.4.

стояние между x_{N –1} и x_{N –2} окажется наверняка боль­ше ε. Предложенный выбор x_{N –1} даёт гарантию того, что длина нового интервала неопределённости не превы­сит величины L_{N –1}, отмеченной на рис.4, причем L_{N –1} не может быть уменьшена, если задана точка x_{N –2}. Зная теперь x_{N –1} и помня о требовании, отражённом в рис.3, при­ходим к выводу: чтобы получить результат L_{N –1}, необхо­димо два последних эксперимента провести так, как по­казано на рис.5, выполнив тем самым условие: L_{N –2} = L_{N –1}+ L_N.

LN –3 Таблица 1. LN –2 xN –2 xN –3 Номер шага поиска q	Формула для интервала неопределённости Lq
LN –1 ε xN –1 xN LN –2 xN –2 xN –1 N N –1 N –2 N –3 N –4 N –5 ∙	LN = LN LN –1 = 2 LN – ε LN –2 = 3 LN – ε LN –3 = 5 LN – 2ε LN –4 = 8 LN – 3ε LN –5 = 13 LN – 5ε ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙
LN –1 LN	Lq = FN – q +1 LN – FN – q –1 ε

Если сделать очередной шаг и поставить задачу: найти x_{N –2}, x_{N –1}, x_N при известных L_{N –3}, x_{N –3}, z_{N –3}, то окажется, что рассуждения, приведенные выше, могут быть целиком перенесены и на этот случай. Таким обра­зом, приходим к равенству L_{N –3} = L_{N –2} + L_{N –1}; далее схе­ма строится так, как показано на рис.6.

Теперь ясно, что основное соотношение, характери­зующее метод, имеет вид

L _{q –1} = L _q + L _{q +1} (q = ). (16)

Его анализ удобно начать с конкретизации выражений L_q (q = N, N— 1,...), сведя их в табл.1. Нетрудно заметить, что коэффициенты при L_N и ε в формулах таблицы составляют последовательность чи­сел Фибоначчи (табл.2), задаваемую равенствами F ₀ = F ₁=1, F_k = F_{k –1}+ F_{k –2}, где k— номер числа Фибоначчи, принимающий значения 2, 3, …. Используя это обстоятельство, можно дать общую запись выражения L_q, приведённую в ниж­ней строке табл.1, откуда сле-дует L ₁ =F_N L_N – F_{N –2} ε. Но L ₁ есть исходный единичный интервал неопределён­ности (L ₁=1), поэтому [4]

L_N = (l + ε F_{N –2} ) / F_N. (17)

Таблица 2. Числа Фибоначчи.

Соотношение (17) позволяет оценить эффективность метода чисел Фибоначчи. Большая эффективность метода чисел Фибоначчи связана с тем, что сокращение длины очередного интервала L_q требует проведения одного нового эксперимента, тогда как, например, в схеме дихотомии их требуется два.

Длина конечного интервала неопределённости L_N должна быть меньше или равна 2ε. Из (17) следует

≤ 2ε 1+ ε F_{N –2} ≤ 2ε F_N ε(F_{N –2} –2 F_N) ≤ –1 ε(F_{N –2} –2 F_{N –1} –2 F_{N –2}) ≤ –1

ε(– F_{N –2} –2 F_{N –1})≤–1 ε(F_{N –2} +2 F_{N –1})≥1 ε(F_{N –2} + F_{N –1}+ F_{N –1}) ≥ 1 ε (F_N + F_{N –1}) ≥ 1 ε F_{N +1} ≥ 1.

Отсюда следует

F_{N +1} ≤ . (18)

Таким образом, конечное число шагов поиска N определяется по формуле (18).

В заключение рассмотрим вопрос о выборе точки х ₁ и связанной с этим возможностью реализации мето­да. Из предыдущего анализа следует х ₁=1– L ₂; но L ₂= F_{N –1} L_N –ε F_{N –3} (см. табл. 1) или с учётом (17) L ₂= F_N [ F_{N –1}+ε(F_{N -1} F_{N –2}– F_N F_{N –3})]. Отсюда сле­дует, что сделать первый шаг здесь можно лишь тогда, когда назначено число N, т. е. х ₁= х ₁(N). Это является недостат-ком, затрудняющим в ряде случаев решение за­дачи из-за невозможности изменить N после начала экспериментов. Отметим, что метод золотого сечения не требует предварительного задания N и приближается по эффективности к исследованному методу чисел Фибоначчи [4].

Не нашли, что искали? Воспользуйтесь поиском: