coneprog

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

Описание

coneprog функция является решателем программирования конуса второго порядка, который находит минимум проблемы заданным

minxfTx

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

Asc(i)xbsc(i)dкв/смT(i)xγ(i)AxbAeqx=beqlbxub.

f, x, b, beq, lb и ub являются векторами, и A и Aeq являются матрицами. Для каждого i, матричный кв/см A (i), векторы кв/см d (i) и кв/см b (i) и скалярный γ (i) находится в коническом ограничении второго порядка, что вы создаете использование secondordercone.

Для получения дополнительной информации о конических ограничениях, смотрите Коническое Ограничение Второго порядка.

пример

x = coneprog(f,socConstraints) решает коническую проблему программирования второго порядка с ограничениями в socConstraints закодированный как

  • Кв/см A (i) = socConstraints(i).A

  • Кв/см b (i) = socConstraints(i).b

  • Кв/см d (i) = socConstraints(i).d

  • γ (i) = socConstraints(i).gamma

пример

x = coneprog(f,socConstraints,A,b,Aeq,beq) решает задачу, удовлетворяющую ограничениям неравенства A*x  b и ограничения равенства   Aeq*x = beq. Установите   A = [] и   b = [] если никакие неравенства не существуют.

пример

x = coneprog(f,socConstraints,A,b,Aeq,beq,lb,ub) задает набор нижних и верхних границ на переменных проекта, x так, чтобы решением всегда был в области значений     lb ≤ x ≤ ub. Установите   Aeq = [] и   beq = [] если никакие равенства не существуют.

пример

x = coneprog(f,socConstraints,A,b,Aeq,beq,lb,ub,options) минимизирует использование опций оптимизации, заданных optionsИспользование optimoptions установить эти опции.

пример

x = coneprog(problem) находит минимум для problem, структура описана в problem.

пример

[x,fval] = coneprog(___) также возвращает значение целевой функции в решении fval = f'*x, использование любой из комбинаций входных аргументов в предыдущих синтаксисах.

пример

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

пример

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

Примеры

свернуть все

Чтобы настроить проблему с коническим ограничением второго порядка, создайте конический ограничительный объект второго порядка.

A = diag([1,1/2,0]);
b = zeros(3,1);
d = [0;0;1];
gamma = 0;
socConstraints = secondordercone(A,b,d,gamma);

Создайте вектор целевой функции.

f = [-1,-2,0];

Проблема не имеет никаких линейных ограничений. Создайте пустые матрицы для этих ограничений.

Aineq = [];
bineq = [];
Aeq = [];
beq = [];

Установите верхние и нижние границы на x(3).

lb = [-Inf,-Inf,0];
ub = [Inf,Inf,2];

Решите задачу при помощи coneprog функция.

[x,fval] = coneprog(f,socConstraints,Aineq,bineq,Aeq,beq,lb,ub)
Optimal solution found.
x = 3×1

    0.4851
    3.8806
    2.0000

fval = -8.2462

Компонент решения x(3) в его верхней границе. Коническое ограничение активно в решении:

norm(A*x-b) - d'*x % Near 0 when the constraint is active
ans = -2.5677e-08

Чтобы настроить проблему с несколькими коническими ограничениями второго порядка, создайте массив ограничительных объектов. Чтобы сэкономить время и память, создайте ограничение самого высокого индекса сначала.

A = diag([1,2,0]);
b = zeros(3,1);
d = [0;0;1];
gamma = -1;
socConstraints(3) = secondordercone(A,b,d,gamma);

A = diag([3,0,1]);
d = [0;1;0];
socConstraints(2) = secondordercone(A,b,d,gamma);

A = diag([0;1/2;1/2]);
d = [1;0;0];
socConstraints(1) = secondordercone(A,b,d,gamma);

Создайте линейный вектор целевой функции.

f = [-1;-2;-4];

Решите задачу при помощи coneprog функция.

[x,fval] = coneprog(f,socConstraints)
Optimal solution found.
x = 3×1

    0.4238
    1.6477
    2.3225

fval = -13.0089

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

f = [-4;-9;-2];
Asc = diag([1,4,0]);
b = [0;0;0];
d = [0;0;1];
gamma = 0;
socConstraints = secondordercone(Asc,b,d,gamma);

Задайте линейное ограничение неравенства.

A = [1/4,1/9,1];
b = 5;

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

[x,fval] = coneprog(f,socConstraints,A,b)
Optimal solution found.
x = 3×1

    3.2304
    0.6398
    4.1213

fval = -26.9225

Наблюдать итерации coneprog решатель, набор Display опция к 'iter'.

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

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

Asc = diag([1,1/2,0]);
b = zeros(3,1);
d = [0;0;1];
gamma = 0;
socConstraints = secondordercone(Asc,b,d,gamma);
f = [-1,-2,0];
Aineq = [];
bineq = [];
Aeq = [];
beq = [];
lb = [-Inf,-Inf,0];
ub = [Inf,Inf,2];
[x,fval] = coneprog(f,socConstraints,Aineq,bineq,Aeq,beq,lb,ub,options)
Iter           Fval  Primal Infeas    Dual Infeas    Duality Gap    Time
   1   0.000000e+00   0.000000e+00   5.714286e-01   1.250000e-01    0.02
   2  -7.558066e+00   0.000000e+00   7.151114e-02   1.564306e-02    0.02
   3  -7.366973e+00   0.000000e+00   1.075440e-02   2.352525e-03    0.02
   4  -8.243432e+00   0.000000e+00   5.191882e-05   1.135724e-05    0.02
   5  -8.246067e+00   0.000000e+00   2.430813e-06   5.317403e-07    0.02
   6  -8.246211e+00   1.387779e-17   6.154504e-09   1.346298e-09    0.02
Optimal solution found.
x = 3×1

    0.4851
    3.8806
    2.0000

fval = -8.2462

Создайте элементы конической проблемы программирования второго порядка. Чтобы сэкономить время и память, создайте ограничение самого высокого индекса сначала.

A = diag([1,2,0]);
b = zeros(3,1);
d = [0;0;1];
gamma = -1;
socConstraints(3) = secondordercone(A,b,d,gamma);
A = diag([3,0,1]);
d = [0;1;0];
socConstraints(2) = secondordercone(A,b,d,gamma);
A = diag([0;1/2;1/2]);
d = [1;0;0];
socConstraints(1) = secondordercone(A,b,d,gamma);
f = [-1;-2;-4];
options = optimoptions('coneprog','Display','iter');

Создайте структуру задачи с обязательными полями, как описано в проблеме.

problem = struct('f',f,...
    'socConstraints',socConstraints,...
    'Aineq',[],'bineq',[],...
    'Aeq',[],'beq',[],...
    'lb',[],'ub',[],...
    'solver','coneprog',...
    'options',options);

Решите задачу путем вызова coneprog.

[x,fval] = coneprog(problem)
Iter           Fval  Primal Infeas    Dual Infeas    Duality Gap    Time
   1   0.000000e+00   0.000000e+00   5.333333e-01   5.555556e-02    0.13
   2  -9.696012e+00   3.700743e-17   7.631901e-02   7.949897e-03    0.15
   3  -1.178942e+01   1.850372e-17   1.261803e-02   1.314378e-03    0.16
   4  -1.294426e+01   9.251859e-18   1.683078e-03   1.753206e-04    0.16
   5  -1.295217e+01   9.251859e-18   8.994595e-04   9.369370e-05    0.16
   6  -1.295331e+01   1.850372e-17   4.748841e-04   4.946709e-05    0.16
   7  -1.300753e+01   9.251859e-18   2.799942e-05   2.916606e-06    0.16
   8  -1.300671e+01   1.850372e-17   2.366136e-05   2.464725e-06    0.16
   9  -1.300850e+01   1.850372e-17   8.177405e-06   8.518130e-07    0.16
  10  -1.300843e+01   2.775558e-17   7.238840e-06   7.540459e-07    0.17
  11  -1.300866e+01   9.251859e-18   2.588453e-06   2.696305e-07    0.17
  12  -1.300892e+01   9.251859e-18   1.806333e-08   1.881597e-09    0.17
Optimal solution found.
x = 3×1

    0.4238
    1.6477
    2.3225

fval = -13.0089

Создайте коническую проблему программирования второго порядка. Чтобы сэкономить время и память, создайте ограничение самого высокого индекса сначала.

A = diag([1,2,0]);
b = zeros(3,1);
d = [0;0;1];
gamma = -1;
socConstraints(3) = secondordercone(A,b,d,gamma);
A = diag([3,0,1]);
d = [0;1;0];
socConstraints(2) = secondordercone(A,b,d,gamma);
A = diag([0;1/2;1/2]);
d = [1;0;0];
socConstraints(1) = secondordercone(A,b,d,gamma);
f = [-1;-2;-4];
options = optimoptions('coneprog','Display','iter');
A = [];
b = [];
Aeq = [];
beq = [];
lb = [];
ub = [];

Решите задачу, запросив информацию о процессе решения.

[x,fval,exitflag,output] = coneprog(f,socConstraints,A,b,Aeq,beq,lb,ub,options)
Iter           Fval  Primal Infeas    Dual Infeas    Duality Gap    Time
   1   0.000000e+00   0.000000e+00   5.333333e-01   5.555556e-02    0.06
   2  -9.696012e+00   3.700743e-17   7.631901e-02   7.949897e-03    0.08
   3  -1.178942e+01   1.850372e-17   1.261803e-02   1.314378e-03    0.08
   4  -1.294426e+01   9.251859e-18   1.683078e-03   1.753206e-04    0.08
   5  -1.295217e+01   9.251859e-18   8.994595e-04   9.369370e-05    0.08
   6  -1.295331e+01   1.850372e-17   4.748841e-04   4.946709e-05    0.09
   7  -1.300753e+01   9.251859e-18   2.799942e-05   2.916606e-06    0.09
   8  -1.300671e+01   1.850372e-17   2.366136e-05   2.464725e-06    0.09
   9  -1.300850e+01   1.850372e-17   8.177405e-06   8.518130e-07    0.09
  10  -1.300843e+01   2.775558e-17   7.238840e-06   7.540459e-07    0.09
  11  -1.300866e+01   9.251859e-18   2.588453e-06   2.696305e-07    0.09
  12  -1.300892e+01   9.251859e-18   1.806333e-08   1.881597e-09    0.09
Optimal solution found.
x = 3×1

    0.4238
    1.6477
    2.3225

fval = -13.0089
exitflag = 1
output = struct with fields:
           iterations: 12
    primalfeasibility: 9.2519e-18
      dualfeasibility: 1.8063e-08
           dualitygap: 1.8816e-09
            algorithm: 'interior-point'
         linearsolver: 'augmented'
              message: 'Optimal solution found.'

  • И итеративное отображение и структура output показывают тот coneprog используемый 12 итераций, чтобы найти решение.

  • Выходное флаговое значение 1 и output.message значение 'Optimal solution found.' укажите, что решение надежно.

  • output структура показывает, что infeasibilities имеют тенденцию уменьшаться посредством процесса решения, как делает разрыв дуальности.

  • Можно воспроизвести fval выведите путем умножения f'*x.

f'*x
ans = -13.0089

Создайте коническую проблему программирования второго порядка. Чтобы сэкономить время и память, создайте ограничение самого высокого индекса сначала.

A = diag([1,2,0]);
b = zeros(3,1);
d = [0;0;1];
gamma = -1;
socConstraints(3) = secondordercone(A,b,d,gamma);
A = diag([3,0,1]);
d = [0;1;0];
socConstraints(2) = secondordercone(A,b,d,gamma);
A = diag([0;1/2;1/2]);
d = [1;0;0];
socConstraints(1) = secondordercone(A,b,d,gamma);
f = [-1;-2;-4];

Решите задачу, запросив двойные переменные в решении наряду со всем другим coneprog вывод ..

[x,fval,exitflag,output,lambda] = coneprog(f,socConstraints);
Optimal solution found.

Исследуйте возвращенный lambda структура. Поскольку единственные ограничения задач являются коническими ограничениями, исследуют только soc поле в lambda структура.

disp(lambda.soc)
   1.0e-06 *

    0.1118
    0.3819
    0.2184

Ограничения имеют ненулевые двойные значения, указывая, что ограничения активны в решении.

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

свернуть все

Вектор коэффициентов в виде вектора действительных чисел или действительного массива. Вектор коэффициентов представляет целевую функцию f'*x. Обозначение принимает тот f вектор-столбец, но можно использовать вектор-строку или массив. Внутренне, coneprog преобразует f к вектор-столбцу f(:).

Пример: f = [1,3,5,-6]

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

Конические ограничения второго порядка в виде вектора из SecondOrderConeConstraint объекты. Создайте эти объекты с помощью secondordercone функция.

socConstraints кодирует ограничения

Asc(i)xbsc(i)dкв/смT(i)xγ(i)

где отображение между массивом и уравнением следующие:

  • Кв/см A (i) = socConstraints.A(i)

  • Кв/см b (i) = socConstraints.b(i)

  • Кв/см d (i) = socConstraints.d(i)

  • γ (i) = socConstraints.gamma(i)

Пример: Asc = diag([1 1/2 0]); bsc = zeros(3,1); dsc = [0;0;1]; gamma = -1; socConstraints = secondordercone(Asc,bsc,dsc,gamma);

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

Линейные ограничения неравенства в виде действительной матрицы. A M- N матрица, где M количество неравенств и N количество переменных (длина f). Для больших проблем передайте 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 количество переменных (длина f). Для больших проблем передайте 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

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

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

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

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

В этом случае решатели выдают предупреждение.

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

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

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

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

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

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

В этом случае решатели выдают предупреждение.

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

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

Опции оптимизации в виде выхода optimoptions.

ОпцияОписание
ConstraintTolerance

Допуск выполнимости к ограничениям, скаляру от 0 через 1. ConstraintTolerance измеряет основной допуск выполнимости. Значением по умолчанию является 1e-6.

Display

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

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

  • 'iter' отображает вывод в каждой итерации.

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

LinearSolver

Алгоритм для решения одного шага в итерации:

  • 'auto' (значение по умолчанию) — coneprog выбирает решатель шага.

    • Если проблема разреженна, решателем шага является 'prodchol'.

    • В противном случае решателем шага является 'augmented'.

  • 'augmented' — Увеличенный решатель шага формы. См. [1].

  • 'normal' — Решатель шага нормальной формы. См. [1].

  • 'prodchol' — Решатель шага Холесского формы продукта. См. [4] и [5].

  • 'schur' — Решатель шага метода дополнения Шура. См. [2].

Если 'auto' не выполняет хорошо, пробуют эти предложения за LinearSolver:

  • Если проблема разреженна, попробуйте 'normal'.

  • Если проблема разреженна с некоторыми плотными столбцами или большими конусами, попробуйте 'prodchol' или 'schur'.

  • Если проблема является плотной, используйте 'augmented'.

Для разреженного примера смотрите, Сравнивают Скорости coneprog Алгоритмов.

MaxIterations

Максимальное количество позволенных итераций, положительное целое число. Значением по умолчанию является 200.

Смотрите допуски и критерий остановки и итерации и функциональные количества.

MaxTime

Максимальное количество времени в секундах, которые алгоритм запускает, положительное число или Inf. Значением по умолчанию является Inf, который отключает этот критерий остановки.

OptimalityTolerance

Допуск завершения на двойной выполнимости, положительной скалярной величине. Значением по умолчанию является 1e-6.

Пример: optimoptions('coneprog','Display','iter','MaxIterations',100)

Структура задачи в виде структуры со следующими полями.

Имя поляЗапись

f

Линейный вектор целевой функции f

socConstraints

Массив структур конических ограничений второго порядка

Aineq

Матрица линейных ограничений неравенства

bineq

Вектор из линейных ограничений неравенства

Aeq

Матрица линейных ограничений равенства

beq

Вектор из линейных ограничений равенства
lbВектор из нижних границ
ubВектор из верхних границ

solver

'coneprog'

options

Опции, созданные с optimoptions

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

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

свернуть все

Решение, возвращенное как вектор действительных чисел или действительный массив. Размер x совпадает с размером f. x выход пуст когда exitflag значение является –2, –3, или –10.

Значение целевой функции в решении, возвращенном как вещественное число. Обычно fval = f'*x. fval выход пуст когда exitflag значение является –2, –3, или –10.

Причина coneprog остановленный, возвращенный как целое число.

ЗначениеОписание

1

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

0

Количество итераций превысило options.MaxIterations, или время решения в секундах превысило options.MaxTime.

-2

Никакая допустимая точка не была найдена.

-3

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

-7

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

-10

Проблема численно неустойчива.

Совет

Если вы получаете выходной флаг 0, -7, или -10, попытайтесь использовать различное значение LinearSolver опция.

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

Поле Описание
algorithm

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

dualfeasibility

Максимум двойных нарушений ограничений

dualitygap

Разрыв дуальности

iterations

Количество итераций

message

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

primalfeasibility

Максимум нарушений ограничений

linearsolverВнутренний алгоритм решателя шага используется

output поля dualfeasibility, dualitygap, и primalfeasibility пусты когда exitflag значение –2, –3, или –10.

Двойные переменные в решении, возвращенном как структура с этими полями.

Поле Описание
lower

Нижние границы, соответствующие lb

upper

Верхние границы, соответствующие ub

ineqlin

Линейные неравенства, соответствующие A и b

eqlin

Линейные равенства, соответствующие Aeq и beq

socКонические ограничения второго порядка, соответствующие socConstraints

lambda isempty) когда exitflag значение является –2, –3, или –10.

Множители Лагранжа (двойные переменные) являются частью следующей функции Лагранжа, которая является стационарной (нулевой градиент) в решении:

fTx+iλsoc(i)(dsocT(i)x\Gamma(i)Asoc(i)xbsoc(i))      +λineqlinT(bAx)+λeqlinT(Aeqxbeq)+λверхнийT(ubx)+λнижеT(xlb).

Термины неравенства, которые умножают lambda поля являются неотрицательными.

Больше о

свернуть все

Коническое ограничение второго порядка

Почему ограничение

AxbdTxγ

названный коническим ограничением второго порядка? Считайте конус в трехмерном пространстве с эллиптическими поперечными сечениями в x-y плоскостью и диаметром пропорциональный координате z. Координата y имеет шкалу ½, и координата x имеет шкалу 1. Неравенство, задающее внутреннюю часть этого конуса с его точкой в [0,0,0],

x2+y24z.

В coneprog синтаксис, этот конус имеет следующие аргументы.

A = diag([1 1/2 0]);
b = [0;0;0];
d = [0;0;1];
gamma = 0;

Постройте контур конуса.

[X,Y] = meshgrid(-2:0.1:2);
Z = sqrt(X.^2 + Y.^2/4);
surf(X,Y,Z)
view(8,2)
xlabel 'x'
ylabel 'y'
zlabel 'z'

Cone with point at zero, widening in the vertical direction.

b и gamma аргументы перемещают конус. A и d аргументы вращают конус и изменяют его форму.

Алгоритмы

Алгоритм использует метод внутренней точки. Для получения дополнительной информации смотрите, что Конус Второго порядка Программирует Алгоритм.

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

Приложение

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

Вопросы совместимости

развернуть все

Поведение изменяется в R2021a

Введенный в R2020b