Exponenta Banner
exponenta event banner

Преобразовать проблему квадратичного программирования в программу второго порядка

Открыть сценарий в реальном времени

В этом примере показано, как преобразовать проблему положительного полуопределенного квадратичного программирования в форму конуса второго порядка, используемую coneprog решатель. Квадратичная проблема программирования имеет вид

minx12xTHx + fTx,

возможно, подвержен ограничениям и линейным ограничениям. coneprog решает проблемы в форме

minxfTx

такой, что

‖ Ascx-bsc‖≤dscx-γ,

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

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

A = sqrtm(H);

возвращает положительную полуопределенную матрицу A такой, что A'*A = A*A = H. Поэтому

xTHx = xTATAx = (Ax) TAx=‖Ax‖2.

Измените форму квадратичной программы следующим образом:

minx12xTHx + fTx = -12 + minx, t [(t + 1/2) + fTx]

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

t+1/2≥12xTHx.

Расширить управляющую переменную x до u, которая включает t в качестве последнего элемента:

u = [xt].

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

Asc = [A001]

bsc=[0⋮0]

dsc=[0⋮01]

γ=-1.

Удлините также вектор коэффициентов f:

fsc = [f1].

С точки зрения новых переменных, проблема квадратичного программирования становится

minu12uTAscu + fscTu = -1/2 + minu [1/2 + fscTu]

где

u (конец) +1/2≥12uTAscu.

Это квадратичное ограничение становится конусным через следующий расчет, который использует более ранние определения Asc, dsc и γ:

12uTAscu=12‖Hx‖2≤t+12

‖Hx‖2≤2t+1

‖ Hx‖2+t2≤t2+2t+1= (t + 1) 2

‖ Hx‖2+t2≤|t+1|=± (t + 1)

‖ u‖≤± (t-γ)

‖ u‖≤± (дск-γ).

Квадратичная программа имеет то же решение, что и соответствующая конусная программа. Единственное отличие - добавленный член -1/2 в конической программе.

Числовой пример

quadprog этот пример приведен в документации.

H = [1,-1,1
    -1,2,-2
    1,-2,4];
f = [-7;-12;-15];
lb = zeros(3,1);
ub = ones(size(lb));
Aineq = [1,1,1];
bineq = 3;
[xqp fqp] = quadprog(H,f,Aineq,bineq,[],[],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.

xqp = 3×1

     1
     1
     1


fqp = -32.5000

Ссылаясь на описание в начале этого примера, укажите переменные ограничения конуса второго порядка, а затем вызовите coneprog функция.

Asc = sqrtm(H);
Asc((end+1),(end+1)) = 1;
d = [zeros(size(f(:)));1];
gamma = -1;
b = zeros(size(d));
qp = secondordercone(Asc,b,d,gamma);
Aq = Aineq;
Aq(:,(end+1)) = 0;
lb(end+1) = -Inf;
ub(end+1) = Inf;
[u,fval,eflag] = coneprog([f(:);1],qp,Aq,bineq,[],[],lb,ub)
Optimal solution found.

u = 4×1

    1.0000
    1.0000
    1.0000
    1.0000


fval = -33.0000

eflag = 1

Первые три элемента конусного раствора u равны элементам решения квадратичного программирования xqp, для отображения точности:

disp([xqp,u(1:(end-1))])
    1.0000    1.0000
    1.0000    1.0000
    1.0000    1.0000

Возвращенное значение квадратичной функции fqp - возвращенное значение конуса минус 1/2, когда 2t + 1 является положительным, или плюс 1/2, когда 2t + 1 является отрицательным.

disp([fqp-sign(2*u(end)+1)*1/2 fval])
  -33.0000  -33.0000

См. также

| |

Связанные темы

Документация по панели инструментов оптимизации

Поддержка