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

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

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

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

Философия позади этого выбора 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 алгоритма выходит, когда он сталкивается с направлением отрицательных (или нуль) искривление, то есть, d^THD ≤ 0. PCG направление выхода p является или направлением отрицательной кривизны или приближенным решением системы Ньютона Hp = –g. В любом случае p помогает задать двумерное подпространство, используемое в подходе доверительной области, обсужденном в Методах Доверительной области для Нелинейной Минимизации.

Линейные ограничения равенства

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

Общее линейное равенство ограничило проблему минимизации, может быть записан

где A является m-by-n матрица (m ≤ n). Некоторые решатели Optimization Toolbox предварительно обрабатывают A, чтобы удалить строгие линейные зависимости с помощью метода на основе LU-факторизации A^T [46]. Здесь A принят, чтобы быть ранга m.

Метод, используемый, чтобы решить  уравнение 5, отличается от неограниченного подхода двумя значительными способами. Во-первых, начальная допустимая точка x ₀ вычисляется, с помощью разреженного шага наименьших квадратов, так, чтобы Ax ₀ = b. Во-вторых, Алгоритм, PCG заменяется Уменьшаемыми предобусловленными методами сопряженных градиентов (RPCG), видят [46], для того, чтобы вычислить аппроксимированный уменьшаемый шаг Ньютона (или направление отрицательной кривизны на пустом пробеле A). Ключевой шаг линейной алгебры включает системы решения формы

где $$\tilde{A}$$ аппроксимирует A (маленькие ненули A обнуляются, если ранг не потерян), и C является разреженным симметричным положительно-определенным приближением к H, т.е. C = H. См. [46] для получения дополнительной информации.

Ограничения поля

Ограниченная проблема поля имеет форму

где l является вектором из нижних границ, и u является вектором из верхних границ. Некоторые (или все) компонентов l могут быть равны – ∞, и некоторые (или все) компонентов u могут быть равны ∞. Метод генерирует последовательность строго допустимых точек. Два метода используются, чтобы обеспечить выполнимость при достижении устойчивого поведения сходимости. Во-первых, масштабированный модифицированный шаг Ньютона заменяет неограниченный шаг Ньютона (чтобы задать двумерное подпространство S). Во-вторых, отражения используются, чтобы увеличить размер шага.

Масштабированный модифицированный шаг Ньютона является результатом исследования необходимых условий Куна-Такера для  уравнения 7,

где

и векторный v (x) задан ниже для каждого 1 ≤ i ≤ n:

Нелинейное системное  уравнение 8 не дифференцируемо везде. Недифференцируемость происходит когда _vi = 0. Можно избежать таких точек путем поддержания строгой выполнимости, т.е. ограничения l < x < u.

Масштабированный модифицированный шаг Ньютона _sk для нелинейной системы уравнений, данной  уравнением 8, задан как решение линейной системы

в k th итерация, где

и

Здесь J^v играет роль якобиана |v |. Каждый диагональный компонент диагональной матрицы J^v равняется 0, –1, или 1. Если все компоненты l и u конечны, J^v = diag (знак (g)). В точке, где _gi = 0, _vi не может быть дифференцируемым. $$J_{ii}^v=0$$ задан в такой точке. Недифференцируемость этого типа не является поводом для беспокойства, потому что для такого компонента это не значительно, какое значение _vi принимает. Далее, |_vi | все еще будет прерывисто в этой точке, но функции _|vi| · _gi непрерывен.

Во-вторых, отражения используются, чтобы увеличить размер шага. (Один) отражательный шаг определяется следующим образом. Учитывая шаг p, который пересекает связанное ограничение, считает первое связанное ограничение пересеченным p; примите, что это - i th связанное ограничение (или i th верхний или i th нижняя граница). Затем отражательный шаг p^R = p кроме i th компонент, где p^R_{i =}  –_pi.

Введение

В ограниченной оптимизации общая цель состоит в том, чтобы преобразовать проблему в более легкую подпроблему, которая может затем решаться и использоваться в качестве базиса итеративного процесса. Характеристика большого класса ранних методов является переводом ограниченной проблемы к основной неограниченной проблеме при помощи функции штрафа для ограничений, которые являются рядом или вне границы ограничений. Таким образом ограниченная задача решена с помощью последовательности параметрической оптимизации без ограничений, которая в пределе (последовательности) сходится к ограниченной проблеме. Эти методы теперь рассматриваются относительно неэффективными и были заменены методами, которые фокусировались на решении уравнений Karush-Kuhn-Tucker (KKT). Уравнения KKT являются необходимыми условиями для оптимальности для ограниченной задачи оптимизации. Если проблемой является так называемая проблема выпуклого программирования, то есть, f (x) и _Gi (x), i = 1..., m, является выпуклыми функциями, то уравнения KKT и необходимы и достаточны для точки глобального решения.

Что касается GP  (уравнение 1), уравнения Куна-Такера могут быть утверждены как

в дополнение к исходным ограничениям в  уравнении 1.

Первое уравнение описывает отмену градиентов между целевой функцией и активными ограничениями в точке решения. Для градиентов, которые будут отменены, множители Лагранжа (_λi, i = 1..., m) необходимы, чтобы сбалансировать отклонения в величине ограничительных градиентов и целевой функции. Поскольку только активные ограничения включены в эту операцию отмены, ограничения, которые не активны, не должны быть включены в эту операцию и так даны множители Лагранжа, равные 0. Это утверждается неявно в последних двух уравнениях Куна-Такера.

Решение уравнений KKT формирует базис ко многим алгоритмам нелинейного программирования. Эти алгоритмы пытаются вычислить множители Лагранжа непосредственно. Ограниченные приближенные методы ньютона гарантируют сверхлинейную сходимость путем накопления информации второго порядка относительно уравнений KKT с помощью процедуры обновления квазиньютона. Эти методы обычно упоминаются как методы Последовательного квадратичного программирования (SQP), поскольку подпроблема QP решена в каждой главной итерации (также известный как Итеративное Квадратичное программирование, Рекурсивное Квадратичное программирование и Ограниченные Переменные Метрические методы).

'active-set' алгоритм не является крупномасштабным алгоритмом; смотрите Крупномасштабный по сравнению с Алгоритмами Средней шкалы.

Последовательное квадратичное программирование (SQP)

Методы SQP представляют состояние в методах нелинейного программирования. Щиттковский [36], например, реализовал и протестировал версию, которая превосходит любой испытанный метод по характеристикам в терминах КПД, точности и процента успешных решений, по большому количеству тестовых задач.

На основе работы Четырехрядных ячменей [1], ханьцы [22], и Пауэлл ([32] и [33]), метод позволяет вам тесно методу имитатора Ньютона для ограниченной оптимизации, как сделан для оптимизации без ограничений. В каждой главной итерации приближение сделано из Гессиана лагранжевой функции с помощью метода обновления квазиньютона. Это затем используется, чтобы сгенерировать подпроблему QP, решение которой используется, чтобы сформировать поисковое направление для процедуры поиска линии. Обзор SQP найден во Флетчере [13], Джилл и др. [19], Пауэлл [35], и Щиттковский [23]. Общий метод, однако, утверждается здесь.

Учитывая описание проблемы в GP  (уравнение 1) основная идея является формулировкой подпроблемы QP на основе квадратичного приближения лагранжевой функции.

Здесь вы упрощаете  уравнение 1 путем принятия, что связанные ограничения были описаны как ограничения неравенства. Вы получаете подпроблему QP путем линеаризации нелинейных ограничений.

Подпроблема квадратичного программирования (QP)

Эта подпроблема может быть решена с помощью любого алгоритма QP (см., например, Решение для Квадратичного программирования). Решение используется, чтобы сформироваться, новое выполняют итерации

_k α параметра длины шага определяется соответствующей процедурой поиска линии так, чтобы достаточное уменьшение в оценочной функции было получено (см. Обновление Матрицы Гессиана). Матричный H _k является положительным определенным приближением матрицы Гессиана лагранжевой функции  (уравнение 13). H _k может быть обновлен любым из приближенных методов ньютона, несмотря на то, что метод BFGS (см. Обновление Матрицы Гессиана), кажется, является самым популярным.

Нелинейно ограниченная задача может часто решаться в меньшем количестве итераций, чем неограниченная проблема с помощью SQP. Одна из причин этого - то, что из-за пределов на выполнимой области оптимизатор может сделать обоснованные решения относительно направлений длины шага и поиска.

Рассмотрите функцию Розенброка с дополнительным нелинейным ограничением неравенства, g (x),

Это было решено реализацией SQP в 96 итерациях по сравнению с 140 для неограниченного случая. Рисунок 5-3, Метод SQP на Функции Нелинейно Принужденного Розенброка показывает, что путь к решению указывает x = [0.9072,0.8228] запуск в x = [-1.9 2.0].

Реализация SQP

Реализация SQP состоит из трех основных этапов, которые обсуждены кратко в следующих подразделах:

• Обновление матрицы гессиана

• Решение для квадратичного программирования

• Инициализация

• Поиск линии и оценочная функция

Обновление Матрицы Гессиана.  В каждой главной итерации положительное определенное приближение квазиньютона Гессиана лагранжевой функции, H, вычисляется с помощью метода BFGS, где _λi, i = 1..., m, является оценкой множителей Лагранжа.

где

Пауэлл [33] рекомендует сохранить Гессиан положительным определенный даже при том, что это может быть положительно неопределенный в точке решения. Положительный определенный Гессиан обеспечен, обеспечив $$q_k^T{s}_k$$ положительно при каждом обновлении и что H инициализируется положительной определенной матрицей. Когда $$q_k^T{s}_k$$ не положительно, _qk изменяется на поэлементно базис так, чтобы $$q_k^T{s}_k>0$$. Общая цель этой модификации состоит в том, чтобы исказить элементы _qk, которые способствуют положительному определенному обновлению, как можно меньше. Поэтому в начальной фазе модификации, самый отрицательный элемент _qk *_sk неоднократно делится на два. Эта процедура продолжена до $$q_k^T{s}_k$$ больше или равен маленькому отрицательному допуску. Если, после этой процедуры, $$q_k^T{s}_k$$ все еще не положительно, измените _qk путем добавления векторного v, умноженного на постоянный скалярный w, то есть,

где

и увеличивайте w систематически до $$q_k^T{s}_k$$ становится положительным.

Функции fmincon, fminimax, fgoalattain, и fseminf все использование SQP. Если Display установлен в 'iter' в options, затем различная информация дана, такие как значения функции и максимальное нарушение ограничений. Когда Гессиан должен быть изменен с помощью первой фазы предыдущей процедуры, чтобы сохранить его положительным определенный, затем Hessian modified отображен. Если Гессиан должен быть изменен снова с помощью второй фазы подхода, описанного выше, то Hessian modified twice отображен. Когда подпроблема QP неосуществима, затем infeasible отображен. Такие отображения обычно являются не поводом для беспокойства, но указывают, что проблема очень нелинейна и что сходимость может занять больше времени чем обычно. Иногда сообщение no update отображен, указав на это $$q_k^T{s}_k$$ почти нуль. Это может быть индикацией, что настройка задач является неправильной, или вы пытаетесь минимизировать ненепрерывную функцию.

Решение для Квадратичного программирования.  В каждой главной итерации метода SQP решена задача QP следующей формы, где _Ai относится к iстрока th m-by-n матричный A.

Метод, используемый в функциях Optimization Toolbox, является активной стратегией набора (также известный как метод проекции) похожий на того из Джилла и др., описанный в [18] и [17]. Это было изменено и для Линейного программирования (LP) и для проблем Квадратичного программирования (QP).

Процедура решения включает две фазы. Первая фаза включает вычисление допустимой точки (если вы существуете). Вторая фаза включает генерацию итеративной последовательности допустимых точек, которые сходятся к решению. В этом методе активный набор, $${\overline{A}}_k$$, обеспечен, который оценка активных ограничений (i.e., те, которые находятся на границах ограничений) в точке решения. Фактически все алгоритмы QP являются активными методами установки. Эта мысль подчеркнута, потому что там существуют много различных методов, которые очень похожи в структуре, но которые описаны в широко различных терминах.

$${\overline{A}}_k$$ обновляется в каждой итерации k, и это используется, чтобы сформировать базис для поискового направления $${\widehat{d}}_k$$. Ограничения равенства всегда остаются в активном наборе $${\overline{A}}_k$$. Обозначение для переменной $${\widehat{d}}_k$$ используется здесь, чтобы отличить его от _dk в главных итерациях метода SQP. Поисковое направление $${\widehat{d}}_k$$ вычисляется и минимизирует целевую функцию при оставлении на любых активных границах ограничений. Выполнимое подпространство для $${\widehat{d}}_k$$ формируется из базиса _Zk, столбцы которого являются ортогональными к оценке активного набора $${\overline{A}}_k$$ т.е. . $${\overline{A}}_k{Z}_k=0$$). Таким образом поисковое направление, которое формируется из линейного суммирования любой комбинации столбцов _Zk, как гарантируют, останется на контурах активных ограничений.

Матричный _Zk формируется из последнего m – столбцы l разложения QR матрицы $${\overline{A}}_k^T$$, где l является количеством активных ограничений и l < m. Таким образом, _Zk дают

где

Если _Zk найден, новое поисковое направление $${\widehat{d}}_k$$ разыскивается, который минимизирует q (d) где $${\widehat{d}}_k$$ находится на пустом пробеле активных ограничений. Таким образом, $${\widehat{d}}_k$$ линейная комбинация столбцов _Zk: $${\widehat{d}}_k=Z_{k}p$$ для некоторого векторного p.

Затем, если вы просматриваете квадратичное в зависимости от p путем замены $${\widehat{d}}_k$$, вы имеете

Дифференциация этого относительно выражений p

∇q (p) упоминается как спроектированный градиент квадратичной функции, потому что это - градиент, спроектированный в подпространстве, заданном _Zk. Термин $$Z_k^{T}H{Z}_k$$ называется спроектированным Гессианом. При принятии матрицы Гессиана, H положителен определенный (который имеет место в этой реализации SQP), затем происходит минимум функционального q (p) в подпространстве, заданном _Zk, когда ∇q (p) = 0, который является решением системы линейных уравнений

Шаг затем сделан формы

В каждой итерации, из-за квадратичной природы целевой функции, существует только два варианта длины шага α. Шаг единицы вперед $${\widehat{d}}_k$$ точный шаг к минимуму функции, ограниченной пустым пробелом $${\overline{A}}_k$$. Если такой шаг может быть сделан без нарушения ограничений, то это - решение QP  (уравнение 18). В противном случае, шаг вперед $${\widehat{d}}_k$$ к самому близкому ограничению меньше единицы, и новое ограничение включено в активный набор в следующей итерации. Расстояние до границ ограничений в любом направлении $${\widehat{d}}_k$$ дают

который задан для ограничений не в активном наборе, и где направление $${\widehat{d}}_k$$ находится к границе ограничений, i.e., $$A_i{\widehat{d}}_k>0,i=1,\mathrm{...},m$$.

Когда n, независимые ограничения включены в активный набор, без местоположения минимума, множителей Лагранжа, _λk, вычисляется, которые удовлетворяют несингулярному набору линейных уравнений

Если все элементы _λk положительны, _xk является оптимальным решением QP  (уравнение 18). Однако, если какой-либо компонент _λk отрицателен, и компонент не соответствует ограничению равенства, то соответствующий элемент удален из активного набора, и новое выполняют итерации, разыскивается.

Инициализация.  Алгоритм требует, чтобы допустимая точка запустилась. Если текущая точка из метода SQP не выполнима, то можно найти точку путем решения задачи линейного программирования

Обозначение _Ai указывает на i th строка матричного A. Можно найти допустимую точку (если вы существуете) к  уравнению 26 установкой x к значению, которое удовлетворяет ограничениям равенства. Можно определить это значение путем решения под - или сверхопределенный набор линейных уравнений, сформированных из набора ограничений равенства. Если существует решение этой проблемы, то слабая переменная γ установлена в максимальное ограничение неравенства в этой точке.

Можно изменить предыдущий алгоритм QP для проблем LP путем установки поискового направления на направление наискорейшего спуска в каждой итерации, где _gk является градиентом целевой функции (равный коэффициентам линейной целевой функции).

Если допустимая точка найдена с помощью предыдущего метода LP, основная фаза QP вводится. Поисковое направление $${\widehat{d}}_k$$ инициализируется поисковым направлением $${\widehat{d}}_1$$ найденный от решения набора линейных уравнений

где _gk является градиентом целевой функции при токе, выполняют итерации _xk (т.е. _Hxk + c).

Если возможное решение не найдено для проблемы QP, направления поиска основной стандартной программы SQP $${\widehat{d}}_k$$ взят в качестве того, который минимизирует γ.

Поиск линии и Оценочная функция.  Решение подпроблемы QP производит векторный _dk, который используется, чтобы сформироваться, новое выполняют итерации

_αk параметра длины шага определяется для того, чтобы произвести достаточное уменьшение в оценочной функции. Оценочная функция, используемая ханьцами [22] и Пауэлл [33] из следующей формы, используется в этой реализации.

Пауэлл рекомендует установить параметр штрафа

Это позволяет позитивный вклад от ограничений, которые неактивны в решении QP, но были недавно активны. В этой реализации параметр штрафа _ri первоначально установлен в

где $$\Vert \Vert$$ представляет Евклидову норму.

Это гарантирует большие вклады в параметр штрафа от ограничений с меньшими градиентами, которые имели бы место для активных ограничений в точке решения.

Строгая выполнимость относительно границ

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

Робастность, чтобы не удвоить результаты

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

Пересмотренные стандартные программы линейной алгебры

sqp алгоритм использует различный набор стандартных программ линейной алгебры, чтобы решить подпроблему квадратичного программирования,  уравнение 14. Эти стандартные программы более эффективны и в использовании памяти и в скорости, чем active-set стандартные программы.

Переформулированные стандартные программы выполнимости

sqp алгоритм имеет два новых подхода к решению  уравнения 14, когда ограничениям не удовлетворяют.

Барьерная функция

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

Аппроксимированное  уравнение 34 задач является последовательностью ограниченных проблем равенства. Их легче решить, чем исходное ограниченное неравенством  уравнение 33 задач.

Чтобы решить аппроксимированную задачу, алгоритм использует один из двух основных типов шагов в каждой итерации:

По умолчанию алгоритм сначала пытается сделать прямой шаг. Если это не может, это делать попытку шага CG. Один случай, где это не делает прямой шаг, - когда аппроксимированная проблема не локально выпукла около тока, выполняют итерации.

В каждой итерации алгоритм уменьшает merit function, такой как

Если или целевая функция или нелинейная ограничительная функция возвращают комплексное число, NaN, Inf или ошибку в выполнить итерации _xj, алгоритм отклоняет _xj. Отклонение оказывает то же влияние, как будто оценочная функция не уменьшилась достаточно: алгоритм затем делает попытку различного, более короткого шага. Перенесите любой код, который может ошибка в try-catch:

function val = userFcn(x)
try
    val = ... % code that can error
catch
    val = NaN;
end

Цель и ограничения должны уступить соответствующий (double) значения в начальной точке.

Прямой шаг

Следующие переменные используются в определении прямого шага:

 Уравнение 38 задает прямой шаг (Δx, Δs):

Это уравнение прибывает непосредственно из попытки решить  уравнение 2 и  уравнение 3 с помощью линеаризовавшей функции Лагранжа.

Можно симметрировать уравнение путем предварительного умножения второй переменной Δs на S^–1:

Для того, чтобы решить это уравнение для (Δx, Δs), алгоритм делает LDL-разложение матрицы. (См. Пример 3 — Структура D в MATLAB^® ldl страница ссылки на функцию.) Это - наиболее в вычислительном отношении дорогой шаг. Одним результатом этой факторизации является определение того, является ли спроектированный Гессиан положительным определенный или нет; в противном случае алгоритм использует шаг метода сопряженных градиентов, описанный на Шаге Метода сопряженных градиентов.

Обновите параметр барьера

Для аппроксимированного  уравнения 34 задач, чтобы приблизиться к исходной проблеме, параметр барьера μ должен уменьшиться к 0, в то время как итерации продолжают. Алгоритм имеет две опции обновления параметра барьера, которые вы задаете использование BarrierParamUpdate опция: 'monotone' (значение по умолчанию) и 'predictor-corrector'.

'monotone' опция уменьшает параметр μ на коэффициент 1/100 или 1/5, когда аппроксимированная задача решена с достаточной точностью в предыдущей итерации. Опция использует фактор 1/100, когда алгоритм берет только одну или две итерации, чтобы достигнуть достаточной точности и использует 1/5 в противном случае. Мерой точности является следующий тест, который определяет, меньше ли размер всех терминов на правой стороне  уравнения 38 μ:

'predictor-corrector' алгоритм для обновления параметра барьера μ похож на линейный алгоритм Корректора Предиктора программирования.

Шаги корректора предиктора могут ускорить существующий Fiacco-McCormick (монотонный) подход путем корректировки для ошибки линеаризации на шагах Ньютона. Эффекты алгоритма корректора предиктора являются двукратными: это часто улучшает направления шага и одновременно обновляется, параметр барьера адаптивно сосредотачивающимся параметром σ, чтобы поощрить выполняет итерации, чтобы следовать за центральным путем. Смотрите Носедэла и Райта [31] обсуждение шагов корректора предиктора для линейных программ, чтобы изучить, почему центральный путь позволяет большие размеры шага и, следовательно, более быструю сходимость.

Шаг предиктора использует линеаризовавший шаг с μ = 0, означая без барьерной функции:

Задайте _ɑs и _ɑλ, чтобы быть самыми большими размерами шага, которые не нарушают ограничения неотрицательности.

Теперь вычислите взаимозависимость из шага предиктора.

где m является количеством ограничений.

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

Чтобы откорректировать квадратичную ошибку, решите линейную систему для направления шага корректора.

Второй шаг корректора является сосредотачивающимся шагом. Сосредотачивающаяся коррекция основана на переменной σ на правой стороне уравнения

Здесь, σ задан как

где _μP задан в  уравнении 39 уравнения, и $$\mu =s^T\lambda /m$$.

Чтобы препятствовать тому, чтобы параметр барьера уменьшился слишком быстро, потенциально дестабилизировав алгоритм, алгоритм сохраняет сосредотачивающийся параметр σ выше 1/100. Это действие заставляет параметр барьера μ уменьшаться не больше, чем фактором 1/100.

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

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

Шаг метода сопряженных градиентов

Подход метода сопряженных градиентов к решению аппроксимированного  уравнения 34 задач похож на другие вычисления метода сопряженных градиентов. В этом случае алгоритм настраивает и x и s, сохраняя слаксы s положительный. Подход должен минимизировать квадратичное приближение к аппроксимированной проблеме в доверительной области согласно линеаризовавшим ограничениям.

А именно, позвольте R обозначить радиус доверительной области и позволить другим переменным быть заданными как на Прямом Шаге. Алгоритм получает множители Лагранжа путем аппроксимированного решения уравнений KKT

в наименьших квадратах распознаются согласно λ, являющемуся положительным. Затем это получает шаг (Δx, Δs), чтобы приблизительно решить

Режим выполнимости

Когда EnableFeasibilityMode опцией является true и итерации не уменьшают недопустимость достаточно быстро, алгоритм переключается на режим выполнимости. Этот переключатель происходит после того, как алгоритм не удается уменьшить недопустимость в режиме normal mode, и затем перестал работать снова после переключения на режим метода сопряженных градиентов. Поэтому для лучшей эффективности, когда решатель не найдет возможное решение без режима выполнимости, установите SubproblemAlgorithm к 'cg' при использовании режима выполнимости. Выполнение так избегает бесплодного поиска в режиме normal mode.

Алгоритм режима выполнимости основан на Nocedal, Öztoprak и Вальсе [1]. Алгоритм игнорирует целевую функцию и вместо этого пытается минимизировать недопустимость, заданную как сумма положительных частей функций ограничения неравенства и абсолютного значения функций ограничения равенства. В терминах релаксационных переменных $$r=\left[r_I,r_e^{+},r_e^{-}\right]$$, которые соответствуют неравенствам, положительным частям равенств и отрицательным частям равенств, соответственно, проблема

удовлетворяющее ограничениям

Чтобы решить расслабленную задачу, программное обеспечение использует формулировку внутренней точки с логарифмической барьерной функцией и слаксами $$s=\left[s_I,s_R,s_e^{+},s_e^{-}\right]$$ минимизировать

удовлетворяющее ограничениям

Процесс решения для расслабленной проблемы начинается с μ, инициализированного к текущему значению параметров барьера. Слабая переменная _sI инициализируется к текущему неравенству слабое значение, наследованное от основного режима. Переменные r инициализируются к

Остающиеся слаксы инициализируются к

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

Алгоритм режима выполнимости заканчивается, когда он уменьшает недопустимость на коэффициент 10. Когда режим выполнимости заканчивается, алгоритм передает переменные x и _sI основному алгоритму и отбрасывает другие слабые переменные и релаксационные переменные r.

Опции алгоритма внутренней точки

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

Поскольку полный список опций видит Алгоритм Внутренней точки в fmincon options.

Формулировка задачи fseminf

fseminf задачи оптимизации адресов с дополнительными типами ограничений по сравнению с обращенными fmincon. Формулировка fmincon

таким образом, что c (x) ≤ 0, ceq (x) = 0, A·x ≤ b, Aeq·x = beq и l ≤ x ≤ u.

fseminf добавляет следующий набор полубесконечных ограничений к уже данным. Для _wj в одном - или двумерный ограниченный интервал или прямоугольник _Ij, для вектора из непрерывных функций K (x, w), ограничения

Термин “размерность” fseminf проблема означает максимальную размерность ограничительного множества I: 1, если весь _Ij является интервалами, и 2, если по крайней мере один _Ij является прямоугольником. Размер вектора из K не вводит в эту концепцию размерности.

Причина это называется полубесконечным программированием, состоит в том, что существует конечное число переменных (x и _wj), но бесконечное число ограничений. Это вызвано тем, что ограничениями на x является по набору непрерывных интервалов или прямоугольников _Ij, который содержит бесконечное число точек, таким образом, существует бесконечное число ограничений: _Kj (x, _wj) ≤ 0 для бесконечного числа точек _wj.

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

где |K | является количеством компонентов векторного K; т.е. количество полубесконечных ограничительных функций. Для фиксированного x это - обычная максимизация на ограниченных интервалах или прямоугольниках.

fseminf далее упрощает проблему путем создания кусочно-квадратичных или кубических приближений _κj (x, _wj) к функциям _Kj (x, _wj), для каждого x, который посещает решатель. fseminf считает только максимумы функции интерполяции _κj (x, _wj), вместо _Kj (x, _wj), в  уравнении 42. Это уменьшает исходную проблему, минимизируя полубесконечно ограниченную функцию, к проблеме с конечным числом ограничений.

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

Начальная буква, располагающая с интервалами s |K |-2 матрица. j th строка s представляет интервал для граничения с точками выборки для ограничительной функции _Kj. Если _Kj зависит от одномерного _wj, установите   s(j,2) = 0. fseminf обновляет матричный s в последующих итерациях.

fseminf использует матричный s сгенерировать выборку указывает w, который она затем использует, чтобы создать приближение _κj (x, _wj). Ваша процедура для генерации w от s должен сохранить те же интервалы или прямоугольники _Ij во время оптимизации.

Пример Создания Точек Выборки.  Рассмотрите задачу с двумя полубесконечными ограничениями, K ₁ и K ₂. K ₁ имеет одномерный w ₁, и K ₂ имеет двумерный w ₂. Следующий код генерирует набор выборки от w ₁ = 2 - 12:

% Initial sampling interval
if isnan(s(1,1))
    s(1,1) = .2;
    s(1,2) = 0;
end

% Sampling set
w1 = 2:s(1,1):12;

fseminf задает s как NaN когда это сначала вызывает вашу ограничительную функцию. Проверка это позволяет вам устанавливать начальный интервал выборки.

Следующий код генерирует набор выборки от w ₂ в квадрате, с каждым компонентом, идущим от 1 до 100, первоначально произведенный чаще в первом компоненте, чем второе:

% Initial sampling interval
if isnan(s(1,1))
   s(2,1) = 0.2;
   s(2,2) = 0.5;
end
 
% Sampling set
w2x = 1:s(2,1):100;
w2y = 1:s(2,2):100;
[wx,wy] = meshgrid(w2x,w2y);

Предыдущие фрагменты кода могут быть упрощены можно следующим образом:

% Initial sampling interval
if isnan(s(1,1))
    s = [0.2 0;0.2 0.5];
end

% Sampling set
w1 = 2:s(1,1):12;
w2x = 1:s(2,1):100;
w2y = 1:s(2,2):100;
[wx,wy] = meshgrid(w2x,w2y);

Алгоритм fseminf

fseminf по существу уменьшает проблему полубесконечного программирования к проблеме, решенной fmincon. fseminf берет следующие шаги, чтобы решить полубесконечные проблемы программирования: