Лекция: Методы минимизации функций одной переменных

Здесь рассматривается простейшая математическая модель оптимизации, в которой целевая функция зависит от одной перемен­ной, а допустимым множеством является отрезок вещественной оси:

F(x) ®min, (1)

хÎ [a; b].

Как уже отмечалось, максимизация целевой функции (f (x) ® max) эквивалентна минимизации противоположной величины (–f (x) ® min), поэтому мы будем рассматривать только задачи минимизации.

К математическим задачам вида (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)

Далее, положим .