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

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

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

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

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

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

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

и

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

Во-вторых, отражения используются, чтобы увеличить размер шага. (Один) отражательный шаг задан можно следующим образом. Учитывая шаг p, который пересекает связанное ограничение, считает первое связанное ограничение пересеченным p; примите, что это - i th связанное ограничение (или i th верхний или i th нижняя граница). Затем отражательный шаг ^pR = p кроме i th компонент, где ^pRi  = –_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 для неограниченного случая. Рисунок 6-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$$, сохраняется, который оценка активных ограничений (т.е. те, которые находятся на ограничительных контурах) в точке решения. Фактически все алгоритмы 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$$ находится к ограничительному контуру, т.е. $$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 взято как та, которая минимизирует γ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Прямой шаг

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

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

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

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

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

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

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

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

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

Поскольку полный список опций видит Алгоритм Внутренней точки в 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), в уравнении 39. Это уменьшает исходную проблему, минимизируя полубесконечно ограниченную функцию, к проблеме с конечным числом ограничений.

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

Начальная буква, располагающая с интервалами 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 берет следующие шаги, чтобы решить полубесконечные проблемы программирования: