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

ライブスクリプトを開く

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

$\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 = 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} 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} 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$ です。

数値例

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×11 1 1

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.

u =4×11.0000 1.0000 1.0000 1.0000

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

Optimization Toolbox ドキュメンテーション

サポート

データサイエンス向け MATLAB チートシート

チートシートをダウンロードして

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

数値例

参考

関連するトピック

Optimization Toolbox ドキュメンテーション

サポート

データサイエンス向け MATLAB チートシート