Квадратичное программирование является проблемой нахождения векторного x, который минимизирует квадратичную функцию, возможно подвергните линейным ограничениям:
таким образом, что A·x ≤ b, Aeq·x = beq, l ≤ x ≤ u.
interior-point-convex алгоритм quadprogАлгоритм interior-point-convex выполняет следующие шаги:
Алгоритм имеет два пути выполнения кода. Это берет тот, когда матрица Гессиана, из которой H является обычной (полной) матрицей, удваивается, и это берет другой, когда H является разреженной матрицей. Для получения дополнительной информации разреженного типа данных, смотрите Разреженные матрицы (MATLAB). Обычно алгоритм быстрее для больших проблем, которые имеют относительно немного ненулевых условий, когда вы задаете H как sparse. Точно так же алгоритм быстрее для небольших или относительно плотных проблем, когда вы задаете H как full.
Алгоритм начинается путем попытки упростить проблему путем удаления сокращения и упрощения ограничений. Задачи, выполняемые во время предварительно решить шага, включают:
Проверяйте, имеют ли какие-либо переменные равные верхние и нижние границы. Если так, проверяйте на выполнимость, и затем зафиксируйте и удалите переменные.
Проверяйте, включает ли какое-либо линейное ограничение неравенства всего одну переменную. Если так, проверяйте на выполнимость и измените линейное ограничение на связанное.
Проверяйте, включает ли какое-либо линейное ограничение равенства всего одну переменную. Если так, проверяйте на выполнимость, и затем зафиксируйте и удалите переменную.
Проверяйте, имеет ли какая-либо линейная матрица ограничений нулевые строки. Если так, проверяйте на выполнимость и удалите строки.
Проверяйте, сопоставимы ли границы и линейные ограничения.
Проверяйте, появляются ли какие-либо переменные только как линейные члены в целевой функции и не появляются ни в каком линейном ограничении. Если так, проверяйте на выполнимость и ограниченность, и зафиксируйте переменные в их соответствующих границах.
Измените любые линейные ограничения неравенства на линейные ограничения равенства путем добавления слабых переменных.
Если алгоритм обнаруживает неосуществимую или неограниченную проблему, он останавливает и выпускает соответствующее выходное сообщение.
Алгоритм может прибыть в одну допустимую точку, которая представляет решение.
Если алгоритм не обнаруживает неосуществимую или неограниченную проблему на предварительно решить шаге, он продолжается, при необходимости, с другими шагами. В конце алгоритм восстанавливает исходную проблему, отменение любого предварительно решает преобразования. Этот последний шаг является пострешить шагом.
Для получения дополнительной информации смотрите Гулда и Тойнта [63].
Начальная точка x0 для алгоритма:
Инициализируйте x0 к ones(n,1), где n является количеством строк в H.
Для компонентов, которые имеют и верхнюю границу ub и нижнюю границу lb, если компонент x0 не строго в границах, компонент установлен в (ub + lb)/2.
Для компонентов, которые имеют только один связанный, измените компонент при необходимости, чтобы лечь строго в связанном.
Сделайте шаг предиктора (см. Корректор Предиктора), с незначительными исправлениями для выполнимости, не полным шагом корректора предиктора. Это помещает начальную точку ближе в central path, не влекущий за собой издержки полного шага корректора предиктора. Для получения дополнительной информации центрального пути, смотрите Носедэла и Райта [7], страница 397.
Разреженные и полные выпуклые внутренней точкой алгоритмы отличаются в основном по фазе корректора предиктора. Алгоритмы подобны, но отличаются по некоторым деталям. Для описания основного алгоритма смотрите Mehrotra [47].
Алгоритмы начинаются путем превращения линейных неравенств Ax <= b в неравенства формы Ax> = b путем умножения A и b-1. Это не имеет никакого влияния на решение, но делает проблему той же формы найденной в некоторой литературе.
Разреженный Корректор Предиктора. Подобно алгоритму внутренней точки fmincon разреженный алгоритм interior-point-convex пытается найти точку, где условия Karush-Kuhn-Tucker (KKT) содержат. Для проблемы квадратичного программирования, описанной в Определении Квадратичного программирования, эти условия:
Здесь
расширенная линейная матрица неравенства, которая включает границы, записанные как линейные неравенства. соответствующий линейный вектор неравенства, включая границы.
s является вектором слаксов, которые преобразовывают ограничения неравенства в равенства. s имеет длину m, количество линейных неравенств и границ.
z является вектором множителей Лагранжа, соответствующих s.
y является вектором множителей Лагранжа, сопоставленных с ограничениями равенства.
Алгоритм сначала предсказывает шаг от формулы Ньютона-Raphson, затем вычисляет шаг корректора. Корректор пытается лучше осуществить нелинейное ограничение sizi = 0.
Определения для шага предиктора:
rd, двойная невязка:
req, основная ограничительная невязка равенства:
rineq, основная невязка ограничения неравенства, которая включает границы и слаксы:
rsz, невязка взаимозависимости:
rsz = Sz.
S является диагональной матрицей слабых условий, z является матрицей столбца множителей Лагранжа.
rc, средняя взаимозависимость:
На шаге Ньютона, изменениях в x, s, y и z, дают:
| (1) |
Однако полный шаг Ньютона может быть неосуществимым из-за ограничений положительности на s и z. Поэтому quadprog сокращает шаг, при необходимости, чтобы поддержать положительность.
Кроме того, чтобы сохранить позицию “в центре” во внутренней части, вместо того, чтобы пытаться решить sizi = 0, алгоритм берет положительный параметр σ и пытается решить
sizi = σrc.
quadprog заменяет rsz в уравнении шага Ньютона с rsz + ΔsΔz – σrc 1, где 1 вектор из единиц. Кроме того, quadprog переупорядочивает уравнения Ньютона, чтобы получить симметричное, более численно устойчивую систему для вычисления шага предиктора.
После вычисления исправленного шага Ньютона алгоритм выполняет больше вычислений, чтобы получить и более длинный текущий шаг и подготовиться к лучшим последующим шагам. Эти несколько вычислений исправления могут улучшать и производительность и робастность. Для получения дополнительной информации смотрите Gondzio [4].
Полный Корректор Предиктора. Полный алгоритм корректора предиктора не комбинирует границы в линейные ограничения, таким образом, он имеет другой набор слабых переменных, соответствующих границам. Алгоритм переключает нижние границы, чтобы обнулить. И, если существует, только один привязал переменную, алгоритм превращает ее в нижнюю границу нуля путем отрицания неравенства верхней границы.
расширенная линейная матрица, которая включает и линейные неравенства и линейные равенства. соответствующий линейный вектор равенства. также включает условия для расширения векторного x со слабыми переменными s, которые поворачивают ограничения неравенства к ограничениям равенства:
где x 0 средних значений исходный вектор x.
Условия KKT
| (2) |
Чтобы найти решение x, слабыми переменными и двойными переменными к уравнению 2, алгоритм в основном рассматривает шаг Ньютона-Raphson:
| (3) |
где X, V, W и T являются диагональными матрицами, соответствующими векторам x, v, w и t соответственно. Вектора невязок на ультраправой стороне уравнения:
rd, двойная невязка
rp, основная невязка
rub, невязка верхней границы
rvx, невязка взаимозависимости нижней границы
rwt, невязка взаимозависимости верхней границы
Алгоритм решает уравнение 3 первым преобразованием его к форме симметрической матрицы
| (4) |
где
Все матричные инверсии в определениях D и R просты вычислить, потому что матрицы являются диагональными.
Чтобы вывести уравнение 4 от уравнения 3, заметьте, что вторая строка уравнения 4 совпадает со второй строкой матрицы уравнения 3. Первая строка уравнения 4 прибывает из решения последних двух строк уравнения 3 для Δv и Δw и затем решения для Δt.
Чтобы решить уравнение 4, алгоритм следует за существенными элементами Олтмена и Гондсио [1]. Алгоритм решает симметричную систему разложением LDL. Как указано авторами, такими как Вэндербеи и Карпентер [2], это разложение численно стабильно без любого поворота, быть быстрым - также.
После вычисления исправленного шага Ньютона алгоритм выполняет больше вычислений, чтобы получить и более длинный текущий шаг и подготовиться к лучшим последующим шагам. Эти несколько вычислений исправления могут улучшать и производительность и робастность. Для получения дополнительной информации смотрите Gondzio [4].
Полный алгоритм корректора предиктора quadprog является в основном тем же самым как этим в алгоритме 'interior-point' linprog, но включает квадратичные условия также. Смотрите Корректор Предиктора.
[1] Олтмен, Анна и Х. Гондсио. Упорядоченные симметричные неопределенные системы в методах внутренней точки для линейной и квадратичной оптимизации. Методы оптимизации и программное обеспечение, 1999. Доступный для скачивания здесь.
[2] Vanderbei, R. J. и Т. Дж. Карпентер. Симметричные неопределенные системы для методов внутренней точки. Математическое программирование 58, 1993. стр 1–32. Доступный для скачивания здесь.
Алгоритм корректора предиктора выполняет итерации, пока он не достигает точки, которая выполнима (удовлетворяет ограничения к в допусках), и где относительные размеры шага являются небольшими. А именно, задайте
Алгоритм останавливается, когда все эти условия удовлетворены:
где
rc по существу измеряет размер невязок взаимозависимости xv и tw, которые являются каждым векторы нулей в решении.
quadprog вычисляет оценочную функцию φ в каждой итерации. Оценочная функция является мерой выполнимости. quadprog останавливается, если оценочная функция становится слишком большой. В этом случае quadprog объявляет проблему быть неосуществимым.
Оценочная функция связана с условиями KKT для проблемы — смотрите Корректор Предиктора. Используйте следующие определения:
Обозначение и означает линейные коэффициенты неравенства, увеличенные с условиями представлять границы для разреженного алгоритма. Обозначение так же представляет множители Лагранжа для линейных ограничений неравенства, включая связанные ограничения. Это было названо z в Корректоре Предиктора, и был назван y.
Оценочная функция φ
Если эта оценочная функция становится слишком большой, quadprog объявляет проблему быть неосуществимым и остановы с выходным флагом -2.
trust-region-reflective алгоритм quadprogМногие методы, используемые в решателях Optimization Toolbox™, основаны на доверительных областях, простой все же мощной концепции в оптимизации.
Чтобы понять подход доверительной области к оптимизации, рассмотрите проблему безусловной минимизации, минимизируйте f (x), где функция берет аргументы вектора и возвращает скаляры. Предположим, что вы - в точке x в n - пробел, и вы хотите улучшиться, т.е. переместиться в точку с более низким значением функции. Основная идея состоит в том, чтобы аппроксимировать f с более простым функциональным q, который обоснованно отражает поведение функционального f в окружении N вокруг точки x. Это окружение является доверительной областью. Испытательный шаг s вычисляется путем минимизации (или приблизительно минимизации) по N. Это - подпроблема доверительной области,
| (5) |
Текущая точка обновляется, чтобы быть x + s если f (x + s) < f (x); в противном случае текущая точка остается неизменной, и N, область доверия, уменьшается, и испытательное вычисление шага повторяется.
Ключевые вопросы в определении определенного подхода доверительной области к минимизации f (x) состоят в том, как выбрать и вычислить приближение q (заданный в текущей точке x), как выбрать и изменить доверительную область N, и как точно решить подпроблему доверительной области. Этот раздел фокусируется на неограниченной проблеме. Более поздние разделы обсуждают дополнительные осложнения из-за присутствия ограничений на переменные.
В стандартном методе доверительной области ([48]), квадратичное приближение q задан первыми двумя сроками приближения Тейлора к F в x; окружение N является обычно сферическим или эллипсоидальным в форме. Математически подпроблема доверительной области обычно утверждается
| (6) |
где g является градиентом f в текущей точке x, H является матрицей Гессиана (симметрическая матрица вторых производных), D является диагональной матрицей масштабирования, Δ является положительной скалярной величиной и ∥. ∥ является 2-нормой. Хорошие алгоритмы существуют для решения уравнения 6 (см. [48]); такие алгоритмы обычно включают вычисление всех собственных значений H, и процесс Ньютона применился к характеристическому уравнению
Такие алгоритмы предоставляют точное решение уравнения 6. Однако они требуют времени, пропорционального нескольким факторизациям H. Поэтому для крупномасштабных проблем другой подход необходим. Несколько приближений и эвристических стратегий, на основе уравнения 6, были предложены в литературе ([42] и [50]). Подход приближения, сопровождаемый в решателях Optimization Toolbox, должен ограничить подпроблему доверительной области двумерным подпространством S ([39] и [42]). Однажды подпространство S был вычислен, работа, чтобы решить уравнение 6 тривиальна, даже если полная информация о собственном значении/собственном векторе необходима (поскольку в подпространстве, проблема только двумерна). Доминирующая работа теперь переключила к определению подпространства.
Двумерное подпространство S определяется при помощи предобусловленного процесса метода сопряженных градиентов, описанного ниже. Решатель задает S как линейный пробел, заполненный s 1 и s 2, где s 1 является в направлении градиента g, и s 2 является любой аппроксимированным направлением Ньютона, т.е. решением
| (7) |
или направление отрицательного искривления,
| (8) |
Философия позади этого выбора S должна обеспечить глобальную сходимость (через направление быстрейшего спуска или отрицательное направление искривления) и достигнуть быстро локальной сходимости (через шаг Ньютона, когда это существует).
Эскиз безусловной минимизации с помощью идей доверительной области теперь легко дать:
Сформулируйте двумерную подпроблему доверительной области.
Решите уравнение 6, чтобы определить испытательный шаг s.
Если f (x + s) <f (x), то x = x + s.
Настройте Δ.
Эти четыре шага повторяются до сходимости. Размерность доверительной области Δ настроена согласно стандартным правилам. В частности, это уменьшено, если испытательный шаг не принят, т.е. f (x + s) ≥ f (x). См. [46] и [49] для обсуждения этого аспекта.
Решатели Optimization Toolbox обрабатывают несколько важных особых случаев f со специализированными функциями: нелинейный метод наименьших квадратов, квадратичные функции и линейный метод наименьших квадратов. Однако базовые алгоритмические идеи эквивалентны для общего случая. Эти особые случаи обсуждены в более поздних разделах.
Метод доверительной области подпространства используется, чтобы определить поисковое направление. Однако вместо того, чтобы ограничить шаг (возможно) одним отражательным шагом, как в нелинейном случае минимизации, кусочный отражающий поиск строки проводится в каждой итерации. См. [45] для деталей поиска строки.
Популярным способом решить большие симметричные положительные определенные системы линейных уравнений Hp = –g является метод Предобусловленных методов сопряженных градиентов (PCG). Этот итерационный подход требует способности вычислить матричные векторные произведения формы H·v, где v является произвольным вектором. Симметричный положительный определенный матричный M является предварительным формирователем для H. Таким образом, M = C 2, где C –1HC–1 является хорошо подготовленной матрицей или матрицей с кластеризованными собственными значениями.
В контексте минимизации можно принять, что матрица Гессиана H симметрична. Однако H, как гарантируют, будет положителен определенный только в окружении сильного минимизатора. PCG алгоритма выходит, когда с направлением отрицательных (или нуль) искривление сталкиваются, т.е. dTHd ≤ 0. PCG направление вывода, p, является или направлением отрицательного искривления или аппроксимированным (tol средства управления как аппроксимированный) решение системы Ньютона Hp = –g. В любом случае p используется, чтобы помочь задать двумерное подпространство, используемое в подходе доверительной области, обсужденном в Методах Доверительной области для Нелинейной Минимизации.
Линейные ограничения усложняют ситуацию, описанную для безусловной минимизации. Однако базовые идеи, описанные ранее, могут быть осуществлены чистым и эффективным способом. Методы доверительной области в решателях Optimization Toolbox генерируют строго выполнимый, выполняет итерации.
Общее линейное равенство ограничило проблему минимизации, может быть записан
| (9) |
где A является m-by-n матрица (m ≤ n). Некоторые решатели Optimization Toolbox предварительно обрабатывают A, чтобы удалить строгие линейные зависимости с помощью метода на основе LU-факторизации AT [46]. Здесь A принят, чтобы быть ранга m.
Метод, используемый, чтобы решить уравнение 9, отличается от неограниченного подхода двумя значительными способами. Во-первых, начальная допустимая точка x 0 вычисляется, с помощью разреженного шага наименьших квадратов, так, чтобы Ax 0 = b. Во-вторых, Алгоритм, PCG заменяется Уменьшаемыми предобусловленными методами сопряженных градиентов (RPCG), видят [46], в порядке вычислить аппроксимированный уменьшаемый шаг Ньютона (или направление отрицательного искривления на пустом пробеле A). Ключевой шаг линейной алгебры включает системы решения формы
| (10) |
где аппроксимирует A (маленькие ненули A обнуляются, если ранг не потерян), и C является разреженным симметричным положительно-определенным приближением к H, т.е. C = H. См. [46] для получения дополнительной информации.
Ограниченная проблема поля имеет форму
| (11) |
где l является вектором нижних границ, и u является вектором верхних границ. Некоторые (или все) компонентов l могут быть равны – ∞, и некоторые (или все) компонентов u могут быть равны ∞. Метод генерирует последовательность строго допустимых точек. Два метода используются, чтобы поддержать выполнимость при достижении устойчивого поведения сходимости. Во-первых, масштабированный измененный шаг Ньютона заменяет неограниченный шаг Ньютона (чтобы задать двумерное подпространство S). Во-вторых, отражения используются, чтобы увеличить размер шага.
Масштабированный измененный шаг Ньютона является результатом исследования необходимых условий Куна-Такера для уравнения 11,
| (12) |
где
и векторный 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
Нелинейное системное уравнение 12 не дифференцируемо везде. Недифференцируемость происходит когда vi = 0. Можно избежать таких точек путем поддержания строгой выполнимости, т.е. ограничения l < x < u.
Масштабированный измененный шаг Ньютона sk для нелинейной системы уравнений, данной уравнением 12, задан как решение линейной системы
| (13) |
в k th итерация, где
| (14) |
и
| (15) |
Здесь Jv играет роль якобиана |v |. Каждый диагональный компонент диагонального матричного Jv равняется 0, –1, или 1. Если все компоненты l и u конечны, Jv = diag (знак (g)). В точке, где gi = 0, vi не может быть дифференцируемым. задан в такой точке. Недифференцируемость этого типа не является поводом для беспокойства, потому что для такого компонента это не значительно, какое значение vi принимает. Далее, |vi | все еще будет прерывисто в этой точке, но функции |vi| · gi непрерывен.
Во-вторых, отражения используются, чтобы увеличить размер шага. (Один) отражательный шаг задан можно следующим образом. Учитывая шаг p, который пересекает связанное ограничение, считает первое связанное ограничение пересеченным p; примите, что это - i th связанное ограничение (или i th верхний или i th нижняя граница). Затем отражательный шаг pR = p кроме i th компонент, где pRi = –pi.