2.2 Методы одномерной оптимизации

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

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

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

2.2.1 Метод прямого сканирования

Задача заключается в локализации экстремума функции одной переменной, заданной на интервале с точностью доПри решении этой задачи весь интервал разбивается на участки величиной. В узлах разбиения вычисляются значения функции и из них выбирается экстремальное. Этот метод требует больших затрат времени (зависящего от значения), но главное его преимущество – это определение глобального экстремума. Блок-схема алгоритма поискапредставлена на рис. 2.4,б.

Рисунок 2.4 –Локализация экстремума методом сканирования:

а – геометрическая интерпретация; б – блок-схема алгоритма

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

Естественным и наиболее распространенным на практике методом поиска экстремума функции одной переменной является метод последовательного деления отрезка пополам. Этот метод был известен еще в древней Греции как метод дихотомии.

Пусть требуется определить экстремум унимодальной функции Q (u) на отрезкес точностью. Отрезокделится пополам и вычисляются значения функцииQ (x1) =F1 иQ (x2) =F2 в точках

x_1,2=.

На основе анализа значений ивдвое уменьшается интервал неопределенности и процесс повторяется пока. Блок-схема этого метода приведена на рис. 2.5,б.

Рисунок 2.5 –Метод деления отрезка пополам:

а – геометрическая интерпретация; б – блок-схема

2.2.3 Метод "золотого сечения"

Гораздо эффективнее, с точки зрения уменьшения затрат на вычисления, метод "золотого сечения": интервал неопределенности делится не пополам, как в методе дихотомии, а в определенном иррациональном соотношении

Это соотношение выполняется при ...

Метод заключается в том, что по заданным a иb как можно точнее определяется значение внутренней точкиx1 (см. рис. 2.6,б) по формуле

x1 = b – (b – a) / 1,618033989…

Рисунок 2.6 –Метод "золотого сечения":

а – золотое сечение; б – геометрическое представление

Точка x2 определяется как точка,симметричная точкеx1 на отрезке (a-b).

На основе анализа значений F1 =Q (x1) иF2 =Q (x2) интервал неопределенности сокращается путем отбрасывания из рассмотрения отрезка в котором экстремум исключен, исходя из условий уни-модальностиQ (u). Далее мы определим симметричную точку внутри новых границ, вычисляем значениеQ в этой точке, проводим анализ и т.д. до тех пор, пока разность между симметричными точками внутри интервала неопределенности больше. Блок-схема алгоритма метода "золотого сечения" представлена на рис. 2.7.

Рисунок 2.7 –Блок-схема метода "золотого сечения"