Лекция 1
Методы одномерной оптимизации

Понятие сходимости

Большинство методов решения задач оптимизации, которые мы будем рассматривать, имеет итерационную природу, т.е. исходя из некоторой начальной точки x⁰, они порождают потенциально бесконечную последовательность точек x⁰, x¹, ..., x^k, ..., которая, как мы рассчитываем, сходится к искомому оптимуму (экстремуму).

Алгоритм решения есть процесс, позволяющий, исходя из заданной начальной точки x⁰, строить последовательность x¹,..., x^k, ...,.

Будем говорить, что алгоритм глобально сходится (или обладает свойством глобальной сходимости), если для любой исходной точки x⁰ последовательность x¹,..., x^k, ..., порожденная данным алгоритмом, сходится к точке, удовлетворяющей необходимому условию оптимальности. Свойство глобальной сходимости выражает в некотором смысле надежность функционирования алгоритма.

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

Если мы хотим получить критерий с некоторым абсолютным значением, то следует прибегнуть к другому типу анализа, взяв за объект исследования асимптотическую сходимость, т.е. поведение последовательности x¹,..., x^k, ... в окрестности предельной точки x^*. Это приводит к тому, что каждому алгоритму приписывается некоторый индекс эффективности, называемый скоростью сходимости.

Если , то говорят о линейной сходимости с коэффициентом сходимости α. Если , то говорят о суперлинейной сходимости. Если существует такое γ > 1, что , то говорят о сходимости порядка γ. В частности, если , то говорят о квадратичной сходимости.

Методы, использующие производные

Методы одномерного поиска используются в многомерных методах минимизации функций n переменных.

Метод Ньютона-Рафсона

В этом методе предполагается, что функция f (x) дважды непрерывно дифференцируемая. Отыскание минимума функции f (x) производится при помощи отыскания стационарной точки, т.е. точки x^*, удовлетворяющей уравнению
f ^'(x) = 0 при помощи метода Ньютона.

Если x^k – точка, полученная на k-м шаге, то функция f ^'(x) аппроксимируется своим уравнением касательной:
y = f ^'(x^k) + (x - x^k) f ^''(x^k), а точка x^k+1 выбирается как пересечение этой прямой с осью Ох, т.е.

x^k+1 = x^k - f ^'(x^k) / f ^''(x^k).

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

Когда начальная точка итераций x⁰ достаточно близка к искомому минимуму, скорость сходимости метода Ньютона в общем случае квадратическая. Однако, глобальная сходимость метода Ньютона, вообще говоря, не гарантируется.

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

Метод секущих

Этот метод состоит в аппроксимации функции f ^'(x) не при помощи своей касательной в точке x^k (как в методе Ньютона), а при помощи секущей – прямой, проходящей через точки с координатами (x^k - 1, f ^'(x^k - 1)) и (x^k, f ^'(x^k)). Тогда

x^k + 1 = x^k - f ^'(x^k)^. (x^k - x^k - 1) / (f ^'(x^k) - f ^'(x^k - 1)).

Этот метод называется также методом хорд.

Глобальная сходимость метода секущих, как и метода Ньютона, не гарантирована. Стало быть, начальные точки x⁰ и x¹ должны быть выбраны достаточно близкими к минимуму.

Методы, не использующие производные

Метод парабол (квадратичная интерполяция)

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

В этом методе вычисляется значение функции сразу в трех близлежащих точках x₀ - h, x₀, x₀ + h, где h – малое число. Через эти три точки проводится интерполяционная парабола: y = ax² + bx + c. Минимум параболы достигается при y = 2ax + b = 0, т.е. при x^* = -b / (2a). Для трех точек получаем систему трех линейных уравнений для коэффициентов a, b, c. Находим a и b и тогда:

.

Общая схема методов поиска минимума на отрезке

Теперь мы перейдем к рассмотрению других методов, более общих в том смысле, что они не требуют условия непрерывности или дифференцируемости. Они просто предполагают, что по крайней мере в некотором интервале функция f (x) обладает свойством унимодальности. Функция называется унимодальной на отрезке [a₀, b₀], если она монотонно убывает от a₀ до некоторого x^* из [a₀, b₀], а затем возрастает до b₀. В этом случае x^* соответствует локальному минимуму функции, и он единственный.

Пусть функция f (x) унимодальна на отрезке [a₀, b₀]. Необходимо найти точку минимума функции на этом отрезке с заданной точностью ε. Все методы одномерного поиска базируются на последовательном уменьшении интервала, содержащего точку минимума. Возьмем внутри отрезка [a₀, b₀] две точки x₁ и x₂: a₀ < x₁ < x₂ < b₀, и вычислим значения функции в этих точках. Из свойства унимодальности функции можно сделать вывод о том, что минимум расположен либо на отрезке [a₀, x₂], либо на отрезке [x₁, b₀]. Действительно, если f (x₁) < f (x₂), то минимум не может находиться на отрезке [x₂, b₀], если f (x₁) > f (x₂), минимум не может находиться на отрезке [a₀, x₁]. Если же f (x₁) = f (x₂), то минимум находится на интервале [x₁, x₂].

Алгоритм заканчивается, когда длина интервала, содержащего минимум, становится меньше ε.

Различные методы одномерного поиска отличаются выбором точек x₁, x₂. Об эффективности алгоритмов можно судить по числу вычислений функции, необходимому для достижения заданной точности.

Метод дихотомии (деление отрезка пополам)

Точки x₁, x₂ выбираются на расстоянии δ < ε от середины отрезка:

x₁ = (a_i + b_i - δ) / 2, x₂ = (a_i + b_i + δ) / 2.

За одну итерацию интервал неопределенности уменьшается примерно в два раза.

За n итераций длина интервала будет примерно равна .

Для достижения точности ε потребуется итераций.

На каждой итерации минимизируемая функция вычисляется дважды.

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

Точки x₁, x₂ находятся симметрично относительно середины отрезка [a₀, b₀] и делят его в пропорции золотого сечения, когда длина всего отрезка относится к длине большей его части также, как длина большей части относится к длине меньшей части:

и .

Отсюда:

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

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

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

Числа Фибоначчи определяются соотношениями: F_n+2 = F_n+1 + F_n, n = 1, 2, 3, ...; F₁ = F₂. С помощью индукции можно показать, что n-е число Фибоначчи представимо в виде (формула Бинэ):

Из этой формулы видно, что при больших n: , так что числа Фибоначчи с увеличением n растут очень быстро.

На начальном интервале вычисляют точки , где n выбирается исходя из точности и начальной длины интервала (см. ниже).

На k-м шаге метода будет получена тройка чисел , локализирующая минимум f (x), такая, что а точка с вычисленным значением , совпадает с одной из точек расположенных на отрезке [a_k, b_k] симметрично относительно его середины. При k = n процесс заканчивается. В этом случае длина отрезка а точки совпадают и делят отрезок пополам.

Следовательно, . Отсюда можно выбрать n из условия .

С ростом n, из-за того, что F_n/F_n+2 – бесконечная десятичная дробь, происходит искажение метода. Поэтому на очередном шаге в качестве новой точки берут наиболее удалённую от на предыдущем шаге.

Поиск интервала, содержащего минимум функции

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

Выбираем начальную точку x₀ и определяем направление убывания функции.

Шаг 1. Если f (x₀) > f (x₀ + δ), то полагаем: k = 1, x₁ = x₀ + δ, h = δ. Если же f (x₀) > f (x₀ -δ), то x₁ = x₀ + δ, h = - δ.

Шаг 2. Удваиваем h и вычисляем x_k+1 = x_k + h.

Шаг 3. Если f (x_k) > f (x_k+1), то полагаем k = k + 1 и переходим к шагу 2. Иначе – поиск прекращаем, т.к. отрезок [x_k-1, x_k+1] содержит точку минимума.