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

Скрипт Open Live Script

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

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

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

$\min_{x} f_{s c}^{T} x$

таким образом, что

$‖ A_{s c} x - b_{s c} ‖ \leq d_{s c}^{T} 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}^{2} 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} ‖ H x ‖^{2} = \frac{1}{2} u^{T} A_{s c}^{2} u \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)$

Но $‖ H x ‖^{2} + t^{2} = ‖ A_{s c} u ‖^{2}$ . Так, вспоминание этого $γ = - 1$ и определение $d_{s c}$ , неравенство становится

$‖ A_{s c} u ‖ \leq \pm (t - γ)$

$‖ A_{s c} u ‖ \leq \pm (d_{s c}^{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.

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

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

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

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

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

Похожие темы

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

Поддержка