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