Алгоритм метода обратного переменного шага.

Новокузнецк

Министерство образования Российской Федерации

Сибирский государственный индустриальный университет

Кафедра информационных технологий в металлургии

АЛГОРИТМЫ И ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ

Методические указания к выполнению лабораторно-практических работ
по курсу «Оптимизация в технике и технологиях»

Специальности: «Информационные системы и технологии» (071900), специализации «Прикладное математическое и программное обеспечение»,
по курсу «Методы оптимизации в металлургии»

Специальности: «Металлургия черных металлов» (110100),

специализации «Информационные технологии и предпринимательство
в металлургии» (110107).

Новокузнецк

УДК 681.3.06

Алгоритмы и примеры решения задач одномерной оптимизации: Метод. указ./ Сост.: С.П Мочалов, И.А. Рыбенко.: СибГИУ.- Новокузнецк, 2004.- 18с., ил.

Изложены теоретические аспекты методов поиска экстремума функции одной переменной, представлены алгоритмы методов, приведены примеры решения задач одномерной оптимизации и варианты заданий.

Предназначены для студентов специальности «Информационные системы и технологии» (071900), специализации «Прикладное математическое и программное обеспечение» и «Металлургия черных металлов» (110100), специализации «Информационные технологии и предпринимательство в металлургии» (110107).

Рецензент - кафедра систем автоматизации (зав. кафедрой С.М.Кулаков)

Печатается по решению редакционно-издательского совета университета.

1. ОБЩИЕ ПОЛОЖЕНИЯ

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

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

Постановка задачи одномерной оптимизации заключается в нахождении точки х^*, в которой целевая функция f(х^*) принимает минимальное (максимальное) значение. Функция f(x) имеет локальный минимум в точке х⁰, если при e>0 существует окрестность [x-e; x+e ], такая, что для всех значений х в этой окрестности f(x) больше f(x^*). Функция f(x) имеет глобальной минимум в точке х^*, если для всех х справедливо неравенство f(x) >f(x^*).

Аналитический анализ функции. Классический подход к задаче нахождения экстремума функции состоит в поиске условий, которым они должны удовлетворять. Необходимым условием экстремума в точке x^* является равенство нулю первой производной, т.е. требуется решить уравнение f ^’(x)=0.

Данному уравнению удовлетворяет как локальные и глобальные экстремумы, так и точки перегиба функции, поэтому приведенное условие является необходимым, но не достаточным.

С целью получения более определенных выводов требуется расчет значений вторых производных в точках, удовлетворяющих уравнению равенства нулю первой производной. При этом доказано, что минимуму функции соответствует положительной значение второй производной (f^’”(x)>0), а максимальному – отрицательное (f^’”(x)<0). Однако, если вторая производная равна нулю, ситуация остается неопределенной.

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

Целью выполнения лабораторно-практических работ является: формирование навыков решения оптимизационных задач с использованием различных методов поиска экстремума функции одной переменной.

2. ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ МЕТОДОВ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ. АЛГОРИТМЫ И ПРИМЕРЫ РЕШЕНИЯ.

2.1 Поисковые методы

Основой всех одномерных поисковых методов является сокращение интервала неопределенности, а именно: построение последовательности отрезков [a_k ; b_k], стягивающихся в точке х^* - минимуму функции на исходном отрезке. Методы оптимизации отличаются друг от друга лишь различным выбором точек на начальном интервале неопределенности: в методе половинного деления – число Е>0 – наименьший сдвиг по х, при котором еще можно отличить f(x) и f(x+Е); в методе золотого сечения – величина ; в методе Фибоначчи используются числа Фибоначчи.

Общая последовательность реализации методов такова: установление границ начального интервала, выбор точек в начальном интервале неопределенности; вычисление значений функции в этих точках и сравнение этих значений; проверка критерия окончания расчетов.

На этапе установления границ интервала на основе априорных данных или правил исключения строится относительно широкий интервал [a, b], содержащий точку оптимума x^*. Обычно поиск граничных точек такого интервала проводится с помощью эвристических методов поиска, хотя в ряде случаев можно также использовать методы экстраполяции. Так как минимум x^* на [a, b] неизвестен, то этот интервал называется интервалом неопределенности. Для унимодальной функции f(x) интервал неопределенности может быть сокращен с помощью вычисления значений функции в двух точках x, y Î [a, b]. При этом возможны два случая. Если f(x) > f(y), то новым интервалом неопределенности является [x, b], поэтому переприсвоение границ интервала на итерациях для этого случая осуществляется по правилу a_k+1 = x_k, а b_k+1 = b_k. При выполнении условия f(x) £ f(y), новым интервалом будет [a, y] и, соответственно, a_k+1 = a_k, b_k+1 = y_k.

2.1.1 Метод сканирования

Сканирование или равномерный поиск является примером одновременного поиска, когда точки, в которых вычисляется значение функции, выбираются заранее. Начальный интервал неопределенности [a₁, b₁] делится на отрезки величиной d сеткой из точек a₁ + kd для k = 1, …, n. Тогда b₁ = a₁+ (n - 1)d. Затем функция f(x) вычисляется в каждой из n точек сетки и определяется , в которой она имеет наименьшее значение. Если f(x) унимодальна, то минимум принадлежит интервалу [ - d , + d].

После n вычислений функции интервал [a₁, b₁] сокращен до длины 2d. Так как n = [(b₁ - a₁)/d] - 1, то для достижения более высокой точности нахождения минимума необходимо большое число вычислений функции.

Алгоритм метода сканирования.

Начальный этап. Выбрать шаг разбиения d> 0 и начальный интервал [a₁, b₁]. Задать k = 1 и перейти к основному этапу.

Основной этап. Шаг 1. Вычислить значение х=a₁ + kd и f(x). Если k=n, то перейти к шагу 2, иначе положить k=k+1 и вернуться к шагу 1.

Шаг 2. Выбрать минимальное значение функции f(x) и соответствующее ему значение . Минимум функции находится в интервале [ -d , + d].

Пример расчета экстремума функции методом сканирования.

Постановка задачи. Определить экстремум функции f(x)=(x-2)²+7.

Определение экстремума аналитически. Необходимым условием существования экстремума является равенство нулю первой производной. Решаем уравнение f'(x)=2(x-2)=0. Полученная точка х*=2 является точкой минимума, так как вторая производная в данной точке f''(x*) =2>0.

Реализация метода сканирования. Выбираем достаточно большой начальный интервал [-100, 100] и количество разбиений n=10. Результаты расчетов точек и значений функции представлены в таблице 2.1.

Таблица 2.1

Результаты расчетов методом сканирования.

Графический анализ функции Строим график функции на данном интервале (рис.2.1).

Рис.2.1

В результате реализации метода сканирования получена минимальная точка х*=0, значение функции в которой составляет f(x)=11. Границами интервала являются две точки по обе стороны от минимальной. Исходя из этого, делаем вывод, что экстремум находится в интервале
[a₁b₁]=[-20,20]. Этот интервал можно использовать в качестве начального при реализации других методов одномерной оптимизации либо двойного сканирования.

2.1.2. Метод локализации оптимума.

С целью повышения точности и уменьшения числа расчетов целевой функции используется процедура двойного сканирования. В начале необходимо определить [ - d, + d], а затем вновь повторить сканирование. Этапы повторяются до достижения заданной точности. Этот метод называется локализацией оптимума. Он работает наиболее эффективно, если текущий интервал неопределенности делится на четыре части. При этом на начальном интервале вычисляются три точки на расстоянии (b₁-a₁)/4 друг от друга, затем рассчитывается значение функции в этих трех точках. Из полученных точек выбирается точка с минимальным значением функции и две точки по обе стороны от нее. Таким образом, получается новый интервал, для которого известны границы и середина интервала. После чего следует рассчитать только две новые точки по обе стороны от середины интервала. Расчет осуществляется до тех пор, пока длина конечного интервала не станет меньше заданной точности.

Алгоритм метода локализации оптимума.

Начальный этап. Выбрать начальный интервал [a₁, b₁] и точность поиска l. Задать k = 1, i=1 и перейти к основному этапу.

Основной этап. Шаг 1. Определить d_k=(b_k–a_k)/4. Вычислить значение х_ik=a_k + id_k и f(x_ik). Если i=3, то перейти к шагу 2, иначе положить i=i+1 и вернуться к шагу 1.

Шаг 2. Выбрать минимальное значение функции f(x_i) и соответствующее ему значение x_ik. Если i(min)=1, то a_к+1= a_к, b_к+1=x_2,k, x_{2, k+1}= x_{1, k..} Если i(min)=2, то a_к+1= x_{1, k}, b_к+1=x_3,k, x_{2, k+1}= x_{2, k..} Если i(min)=3, то a_к+1= x₂,_к, b_к+1=b_,k, x_2,k+1=x_3,k, положить k=k+1 и перейти к шагу 3.

Шаг 3. Если (b_k – a_k)<l, то остановиться, минимум функции находится на интервале [b_k – a_k]. Иначе, перейти к шагу 4.

Шаг 4. Вычислить d_k=(b_k – a_k)/4, x_1,k=a_k+d_k и x_3,k=a_k+3d_k , а также f(x_1,k ), f(x_3,k ). Перейти к шагу 2.

Пример расчета экстремума функции методом локализации оптимума.

Постановка задачи. Определить экстремум функции f(x)=(x-2)²+7 на полученном с использованием метода сканирования начальном интервале
[-20;20] с точностью l=0,5.

Расчет экстремума методом локализации оптимума для заданной задачи реализован средствами ECXEL. Результаты расчета представлены в таблице 2.2.

Таблица 2.2

Расчет экстремума функции f(x)=(x-2)²+7 методом локализации оптимума.

После семи итераций и восьми расчетов значений функции интервал неопределенности составил [1,88; 2,19]. При этом |b₈ – a₈|=0,31, что меньше заданной величины 0,5. В качестве точки минимума может быть взята середина интервала 2,03. Следует отметить, что искомый минимум находится в точке х*=2.0.

2.1.3. Метод половинного деления.

Метод половинного деления является процедурой последовательного поиска. Используется стратегия выбора точек x₁ и y₁ на интервале [a₁, b₁], направленная на минимизацию максимумов из x₁ - a₁ и b₁ - y₁. Это может быть достигнуто расчетом точек x₁ и y₁, симметрично расположенных на расстоянии e>0 от середины интервала каждая. Здесь число e>0 настолько мало, чтобы длина нового интервала e + (b₁ - a₁)/2 являлась достаточно близкой к значению (b₁ - a₁)/2 и в то же время, чтобы значения функций f(x₁), f(y₁) были различны.

Алгоритм метода половинного деления.

Начальный этап. Выбрать константу 2e > 0, допустимую конечную длину интервала l > 0, начальный интервал [a₁, b₁]. Задать k = 1 и перейти к основному этапу.

Основной этап. Шаг 1. Если b_k - a_k < l то остановиться; точка минимума принадлежит интервалу [a_k, b_k], иначе вычислить

x_k = y_k =

и перейти к шагу 2.

Шаг 2. Если f(x_k) < f(y_k) то a_k+1 = a_k и b_k+1 = y_k. В противном случае положить a_k+1 = x_k и b_k+1 = b_k . Заменить k = k + 1 и перейти к шагу 1.

Пример расчета экстремума функции методом половинного деления.

Постановка задачи. Определить экстремум функции f(x)=x₂-3x+2 на интервале
[-10;10] с точностью l=0,03 и константой различимости e=0,005 .

Результаты расчета с применением табличного процессора ECXEL по алгоритму, рассмотренному выше, представлены в таблице 2.3.

Таблица 2.3

Расчет экстремума функции f(x)=x₂-3x+2 методом половинного деления.

Таким образом, при поиске экстремума функции f(x)=x₂-3x+2 методом половинного деления после десяти итераций и одиннадцати вычислений значений функции интервал неопределенности составил [1,479; 1,508]. При этом |b₁₁ – a₁₁|=0,030, что равно заданной величине l=0,3. Следует отметить, что искомый минимум находится в точке х*=1,5.

2.1.4. Метод золотого сечения.

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

Основные соотношения метода вытекают из следующих предпосылок. Пусть на k-ой итерации метода золотого сечения интервал неопределенности равен [a_k, b_k]. Точки x_k, y_k выбираются на основе следующих условий.

x_k=a_k+(1-a)×(b_k-a_k)

y_k=a_k+a×(b_k-a_k), где aÎ (0, 1)– коэффициент сжатия.

Длина нового интервала неопределенности определяется следующим способом: b_k+1 - a_k+1 = a(b_k - a_k)

Кроме того, должны выполняться равенства

b_k - x_k = y_k - a_k; x_k = a_k + (1 - a)(b_k - a_k); y_k = a_k +a(b_k - a_k).

Для новой итерации x_k+1 и y_k+1 выбираются так, что x_k+1 совпадает с y_k, или y_k+1 совпадает с x_k. Это условие обеспечивает возможность того, что на (k +1)-й итерации потребуется только одно новое вычисление функции.

При сравнении значений функции в двух точках возможны два варианта.
1. Если f(x_k) > f(y_k), то в этом случае a_k+1 = x_k и b_k+1 = b_k. При x_k+1 = y_k имеем y_k+1 = a_k+1 + a(b_k+1 - a_k+1) = x_k + a(b_k+1 - a_k+1). Подставляя в это выражение для x_k и y_k уравнения из предыдущего первого условия, получим, что a² + a - 1 = 0.

2. Если f(x_k) £ f(y_k), то в этом случае a_k+1 = a_k и b_k+1 = y_k. При y_k+1 = x_k имеем x_k+1 = a_k+1 + (1 - a)(b_k+1 - a_k+1) = a_k + (1 - a)(y_k - a_k). Подставляем в это выражение для x_k и y_k уравнения из предыдущего первого условия также получим a² + a - 1 = 0.

Корнями уравнения a² + a- 1=0 являются a= 0.618 и a= -1.618. Так как a должно быть из интервала (0, 1), то принимаем a= 0.618. На первой итерации метода необходимы два вычисления функции в точках x₁ и y₁, но на каждой последующей требуется только одно вычисление, так как либо x_k+1 = y_k, либо y_k+1 = x_k.

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

Начальный этап. Задается конечная длина интервала неопределенности l > 0, начальный интервал [a₁, b₁]. Вычислить x₁ = a₁ + (1 - a)(b₁ - a₁) и y₁ = a₁ + a(b₁ - a₁), приняв a = 0.618. Найти f(x₁), и f(y₁). Задать k = 1 и перейти к основному этапу.

Основной этап. Шаг 1. Если b_k - a_k < 1, то остановиться; оптимальная точка принадлежит интервалу [a_k, b_k]. При f(x_k) > f(y_k), перейти к шагу 2, если f(x_k) £ f(y_k), то к шагу 3.

Шаг 2. Положить a_k+1 = x_k; b_k+1 = b_k; x_k+1 = y_k; f(x_k+1) = f(y_k). Вычислить y_k+1 = a_k+1 + a(b_k+1 - a_k+1).

Вычислить f(y_k+1) и перейти к шагу 4.

Шаг 3. Положить а_k+1 = a_k, b_k+1 = y_k, y_k+1 = x_k, f(y_k+1) = f(x_k). Вычислить x_k+1 = a_k+1 + (1-a)(b_k+1 - a_k+1). Вычислить f(x_k+1) и перейти к шагу 4.

Шаг 4. Заменить k = k + 1 и перейти к шагу 1.

Пример расчета экстремума функции методом золотого сечения.

Постановка задачи. Минимизировать f(x) = x² + 2x на интервале xÎ[-3; 5] сократив его до величины l £ 0,2.

Рассчитываем минимум функции f(x) = x² + 2x с использованием табличного процессора ECXEL по рассмотренному выше алгоритму. Результаты расчетов представлены в таблице 2.4.

Таблица 2.4

Расчет экстремума функции f(x)= x² + 2x методом золотого сечения.

После восьми итераций интервал неопределенности составил
[-1,111; -0,941]. При этом |b₉ - a₉|=0,170, что меньше заданной величины 0,2. В качестве точки минимума может быть взята середина интервала -1,026. Искомый минимум равен ‑1,0.

2.1.5. Метод Фибоначчи.

В отличие от рассмотренных поисковых процедур в методе Фибоначчи используется числовая последовательность, поэтому общее число n вычислений функции заранее задается. Это объясняется тем, что точки, в которых производятся вычисления, определяются по зависящим от n формулам

x_k = a_k + (b_k - a_k), k = 1, …, n - 1;

y_k = a_k + (b_k - a_k), k = 1, …, n - 1.

где F_j =F_j-1 + F_j-2, j = 3, 4, …; F₀=F₁=1 называется последовательностью чисел Фибоначчи (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,...). В этом методе длина интервала неопределенности на k-й итерации сократится от b₁ - a₁ до (b₁ - a₁)/F_n. Поэтому для требуемой точности можно заранее рассчитать величину F_n и количество вычислений функции.

Алгоритм метода Фибоначчи.

Начальный этап. Задается конечная длина интервала l > 0 и константа различимости e > 0, начальный интервал [a₁, b₁]. Выбрать число вычислений функции n так, чтобы F_n > (b₁ - a₁)/l. Вычислить x₁ = a₁ + (F_n-2/F_n)(b₁ - a₁), y₁ = a₁+(F_n-1/F_n)(b₁-a₁); f(x₁); f(y₁) . Принять k = 1 и перейти к основному этапу.

Основной этап. Шаг 1. Если f(x_k) > f(y_k), то перейти к шагу 2, если f(x_k) £ f(y_k), то к шагу 3.

Шаг 2. Принять a_k+1 = x_k; b_k+1 = b_k. Затем вычислить x_k+1 = y_k, y_k+1 = a_k+1 + (F_n-k-1/F_n-k)×(b_k+1 - a_k+1). Если k = n - 2, то перейти к шагу 4.

Шаг 3. Принять a_k+1 = a_k; b_k+1 = y_k; x_k+1 =a_k+1 + (F_n-k-2/F_n-k)×(b_k+1 - a_k+1). Если k = n - 2, то перейти к шагу 5, иначе вычислить f(x_k+1) и перейти к шагу 4.

Шаг 4. Присвоить k = k + 1 и перейти к шагу 1.

Шаг 5. Принять x_n = x_n-1 и y_n = x_n+e . Если f(x_n) > f(y_n) , то a_n = x_n и b_n = b_n‑1. При f(x_n) £ f(y_n) вычислить a_n = a_n-1 и b_n = у_n и остановиться.

Оптимальное решение содержится в интервале [a_n, b_n].

Пример расчета экстремума функции методом Фибоначчи

Постановка задачи. Минимизировать f(x) = x² - 5x+8на интервале [-5, 5] с точностью l =0,25.

Результаты расчетов представлены в таблице 2.5.

Таблица 2.5

Расчет минимума функции f(x) = x² - 5x+8методом Фибоначчи.

Конечный интервал неопределенности равен [2,455; 2,636], длина которого l = 0,182. Середина интервала равна 2,545. Точка минимума х*=2,5.

2.2. Методы точечного оценивания.

2.2.1. Метод обратного переменного шага.

Предполагает задание начальной координаты x₁ и приращения Dx. Сущность метода заключается в следующем. Рассчитывается координата x_k+1 = x_k + Dx Если f(x_k+1) < f(x_k), то шаг считается “удачным” и его значение увеличивается Dx = aDx, a > 1. Если f(x_k+1) £ f(x_k), то шаг считается “неудачным”. Поэтому направление изменяется на противоположное, а значение шага уменьшается на величину b < 1 и будет равно Dx =-bDx. Затем проверяется условие окончания |x_k+1 - x_k| £ e и поиск продолжается.

Алгоритм метода обратного переменного шага.

Начальный этап. Выбрать начальную точку x₁ и приращение Dx. Задать коэффициенты деформации шага a > 1, 0<b < 1 и точность поиска e>0. Положить k = 1 и перейти к основному этапу.

Основной этап. Шаг 1. Если Dx < e то остановиться; точкой минимума является точка x_k, иначе вычислить x_k+1 = x_k+Dx и перейти к шагу 2.

Шаг 2. Если f(x_k) > f(х_k+1), то Dх=a Dx. В противном случае положить Dx =-bDx. Заменить k = k + 1 и перейти к шагу 1.

Пример расчета экстремума функции методом обратного переменного шага.

Постановка задачи. Рассчитать минимум функции f(x) = x² – 10х+3с точностью e=0,1. Начальную точку принять равной x₁=-1.

Выбираем следующие параметры метода: начальный шаг - Dх=1, коэффициенты растяжения и сжатия шага - a =1,5; b=0,4. Результаты расчета представлены в таблице 2.6.

Таблица 2.6

Расчет минимума функции f(x) = x² – 10х+3методом обратного переменного шага.

Таким образом, в результате реализации метода обратного переменного шага за шестнадцать итераций определена минимальная точка х*=5,114 с точностью 0,063.

2.2.2. Метод квадратичной аппроксимации.

Метод основан на предположении о том, что в ограниченном интервале можно аппроксимировать функцию квадратичным полиномом, который используется для оценивания координаты оптимума. Оценка оптимального значения рассчитывается по формуле:

= (x₂ + x₁)/2 - (a₁/2a₂).

Предполагается, что заданы x₁, x₂, x₃, и известны значения функции в этих точках f₁, f₂, f₃, а аппроксимирующая функция

g(x) = a₀ + a₁(x - x₁) + a₂(x - x₁)(x - x₂)

совпадает с f(x) в трех указанных точках.

Коэффициенты полинома определяются уравнениями

a₀ = f₁; a₁ = (f₂ - f₁)/(x₂ - x₁); a₂ = 1/(x₃ - x₂)×[(f₃ - f₁)/(x₃ - x₁) - (f₂ - f₁)(x₂ - x₁)].

Для унимодальных функций оказывается приемлемой для оценки оптимума x^*.

Алгоритм метода квадратичной аппроксимации.

Шаг 1. Задать x₁, x₂, x₃, и вычислить значения функции в этих точках f(х₁), f(х₂), f(х₃).

Шаг 2. Рассчитать a₀ = f(х₁); a₁ = (f(х₂) - f(х₁))/(x₂ - x₁);
a₂ = 1/(x₃ - x₂)×[(f(х₃) - f(х₁))/(x₃ - x₁) - (f(х₂) - f(х₁))(x₂ - x₁)].

Шаг 2. Вычислить оптимальное решение: = (x₂ + x₁)/2 - (a₁/2a₂).

Пример расчета экстремума функции методом квадратичной аппроксимации.

Постановка задачи.Найти минимум функции f(x) = x² + 5x методом квадратичной аппроксимации.

Для реализации метода необходимо выбрать три точки, по который будет производиться аппроксимация. Задаем следующие значения: x₁=-5, x₂=0, x₃=5, Результаты расчета, реализованного средствами ECXEL, представлены в таблице 2.7

Таблица 2.7

Расчет экстремума функции f(x) = x² + 5x методом квадратичной аппроксимации

Таким образом, с использованием метода квадратичной аппроксимации за одну итерацию найдена точка минимума x_опт=-2,5, которая совпадает с точкой экстремума x^*=-2,5, полученной аналитически.

2.2.3. Метод Пауэлла.

Заключается в последовательном применении процедуры оценивания с использованием квадратичной аппроксимации. Схему алгоритма можно описать следующим образом.