Методы минимизации функций одной переменных
Здесь рассматривается простейшая математическая модель оптимизации, в которой целевая функция зависит от одной переменной, а допустимым множеством является отрезок вещественной оси: f (x) ®min, (2.1) хÎ [a; b]. Как уже отмечалось, максимизация целевой функции (f (x) ® max) эквивалентна минимизации противоположной величины (–f (x) ® min), поэтому мы будем рассматривать только задачи минимизации. К математическим задачам вида (2.1) приводят прикладные задачи оптимизации с одной управляемой переменной. Кроме того, необходимость в минимизации функций одной переменной возникает при реализации некоторых методов решения более сложных задач оптимизации. Классический метод минимизации. Шаг 1. Решить уравнение на интервале х Î (а; b), т.е. найти все стационарные точки x1,.., xk–1Î (а; b). Положить x0 = а, xk = b. Шаг 2. Вычислить значения f (х) функции f (х) в точках xi, i = 0,.., k. Шаг 3. Найти . Положить х* = xm. Для решения задачи минимизации функции f (х) на отрезке [а; b] на практике, как правило, применяют приближенные методы. Они позволяют найти решение этой задачи с необходимой точностью в результате определения конечного числа значений функции f (х) и ее производных в некоторых точках отрезка [а; b]. Методы, использующие только значения функции и не требующие вычисления ее производных, называются прямыми методами минимизации. Большим достоинством прямых методов является то, что от целевой функции не требуется дифференцируемости и, более того, она может быть не задана в аналитическом виде. Единственное, на чем основаны алгоритмы прямых методов минимизации, это возможность определения значений f (х) в заданных точках. Рассмотрим наиболее распространенные на практике прямые методы поиска точки минимума. Самым слабым требованием на функцию f (х), позволяющим использовать эти методы, является ее унимодальность. Поэтому далее будем считать функцию f (х) унимодальной на отрезке [а; b]. Метод перебора или равномерного поиска является простейшим из прямых методов минимизации и состоит в следующем. Разобьем отрезок [а; b] на п равных частей точками деления xi = а + i(b – а)/п, i = 0,.., n. Вычислив значения f (х) в точках xi, путем сравнения найдем точку xm, 0 £ т £ п, для которой (2.9) Далее, положим .
МЕТОДЫ ИСКЛЮЧЕНИЯ ОТРЕЗКОВ В методе перебора, рассмотренном выше, точки xi, в которых определяются значения f (x), выбирают заранее. Если же для выбора очередной точки вычисления (измерения) f (x) использовать информацию, содержащуюся в уже найденных значениях f (x), то поиск точки минимума можно сделать более эффективным, т.е. сократить число определяемых для этого значений f (x), как, например, в методе поразрядного поиска. На один из путей такого более эффективного поиска точки х* указывает свойство 3 унимодальных функций (см. формулу (2.3)). Пусть а < x1<х2<b. Сравнив значения f (x) в точках x1 и х2 (пробных точках), можно сократить отрезок поиска точки х *, перейдя к отрезку [а; х2], если или к отрезку m [x1; b] если (рис. 2.6). Описанную процедуру можно повторить необходимое число раз, последовательно уменьшая отрезок, содержащий точку минимума. Когда длина последнего из найденных отрезков станет достаточно малой, следует положить , где – одна из точек этого отрезка, например, его середина. Методы минимизации, основанные на этом принципе, называются методами исключения отрезков. Первый метод деления отрезка пополам (дихотомии). Шаг 1. Определить x1 и х2 по формулам , где d > 0 – малое число.. Вычислить f (x1) и f (x2). Шаг 2. Сравнить f (x1) и f (x2). Если , то перейти к отрезку [а; x2], положив b = x2, иначе – к отрезку [x1; b], положив а = x1. Шаг 3. Найти достигнутую точность Если , то перейти к следующей итерации, вернувшись к шагу 1. Если , то завершить поиск х*, перейдя к шагу 4. Шаг 4. Положить . Метод золотого сечения. Шаг 1. Найти х1 и х2 по формулам . Вычислить f (x1) и f (x2). Положить , . Шаг 2. Проверка на окончание поиска: если en > e, то перейти к шагу 3, иначе – к шагу 4. Шаг 3. Переход к новому отрезку и новым пробным точкам. Если f (x1) £ f (x2) то положить b=x2, x2=x1, f (x2) £ f (x1), x1=b–t(b–a) и вычислить f (x1), иначе – положить a=x1, x1= x2, f (x1) = f (x2), x2=b+t(b–a) и вычислить f (x2). Положить en = ten и перейти к шагу 2. Шаг 4. Окончание поиска: положить , . метод парабол Шаг 1. Выбрать точки x1, x2, x3, удовлетворяющие условиям х1 < х2 < х3, f (x1) ³ f (x2) £ f (x3). Перейти к шагу 2.
Шаг 2. Найти по формуле . На первой итерации перейти к шагу 4, на остальных – к шагу 3.
Шаг 3. Проверка на окончание поиска. Сравнить модуль разности значений на данной и предыдущей итерациях D с числом e. Если |D| £ e, то поиск завершить, полагая х*» , f *» f (x), иначе – перейти к шагу 4. Шаг 4. Вычислить значение f (). Перейти к шагу 5. Шаг 5. Определить новую тройку чисел x1, x2, x3. Присвоить f (x1), f (x2) и f (x3) соответствующие значения f (x) найденные ранее. Перейти к шагу 2.
|