Этот пример показывает, как преобразовать положительную полуопределенную проблему квадратичного программирования в коническую форму второго порядка, используемую coneprog
решатель. Проблема квадратичного программирования имеет форму
,
возможно подвергните границам и линейным ограничениям. coneprog
решает задачи в форме
таким образом, что
,
возможно подвергните границам и линейным ограничениям.
Преобразовывать квадратичную программу в coneprog
сформируйте, сначала вычислите матричный квадратный корень из матрицы . Принятие этого симметричная положительная полуопределенная матрица, команда
A = sqrtm(H);
возвращает положительный полуопределенный матричный A
таким образом, что A'*A = A*A = H
. Поэтому
.
Измените форму квадратичной программы можно следующим образом:
где удовлетворяет ограничению
.
Расширьте контрольную переменную к , который включает как его последний элемент:
.
Расширьте конические ограничительные матрицы второго порядка и векторы можно следующим образом:
.
Расширьте вектор коэффициентов также:
.
В терминах новых переменных проблема квадратичного программирования становится
где
.
Это квадратичное ограничение становится коническим ограничением посредством следующего вычисления, которое использует более ранние определения , , и :
.
Квадратичная программа имеет то же решение как соответствующая коническая программа. Единственной разницей является добавленный термин в конической программе.
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 когда положительно, или плюс 1/2 когда отрицательно.
disp([fqp-sign(2*u(end)+1)*1/2 fval])
-33.0000 -33.0000
coneprog
| quadprog
| secondordercone