Основы теории оптимизации (стр. 27 )

9°. Положить = х2 и закончить процесс.

10°. Сравнить f (x1) и f (x2):

а) если то перейти к п. 11°;

б) если f (x1) > f (х2), то перейти к п. 14°.

11°. Переобозначить

12°. Вычислить

13°. Вычислить f (x1) и перейти к п. 6°.

14°. Переобозначить ,

15°. Вычислить

16°. Вычислить f(x2) и перейти к п. 6°.

14. Хотя сформулированное описание оптималь­ного плана поисков минимума функции f абсолютно четкое, не оставляющее места какому-либо произволу, и в применении к каждой конкретной функции f, от­резку от х' до х" и числу п предписывает совершенно точную последовательность действий, оно является довольно запутанным и трудно обозримым.

Приведем поэтому для наглядности еще одно описание этого же плана в виде блок-схемы (рис. 9).

Рис. 9

15. Приведем в заключение пример использова­нии описанного в пп. 13 и 14 плана для нахождения с помощью пяти вычислений на отрезке от 1 до 2 точки , минимизирующей функцию

Предварительно сделаем замечание.

Нахождение точки, минимизирующей (или макси­мизирующей) функцию, которая задана аналитически, обычно удобнее проводить не методами теории поиска, а другими, более приспособленными для этого приемами, которые относятся к дифферен­циальному исчислению. Поэтому следует иметь в виду, что приводимый далее пример носит чисто иллюстративный характер. Диференциальное исчисле­ние позволяет без труда показать, что в этом случае Нам же удастся найти значи­тельно более грубое приближение. Однако в тех слу­чаях, когда заранее о функции нам неизвестно ничего (кроме того, что она не может переходить от возра­стания к убыванию) или же выражения, которыми она задается, чересчур сложны, методика дифферен­циальною исчисления неприменима, и теория поиска оказывается полезным инструментом.

1°. Сравнение п=5 и 1 дает нам, что п≠1, по­этому переходим к п. 4°.

4°. Вычисляем:

5°. Вычисляем:

6°. Сравнение п = 5 и 2 дает, что п≠ 2; поэтому Переходим к п. 10°.

10°. Сравнение

дает нам f(х1)> f (х2); поэтому переходим к п. 14°.

14°. Переобозначаем:

15°. Вычисляем:

16°. Вычисляем:

и переходим к п. 6°.

6°. Сравниваем п = 4 и 2; поскольку п≠2, пере­ходим к п. 10°.

10°. Сравниваем поскольку переходим к п. 11°.

11°. Переобозначаем:

12°. Вычисляем:

13°. Вычисляем:

и переходим к п. 6°.

6°. Сравниваем п = 3 и 2; поскольку п≠2, переходим к п. 10°.

10°. Сравниваем

поскольку f (x1) > f (x2), переходим к п. 14°.

14°. Переобозначаем:

15°. Вычисляем:

16°. Вычисляем

и переходим к п. 6°.

6°. Сравнение g и 2 дает нам, что п = 2; перехо­дим к п. 7°.

7°. Сравниваем

f (x1) ≤ f (x2); поэтому переходим к п. 8.

8°. Полагаем =1,61538.

На основании теоремы п. 11 найденное нами может отличаться от истинного положения миними­зирующей точки не более чем на

Фактически эта ошибка оказывается мень­шей; она равна 0,028. Заметим, что принимаемое нами за наименьшее значение функции f, т. е. f(x), равно 1,89003 и отличается от истинного наименьшего зна­чения f, равного

лишь, на 0,00015. Это показывает, что значения х можно было в ходе наших вычислений определять с меньшей точностью, чем значения f.

Сам по себе такой вывод не содержит ничего уди­вительного. В самом деле, значения х мы должны находить с той предельной точностью, с какой мы можем в наших условиях найти минимизирующую точку (мы знаем, что эта точность равна

Значения же функции f должны вычисляться с точ­ностью, обеспечивающей сравнение пар значений этой функции и выделение из каждой такой пары наи­меньшего и наибольшего значения. Поэтому если в действительности какие-нибудь f(а) и f(b) сильно отличаются друг от друга и это отличие заметно уже при грубом определении f(а) и f(b), то мы можем вычислять эти значения с малой точностью. Наоборот, если эти f(а) и f(b) в действительности близки, то для выяснения того, какое из них больше другого, приходится вести вычисление с большой точностью. Так как мы наперед (до фактического выполнения вычислений) не знаем, насколько отличаются друг ог друга сравниваемые значения функции, мы можем «промахнуться» и вычислить их с недостаточной точ­ностью, которая не даст возможности решить, какое из этих значений больше. В этом случае придется произвести повторные, более точные вычисления, за­тратив на это дополнительные усилия.

А теперь рассмотрим метод Фибоначчи как метод однопараметрической оптимизации.

Предположим, что нужно определить минимум как можно точнее, т. е. с наименьшим возможным интервалом неопределенности, но при этом можно выполнить только n вычислений функции. Как следует выбрать n точек, в которых вычисляется функция? С первого взгляда кажется ясным, что не следует искать решение для всех точек, получаемых в результате эксперимента. Напротив, надо попытаться сделать так, чтобы значения функции, полученные в предыдущих экспериментах, определяли положение последующих точек. Действительно, зная значения функции, мы тем самым имеем информацию о самой функции и положении ее минимума и используем эту информацию в дальнейшем поиске.

Предположим, что имеется интервал неопределенности (x1,x3) и известно значение функции f(x2) внутри этого интервала (см. рис. 10). Если можно вычислить функцию всего один раз в точке х4, то где следует поместить точку х4, для того чтобы получить наименьший возможный интервал неопределенности?

Рис. 10.

Положим х2–х1=L и х3–х2=R, причем L > R, как показано на рис. 10, и эти значения будут фиксированы, если известны x1, x2 и х3. Если х4 находится в интервале (х1; х2), то:

если f(x4) < f(x2), то новым интервалом неопределенности будет (x1,x2) длиной х2–х1=L; если f(х4)>f(x2), то новым интервалом неопределенности будет (х4,х3) длиной х3–х4.

Поскольку не известно, какая из этих ситуаций будет иметь место, выберем х4 таким образом, чтобы минимизировать наибольшую из длин х3-х4 и х2-х1. Достигнуть этого можно, сделав длины х3 – х4 и х2 – х1 равными т. е. поместив х4 внутри интервала симметрично относительно точки х2, уже лежащей внутри интервала. Любое другое положение точки х4 может привести к тому, что полученный интервал будет больше L. Помещая х4 симметрично относительно х2, мы ничем не рискуем в любом случае. Если окажется, что можно выполнить еще одно вычисление функции, то следует применить описанную процедуру к интервалу (х1, х2), в котором уже есть значение функции, вычисленное в точке х4, или к интервалу (х4,х3), в котором уже есть значение функции, вычисленное в точке х2.