2. 3 Методы одномерной оптимизации



Дата13.07.2016
өлшемі33.79 Kb.


<== Возврат к содержанию раздела
2.3 Методы одномерной оптимизации
К числу наиболее популярных численных методов одномерной оптимизации, т.е. поиска экстремума функции f (x), относятся: метод Больцано (деления интервала пополам), метод "золотого сечения" и пошаговый метод. Первые два метода ориентированы на поиск ext f (x) внутри фиксированного интервала (а;b) оси х, последний – на поиск ext f (x) в окрестности заданной точки х0.

Будем рассматривать эти методы как методы поиска min f (x) (поиск max f (x) можно заменить поиском min [–f (x)] .



М

Рисунок 2.6 Иллюстрация к методу Больцано



етод Больцано
при поиске минимума функции f (x) предусматривает следующие действия (рисунок 2.6):

1) определяется средняя точка интервала (а;b) с = (a+b)/2;

2) выбирается число   (b-a)/2 (наиболее популярная рекомендация:  =(b-a)/4) и определяются точки x1=c- и x2=c+ ;

3) вычисляются значения функции в этих точках f (x1) и f (x2);

4) если f (x1)  f (x2), то интервал (а;b) стягивается в свою левую половину: b c, в противном случае – в правую: а с.

Для нового интервала (а;b) вновь выполняются действия п.п. 1)-4). Процесс деления интервала продолжается до тех пор, пока его длина не станет меньше заданной точности: b-а  . При завершении процесса поиска за точку минимума f (x) принимается середина последнего отрезка: x*=(а+b)/2.



Достаточные условия сходимости алгоритма метода Больцано:

а) функция f (x) непрерывна внутри интервала (а;b) оси x;

б) f (x) унимодальна на интервале (а;b), т.е. имеет внутри него единственный экстремум;

в) в некоторой окрестности искомой точки х* f (x) является монотонной (с одной стороны возрастает, с другой - убывает).

При тех же условиях сходится алгоритм метода "золотого сечения".

Определение: "Золотым сечением" отрезка называется его деление на две части таким образом, что отношение длины отрезка к его большей части равно отношению большей части к меньшей.

Следовательно, для отрезка единичной длины: 1/t = t/(1-t)  t2+t-1=0, откуда

Алгоритм метода "золотого сечения" при поиске минимума функции

f (x) включает операции (рисунок 2.7):

1


Рисунок 2.7 Иллюстрация к методу

"золотого сечения"
) деление интервала (а;b) точками х1, х2 в отношении "золотого сечения": x1=a+(b-a)(3–)/2, x2=b-(b-a)(3–)/2;

2) вычисление значений функции f (x1) и f x2);

3) при f (x1)  f (x2) – отсечение от интервала (а;b) его правой части: b x2, x2 x1; в противном случае – левой: a x1, x1 x2;

4) если b x2, то определяется точка х1 нового интервала (а;b), а если а х1, то точка х2, по правилам п.1).

Для нового интервала (а;b) вновь выполняются действия п.п. 2)-4), причем в п.2) значение функции f (x) вычисляется один раз: только для вновь определяемой точки х1 или х2. Процесс деления интервала продолжается до тех пор, пока не выполнится условие b - а  . При завершении процесса поиска за точку минимума f (x) принимается значение х* = (а+b)/2 .

Число модификаций исходного интервала (a;b) при использовании метода “золотого сечения” больше, чем при использовании метода Больцано (от интервала отсекается не половина, а 0.382 его длины), но количество вычислений значения функции f (x) существенно меньше. Поэтому в случаях, когда значение f (x) вычисляется достаточно долго, метод “золотого сечения” имеет заметное преимущество перед методом Больцано.



Пошаговый метод применяется в тех случаях, когда интервал (а;b) оси х, содержащий точку экстремума функции f (x) неизвестен, но известно, что экстремум находится в окрестности экспериментально найденной точки х0. Этот метод применяется на практике значительно чаще методов Больцано и "золотого сечения", т.к. условие сходимости его алгоритма намного проще: достаточно, чтобы функция f (x) была непрерывна в окрестности т. х0.

П


Рисунок 2.8 Иллюстрация к пошаговому методу



ри поиске минимума f (x) метод заключается в следующем (рисунок 2.8):

1) выполняется пробный шаг от точки х0 с целью выбора направления поиска: x = x0 +x (x~0.5) и вычисляются значения f (х0), f (х);

2) если f (х) < f (х0), то величина основного шага, с которым осуществляется движение в направлении убывания функции, положительна (h > 0), в противном случае – отрицательна (h < 0);

3) движение в выбранном направлении с шагом h: xk+1= xk+h, k=0,1, ... осуществляется до тех пор, пока f (xk+1) < f (xk);



4) если f (xk+1) ≥ f (xk), то при выполнении условия h < ε процесс поиска заканчивается: x* =(xk+1+xk)/2; если h  ε, то шаг уменьшается h=|h|/p, p > 1 (часто используют p = e  2,71828) и осуществляется возврат к п. 1) с начальной точкой х0 = xk .


<== Возврат к содержанию раздела
Каталог: win-1251 -> lab


Достарыңызбен бөлісу:




©dereksiz.org 2020
әкімшілігінің қараңыз

    Басты бет