mpcActiveSetSolver

Решите задачу квадратичного программирования с помощью алгоритма активного набора

Описание

Используя mpcActiveSetSolver, можно решить задачу квадратичного программирования (QP) с помощью алгоритма активного набора. Эта функция обеспечивает доступ к встроенному активному набору Model Predictive Control Toolbox™ решатель QP.

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

Этот решатель полезен для:

  • Усовершенствованные приложения MPC, которые выходят за рамки программного обеспечения Model Predictive Control Toolbox.

  • Пользовательские приложения QP, включая приложения, которые требуют генерации кода.

В качестве альтернативы можно также получить доступ к встроенной внутренней точке использование решателя QP mpcInteriorPointSolver.

пример

[x,exitflag] = mpcActiveSetSolver(H,f,A,b,Aeq,beq,iA0,options) находит оптимальное решение x к проблеме квадратичного программирования путем минимизации целевой функции:

J=12xHx+fx

подвергните ограничениям неравенства Axb и ограничения равенства Aeqx=beqexitflag указывает на валидность x.

[x,exitflag,iA,lambda] = mpcActiveSetSolver(H,f,A,b,Aeq,beq,iA0,options) также возвращает активные неравенства iA в решении и множителях Лагранжа lambda для решения.

Примеры

свернуть все

Найдите значения x, которые минимизируют

f(x)=0.5x12+x22-x1x2-2x1-6x2,

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

x10x20x1+x22-x1+2x222x1+x23.

Задайте Гессиан матричный и линейный вектор множителя для целевой функции.

H = [1 -1; -1 2];
f = [-2; -6];

Задайте параметры ограничения неравенства.

A = [-1 0; 0 -1; 1 1; -1 2; 2 1];
b = [0; 0; 2; 2; 3];

Задайте Aeq и beq указать, что нет никаких ограничений равенства.

n = length(f);
Aeq = zeros(0,n);
beq = zeros(0,1);

Создайте набор опции по умолчанию для mpcActiveSetSolver.

opt = mpcActiveSetOptions;

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

iA0 = false(size(b));

Решите задачу QP.

[x,exitflag] = mpcActiveSetSolver(H,f,A,b,Aeq,beq,iA0,opt);

Исследуйте решение x.

x
x = 2×1

    0.6667
    1.3333

При решении задачи QP можно также определить, какие ограничения неравенства активны для решения.

[x,exitflag,iA,lambda] = mpcActiveSetSolver(H,f,A,b,Aeq,beq,iA0,opt);

Проверяйте активные ограничения неравенства. Активное ограничение неравенства в равенстве для оптимального решения.

iA
iA = 5x1 logical array

   0
   0
   1
   1
   0

Существует одно активное ограничение неравенства. Просмотрите множитель Лагранжа для этого ограничения.

lambda.ineqlin(1)
ans = 0

Входные параметры

свернуть все

Матрица гессиана в виде симметричного n-by-n матрица, где n> 0 является количеством переменных оптимизации.

Алгоритм QP активного набора требует, чтобы матрица Гессиана была положительна определенный. Определить ли H положителен определенный, используйте chol функция.

[~,p] = chol(H);

Если p = 0, затем H положителен определенный. В противном случае, p положительное целое число.

Активный набор алгоритм QP вычисляет нижнее треугольное разложение Холесского (Linv) из матрицы Гессиана. Если ваше приложение требует повторяющихся вызовов mpcInteriorPointSolver с помощью постоянной матрицы Гессиана можно повысить вычислительную эффективность путем вычисления Linv однажды и передача его к mpcActiveSetSolver вместо матрицы Гессиана. Для этого необходимо установить UseHessianAsInput поле options к false.

options = mpcActiveSetOptions;
options.UseHessianAsInput = false;

Вычислить Linv, используйте следующий код.

[L,p] = chol(H,'lower');
Linv = linsolve(L,eye(size(L)),struct('LT',true));

Множитель линейного члена целевой функции в виде вектор-столбца длины n, где n является количеством переменных оптимизации.

Линейные коэффициенты ограничения неравенства в виде m-by-n матрица, где n является количеством переменных оптимизации и m, являются количеством ограничений неравенства.

Если ваша проблема не имеет никаких ограничений неравенства, используйте zeros(0,n).

Правая сторона ограничений неравенства в виде вектор-столбца длины m, где m является количеством ограничений неравенства.

Если ваша проблема не имеет никаких ограничений неравенства, используйте zeros(0,1).

Линейные коэффициенты ограничения равенства в виде q-by-n матрица, где n является количеством переменных оптимизации и q <= n, являются количеством ограничений равенства. Ограничения равенства должны быть линейно независимыми с rank(Aeq) = q.

Если ваша проблема не имеет никаких ограничений равенства, используйте zeros(0,n).

Правая сторона ограничений равенства в виде вектор-столбца длины q, где q является количеством ограничений равенства.

Если ваша проблема не имеет никаких ограничений равенства, используйте zeros(0,1).

Начальные активные неравенства, где равный фрагмент неравенства верен в виде логического вектора из длины m, где m является количеством ограничений неравенства. Задайте iA0 можно следующим образом:

  • Если ваша проблема не имеет никаких ограничений неравенства, используйте false(0,1).

  • Для холодного запуска используйте false(m,1).

  • Для горячего запуска, набор iA0(i) == true начинать алгоритм с i th активное ограничение неравенства. Используйте дополнительный выходной аргумент iA из предыдущего решения задать iA0 таким образом. Если оба iA0(i) и iA0(j) true, затем строки i и j A должно быть линейно независимым. В противном случае решение может перестать работать с exitflag = -2.

Набор опции для mpcActiveSetSolverВ виде структуры, созданной с помощью mpcActiveSetOptions.

Выходные аргументы

свернуть все

Оптимальное решение проблемы QP, возвращенной как вектор-столбец длины n, где n является количеством переменных оптимизации. mpcActiveSetSolver всегда возвращает значение для x. Чтобы определить, оптимально ли решение или выполнимо, проверяйте exitflag.

Индикатор валидности решения, возвращенный как целое число согласно следующей таблице.

ЗначениеОписание
> 0x оптимально. В этом случае, exitflag представляет количество итераций, выполняемых во время оптимизации.
0

Максимальное количество итераций было достигнуто. Решение x может быть субоптимальным или неосуществимым.

Определить если x неосуществимо, проверяйте, нарушает ли решение допуск ограничения, заданный в options.

feasible = (A*x-b) <= options.ConstraintTolerance;

Если любой элемент feasible false, затем x неосуществимо.

-1Проблема, кажется, неосуществима, то есть, ограничение Axb не может быть удовлетворен.
-2Произошла неисправимая числовая ошибка.

Активные неравенства, где равный фрагмент неравенства верен, возвратились как логический вектор из длины m. Если iA(i) == true, затем i th неравенство активен для решения x.

Используйте iA к горячему запуску последующее mpcActiveSetSolver решение.

Множители Лагранжа, возвращенные как структура со следующими полями.

Поле Описание
ineqlinМножители ограничений неравенства, возвращенных как вектор из длины n. Когда решение оптимально, элементы ineqlin являются неотрицательными.
eqlinМножители ограничений равенства, возвращенных как вектор из длины q. В оптимальном решении нет никаких ограничений знака.

Советы

  • Алгоритм KWIK требует, чтобы матрица Гессиана H была положительна определенный. При вычислении Linv, используйте chol функция.

    [L,p] = chol(H,'lower');

    Если p = 0, затем H положителен определенный. В противном случае, p положительное целое число.

  • mpcActiveSetSolver обеспечивает доступ к активному набору по умолчанию решатель QP, используемый программным обеспечением Model Predictive Control Toolbox. Используйте эту команду, чтобы решить задачи QP в ваших собственных приложениях MPC. Для примера пользовательского использования приложения MPC mpcActiveSetSolver, смотрите Решают Пользовательскую задачу Квадратичного программирования MPC и Генерируют Код.

Алгоритмы

mpcActiveSetSolver решает задачу QP с помощью активного метода установки, алгоритма KWIK, на основе [1]. Для получения дополнительной информации см. Решатели QP.

Ссылки

[1] Шмид, C. и Л.Т. Биглер. "Методы Квадратичного программирования для Уменьшаемого Гессиана SQP". Computers & Chemical Engineering 18, № 9 (сентябрь 1994): 817–32. https://doi.org/10.1016/0098-1354 (94) E0001-4.

Расширенные возможности

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