二次計画問題から 2 次錐問題への変換

ライブスクリプトを開く

この例では、半正定値二次計画問題を coneprog ソルバーで使用される 2 次錐形式に変換する方法を示します。二次計画問題の形式は次のとおりです。

$\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 = H となる半正定値行列 A を返します。したがって次のようになります。

$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}]$ .

2 次錐制約行列とベクトルを次のように拡張します。

$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$ .

この 2 次制約は、 $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

この例の冒頭の説明を参照しながら、2 次錐制約変数を指定してから、関数 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 の最初の 3 つの要素は、表示精度に対する二次計画法の解 xqp の要素と同じです。

disp([xqp,u(1:(end-1))])

    1.0000    1.0000
    1.0000    1.0000
    1.0000    1.0000

返される 2 次関数値 fqp は、 $2 t + 1$ が正の場合は返される錐の値 - 1/2 に、 $2 t + 1$ が負の場合は返される錐の値 + 1/2 になります。

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

  -33.0000  -33.0000

参考

quadprog | coneprog | secondordercone

二次計画問題から 2 次錐問題への変換

数値例

参考

関連するトピック