将二次规划问题转化为二阶锥规划

打开生活的脚本

这个例子展示了如何将一个正的半定二次规划问题转化为二阶圆锥形式coneprog解算器。二次规划问题有这样的形式

$\underset{x}{最小值} \frac{1}{2} x^{T} H x + f^{T} x$ ，

可能受到边界和线性约束。coneprog解决表单中的问题

$\underset{x}{最小值} f_{年代 c}^{T} x$

这样

$为 {一个}_{年代 c} x - b_{年代 c} 为 \leq d_{年代 c}^{T} x - γ$ ，

可能受到边界和线性约束。

将二次程序转换为coneprog表格中，首先计算出矩阵的平方根 $H$ ．假设 $H$ 是对称正半定矩阵的命令吗

一个= sqrtm (H);

返回一个正的半定矩阵一个这样A'*A = A*A = h．因此,

$x^{T} H x ＝ x^{T} {一个}^{T} 一个 x ＝（一个 x ）^{T} 一个 x ＝为一个 x 为^{2}$ ．

将二次规划的形式修改如下:

$\underset{x}{最小值} \frac{1}{2} x^{T} H x + f^{T} x ＝ - \frac{1}{2} + \underset{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} ］$ ．

将二阶锥约束矩阵和向量扩展为:

${一个}_{sc} ＝［ \begin{array}{c} 一个 & 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} ］$ ．

用这些新变量表示二次规划问题

$\underset{u}{最小值} \frac{1}{2} u^{T} {一个}_{年代 c}^{2} u + f_{年代 c}^{T} u ＝ - 1 / 2 + \underset{u}{最小值} ［ 1 / 2 + f_{年代 c}^{T} u ］$

在哪里

$u （ e n d ） + 1 / 2 \geq \frac{1}{2} u^{T} {一个}_{年代 c} u$ ．

这个二次约束通过下面的计算变成了一个圆锥约束，其中使用了前面的定义 ${一个}_{年代 c}$ ， $d_{年代 c}$ , $γ$ ：

$\frac{1}{2} 为 H x 为^{2} ＝ \frac{1}{2} u^{T} {一个}_{年代 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} ＝为 {一个}_{年代 c} u 为^{2}$ ．所以,回忆 $γ ＝ - 1$ 定义是 $d_{年代 c}$ ，不等式就变成

$为 {一个}_{年代 c} u 为 \leq \pm （ t - γ ）$

$为 {一个}_{年代 c} u 为 \leq \pm （ d_{年代 c}^{T} u - γ ）$ ．

二次规划与相应的锥规划具有相同的解。唯一的区别是附加项 $- 1 / 2$ 在圆锥程序中。

数值例子

的quadprog文档给出了这个例子。

H = [1，-1,1 -1,2，-2 1，-2,4];f = [7, -12; -15);磅= 0 (3,1);乌兰巴托= 1(大小(磅));Aineq = (1 1 1);bineq = 3;[xqp fqp] = quprog (H,f,Aineq,bineq，[]，[]，lb,ub)

找到满足约束条件的最小值。由于目标函数在可行方向上不减小，达到最优容差的值，且约束条件满足于约束容差的值，从而完成了优化。

xqp =3×11 1 1

哲学基本问题= -32.5000

引用本示例开头的描述，指定二阶锥约束变量，然后调用coneprog函数。

Asc = sqrtm (H);Asc(+ 1)结束,结束(+ 1)= 1;d =[0(大小(f (:))); 1];γ= 1;b = 0(大小(d));qp = secondordercone (Asc, b, d,γ);Aq = Aineq;Aq (:, (+ 1) = 0;结束磅(+ 1)=无穷;乌兰巴托(结束+ 1)=正; [u,fval,eflag] = coneprog([f(:);1],qp,Aq,bineq,[],[],lb,ub)

找到最优解。

u =4×11.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/2时 $2 t + 1$ 是正的，还是+ 1/2 $2 t + 1$ 是负的。

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

-33.0000 - -33.0000

另请参阅

quadprog|coneprog|secondordercone

将二次规划问题转化为二阶锥规划

数值例子

另请参阅

相关的话题

优化工具箱的文档

金宝app

8 MATLAB数据科学备忘单