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

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

Многие методы, используемые в решателях 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, является или направлением отрицательного искривления или аппроксимированным (tol средства управления как аппроксимированный) решение системы Ньютона 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 может быть сделан столь же маленьким в значении как требуется путем увеличения точности поиска строки.