quadprog

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

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

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

$\min_{x} \frac{}{12} x^{T} H x + f^{T} x таким образом , что {\begin{matrix} A \cdot x \leq b, \\ A e q \cdot x = b e q, \\ l b \leq x \leq u b . \end{matrix}$

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

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

Примечание

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

Синтаксис

x = quadprog(H,f)

x = quadprog(H,f,A,b)

x = quadprog(H,f,A,b,Aeq,beq)

x = quadprog(H,f,A,b,Aeq,beq,lb,ub)

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)

x = quadprog(problem)

[x,fval]
= quadprog(___)

[x,fval,exitflag,output]
= quadprog(___)

[x,fval,exitflag,output,lambda]
= quadprog(___)

Описание

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.

пример

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

пример

x = quadprog(problem) возвращает минимум для problem, где problem является структурой, описанной в Описании. Создайте problem путем экспорта проблемы с помощью приложения Оптимизации; смотрите Экспорт Вашей работы. Также создайте структуру 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.

Примеры

свернуть все

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

Скрипт Open Live Script

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

$f (x) = \frac{1}{2} x_{1}^{2} + x_{2}^{2} - x_{1} x_{2} - 2 x_{1} - 6 x_{2}$

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

$\begin{array}{l} x_{1} + x_{2} \leq 2 \\ - x_{1} + 2 x_{2} \leq 2 \\ 2 x_{1} + x_{2} \leq 3 . \end{array}$

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

$f (x) = \frac{1}{2} x^{T} H x + f^{T} x$ ,

где

$\begin{array}{l} H = [\begin{matrix} 1 & - 1 \\ - 1 & 2 \end{matrix}] \\ f = [\begin{matrix} - 2 \\ - 6 \end{matrix}], \end{array}$

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

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

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

fval = -8.2222

exitflag = 1

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

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

eig(H)

ans = 2×1

    0.3820
    2.6180

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

Скрипт Open Live Script

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

$f (x) = \frac{1}{2} x_{1}^{2} + x_{2}^{2} - x_{1} x_{2} - 2 x_{1} - 6 x_{2}$

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

$x_{1} + x_{2} = 0 .$

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

$f (x) = \frac{1}{2} x^{T} H x + f^{T} x$ ,

где

$\begin{array}{l} H = [\begin{matrix} 1 & - 1 \\ - 1 & 2 \end{matrix}] \\ f = [\begin{matrix} - 2 \\ - 6 \end{matrix}], \end{array}$

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

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

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

fval = -1.6000

exitflag = 1

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

eig(H)

ans = 2×1

    0.3820
    2.6180

Квадратичная минимизация с линейными ограничениями и границами

Скрипт Open Live Script

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

$\frac{1}{2} x^{T} H x + f^{T} x$

где

$H = [\begin{matrix} 1 & - 1 & 1 \\ - 1 & 2 & - 2 \\ 1 & - 2 & 4 \end{matrix}]$ , $f = [\begin{matrix} 2 \\ - 3 \\ 1 \end{matrix}]$ ,

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

$0 \leq x \leq 1$ , $\sum 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.

Квадратичная минимизация с опциями не по умолчанию

Скрипт Open Live Script

Установите опции контролировать прогресс 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.

Квадратичная проблема от `prob2struct`

Скрипт Open Live Script

Создайте структуру 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.

fval = -8.2222

Возвратите значение целевой функции `quadprog`

Скрипт Open Live Script

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

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.

fval = -47.1786

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

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

fval2 = -47.1786

Исследуйте процесс оптимизации `quadprog`

Скрипт Open Live Script

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

$\frac{1}{2} x^{T} H x + f^{T} x$

подвергающийся

$0 \leq x \leq 1$ ,

где

$H = [\begin{matrix} 2 & 1 & - 1 \\ 1 & 3 & \frac{1}{2} \\ - 1 & \frac{1}{2} & 5 \end{matrix}]$ , $f = [\begin{matrix} 4 \\ - 7 \\ 12 \end{matrix}]$ .

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

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.

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: []

Возвратите множители Лагранжа `quadprog`

Скрипт Open Live Script

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

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

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

свернуть все

`H` Квадратичный объективный термин
симметричная действительная матрица

Квадратичный объективный термин, заданный как симметричная действительная матрица. 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` Линейный объективный термин
вектор действительных чисел

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

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

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

`A` Линейные ограничения неравенства
действительная матрица

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

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

A*x <= b,

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

Например, чтобы задать

x ₁ + 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` Линейные ограничения неравенства
вектор действительных чисел

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

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

A*x <= b,

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

Например, чтобы задать

x ₁ + 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` — Линейные ограничения равенства
действительная матрица

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

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

Aeq*x = beq,

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

Например, чтобы задать

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

введите эти ограничения:

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

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

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

`beq` — Линейные ограничения равенства
вектор действительных чисел

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

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

Aeq*x = beq,

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

Например, чтобы задать

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

введите эти ограничения:

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

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

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

`lb` — Нижние границы
вектор действительных чисел | действительный массив

Нижние границы, заданные как вектор действительных чисел или действительный массив. Если число элементов в 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

`ub` — Верхние границы
вектор действительных чисел | действительный массив

Верхние границы, заданные как вектор действительных чисел или действительный массив. Если число элементов в 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` Начальная точка
вектор действительных чисел

Начальная точка, заданная как вектор действительных чисел. Этот вход является дополнительным. x0 применяется только к алгоритму 'trust-region-reflective', когда существуют только связанные ограничения.

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

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

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

`опции` Опции оптимизации
вывод `optimoptions` | структура, такая как `optimset` возвращается

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

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

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

`Algorithm`	Выберите алгоритм: `'interior-point-convex'` (значение по умолчанию) `'trust-region-reflective'` Алгоритм `'interior-point-convex'` решает только выпуклые проблемы. Алгоритм `'trust-region-reflective'` решает проблемы только с границами или только линейными ограничениями равенства, но не обоими. Для получения дополнительной информации смотрите Выбор Algorithm.
Диагностика	Отобразите диагностическую информацию о функции, которая будет минимизирована или решена. Выбором является `'on'` или `'off'` (значение по умолчанию).
`Display`	Уровень отображения (см. Итеративное Отображение): `'off'` или `'none'` не отображают вывода. `'final'` отображает только окончательный вывод (значение по умолчанию). Алгоритм `'interior-point-convex'` позволяет дополнительные значения: `'iter'` задает итеративное отображение. `'iter-detailed'` задает итеративное отображение с подробным выходным сообщением. `'final-detailed'` отображает только окончательный вывод с подробным выходным сообщением.
`MaxIterations`	Максимальное количество итераций позволено; положительное целое число. Для `'trust-region-reflective'` ограниченная равенством проблема значением по умолчанию является `2*(numberOfVariables - numberOfEqualities)`. Для всех других алгоритмов и проблем, значением по умолчанию является `200`. Для `optimset` именем опции является `MaxIter`. См. Текущие и Устаревшие Таблицы Имени Опции.
`OptimalityTolerance`	Допуск завершения на оптимальности первого порядка; положительная скалярная величина. Для `'trust-region-reflective'` ограниченная равенством проблема значением по умолчанию является `1e-6`. Для `'trust-region-reflective'` связано ограниченная проблема значением по умолчанию является `100*eps` о `2.2204e-14`. Для алгоритмов `'interior-point-convex'` значением по умолчанию является `1e-8`. Смотрите допуски и критерий остановки. Для `optimset` именем опции является `TolFun`. См. Текущие и Устаревшие Таблицы Имени Опции.
`StepTolerance`	Допуск завершения на `x`; положительная скалярная величина. Для `'trust-region-reflective'` значением по умолчанию является `100*eps` о `2.2204e-14`. Для `'interior-point-convex'` значением по умолчанию является `1e-12`. Для `optimset` именем опции является `TolX`. См. Текущие и Устаревшие Таблицы Имени Опции.

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

`FunctionTolerance`	Допуск завершения на значении функции; положительная скалярная величина. Значение по умолчанию зависит от проблемного типа: связано ограниченные проблемы используют `100*eps`, и линейные ограниченные равенством проблемы используют `1e-6`. Смотрите Допуски и Критерий остановки. Для `optimset` именем опции является `TolFun`. См. Текущие и Устаревшие Таблицы Имени Опции.
`HessianMultiplyFcn`	Гессиан умножает функцию, заданную как указатель на функцию. Для крупномасштабных структурированных проблем эта функция вычисляет матричное произведение Гессиана `HY`, на самом деле не формируя `H`. Функция имеет форму W = hmfun(Hinfo,Y) то, где `Hinfo` (и потенциально некоторые дополнительные параметры) содержит матрицы, раньше вычисляло `HY`. Смотрите Квадратичную Минимизацию с Плотным, Структурированным Гессианом для примера, который использует эту опцию. Для `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' в противном случае.
разреженный Используйте линейную алгебру для разреженных матриц. Смотрите Разреженные матрицы (MATLAB).
'dense' — Используйте плотную линейную алгебру.

`problem` — Структура задачи
структура

Структура задачи, заданная как структура с этими полями:

`H`	Симметрическая матрица в `1/2x'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` или приложения Оптимизации

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

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

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

свернуть все

`x` Решение
вектор действительных чисел

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

`fval` Значение целевой функции в решении
действительный скаляр

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

`exitflag` Обоснуйте остановленный `quadprog`
целое число

Обоснуйте, что остановленный 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	Текущее поисковое направление не было направлением спуска. Никакие дальнейшие успехи не могли быть сделаны.

`вывод` Информация о процессе оптимизации
структура

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

`iterations`	Количество проделанных итераций
`algorithm`	Алгоритм оптимизации используется
`cgiterations`	Общее количество итераций PCG (только алгоритм `'trust-region-reflective'`)
`constrviolation`	Максимум ограничительных функций
`firstorderopt`	Мера оптимальности первого порядка
`linearsolver`	Тип внутреннего линейного решателя, `'dense'` или `'sparse'` (только алгоритм `'interior-point-convex'`)
`message`	Выходное сообщение

`\lambda` Множители Лагранжа в решении
структура

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

`lower`	Нижние границы `lb`
`upper`	Верхние границы `ub`
`ineqlin`	Линейные неравенства
`eqlin`	Линейные равенства

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

Алгоритмы

свернуть все

'выпуклый внутренней точкой'

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

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

'доверяйте отражающей области'

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

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

Приложение

Можно использовать приложение Оптимизации для квадратичного программирования. Введите optimtool в командной строке MATLAB^® и выберите решатель quadprog - Quadratic programming. Для получения дополнительной информации см. Приложение Оптимизации.

Основанный на проблеме подход

Можно решить проблемы квадратичного программирования с помощью Основанного на проблеме Setup Оптимизации. Для примеров смотрите Квадратичное программирование.

Ссылки

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

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

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

Документация

quadprog

Примечание

Синтаксис

Описание

Примечание

Примеры

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

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

Квадратичная минимизация с линейными ограничениями и границами

Квадратичная минимизация с опциями не по умолчанию

Квадратичная проблема от prob2struct

Возвратите значение целевой функции quadprog

Исследуйте процесс оптимизации quadprog

Возвратите множители Лагранжа quadprog

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

H Квадратичный объективный термин симметричная действительная матрица

f Линейный объективный термин вектор действительных чисел

A Линейные ограничения неравенства действительная матрица

b Линейные ограничения неравенства вектор действительных чисел

Aeq — Линейные ограничения равенства действительная матрица

beq — Линейные ограничения равенства вектор действительных чисел

lb — Нижние границы вектор действительных чисел | действительный массив

ub — Верхние границы вектор действительных чисел | действительный массив

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

опции Опции оптимизации вывод optimoptions | структура, такая как optimset возвращается

problem — Структура задачи структура

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

x Решение вектор действительных чисел

fval Значение целевой функции в решении действительный скаляр

exitflag Обоснуйте остановленный quadprog целое число

вывод Информация о процессе оптимизации структура

\lambda Множители Лагранжа в решении структура

Алгоритмы

'выпуклый внутренней точкой'

'доверяйте отражающей области'

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

Приложение

Основанный на проблеме подход

Ссылки

Смотрите также

Темы

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

Документация Optimization Toolbox

Поддержка

Квадратичная проблема от `prob2struct`

Возвратите значение целевой функции `quadprog`

Исследуйте процесс оптимизации `quadprog`

Возвратите множители Лагранжа `quadprog`

`H` Квадратичный объективный термин
симметричная действительная матрица

`f` Линейный объективный термин
вектор действительных чисел

`A` Линейные ограничения неравенства
действительная матрица

`b` Линейные ограничения неравенства
вектор действительных чисел

`Aeq` — Линейные ограничения равенства
действительная матрица

`beq` — Линейные ограничения равенства
вектор действительных чисел

`lb` — Нижние границы
вектор действительных чисел | действительный массив

`ub` — Верхние границы
вектор действительных чисел | действительный массив

`x0` Начальная точка
вектор действительных чисел

`опции` Опции оптимизации
вывод `optimoptions` | структура, такая как `optimset` возвращается

`problem` — Структура задачи
структура

`x` Решение
вектор действительных чисел

`fval` Значение целевой функции в решении
действительный скаляр

`exitflag` Обоснуйте остановленный `quadprog`
целое число

`вывод` Информация о процессе оптимизации
структура

`\lambda` Множители Лагранжа в решении
структура