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

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

Многие методы, используемые в решателях 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 1 и _s 2, где s 1 находится в направлении градиента g, и s 2 является либо приблизительным направлением Ньютона, т.е. решением

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

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

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

Эти четыре шага повторяются до сходимости. Размерность Β доверительной области регулируется согласно стандартным правилам. В частности, это уменьшено, если шаг испытания не принят, т.е. f (x + s) ≥ <reservedrangesplaceholder1> (<reservedrangesplaceholder0>). Для обсуждения этого аспекта см. [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 n матрицей (m  ≤ <reservedrangesplaceholder1>). Некоторые решатели Optimization Toolbox предварительно обрабатывают A, чтобы удалить строгие линейные зависимости, используя метод, основанный на LU-факторизации A^T [46]. Здесь A принято рангом m.

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

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

Прямоугольные ограничения

Задача с ограничениями в прямоугольнике имеет вид

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

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

где

и вектор v (<reservedrangesplaceholder2>)   определен  ниже для каждого 1 ≤ <reservedrangesplaceholder1> ≤ <reservedrangesplaceholder0>:

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

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

на k-й итерации, где

и

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

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

Введение

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

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

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

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

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

The 'active-set' алгоритм не является крупномасштабным алгоритмом; см. «Алгоритмы большого и среднего масштаба».

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

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

Основываясь на работе Биггса [1], Хана [22] и Пауэлла ([32] и [33]), метод позволяет вам тесно имитировать метод Ньютона для ограниченной оптимизации так же, как это делается для оптимизации без ограничений. На каждой основной итерации делается приближение Гессиана функции Лагранжа с помощью квази-Ньютонского метода обновления. Затем он используется для генерации подпрограммы QP, решение которой используется для формирования направления поиска для процедуры поиска по линии. Обзор SQP представлен во Fletcher [13], Gill et al. [19], Powell [35] и Schittkowski [23]. Общий способ, однако, изложен здесь.

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

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

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

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

Параметр α k длины шага определяется соответствующей линией процедурой поиска, так что достигается достаточное уменьшение функции заслуг (см. Обновление Матрицы Гессиана). Матрица _H k является положительным определенным приближением Гессианской матрицы функции Лагранжа ( Equation 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, является оценкой множителей Лагранжа .

где

Powell [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вторая строка m -by n матрицы A.

Метод, используемый в функциях Optimization Toolbox, является стратегией активного набора (также известной как метод проекции), подобной стратегии Gill et al., описанной в [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-ю строку матричного A. Можно найти допустимую точку (если она существует) к  Уравнению 26, установив x на значение, которое удовлетворяет ограничениям равенствам. Можно определить это значение, решив недостаточно - или переопределенный набор линейных уравнений, сформированных из набора ограничений равенства. Если существует решение этой задачи, то γ переменной slack устанавливается на ограничение максимального неравенства в этой точке.

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

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

где _gk - градиент целевой функции в текущей итерационной _xk (т.е. _Hxk + c).

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

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

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

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

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

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

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

Строгая осуществимость с учетом границ

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

Робастность к недвойственным результатам

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

Refactored Linear Algebra Стандартных программ

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

Переформулированные стандартные программы технико-экономического обоснования

The 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'.

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

В оставшейся части этого раздела рассматриваются 'predictor-corrector' алгоритм обновления параметра барьера μ. Механизм аналогичен алгоритму линейного программирования Predictor-Corrector.

Шаги Предиктора-Корректора могут ускорить существующий подход Фиакко-Маккормака (Монотон), скорректировав ошибку линеаризации в шагах Ньютона. Эффекты режима Predictor-Corrector двояки: он (часто) улучшает направления шага и одновременно адаптивно обновляет параметр барьера с помощью параметра centering, чтобы побудить итератов следовать «центральному пути». Смотрите обсуждение Nocedal и Wright шагов предиктора-корректора для линейных программ, чтобы понять, почему центральный путь позволяет большие размеры шага и, следовательно, более быстрое сходимость.

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

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

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

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

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

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

Второй шаг корректора является шагом центрирования. Коррекция центрирования основана на переменной, σ с правой стороны уравнения

Здесь σ определяется как

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

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

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

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

Сопряженный градиентный шаг

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

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

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

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

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

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

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

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

таким образом, что c (<reservedrangesplaceholder9>)      ≤ 0 , ceq (<reservedrangesplaceholder7>)    = 0, <reservedrangesplaceholder6> ≤ <reservedrangesplaceholder5>, Aeq·x = beq, и <reservedrangesplaceholder2> ≤ <reservedrangesplaceholder1> ≤ <reservedrangesplaceholder0>.

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

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

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

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

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

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

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

Начальный интервал s является матрицей |<reservedrangesplaceholder2>|-by-2. j строка 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 выполняет следующие шаги для решения полунепрерывных задач программирования: