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

Ограниченное определение оптимизации

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

minxf(x)

таким образом, что один или несколько из следующего содержит: c (x) ≤ 0, ceq (x) = 0, A·x ≤ b, Aeq·x = beq, l ≤ x ≤ u. Существует еще больше ограничений, используемых в полубесконечном программировании; см. fseminf Формулировку задачи и Алгоритм.

область Доверия fmincon Отражающий Алгоритм

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

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

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

mins{q(s), sN}.(1)

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

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

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

min{12sTHs+sTg  таким образом , что  DsΔ},(2)

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

1Δ1s=0.

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

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

Hs2=g,(3)

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

s2THs2<0.(4)

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

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

  1. Сформулируйте двумерную подпроблему доверительной области.

  2. Решите  уравнение 2, чтобы определить испытательный шаг s.

  3. Если f (x + s) <f (x), то x = x + s.

  4. Настройте Δ.

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

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

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

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

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

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

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

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

min{f(x)  such that  Ax=b},(5)

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

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

[CA˜TA˜0][st]=[r0],(6)

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

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

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

min{f(x)  such that  lxu},(7)

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

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

(D(x))2g=0,(8)

где

D(x)=diag(|vk|1/2),

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

  • Если gi < 0 и ui < ∞ затем vi = xi – ui

  • Если gi ≥ 0 и li > – ∞ затем vi = xi – li

  • Если gi < 0 и ui = ∞ затем vi = –1

  • Если gi ≥ 0 и li = – ∞ затем vi = 1

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

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

M^DsN=g^(9)

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

g^=D1g=diag(|v|1/2)g,(10)

и

M^=D1HD1+diag(g)Jv.(11)

Здесь Jv играет роль якобиана |v |. Каждый диагональный компонент диагонального матричного Jv равняется 0, –1, или 1. Если все компоненты l и u конечны, Jv = diag (знак (g)). В точке, где gi = 0, vi не может быть дифференцируемым. Jiiv=0 задан в такой точке. Недифференцируемость этого типа не является поводом для беспокойства, потому что для такого компонента это не значительно, какое значение vi принимает. Далее, |vi | все еще будет прерывисто в этой точке, но функции |vi| · gi непрерывен.

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

fmincon Активный Алгоритм Набора

Введение

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

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

f(x*)+i=1mλiGi(x*)=0λiGi(x*)=0,  i=1,...,meλi0,  i=me+1,...,m,(12)

в дополнение к исходным ограничениям в  уравнении 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 на основе квадратичного приближения лагранжевой функции.

L(x,λ)=f(x)+i=1mλigi(x).(13)

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

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

mindn12dTHkd+f(xk)Tdgi(xk)Td+gi(xk)=0,  i=1,...,megi(xk)Td+gi(xk)0,  i=me+1,...,m.(14)

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

x k + 1 = x k + α k d k.

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

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

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

x12+x221.50.(15)

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

Рисунок 6-3, метод SQP на функции нелинейно принужденного Розенброка

Реализация SQP

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

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

Hk+1=Hk+qkqkTqkTskHkskskTHkTskTHksk,(16)

где

sk=xk+1xkqk=(f(xk+1)+i=1mλigi(xk+1))(f(xk)+i=1mλigi(xk)).

Пауэлл [33] рекомендует сохранить Гессиан положительным определенный даже при том, что это может быть положительно неопределенный в точке решения. Положительный определенный Гессиан обеспечен, обеспечив qkTsk положительно при каждом обновлении и что H инициализируется положительной определенной матрицей. Когда qkTsk не положительно, qk изменяется на поэлементно основание так, чтобы qkTsk>0. Общая цель этой модификации состоит в том, чтобы исказить элементы qk, которые способствуют положительному определенному обновлению, как можно меньше. Поэтому в начальной фазе модификации, самый отрицательный элемент qk *sk неоднократно делится на два. Эта процедура продолжена до qkTsk больше или равен маленькому отрицательному допуску. Если, после этой процедуры, qkTsk все еще не положительно, измените qk путем добавления векторного v, умноженного на постоянный скалярный w, то есть,

qk=qk+wv,(17)

где

vi=gi(xk+1)gi(xk+1)gi(xk)gi(xk)           если (qk)iw<0 и (qk)i(sk)i<0, i=1,...,mvi=0  в противном случае,

и увеличивайте w систематически до qkTsk становится положительным.

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

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

mindnq(d)=12dTHd+cTd,Aid=bi,  i=1,...,meAidbi,  i=me+1,...,m.(18)

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

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

A¯k обновляется в каждой итерации k, и это используется, чтобы сформировать основание для поискового направления d^k. Ограничения равенства всегда остаются в активном наборе A¯k. Обозначение для переменной d^k используется здесь, чтобы отличить его от dk в главных итерациях метода SQP. Поисковое направление d^k вычисляется и минимизирует целевую функцию при оставлении на любых активных границах ограничений. Выполнимое подпространство для d^k формируется из основания Zk, столбцы которого являются ортогональными к оценке активного набора A¯k т.е. . A¯kZk=0). Таким образом поисковое направление, которое формируется из линейного суммирования любой комбинации столбцов Zk, как гарантируют, останется на контурах активных ограничений.

Матричный Zk формируется из последнего m – столбцы l разложения QR матрицы A¯kT, где l является количеством активных ограничений и l < m. Таким образом, Zk дают

Zk=Q[:,l+1:m],(19)

где

QTA¯kT=[R0].

Если Zk найден, новое поисковое направление d^k разыскивается, который минимизирует q (d) где d^k находится на пустом пробеле активных ограничений. Таким образом, d^k линейная комбинация столбцов Zk: d^k=Zkp для некоторого векторного p.

Затем, если вы просматриваете квадратичное как функцию p путем замены d^k, вы имеете

q(p)=12pTZkTHZkp+cTZkp.(20)

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

q(p)=ZkTHZkp+ZkTc.(21)

q (p) упоминается как спроектированный градиент квадратичной функции, потому что это - градиент, спроектированный в подпространстве, заданном Zk. Термин ZkTHZk называется спроектированным Гессианом. При принятии матрицы Гессиана, H положителен определенный (который имеет место в этой реализации SQP), затем происходит минимум функционального q (p) в подпространстве, заданном Zk, когда q (p) = 0, который является решением системы линейных уравнений

ZkTHZkp=ZkTc.(22)

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

xk+1=xk+αd^k,  где d^k=Zkp.(23)

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

α=mini{1,...,m}{(Aixkbi)Aid^k},(24)

который задан для ограничений не в активном наборе, и где направление d^k находится к границе ограничений, i.e., Aid^k>0, i=1,...,m.

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

A¯kTλk=c+Hxk.(25)

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

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

minγ, xnγ  таким образом , чтоAix=bi,      i=1,...,meAixγbi,  i=me+1,...,m.(26)

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

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

d^k=ZkZkTgk.(27)

Если допустимая точка найдена с помощью предыдущего метода LP, основная фаза QP вводится. Поисковое направление d^k инициализируется поисковым направлением d^1 найденный от решения набора линейных уравнений

Hd^1=gk,(28)

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

Если возможное решение не найдено для проблемы QP, направления поиска основной стандартной программы SQP d^k взят в качестве того, который минимизирует γ.

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

xk+1=xk+αdk.(29)

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

Ψ(x)=f(x)+i=1merigi(x)+i=me+1mrimax[0,gi(x)].(30)

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

ri=(rk+1)i=maxi{λi,(rk)i+λi2},  i=1,...,m.(31)

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

ri=f(x)gi(x),(32)

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

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

fmincon SQP Алгоритм

sqp алгоритм (и почти идентичный sqp-legacy алгоритм), похоже на active-set алгоритм (для описания, см. fmincon Активный Алгоритм Набора). Основной sqp алгоритм описан в Главе 18 Носедэла и Райта [31].

sqp алгоритм является по существу тем же самым как sqp-legacy алгоритм, но имеет различную реализацию. Обычно, sqp имеет более быстрое время выполнения и меньше использования памяти, чем sqp-legacy.

Наиболее важные различия между sqp и active-set алгоритмы:

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

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

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

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

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

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

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

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

  • sqp алгоритм комбинирует цель и ограничительные функции в оценочную функцию. Алгоритм пытается минимизировать оценочную функцию, удовлетворяющую расслабленным ограничениям. Эта модифицированная проблема может привести к возможному решению. Однако этот подход имеет больше переменных, чем исходная проблема, таким образом, проблемный размер в  увеличениях уравнения 14. Увеличенный размер может замедлить решение подпроблемы. Эти стандартные программы основаны на статьях Spellucci [60] и Тона [61]. sqp алгоритм устанавливает параметр штрафа для  уравнения 30 оценочной функции согласно предложению в [41].

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

Алгоритм Внутренней точки fmincon

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

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

minxf(x),  при ограничениях h(x)=0 и g(x)0.(33)
Для каждого μ> 0, аппроксимированная проблема
minx,sfμ(x,s)=minx,sf(x)μiln(si),  при ограничениях h(x)=0 и g(x)+s=0.(34)
Существует столько же слабых переменных si, сколько существуют ограничения неравенства g. si ограничивается, чтобы быть положительным сохранить ln (si) ограниченный. Когда μ уменьшается к нулю, минимум должен приблизиться к минимуму f. Добавленный логарифмический термин называется barrier function. Этот метод описан в [40], [41], и [51].

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

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

  • direct вступает (x, s). Этот шаг пытается решить уравнения KKT,  уравнение 2 и  уравнение 3, для аппроксимированной проблемы через линейную аппроксимацию. Это также называется Newton step.

  • CG (метод сопряженных градиентов) шаг, с помощью доверительной области.

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

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

fμ(x,s)+ν(h(x),g(x)+s).

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

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

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

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

Прямой шаг

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

  • H обозначает Гессиан функции Лагранжа :

    H=2f(x)+iλi2gi(x)+jλj2hj(x).(35)

  • Jg обозначает якобиан ограничительной функции g.

  • Jh обозначает якобиан ограничительной функции h.

  • S = diag (s).

  • λ обозначает вектор множителей Лагранжа, сопоставленный с ограничениями g

  • Λ = diag (λ).

  • y обозначает вектор множителей Лагранжа, сопоставленный с h.

  • e обозначает вектор из единиц тот же размер как g.

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

[H0JhTJgT0SΛ0SJh0I0JgS0I][ΔxΔsΔyΔλ]=[fJhTyJgTλSλμehg+s].(36)
Это уравнение прибывает непосредственно из попытки решить  уравнение 2 и  уравнение 3 с помощью линеаризовавшей функции Лагранжа.

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

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

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

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

xL=xf(x)+iλigi(x)+jyjhj(x)=0,

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

minΔx,ΔsfTΔx+12ΔxTxx2LΔx+μeTS1Δs+12ΔsTS1ΛΔs,(37)
подвергните линеаризовавшим ограничениям
g(x)+JgΔx+Δs=0,  h(x)+JhΔx=0.(38)
Чтобы решить  уравнение 38, алгоритм пытается минимизировать норму линеаризовавших ограничений в области с радиусом, масштабируемым R. Затем  уравнение 37 решено с ограничениями быть, чтобы совпадать с невязкой решения  уравнения 38, пребывания в доверительной области радиуса R и хранение строго положительного s. Для получения дополнительной информации алгоритма и деривации, см. [40], [41], и [51]. Для другого описания методов сопряженных градиентов смотрите Предобусловленный Метод сопряженных градиентов.

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

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

  • HonorBounds — Когда установлено в true, каждый выполнять итерации удовлетворяет связанным ограничениям, которые вы установили. Когда установлено в false, алгоритм может нарушить границы во время промежуточных итераций.

  • HessianApproximation — Когда установлено в:

    • 'bfgs', fmincon вычисляет Гессиан плотным приближением квазиньютона.

    • 'lbfgs', fmincon вычисляет Гессиан ограниченной памятью, крупномасштабным приближением квазиньютона.

    • 'fin-diff-grads', fmincon вычисляет Векторное произведение времен гессиана конечными разностями градиента (градиентов); другие опции должны быть установлены соответственно.

  • HessianFcnfmincon использует указатель на функцию, который вы задаете в HessianFcn вычислить Гессиан. Смотрите Включая Гессианы.

  • HessianMultiplyFcn — Дайте отдельную функцию для Векторной временами гессианом оценки. Для получения дополнительной информации смотрите Включая Гессианы и функцию умножения Гессиана.

  • SubproblemAlgorithm — Определяет, делать ли попытку прямого шага Ньютона. Настройка по умолчанию 'factorization' позволяет этому типу шага быть предпринятым. Установка 'cg' позволяет только шаги метода сопряженных градиентов.

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

Алгоритм fminbnd

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

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

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

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

minxf(x)

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

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

Kj (x, wj) ≤ 0 для всего wjIj.

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

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

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

maxwjIjKj(x,wj)0  \forall j=1,...,|K|,(39)

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

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

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

  • Начальная буква, располагающая с интервалами s между выборкой точек w

  • Способ сгенерировать набор выборки точек w от s

Начальная буква, располагающая с интервалами 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 1 и K 2. K 1 имеет одномерный w 1, и K 2 имеет двумерный w 2. Следующий код генерирует набор выборки от w 1 = 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 2 в квадрате, с каждым компонентом, идущим от 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 берет следующие шаги, чтобы решить полубесконечные проблемы программирования:

  1. В текущем значении x, fseminf идентифицирует весь wj,i, таким образом, что интерполяция κj (x, wj,i) является локальным максимумом. (Максимум относится к различному w для фиксированного x.)

  2. fseminf делает один шаг итерации в решении fmincon проблема:

    minxf(x)

    таким образом, что c (x) ≤ 0, ceq (x) = 0, A·x ≤ b, Aeq·x = beq и l ≤ x ≤ u, где c (x) увеличивается со всеми максимумами κj (xwj) принятый весь wjIj, который равен максимумам по j и i κj (xwj,i).

  3. fseminf проверки, если какому-либо критерию остановки соответствуют в новой точке x (чтобы остановить итерации); в противном случае это продолжается к шагу 4.

  4. fseminf проверки, если дискретизация полубесконечных ограничений нуждается в обновлении и обновляет точки выборки соответственно. Это предоставляет обновленному приближению κj (x, wj). Затем это продолжается на шаге 1.

Для просмотра документации необходимо авторизоваться на сайте