2 次制約から 2 次錐制約への変換

この例では、2 次制約を 2 次錐制約形式に変換する方法を示します。2 次制約の形式は次のとおりです。

$x^{T} Q x + 2 q^{T} x + c \leq 0 .$

2 次錐計画法の制約の形式は次のとおりです。

$‖ A_{s c} (i) \cdot x - b_{s c} (i) ‖ \leq d_{s c} (i) \cdot x - γ (i)$ .

2 次制約を変換するためには、行列 $Q$ が対称かつ半正定値でなければなりません。 $S$ を $Q = S * S = S^{T} * S$ を意味する $Q$ の平方根とします。sqrtm を使用して、 $S$ を計算します。方程式 $S^{T} b = - q$ の解 $b$ が存在するものとします。この解は、 $Q$ が正定値であれば常に真です。b = -S\q を使用して、 $b$ を計算します。

$\begin{array}{l} x^{T} Q x + 2 q^{T} x + c & = x^{T} S^{T} S x - 2 {(S^{T} b)}^{T} x + c \\ = {(S x - b)}^{T} (S x - b) - b^{T} b + c \\ = {‖ S x - b ‖}^{2} + c - b^{T} b . \end{array}$

そのため、 $b^{T} b > c$ の場合は、2 次制約が以下による 2 次錐制約と等しくなります。

$A_{s c} = S$
$b_{s c} = b$
$d_{s c} = 0$
$γ = - \sqrt{b^{T} b - c}$

数値の例

目的関数 $f^{T} x$ を表す 5 要素ベクトル f を指定します。

f = [1;-2;3;-4;5];

2 次制約行列 Q を 5 x 5 のランダム正定値行列として設定します。q をランダム 5 要素ベクトルとして設定し、付加定数 $c = - 1$ をとります。

rng default % For reproducibility
Q = randn(5) + 3*eye(5);
Q = (Q + Q')/2; % Make Q symmetric
q = randn(5,1);
c = -1;

coneprog の入力を作成するために、行列 S を Q の平方根として作成します。

S = sqrtm(Q);

この例の最初の部分で指定したように、2 次錐制約の残りの入力を作成します。

b = -S\q;
d = zeros(size(b));
gamma = -sqrt(b'*b-c);
sc = secondordercone(S,b,d,gamma);

coneprog を呼び出してこの問題を解きます。

[x,fval] = coneprog(f,sc)

Optimal solution found.

fval = -4.6148

この結果を、fmincon を使用して同じ問題を解くことによって得られる結果と比較します。非線形制約の無名関数で説明されているように、2 次制約を記述します。

x0 = randn(5,1); % Initial point for fmincon
nlc = @(x)x'*Q*x + 2*q'*x + c;
nlcon = @(x)deal(nlc(x),[]);
[xfmc,fvalfmc] = fmincon(@(x)f'*x,x0,[],[],[],[],[],[],nlcon)

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

xfmc = 5×1

   -0.7196
    0.2672
   -0.6312
    0.2541
   -0.0902

fvalfmc = -4.6148

2 つの解はほぼ同じです。

参考

coneprog | quadprog | secondordercone

2 次制約から 2 次錐制約への変換

数値の例

参考

関連するトピック