Документация

Методы доверительной области для нелинейной минимизации

Многие методы, используемые в решателях Optimization Toolbox™, основаны на доверительных областях, простой все же мощной концепции в оптимизации.

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

Текущая точка обновляется, чтобы быть x + s если f (x + s) < f (x); в противном случае текущая точка остается неизменной, и N, область доверия, уменьшается, и испытательный расчет шага повторяется.

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

В стандартном методе доверительной области ([48]), квадратичное приближение q задан первыми двумя сроками приближения Тейлора к F в x; окружение N является обычно сферическим или эллипсоидальным в форме. Математически подпроблема доверительной области обычно утверждается

где g является градиентом f в текущей точке x, H является матрицей Гессиана (симметрическая матрица вторых производных), D является диагональной матрицей масштабирования, Δ является положительной скалярной величиной и ∥. ∥ является 2-нормой. Хорошие алгоритмы существуют для решения уравнения 2 (см. [48]); такие алгоритмы обычно включают расчет всех собственных значений H, и процесс Ньютона применился к характеристическому уравнению

Такие алгоритмы предоставляют точное решение уравнения 2. Однако они требуют времени, пропорционального нескольким факторизациям H. Поэтому для крупномасштабных проблем другой подход необходим. Несколько приближений и эвристических стратегий, на основе уравнения 2, были предложены в литературе ([42] и [50]). Подход приближения, сопровождаемый в решателях Optimization Toolbox, должен ограничить подпроблему доверительной области двумерным подпространством S ([39] и [42]). Однажды подпространство S был вычислен, работа, чтобы решить уравнение 2 тривиальна, даже если полная информация о собственном значении/собственном векторе необходима (поскольку в подпространстве, проблема только двумерна). Доминирующая работа теперь переключила к определению подпространства.

Двумерное подпространство S определяется при помощи предобусловленного процесса метода сопряженных градиентов, описанного ниже. Решатель задает S как линейный пробел, заполненный s ₁ и s ₂, где s ₁ является в направлении градиента g, и s ₂ является любой аппроксимированным направлением Ньютона, т.е. решением

или направление отрицательной кривизны,

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

Эскиз безусловной минимизации с помощью идей доверительной области теперь легко дать:

Эти четыре шага повторяются до сходимости. Размерность доверительной области Δ настроена согласно стандартным правилам. В частности, это уменьшено, если испытательный шаг не принят, т.е. f (x + s) ≥ f (x). См. [46] и [49] для обсуждения этого аспекта.

Решатели Optimization Toolbox обрабатывают несколько важных особых случаев f со специализированными функциями: нелинейный метод наименьших квадратов, квадратичные функции и линейный метод наименьших квадратов. Однако базовые алгоритмические идеи эквивалентны для общего случая. Эти особые случаи обсуждены в более поздних разделах.

Предобусловленный метод сопряженных градиентов

Популярным способом решить большие, симметричные, положительные определенные системы линейных уравнений Hp = –g является метод Предобусловленных методов сопряженных градиентов (PCG). Этот итерационный подход требует способности вычислить матричные векторные произведения формы H·v, где v является произвольным вектором. Симметричный положительный определенный матричный M является предварительным формирователем для H. Таким образом, M = C ², где C ^–1HC–1 является хорошо подготовленной матрицей или матрицей с кластеризованными собственными значениями.

В контексте минимизации можно принять, что матрица Гессиана H симметрична. Однако H, как гарантируют, будет положителен определенный только в окружении сильного минимизатора. PCG алгоритма выходит, когда он сталкивается с направлением отрицательных (или нуль) искривление, то есть, ^dTHd ≤ 0. PCG направление выхода p является или направлением отрицательной кривизны или приближенным решением системы Ньютона Hp = –g. В любом случае p помогает задать двумерное подпространство, используемое в подходе доверительной области, обсужденном в Методах Доверительной области для Нелинейной Минимизации.

Основы оптимизации без ограничений

Несмотря на то, что широкий спектр методов существует для оптимизации без ограничений, методы могут быть широко категоризированы в терминах производной информации или нет, используются. Методы поиска, которые используют только вычисления функции (например, симплексный поиск Nelder и Mead [30]) наиболее подходят для проблем, которые не являются гладкими или имеют много разрывов. Градиентные методы обычно более эффективны, когда функция, которая будет минимизирована, непрерывна в ее первой производной. Методы высшего порядка, такие как метод Ньютона, только действительно подходят, когда информация второго порядка с готовностью и легко вычисляется, потому что вычисление информации второго порядка, с помощью числового дифференцирования, является в вычислительном отношении дорогим.

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

Минимум этой функции в x = [1,1], где f (x) = 0. Контурная карта этой функции показана на рисунке ниже, наряду с путем к решению к минимуму для реализации наискорейшего спуска, запускающейся в точке [-1.9,2]. Оптимизация была отключена после 1 000 итераций, все еще значительное расстояние от минимума. Черные области - то, где метод постоянно делает зигзаги с одной стороны оврага другому. Обратите внимание на то, что к центру графика, много больших шагов сделаны, когда точка приземляется точно в центре оврага.

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

Для большего количества полного описания этого рисунка, включая скрипты, которые генерируют итеративные точки, смотрите Банановую Минимизацию Функции.

Приближенные методы ньютона

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

где матрица Гессиана, H, является положительной определенной симметрической матрицей, c является постоянным вектором, и b является константой. Оптимальное решение для этой проблемы происходит, когда частные производные x переходят к нулю, т.е.

Точка оптимального решения, x*, может быть записана как

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

Большое количество методов обновления Гессиана было разработано. Однако формула Broyden [3], Флетчер [12], Goldfarb [20] и Shanno [37] (BFGS), как думают, является самой эффективной для использования в методе общего назначения.

Формула, данная BFGS,

где

Как начальная точка, H ₀ может быть установлен в любую симметричную положительную определенную матрицу, например, единичная матрица I. Чтобы избежать инверсии Гессиана H, можно вывести метод обновления, который избегает прямой инверсии H при помощи формулы, которая делает приближение обратного Гессиана H ^–1 при каждом обновлении. Известная процедура является формулой DFP Davidon [7], Флетчера и Пауэлла [14]. Это использует ту же формулу в качестве метода BFGS (уравнение 9) за исключением того, что _qk заменяют _sk.

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

В каждой главной итерации, k, поиск линии выполняется в направлении

Приближенный метод ньютона проиллюстрирован путем к решению на функции Розенброка в рисунке 6-2, Методе BFGS на Функции Розенброка. Метод может следовать за формой оврага и сходится к минимуму после 140 вычислений функции с помощью только градиенты конечной разности.

Для большего количества полного описания этого рисунка, включая скрипты, которые генерируют итеративные точки, смотрите Банановую Минимизацию Функции.

Поиск линии

Поиск линии является методом поиска, который используется в качестве части большего алгоритма оптимизации. На каждом шаге основного алгоритма метод поиска линии ищет вдоль линии, содержащей текущую точку, _xk, параллельный поисковому направлению, которое является вектором, определенным основным алгоритмом. Таким образом, метод находит, что следующие выполняют итерации x _{k +1} из формы

где _xk обозначает, что ток выполняет итерации, _dk является поисковым направлением, и α* является скалярным параметром длины шага.

Метод поиска линии пытается уменьшить целевую функцию вдоль линии _xk + α *_dk путем повторной минимизации моделей полиномиальной интерполяции целевой функции. Процедура поиска линии имеет два основных шага:

Получившаяся длина шага α удовлетворяет условиям Вольфа:

где c ₁ и c ₂ является константами с 0 <c ₁ <c ₂ <1.

Первое условие (уравнение 12) требует, чтобы _αk достаточно уменьшил целевую функцию. Второе условие (уравнение 13) гарантирует, что длина шага не слишком мала. Точки, которые удовлетворяют обоим условиям (Уравнение 12 и уравнение 13) называются приемлемыми точками.

Метод поиска линии является реализацией алгоритма, описанного в Разделе 2-6 из [13]. См. также [31] для получения дополнительной информации о поиске линии.

Обновление гессиана

Многие оптимизационные функции определяют направление поиска путем обновления матрицы Гессиана в каждой итерации, использования метода BFGS (уравнение 9). Функциональный fminunc также предоставляет возможность использовать метод DFP, данный в Приближенных методах ньютона (установите HessUpdate к 'dfp' в options выбрать метод DFP). Гессиан, H, всегда обеспечивается, чтобы быть положителен определенный так, чтобы направление поиска, d, всегда было в направлении спуска. Это означает, что для некоторого произвольно небольшого шага α в направлении d, целевая функция уменьшается в величине. Вы достигаете положительной определенности H путем гарантирования, что H инициализируется, чтобы быть положителен определенный и после этого $$q_k^T{s}_k$$ (от уравнения 14), всегда положительно. Термин $$q_k^T{s}_k$$ продукт параметра длины шага поиска линии _αk и комбинация поискового направления d с прошлыми и настоящими оценками градиента,

Вы всегда достигаете условия это $$q_k^T{s}_k$$ положительно путем выполнения достаточно точного поиска линии. Это вызвано тем, что поисковое направление, d, является направлением спуска, так, чтобы _αk и отрицательный градиент – ∇f (_xk) ^Td были всегда положительны. Таким образом возможный отрицательный термин – ∇f (x _{k +1}) ^Td может быть сделан столь же маленьким в величине как требуется путем увеличения точности поиска линии.