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

Открыть Live Script

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

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

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

$\min_{x} f^{T} x$

таким, что

$‖ A_{s c} x - b_{s c} ‖ \leq d_{s c} x - γ$ ,

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

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

A = sqrtm(H);

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

$x^{T} H x = x^{T} A^{T} A x = (A x)^{T} A x = ‖ A x ‖^{2}$ .

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

$\min_{x} \frac{1}{2} x^{T} H x + f^{T} x = - \frac{1}{2} + \min_{x, t} [(t + 1 / 2) + f^{T} x]$

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

$t + 1 / 2 \geq \frac{1}{2} x^{T} H x$ .

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

$u = [\begin{array}{c} x \\ t \end{array}]$ .

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

$A_{sc} = [\begin{array}{c} A & 0 \\ 0 & 1 \end{array}]$

$b_{sc} = [\begin{array}{c} 0 \\ ⋮ \\ 0 \end{array}]$

$d_{sc} = [\begin{array}{c} 0 \\ ⋮ \\ 0 \\ 1 \end{array}]$

$γ = - 1$ .

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

$f_{sc} = [\begin{array}{c} f \\ 1 \end{array}]$ .

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

$\min_{u} \frac{1}{2} u^{T} A_{s c} u + f_{s c}^{T} u = - 1 / 2 + \min_{u} [1 / 2 + f_{s c}^{T} u]$

где

$u (e n d) + 1 / 2 \geq \frac{1}{2} u^{T} A_{s c} u$ .

Это квадратичное ограничение становится ограничением конуса посредством следующего вычисления, которое использует более ранние определения $A_{s c}$ , $d_{s c}$ , и $γ$ :

$\frac{1}{2} u^{T} A_{s c} u = \frac{1}{2} ‖ H x ‖^{2} \leq t + \frac{1}{2}$

$‖ H x ‖^{2} \leq 2 t + 1$

$‖ H x ‖^{2} + t^{2} \leq t^{2} + 2 t + 1 = (t + 1)^{2}$

$\sqrt{‖ H x ‖^{2} + t^{2}} \leq | t + 1 | = \pm (t + 1)$

$‖ u ‖ \leq \pm (t - γ)$

$‖ u ‖ \leq \pm (d_{s c} - γ)$ .

Квадратичная программа имеет то же решение что и соответствующая конусная программа. Единственное различие - это добавленный термин $- 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.

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.

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, когда $2 t + 1$ положительно, или плюс 1/2, когда $2 t + 1$ отрицательно.

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

  -33.0000  -33.0000

См. также

coneprog | quadprog | secondordercone

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

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

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

См. также

Похожие темы

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

Поддержка