Преобразуйте квадратичную задачу программирования в программу конуса второго порядка

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

minx12xTHx+fTx,

возможно, удовлетворяющее границам и линейным ограничениям. coneprog решает задачи в форме

minxfTx

таким, что

Ascx-bscdscx-γ,

возможно, удовлетворяющее границам и линейным ограничениям.

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

A = sqrtm(H);

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

xTHx=xTATAx=(Ax)TAx=Ax2.

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

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

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

t+1/212xTHx.

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

u=[xt].

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

Asc=[A001]

bsc=[00]

dsc=[001]

γ=-1.

Расширьте вектор коэффициента f также:

fsc=[f1].

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

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

где

u(end)+1/212uTAscu.

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

12uTAscu=12Hx2t+12

Hx22t+1

Hx2+t2t2+2t+1=(t+1)2

Hx2+t2|t+1|=±(t+1)

u±(t-γ)

u±(dsc-γ).

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

Численный пример

The 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

См. также

| |

Похожие темы

Для просмотра документации необходимо авторизоваться на сайте