Exponenta Banner

mpcActiveSetSolver

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

Свернуть все на странице

Синтаксис

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

Описание

Используя 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=12x⊺Hx+f⊺x

удовлетворяющее ограничениям неравенства Ax≤b и ограничения равенства Aeqx=beq. exitflag указывает на валидность x.

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

Примеры

свернуть все

Открыть Live Script

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

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

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

x1≥0x2≥0x1+x2≤2-x1+2x2≤22x1+x2≤3.

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

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 ограничением неравенства. Используйте необязательный выходной аргумент 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Задача представляется недопустимой, то есть ограничением Ax≤b не может быть удовлетворен.
-2Произошла неустранимая числовая ошибка.

Активное неравенство, где равный фрагмент неравенства верен, возвращается как логический вектор длины m. Если iA(i) == true, тогда i-е неравенство активно для решения 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 с помощью метода active-set, алгоритма KWIK, основанного на [1]. Для получения дополнительной информации см. Раздел «Решатели QP».

Ссылки

[1] Шмид, С. и Л.Т. Биглер. «Квадратичные методы программирования для сокращенного гессианского SQP». Компьютеры и химическая техника 18, № 9 (сентябрь 1994): 817-32. https://doi.org/10.1016/0098-1354 (94) E0001-4.

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

.

См. также

| | (Optimization Toolbox)

Темы

Введенный в R2020a

Документация Model Predictive Control Toolbox

Поддержка