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 = 5×1 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Использование:

    [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

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