Сравнительный анализ методов оптимизации (стр. 3 из 7)

Найдем точки x₁и х_2, обладающие указанным свойством.

Рассмотрим сначала отрезок [0; 1] и для определенности предположим, что при его уменьшении исключается правая часть этого отрезка. Пусть х₂= t, тогда симметрично расположенная точка х₁= 1-t (рисунок 6).

Рисунок 6 - Определение пробных точек в методе золотого сечения

Пробная точка х₁отрезка [0; 1] перейдет в пробную точку х₂¢ = 1-t нового отрезка [0; t]. Чтобы точки х₂= t, и х₂¢ = 1-t делили отрезки [0; 1] и [0; t] в одном и том же отношении, должно выполняться равенство

или

, откуда находим положительное значение

…

Таким образом,

х₁= 1-t =

Для произвольного отрезка [а; b] выражения для пробных точек примут вид

;

. (5)

Замечания:

1. Точки x₁и х₂из (5) обладают следующим свойством: каждая из них делит отрезок [а; b] на две неравные части так, что отношение длины всего отрезка к длине его большей части равно отношению длин большей и меньшей частей отрезка. Точки с таким свойством называются точками золотого сечения отрезка [а; b]. Это и объясняет название рассматриваемого метода.

2. На каждой итерации исключения отрезков с пробными точками (5) одна из них

переходит на следующий отрезок и значение f (x) в этой точке вычислять не следует. Если новым отрезком становится [а; х₂], то на него переходит пробная точка
исходного отрезка, становясь его второй пробной точкой (х₂^’= х₁) (рисунок 6). В случае перехода к отрезку [х₁; b] пробная точка

исходного отрезка становится первой пробной точкой отрезка [х₁; b].

3. Легко проверить, что х₁=а+b-х_2, и x₂=а+b-х₁. Поэтому на каждой итерации метода золотого сечения недостающую пробную точку нового отрезка можно найти по перешедшей на него пробной точке с помощью сложения и вычитания, не используя формул (5).

4. В конце вычислений по методу золотого сечения в качестве приближенного значения х* можно взять середину последнего из полученных отрезков

Опишем алгоритм метода золотого сечения.

Шаг 1. Найти х₁ и х₂ по формулам (5). Вычислить f (x₁) и f (x₂).

Шаг 2. Определить

. Проверка на окончание поиска: если e_n > e, то перейти к шагу 3, иначе - к шагу 4.

Шаг 3. Переход к новому отрезку и новым пробным точкам. Еслиf (x₁) £f (x₂) то положить b=x_2,x₂=x₁, f (x₂) £f (x₁), x₁=b-t (b-a) и вычислить f (x₁), иначе - положить a=x₁, x₁= x₂, f (x₁) = f (x₂), x₂=b+t (b-a) и вычислить f (x₂). Перейти к шагу 2.

Шаг 4. Окончание поиска: положить

Сравнение методов исключения отрезков. При сравнении прямых методов минимизации обычно учитывают количество N значений f (x), гарантирующее заданную точность определения точки х* тем или иным методом. Чем меньше N, тем эффективнее считается метод. При этом вспомогательные операции такие, как выбор пробных точек, сравнение значений f (x) и т.п., не учитываются. Во многих практических случаях определение значений целевой функции требует больших затрат (например, времени ЭВМ или средств для проведения экспериментов) и вспомогательными вычислениями можно пренебречь. А эффективность метода минимизации особенно важна именно в таких случаях, поскольку позволяет сократить указанные затраты.

Эффективность методов минимизации можно также сравнивать, на основании гарантированной точности e (N) нахождения точки х*, которую они обеспечивают в результате определения N значений f (x). Метод золотого сечения считают более точным, чем метод дихотомии, однако разница в точности в данном случае незначительна.

2.1.3 Практическое применение прямых методов одномерной безусловной оптимизации

Пусть заданы следующие параметры:

Примем

. Тогда

(рисунок 7).

Рисунок 7 - Поведение исходной функции на заданном отрезке

Проведем несколько итерации методом дихотомии:

Поскольку f (x₁) < f (x₂), то b: =x₂, a оставляем прежним. Тогда для следующей итерации:

Так как f (x₁) > f (x₂), то a: =x₁, b оставляем прежним. Тогда на третьем шаге:

Результаты полного решения данной задачи представлены на рисунке 8. Листинг программы представлен в приложении А.

Рисунок 8 - Получение решения методом дихотомии

Для метода золотого сечения:

Так как f (x₁) < f (x₂), то b: =x₂, a оставляем прежним. Тогда для следующей итерации:

Поскольку f (x₁) < f (x₂), то b: =x₂, a оставляем прежним. Тогда на третьем шаге:

И так далее до тех пор, пока не достигнем указанной точности. Полный расчет представлен на рисунке 9. Листинг программы представлен в приложении А.

Рисунок 9 - Получение решения методом золотого сечения

2.2 Методы безусловной минимизации функций многих переменных

Теперь рассмотрим задачи оптимизации, сводящиеся к поиску точек минимума функции многих переменных на всем пространстве. В большинстве случаев такая задача бывает сложнее задачи минимизации функции одной переменной, так как с ростом размерности пространства переменных, как правило, возрастают объем вычислений и сложность алгоритмов, а также затрудняется анализ поведения целевой функции.

2.2.1 Метод циклического покоординатного спуска

Этот метод заключается в последовательной минимизации целевой функции f (x) по направлениямx1 и x2.

Рисунок 10 - Циклический покоординатный спуск.

Опишем этот алгоритм.

Шаг 0. Выбрать х ÎE_n, критерий достижения точности e и шаг

. Найти f (x1^(0),x2⁽⁰⁾⁾.

Шаг 1. Принять x1⁽¹⁾= x1⁽⁰⁾+

. Определить f (x1^(1),x2⁽⁰⁾⁾. Сравнить полученное значение с значением начальной функции. Если f (x1^(1),x2⁽⁰⁾⁾ < f (x1^(0),x2⁽⁰⁾⁾, то перейти к шагу 5, если же f (x1^(1),x2⁽⁰⁾⁾ > f (x1^(0),x2⁽⁰⁾⁾, то перейти к шагу 2.

Шаг 2. Принять x1⁽¹⁾= x1^{(0) -}

Шаг 3. Принять x2⁽¹⁾= x2⁽⁰⁾+

. Определить f (x1^(0),x2⁽¹⁾⁾. Сравнить полученное значение с значением начальной функции. Если f (x1^(0),x2⁽¹⁾⁾ < f (x1^(0),x2⁽⁰⁾⁾, то перейти к шагу 5, если же f (x1^(0),x2⁽¹⁾⁾ > f (x1^(0),x2⁽⁰⁾⁾, то перейти к шагу 4.

Шаг 4. Принять x2⁽¹⁾= x2^{(0) -}

. Определить f (x1^(0),x2⁽¹⁾⁾. Сравнить полученное значение с значением начальной функции. Если f (x1^(0),x2⁽¹⁾⁾ < f (x1^(0),x2⁽⁰⁾⁾, то перейти к шагу 4, если же f (x1^(0),x2⁽¹⁾⁾ > f (x1^(0),x2⁽⁰⁾⁾, то принять исходную точку за минимум.

Шаг 5. Проверить условие достижения точности