Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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




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

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.


 







Дата добавления: 2015-04-19; просмотров: 2463. Нарушение авторских прав


Рекомендуемые страницы:


Studopedia.info - Студопедия - 2014-2019 год . (0.002 сек.) русская версия | украинская версия