Введение

Алгоритм оптимизации

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

Одномерный поиск по линии

Предположим, что f — одномерная функция, и предположим, что она унимодальна, то есть содержит ровно один локальный минимум x* в заданном интервале [a, z]. Это означает, что f строго убывает на интервале [a, x*] и строго возрастает на интервале [x*, z]. В этом случае существует несколько способов найти (приблизительную) точку минимума.

Методы нулевого порядка

Методы нулевого порядка используют только оценки функций (т.е. значение оракула), а не производные:
Троичный поиск: выберите две точки b, c такие, что a < b < c < z. Если f(b) ≤ f(c), то x* должно находиться в [a, c]; если f(b) ≥ f(c), то x* должно находиться в [b, z]. В обоих случаях мы можем заменить интервал поиска на меньший. Если выбирать b, c очень близко к центру интервала, то интервал сокращается примерно на 1/2 на каждой итерации, но требуется две оценки функции за итерацию. Следовательно, метод имеет линейную сходимость со скоростью. Если выбирать b, c таким образом, чтобы разбиение a, b, c, z имело три интервала равной длины, то интервал сокращается на 2/3 на каждой итерации, поэтому метод имеет линейную сходимость со скоростью.
Поиск Фибоначчи: это вариант троичного поиска, в котором точки b, c выбираются на основе последовательности Фибоначчи. На каждой итерации требуется только одна оценка функции, поскольку другая точка уже была конечной точкой предыдущего интервала. Поэтому метод имеет линейную сходимость со скоростью.
Поиск по золотому сечению: это вариант, в котором точки b, c выбираются на основе золотого сечения. Снова, на каждой итерации требуется только одна оценка функции, и метод имеет линейную сходимость со скоростью. Это соотношение оптимально среди методов нулевого порядка.
Методы нулевого порядка очень общие – они не предполагают дифференцируемости или даже непрерывности.

Методы первого порядка

Методы первого порядка предполагают, что функция f непрерывно дифференцируема, и что мы можем вычислить не только значение f, но и её производную. Метод бисекции вычисляет производную f в центре интервала, c: если f'(c) = 0, то это точка минимума; если f'(c) > 0, то минимум должен находиться в интервале [a, c]; если f'(c) < 0, то минимум должен находиться в интервале [c, z]. Этот метод имеет линейную сходимость со скоростью 0,5.

Методы укладки кривой

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

Метод Ньютона является частным случаем метода подбора кривой, в котором кривая представляет собой многочлен второй степени, построенный с использованием первой и второй производных f. Если метод запущен достаточно близко к невырожденному локальному минимуму (с положительной второй производной), то он обладает квадратичной сходимостью. Метод Regula falsi – это другой метод, который аппроксимирует функцию многочленом второй степени, но использует первую производную в двух точках, а не первую и вторую производные в одной точке. Если метод запущен достаточно близко к невырожденному локальному минимуму, то он имеет сверхлинейную сходимость. Cubic fit аппроксимирует функцию многочленом третьей степени, используя как значения функции, так и её производную в последних двух точках. Если метод запущен достаточно близко к невырожденному локальному минимуму, то он имеет квадратичную сходимость. Методы подбора кривой обладают сверхлинейной сходимостью при запуске достаточно близко к локальному минимуму, но в противном случае могут расходиться. Защищённые методы подбора кривой одновременно выполняют метод линейной сходимости параллельно с методом подбора кривой. Они проверяют на каждой итерации, достаточно ли близка точка, найденная методом подбора кривой, к интервалу, поддерживаемому защищённым методом; если это не так, то защищённый метод используется для вычисления следующей итерации.

Преодоление местных минимумов

Как и другие методы оптимизации, метод поиска вдоль линии может быть объединен с имитацией отжига, чтобы позволить ему преодолевать некоторые локальные минимумы.