quadprog

Квадратичное программирование

Описание

Решатель для квадратичных целевых функций с линейными ограничениями.

quadprog находит минимум для проблемы заданным

minx12xTHx+fTx таким образом , что {Axb,Aeqx=beq,lbxub.

H, A и Aeq являются матрицами, и f, b, beq, lb, ub, и x является векторами.

Можно передать f, lb и ub как векторы или матрицы; смотрите Матричные аргументы.

Примечание

quadprog применяется только к основанному на решателе подходу. Для обсуждения двух подходов оптимизации смотрите, Сначала Выбирают Problem-Based or Solver-Based Approach.

x = quadprog(H,f) возвращает векторный x это минимизирует   1/2*x'*H*x + f'*x. Вход H должен быть положителен определенный для проблемы иметь конечный минимум. Если H положителен определенный, затем решение x = H\(-f).

пример

x = quadprog(H,f,A,b) минимизирует   1/2*x'*H*x + f'*x подвергните ограничениям A*x  b. Вход A матрица, удваивается, и b вектор из, удваивается.

пример

x = quadprog(H,f,A,b,Aeq,beq) решает предыдущую задачу, удовлетворяющую дополнительным ограничениям   Aeq*x = beq. Aeq матрица, удваивается, и beq вектор из, удваивается. Если никакие неравенства не существуют, устанавливают   A = [] и   b = [].

пример

x = quadprog(H,f,A,b,Aeq,beq,lb,ub) решает предыдущую задачу, удовлетворяющую дополнительным ограничениям lb  x  ub. Входные параметры lb и ub векторы из, удваивается, и ограничения содержат для каждого x компонент. Если никакие равенства не существуют, устанавливают   Aeq = [] и   beq = [].

Примечание

Если заданные входные границы для проблемы противоречивы, выход x x0 и выход fval [].

quadprog компоненты сброса x0 это нарушает границы lb  x  ub к внутренней части поля, заданного границами. quadprog не изменяет компоненты, которые уважают границы.

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0) решает предыдущую задачу, начинающую с векторного x0. Если никакие границы не существуют, устанавливают   lb = [] и   ub = []. Некоторые quadprog алгоритмы игнорируют x0; смотрите x0.

Примечание

x0 обязательный аргумент для 'active-set' алгоритм.

пример

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options) решает предыдущую задачу с помощью опций оптимизации, заданных в optionsИспользование optimoptions создать options. Если вы не хотите давать начальную точку, установите   x0 = [].

пример

x = quadprog(problem) возвращает минимум для problem, структура описана в problem. Создайте problem структура с помощью записи через точку или struct функция. В качестве альтернативы создайте problem структура от OptimizationProblem объект при помощи prob2struct.

пример

[x,fval] = quadprog(___), для любых входных переменных, также возвращает fval, значение целевой функции при x:

fval = 0.5*x'*H*x + f'*x

пример

[x,fval,exitflag,output] = quadprog(___) также возвращает exitflag, целое число, которое описывает выходное условие quadprog, и output, структура, которая содержит информацию об оптимизации.

пример

[x,fval,exitflag,output,lambda] = quadprog(___) также возвращает lambda, структура, поля которой содержат множители Лагранжа в решении x.

пример

[wsout,fval,exitflag,output,lambda] = quadprog(H,f,A,b,Aeq,beq,lb,ub,ws) запускается quadprog из данных в объекте ws горячего запуска, использование опций в ws. Возвращенный аргумент wsout содержит точку решения в wsout.X. При помощи wsout как начальный горячий запуск возражают в последующем вызове решателя, quadprog может работать быстрее.

Примеры

свернуть все

Найдите минимум

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

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

x1+x22-x1+2x222x1+x23.

В quadprog синтаксис, эта проблема состоит в том, чтобы минимизировать

f(x)=12xTHx+fTx,

где

H=[1-1-12]f=[-2-6],

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

Чтобы решить эту задачу, сначала введите содействующие матрицы.

H = [1 -1; -1 2]; 
f = [-2; -6];
A = [1 1; -1 2; 2 1];
b = [2; 2; 3];

Вызовите quadprog.

[x,fval,exitflag,output,lambda] = ...
   quadprog(H,f,A,b);
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

Исследуйте конечную точку, значение функции и выходной флаг.

x,fval,exitflag
x = 2×1

    0.6667
    1.3333

fval = -8.2222
exitflag = 1

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

Подтвердите тот H положителен определенный путем проверки его собственных значений.

eig(H)
ans = 2×1

    0.3820
    2.6180

Найдите минимум

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

подвергните ограничению

x1+x2=0.

В quadprog синтаксис, эта проблема состоит в том, чтобы минимизировать

f(x)=12xTHx+fTx,

где

H=[1-1-12]f=[-2-6],

подвергните линейному ограничению.

Чтобы решить эту задачу, сначала введите содействующие матрицы.

H = [1 -1; -1 2]; 
f = [-2; -6];
Aeq = [1 1];
beq = 0;

Вызовите quadprog, ввод [] для входных параметров A и b.

[x,fval,exitflag,output,lambda] = ...
   quadprog(H,f,[],[],Aeq,beq);
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

Исследуйте конечную точку, значение функции и выходной флаг.

x,fval,exitflag
x = 2×1

   -0.8000
    0.8000

fval = -1.6000
exitflag = 1

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

Подтвердите тот H положителен определенный путем проверки его собственных значений.

eig(H)
ans = 2×1

    0.3820
    2.6180

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

12xTHx+fTx

где

H=[1-11-12-21-24], f=[2-31],

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

0x1, x=1/2.

Чтобы решить эту задачу, сначала введите коэффициенты.

H = [1,-1,1
    -1,2,-2
    1,-2,4];
f = [2;-3;1];
lb = zeros(3,1);
ub = ones(size(lb));
Aeq = ones(1,3);
beq = 1/2;

Вызовите quadprog, ввод [] для входных параметров A и b.

x = quadprog(H,f,[],[],Aeq,beq,lb,ub)
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
x = 3×1

    0.0000
    0.5000
    0.0000

Установите опции контролировать прогресс quadprog.

options = optimoptions('quadprog','Display','iter');

Опишите задачу с квадратичные объективные и линейные ограничения неравенства.

H = [1 -1; -1 2]; 
f = [-2; -6];
A = [1 1; -1 2; 2 1];
b = [2; 2; 3];

Помочь записать quadprog вызов функции, набор ненужные входные параметры к [].

Aeq = [];
beq = [];
lb = [];
ub = [];
x0 = [];

Вызовите quadprog решать задачу.

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)
 Iter            Fval  Primal Infeas    Dual Infeas  Complementarity  
    0   -8.884885e+00   3.214286e+00   1.071429e-01     1.000000e+00  
    1   -8.331868e+00   1.321041e-01   4.403472e-03     1.910489e-01  
    2   -8.212804e+00   1.676295e-03   5.587652e-05     1.009601e-02  
    3   -8.222204e+00   8.381476e-07   2.793826e-08     1.809485e-05  
    4   -8.222222e+00   3.064216e-14   1.352696e-12     7.525735e-13  

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
x = 2×1

    0.6667
    1.3333

Создайте problem структура с помощью Основанного на проблеме Рабочего процесса Оптимизации. Создайте задачу оптимизации, эквивалентную Квадратичной Программе с Линейными Ограничениями.

x = optimvar('x',2);
objec = x(1)^2/2 + x(2)^2 - x(1)*x(2) - 2*x(1) - 6*x(2);
prob = optimproblem('Objective',objec);
prob.Constraints.cons1 = sum(x) <= 2;
prob.Constraints.cons2 = -x(1) + 2*x(2) <= 2;
prob.Constraints.cons3 = 2*x(1) + x(2) <= 3;

Преобразуйте prob к problem структура.

problem = prob2struct(prob);

Решите задачу с помощью quadprog.

[x,fval] = quadprog(problem)
Warning: Your Hessian is not symmetric. Resetting H=(H+H')/2.
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
x = 2×1

    0.6667
    1.3333

fval = -8.2222

Решите квадратичную программу и возвратите и решение и значение целевой функции.

H = [1,-1,1
    -1,2,-2
    1,-2,4];
f = [-7;-12;-15];
A = [1,1,1];
b = 3;
[x,fval] = quadprog(H,f,A,b)
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
x = 3×1

   -3.5714
    2.9286
    3.6429

fval = -47.1786

Проверяйте, что возвращенное значение целевой функции совпадает со значением, вычисленным из quadprog определение целевой функции.

fval2 = 1/2*x'*H*x + f'*x
fval2 = -47.1786

Видеть процесс оптимизации для quadprog, установите опции показывать итеративное отображение и возвращать четыре выходных параметра. Проблема состоит в том, чтобы минимизировать

12xTHx+fTx

при ограничениях

0x1,

где

H=[21-11312-1125], f=[4-712].

Введите проблемные коэффициенты.

H = [2 1 -1
    1 3 1/2
    -1 1/2 5];
f = [4;-7;12];
lb = zeros(3,1);
ub = ones(3,1);

Установите опции отображать итеративный прогресс решателя.

options = optimoptions('quadprog','Display','iter');

Вызовите quadprog с четырьмя выходными параметрами.

[x fval,exitflag,output] = quadprog(H,f,[],[],[],[],lb,ub,[],options)
 Iter            Fval  Primal Infeas    Dual Infeas  Complementarity  
    0    2.691769e+01   1.582123e+00   1.712849e+01     1.680447e+00  
    1   -3.889430e+00   0.000000e+00   8.564246e-03     9.971731e-01  
    2   -5.451769e+00   0.000000e+00   4.282123e-06     2.710131e-02  
    3   -5.499997e+00   0.000000e+00   1.221903e-10     6.939689e-07  
    4   -5.500000e+00   0.000000e+00   5.842173e-14     3.469847e-10  

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
x = 3×1

    0.0000
    1.0000
    0.0000

fval = -5.5000
exitflag = 1
output = struct with fields:
            message: '...'
          algorithm: 'interior-point-convex'
      firstorderopt: 1.5921e-09
    constrviolation: 0
         iterations: 4
       linearsolver: 'dense'
       cgiterations: []

Решите задачу квадратичного программирования и возвратите множители Лагранжа.

H = [1,-1,1
    -1,2,-2
    1,-2,4];
f = [-7;-12;-15];
A = [1,1,1];
b = 3;
lb = zeros(3,1);
[x,fval,exitflag,output,lambda] = quadprog(H,f,A,b,[],[],lb);
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

Исследуйте структуру множителя Лагранжа lambda.

disp(lambda)
    ineqlin: 12.0000
      eqlin: [0x1 double]
      lower: [3x1 double]
      upper: [3x1 double]

Линейное ограничение неравенства имеет связанный множитель Лагранжа 12.

Отобразите множители, сопоставленные с нижней границей.

disp(lambda.lower)
    5.0000
    0.0000
    0.0000

Только первый компонент lambda.lower имеет ненулевой множитель. Это обычно означает что только первый компонент x в нижней границе нуля. Подтвердите путем отображения компонентов x.

disp(x)
    0.0000
    1.5000
    1.5000

Ускориться последующий quadprog вызовы, создайте объект горячего запуска.

options = optimoptions('quadprog','Algorithm','active-set');
x0 = [1 2 3];
ws = optimwarmstart(x0,options);

Решите квадратичную программу с помощью ws.

H = [1,-1,1
    -1,2,-2
    1,-2,4];
f = [-7;-12;-15];
A = [1,1,1];
b = 3;
lb = zeros(3,1);
tic
[ws,fval,exitflag,output,lambda] = quadprog(H,f,A,b,[],[],lb,[],ws);
toc
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
Elapsed time is 0.021717 seconds.

Измените целевую функцию и решите задачу снова.

f = [-10;-15;-20];

tic
[ws,fval,exitflag,output,lambda] = quadprog(H,f,A,b,[],[],lb,[],ws);
toc
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
Elapsed time is 0.018485 seconds.

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

свернуть все

Квадратичный объективный термин в виде симметричной действительной матрицы. H представляет квадратичное в выражении   1/2*x'*H*x + f'*x. Если H не симметрично, quadprog выдает предупреждение и использует симметрированную версию (H + H')/2 вместо этого.

Если квадратичный матричный H разреженно, затем по умолчанию, 'interior-point-convex' алгоритм использует немного отличающийся алгоритм чем тогда, когда H является плотным. Обычно разреженный алгоритм быстрее на больших, разреженных проблемах, и плотный алгоритм быстрее на плотных или небольших проблемах. Для получения дополнительной информации смотрите LinearSolver описание опции и выпуклый внутренней точкой quadprog Алгоритм.

Пример: [2,1;1,3]

Типы данных: double

Линейный объективный термин в виде вектора действительных чисел. f представляет линейный член в выражении   1/2*x'*H*x + f'*x.

Пример: [1;3;2]

Типы данных: double

Линейные ограничения неравенства в виде действительной матрицы. A M- N матрица, где M количество неравенств и N количество переменных (число элементов в x0). Для больших проблем передайте A как разреженная матрица.

A кодирует M линейные неравенства

A*x <= b,

где x вектор-столбец N переменные x(:), и b вектор-столбец с M элементы.

Например, рассмотрите эти неравенства:

x 1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30,

Задайте неравенства путем ввода следующих ограничений.

A = [1,2;3,4;5,6];
b = [10;20;30];

Пример: Чтобы указать что x сумма компонентов к 1 или меньше, используйте A = ones(1,N) и b = 1.

Типы данных: double

Линейные ограничения неравенства в виде вектора действительных чисел. b M- вектор элемента связан с A матрица. Если вы передаете b как вектор-строка, решатели внутренне преобразуют b к вектор-столбцу b(:). Для больших проблем передайте b как разреженный вектор.

b кодирует M линейные неравенства

A*x <= b,

где x вектор-столбец N переменные x(:), и A матрица размера M- N.

Например, рассмотрите эти неравенства:

x 1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30.

Задайте неравенства путем ввода следующих ограничений.

A = [1,2;3,4;5,6];
b = [10;20;30];

Пример: Чтобы указать что x сумма компонентов к 1 или меньше, используйте A = ones(1,N) и b = 1.

Типы данных: double

Линейные ограничения равенства в виде действительной матрицы. Aeq Me- N матрица, где Me количество равенств и N количество переменных (число элементов в x0). Для больших проблем передайте Aeq как разреженная матрица.

Aeq кодирует Me линейные равенства

Aeq*x = beq,

где x вектор-столбец N переменные x(:), и beq вектор-столбец с Me элементы.

Например, рассмотрите эти неравенства:

x 1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x 3 = 20,

Задайте неравенства путем ввода следующих ограничений.

Aeq = [1,2,3;2,4,1];
beq = [10;20];

Пример: Чтобы указать что x сумма компонентов к 1, используйте Aeq = ones(1,N) и beq = 1.

Типы данных: double

Линейные ограничения равенства в виде вектора действительных чисел. beq Me- вектор элемента связан с Aeq матрица. Если вы передаете beq как вектор-строка, решатели внутренне преобразуют beq к вектор-столбцу beq(:). Для больших проблем передайте beq как разреженный вектор.

beq кодирует Me линейные равенства

Aeq*x = beq,

где x вектор-столбец N переменные x(:), и Aeq матрица размера Me- N.

Например, рассмотрите эти равенства:

x 1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x 3 = 20.

Задайте равенства путем ввода следующих ограничений.

Aeq = [1,2,3;2,4,1];
beq = [10;20];

Пример: Чтобы указать что x сумма компонентов к 1, используйте Aeq = ones(1,N) и beq = 1.

Типы данных: double

Нижние границы в виде вектора действительных чисел или действительного массива. Если число элементов в x0 равно числу элементов в lb, затем lb задает это

x(i) >= lb(i) для всех i.

Если numel(lb) < numel(x0), затем lb задает это

x(i) >= lb(i) для 1 <= i <= numel(lb).

Если lb имеет меньше элементов, чем x0, решатели выдают предупреждение.

Пример: Чтобы указать, что все x компоненты положительны, используйте lb = zeros(size(x0)).

Типы данных: double

Верхние границы в виде вектора действительных чисел или действительного массива. Если число элементов в x0 равно числу элементов в ub, затем ub задает это

x(i) <= ub(i) для всех i.

Если numel(ub) < numel(x0), затем ub задает это

x(i) <= ub(i) для 1 <= i <= numel(ub).

Если ub имеет меньше элементов, чем x0, решатели выдают предупреждение.

Пример: Чтобы указать, что все x компоненты меньше 1, используйте ub = ones(size(x0)).

Типы данных: double

Начальная точка в виде вектора действительных чисел. Длина x0 количество строк или столбцы H.

x0 применяется к 'trust-region-reflective' алгоритм, когда проблема только связала ограничения. x0 также применяется к 'active-set' алгоритм.

Примечание

x0 обязательный аргумент для 'active-set' алгоритм.

Если вы не задаете x0, quadprog наборы все компоненты x0 к точке во внутренней части поля, заданного границами. quadprog игнорирует x0 для 'interior-point-convex' алгоритм и для 'trust-region-reflective' алгоритм с ограничениями равенства.

Пример: [1;2;1]

Типы данных: double

Опции оптимизации в виде выхода optimoptions или структура такой как optimset возвращается.

Некоторые опции отсутствуют в optimoptions отображение. Эти опции появляются курсивом в следующей таблице. Для получения дополнительной информации, Опции вида на море.

Все алгоритмы

Algorithm

Выберите алгоритм:

  • 'interior-point-convex' (значение по умолчанию)

  • 'trust-region-reflective'

  • 'active-set'

'interior-point-convex' алгоритм решает только выпуклые проблемы. 'trust-region-reflective' алгоритм решает проблемы только с границами или только линейными ограничениями равенства, но не обоими. 'active-set' алгоритм решает неопределенные проблемы при условии, что проекция H на nullspace Aeq положителен полуопределенный. Для получения дополнительной информации смотрите Выбор Algorithm.

Диагностика

Отобразите диагностическую информацию о функции, которая будет минимизирована или решена. Выбором является 'on' или 'off' (значение по умолчанию).

Display

Level of display (см. Итеративное Отображение):

  • 'off' или 'none' не отображает вывода.

  • 'final' отображения только окончательный результат (значение по умолчанию).

'interior-point-convex' и 'active-set' алгоритмы позволяют дополнительные значения:

  • 'iter' задает итеративное отображение.

  • 'iter-detailed' задает итеративное отображение с подробным выходным сообщением.

  • 'final-detailed' отображает только окончательный вывод с подробным выходным сообщением.

MaxIterations

Максимальное количество итераций позволено; положительное целое число.

  • Для 'trust-region-reflective' ограниченная равенством проблема, значением по умолчанию является 2*(numberOfVariables – numberOfEqualities).

  • 'active-set' имеет значение по умолчанию 10*(numberOfVariables + numberOfConstraints).

  • Для всех других алгоритмов и проблем, значением по умолчанию является 200.

Для optimset, именем опции является MaxIter. Смотрите текущие и устаревшие имена опции.

OptimalityTolerance

Допуск завершения на оптимальности первого порядка; положительная скалярная величина.

  • Для 'trust-region-reflective' ограниченная равенством проблема, значением по умолчанию является 1e-6.

  • Для 'trust-region-reflective' связано ограниченная проблема, значением по умолчанию является 100*eps, о 2.2204e-14.

  • Для 'interior-point-convex' и 'active-set' алгоритмы, значением по умолчанию является 1e-8.

Смотрите допуски и критерий остановки.

Для optimset, именем опции является TolFun. Смотрите текущие и устаревшие имена опции.

StepTolerance

Допуск завершения на x; положительная скалярная величина.

  • Для 'trust-region-reflective', значением по умолчанию является 100*eps, о 2.2204e-14.

  • Для 'interior-point-convex', значением по умолчанию является 1e-12.

  • Для 'active-set', значением по умолчанию является 1e-8.

Для optimset, именем опции является TolX. Смотрите текущие и устаревшие имена опции.

'trust-region-reflective' Алгоритм только

FunctionTolerance

Допуск завершения на значении функции; положительная скалярная величина. Значение по умолчанию зависит от проблемного типа: связано ограниченные проблемы используют 100*eps, и линейные ограниченные равенством проблемы используют 1e-6. Смотрите допуски и критерий остановки.

Для optimset, именем опции является TolFun. Смотрите текущие и устаревшие имена опции.

HessianMultiplyFcn

Функция умножения Гессиана в виде указателя на функцию. Для крупномасштабных структурированных проблем эта функция вычисляет матричное произведение Гессиана H*Y на самом деле не формируя H. Функция имеет форму

W = hmfun(Hinfo,Y)

где Hinfo (и потенциально некоторые дополнительные параметры), содержат матрицы, использованные для расчета H*Y.

Смотрите Квадратичную Минимизацию с Плотным, Структурированным Гессианом для примера, который использует эту опцию.

Для optimset, именем опции является HessMult. Смотрите текущие и устаревшие имена опции.

MaxPCGIter

Максимальное количество PCG (предобусловленный метод сопряженных градиентов) итерации; положительная скалярная величина. Значением по умолчанию является max(1,floor(numberOfVariables/2)) для связано ограниченных проблем. Для ограниченных равенством проблем, quadprog игнорирует MaxPCGIter и использование MaxIterations ограничить количество итераций PCG. Для получения дополнительной информации смотрите Предобусловленный Метод сопряженных градиентов.

PrecondBandWidth

Верхняя полоса пропускания предварительного формирователя для PCG; неотрицательное целое число. По умолчанию, quadprog диагональ использования, предварительно обусловливающая (верхняя полоса пропускания 0). Для некоторых проблем, увеличивая полосу пропускания сокращает количество итераций PCG. Установка PrecondBandWidth к Inf использует прямую факторизацию (Холесский), а не методы сопряженных градиентов (CG). Прямая факторизация является в вычислительном отношении более дорогой, чем CG, но производит лучший качественный шаг к решению.

SubproblemAlgorithm

Определяет, как шаг итерации вычисляется. Значение по умолчанию, 'cg', делает более быстрый, но менее точный шаг, чем 'factorization'. См. "доверительную область, отражающую" quadprog Алгоритм.

TolPCG

Допуск завершения на итерации PCG; положительная скалярная величина. Значением по умолчанию является 0.1.

TypicalX

Типичный x значения. Число элементов в TypicalX равняется числу элементов в x0, начальная точка. Значением по умолчанию является ones(numberOfVariables,1). quadprog использование TypicalX внутренне для масштабирования. TypicalX оказывает влияние только когда x имеет неограниченные компоненты, и когда TypicalX значение для неограниченного компонента превышает 1.

'interior-point-convex' Алгоритм только

ConstraintTolerance

Допуск на нарушении ограничений; положительная скалярная величина. Значением по умолчанию является 1e-8.

Для optimset, именем опции является TolCon. Смотрите текущие и устаревшие имена опции.

LinearSolver

Тип внутреннего линейного решателя в алгоритме:

  • 'auto' (значение по умолчанию) — использует 'sparse' если H матрица разреженна и 'dense' в противном случае.

  • 'sparse' — Используйте линейную алгебру для разреженных матриц. Смотрите Разреженные матрицы.

  • 'dense' — Используйте плотную линейную алгебру.

'active-set' Алгоритм только

ConstraintTolerance

Допуск на нарушении ограничений; положительная скалярная величина. Значением по умолчанию является 1e-8.

Для optimset, именем опции является TolCon. Смотрите текущие и устаревшие имена опции.

ObjectiveLimit

Допуск (останавливающий критерий), который является скаляром. Если значение целевой функции понижается ObjectiveLimit и текущая точка выполнима, останов итераций, потому что проблема неограниченна, по-видимому. Значением по умолчанию является -1e20.

Структура задачи в виде структуры с этими полями:

H

Симметрическая матрица в 1/2*x'*H*x

f

Вектор в линейном члене f'*x

Aineq

Матрица в линейных ограничениях неравенства Aineq*x  bineq

bineq

Вектор в линейных ограничениях неравенства Aineq*x  bineq

Aeq

Матрица в линейных ограничениях равенства   Aeq*x = beq

beq

Вектор в линейных ограничениях равенства   Aeq*x = beq
lbВектор из нижних границ
ubВектор из верхних границ

x0

Начальная точка для x

solver

'quadprog'

options

Опции создали использование optimoptions или optimset

Обязательными полями является HF, solver, и options. При решении, quadprog игнорирует любые поля в problem кроме перечисленных.

Примечание

Вы не можете использовать горячий запуск с problem аргумент.

Типы данных: struct

Объект горячего запуска в виде объекта, созданного с помощью optimwarmstart. Объект горячего запуска содержит стартовую точку и опции и дополнительные данные для емкости памяти в генерации кода. Смотрите Лучшие практики Горячего запуска.

Пример: ws = optimwarmstart(x0,options)

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

свернуть все

Решение, возвращенное как вектор действительных чисел. x вектор, который минимизирует   1/2*x'*H*x + f'*x подвергните всем границам и линейным ограничениям. x может быть локальный минимум для невыпуклых проблем. Для выпуклых проблем, x глобальный минимум. Для получения дополнительной информации смотрите Локальный по сравнению с Глобальными оптимумами.

Объект горячего запуска решения, возвращенный как QuadprogWarmStart объект. Точкой решения является wsout.X.

Можно использовать wsout как входной горячий запуск возражают в последующем quadprog вызвать.

Значение целевой функции в решении, возвращенном как действительный скаляр. fval значение   1/2*x'*H*x + f'*x в решении x.

Обоснуйте quadprog остановленный, возвращенный как целое число, описанное в этой таблице.

Все алгоритмы

1

Функция сходилась к решению x.

0

Количество итераций превысило options.MaxIterations.

-2

Проблема неосуществима. Или, для 'interior-point-convex', размер шага был меньшим, чем options.StepTolerance, но ограничениям не удовлетворили.

-3

Проблема неограниченна.

'interior-point-convex' Алгоритм

2

Размер шага был меньшим, чем options.StepTolerance, ограничениям удовлетворили.

-6

Невыпуклая проблема обнаруживается.

-8

Не мог вычислить направление шага.

'trust-region-reflective' Алгоритм

4

Локальный минимум найден; минимум не уникален.

3

Изменение в значении целевой функции было меньшим, чем options.FunctionTolerance.

-4

Текущее поисковое направление не было направлением спуска. Никакие дальнейшие успехи не могли быть сделаны.

'active-set' Алгоритм

-6

Невыпуклая проблема обнаруживается; проекция H на nullspace Aeq не положителен полуопределенный.

Примечание

Иногда, 'active-set' алгоритм останавливается с выходным флагом 0 когда проблема, на самом деле, неограниченна. Установление более высокого предела итерации также приводит к выходному флагу 0.

Информация о процессе оптимизации, возвращенном как структура с этими полями:

iterations

Количество проделанных итераций

algorithm

Алгоритм оптимизации используется

cgiterations

Общее количество итераций PCG ('trust-region-reflective' только алгоритм)

constrviolation

Максимум ограничительных функций

firstorderopt

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

linearsolver

Тип внутреннего линейного решателя, 'dense' или 'sparse' ('interior-point-convex' только алгоритм)

message

Выходное сообщение

Множители Лагранжа в решении, возвращенном как структура с этими полями:

lower

Нижние границы lb

upper

Верхние границы ub

ineqlin

Линейные неравенства

eqlin

Линейные равенства

Для получения дополнительной информации смотрите Структуры множителя Лагранжа.

Алгоритмы

свернуть все

'interior-point-convex'

'interior-point-convex' алгоритм пытается следовать за путем, который является строго в ограничениях. Это использует предварительно решить модуль, чтобы удалить сокращение и упростить проблему путем решения для компонентов, которые являются прямыми.

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

'trust-region-reflective'

'trust-region-reflective' алгоритм является методом доверительной области подпространства на основе внутреннего отражающего метода Ньютона, описанного в [1]. Каждая итерация включает приближенное решение большой линейной системы с помощью метода предобусловленных методов сопряженных градиентов (PCG). Для получения дополнительной информации см. "доверительную область, отражающую" quadprog Алгоритм.

'active-set'

'active-set' алгоритм является методом проекции, похожим на тот, описанный в [2]. Алгоритм не является крупномасштабным; смотрите Крупномасштабный по сравнению с Алгоритмами Средней шкалы. Для получения дополнительной информации смотрите активный набор quadprog Алгоритм.

Горячий запуск

Объект горячего запуска ведет список активных ограничений от предыдущей решенной задачи. Решатель переносит как можно больше активной информации об ограничении, чтобы решить текущую задачу. Если предыдущая проблема слишком отличается от текущей, никакая активная информация о наборе не снова используется. В этом случае решатель эффективно выполняет холодный запуск для того, чтобы восстановить список активных ограничений.

Альтернативная функциональность

Приложение

Оптимизировать задача Live Editor обеспечивает визуальный интерфейс для quadprog.

Ссылки

[1] Коулман, T. F. и И. Ли. “Отражающий Метод Ньютона для Минимизации Квадратичной Функции Согласно Границам на Некоторых Переменных”. SIAM Journal на Оптимизации. Издание 6, Номер 4, 1996, стр 1040–1058.

[2] Жабры, P. E. В. Мюррей и М. Х. Райт. Практическая оптимизация. Лондон: Academic Press, 1981.

[3] Гулд, N. и П. Л. Тойнт. “Предварительно обрабатывая для квадратичного программирования”. Математическое программирование. Серии B, Издание 100, 2004, стр 95–132.

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

Представлено до R2006a