最新のリリースでは、このページがまだ翻訳されていません。 このページの最新版は英語でご覧になれます。

quadprog

二次計画法

構文

x = quadprog(H,f)

x = quadprog(H,f,A,b)

x = quadprog(H,f,A,b,Aeq,beq)

x = quadprog(H,f,A,b,Aeq,beq,lb,ub)

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)

x = quadprog(problem)

[x,fval] = quadprog(___)

[x,fval,exitflag,output] = quadprog(___)

[x,fval,exitflag,output,lambda] = quadprog(___)

説明

線形制約がある二次目的関数のソルバーです。

quadprog は、次によって指定される問題の最小値を求めます。

$$\underset{x}{\min }\frac{1}{2}{x}^{T}Hx+f^{T}x\text{ such that }\{\begin{array}{c}A\cdot x\le b,\\ Aeq\cdot x=beq,\\ lb\le x\le ub.\end{array}$$

H、A、Aeq は行列、f、b、beq、lb、ub、x はベクトルです。

f、lb および ub はベクトルまたは行列として渡すことができます。行列引数を参照してください。

メモ

quadprog は、ソルバーベースのアプローチのみに適用されます。2 つの最適化アプローチの詳細については、はじめに問題ベース アプローチまたはソルバーベース アプローチを選択を参照してください。

x = quadprog(H,f) は、1/2*x'*H*x + f'*x を最小化するベクトル x を返します。入力 H は、有限の最小値をもつ問題の場合には正定でなければなりません。H が正定である場合、解は x = H\(-f) です。

x = quadprog(H,f,A,b) は、A*x ≤ b という制約の下で1/2*x'*H*x + f'*x を最小化します。入力 A は double の行列、b は double のベクトルです。

x = quadprog(H,f,A,b,Aeq,beq) は追加の制約 Aeq*x = beq に従って上記の問題を解きます。Aeq は double 型の行列で、beq は double 型のベクトルです。不等式が存在しない場合は A = [] および b = [] と設定してください。

x = quadprog(H,f,A,b,Aeq,beq,lb,ub) は、lb ≤  x≤ ub という追加制約の下で上記の問題を解きます。入力 lb および ub は double のベクトルであり、制約は x の各成分に適用されます。等式が存在しない場合には Aeq = [] と beq = [] を設定してください。

メモ

問題の指定された入力範囲が矛盾する場合、出力 x は x0、出力 fval は [] です。

quadprog は、範囲 lb ≤ x ≤ ub に違反する x0 の要素を、この範囲で定義されたボックスの内部にリセットします。quadprog は、範囲内の要素を変更しません。

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0) は上記の問題をまず x0 から解いていきます。範囲が存在しない場合には lb = [] および ub = [] を設定します。一部の quadprog のアルゴリズムでは x0 が無視されます。x0 を参照してください。

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options) は、options で指定された最適化オプションを使用して上記の問題を解きます。optimoptions を使用して options を作成してください。初期点を与えない場合は x0 = [] を設定します。

x = quadprog(problem) は、problem の最小値を返します。ここで、problem は説明で説明されている構造体です。最適化アプリを使用して問題をエクスポートすることで problem を作成します。作業のエクスポートを参照してください。または、prob2struct を使用して OptimizationProblem オブジェクトから構造体 problem を作成します。

[x,fval] = quadprog(___) は、どの入力変数についても、x における目的関数の値 fval も返します。

fval = 0.5*x'*H*x + f'*x

[x,fval,exitflag,output] = quadprog(___) は、quadprog の終了条件を記述する整数 exitflag と、最適化に関数情報が含まれている構造体 output も返します。

[x,fval,exitflag,output,lambda] = quadprog(___) は、解 x におけるラグランジュ乗数がフィールドに含まれている構造体 lambda も返します。

例

線形制約がある二次計画法

次の関数の最小値を求めます。

$$f(x)=\frac{1}{2}{x}_1^2+x_2^2-x_1{x}_2-2x_1-6x_2$$

以下の制約に従います。

$$\begin{array}{l}{x}_1+x_2\le 2\\ -x_1+2x_2\le 2\\ 2x_1+x_2\le 3\end{array}$$

quadprog の構文では、この問題は次を最小化することです。

$$f(x)=\frac{1}{2}{x}^{T}Hx+f^{T}x$$

ここで、

$$\begin{array}{l}\mathit{H}=\left[\begin{array}{cc}1& -1\\ -1& 2\end{array}\right]\\ \mathit{f}=\left[\begin{array}{c}-2\\ -6\end{array}\right]\end{array}$$

これには線形制約が適用されます。

この問題を解くため、まず係数行列を入力します。

H = [1 -1; -1 2]; 
f = [-2; -6];
A = [1 1; -1 2; 2 1];
b = [2; 2; 3];

quadprog を呼び出します。

[x,fval,exitflag,output,lambda] = ...
   quadprog(H,f,A,b);

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.

最終点、関数の値、および終了フラグを調べます。

x,fval,exitflag

x = 2×1

    0.6667
    1.3333

fval = -8.2222

exitflag = 1

終了フラグが 1 の場合、その結果は局所的最小値です。H は正定行列であるため、この問題は凸であり、最小値は大域的最小値です。

固有値をチェックして、H が正定であることを確認します。

eig(H)

ans = 2×1

    0.3820
    2.6180

線形等式制約がある二次計画法

次の関数の最小値を求めます。

$$f(x)=\frac{1}{2}{x}_1^2+x_2^2-x_1{x}_2-2x_1-6x_2$$

制約は以下になります。

$$x_1+x_2=0$$

quadprog の構文では、この問題は次を最小化することです。

$$f(x)=\frac{1}{2}{x}^{T}Hx+f^{T}x$$

ここで、

$$\begin{array}{l}\mathit{H}=\left[\begin{array}{cc}1& -1\\ -1& 2\end{array}\right]\\ \mathit{f}=\left[\begin{array}{c}-2\\ -6\end{array}\right]\end{array}$$

これには線形制約が適用されます。

この問題を解くため、まず係数行列を入力します。

H = [1 -1; -1 2]; 
f = [-2; -6];
Aeq = [1 1];
beq = 0;

入力 A および b に [] を指定して quadprog を呼び出します。

[x,fval,exitflag,output,lambda] = ...
   quadprog(H,f,[],[],Aeq,beq);

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.

最終点、関数の値、および終了フラグを調べます。

x,fval,exitflag

x = 2×1

   -0.8000
    0.8000

fval = -1.6000

exitflag = 1

終了フラグが 1 の場合、その結果は局所的最小値です。H は正定行列であるため、この問題は凸であり、最小値は大域的最小値です。

固有値をチェックして、H が正定であることを確認します。

eig(H)

ans = 2×1

    0.3820
    2.6180

線形制約と範囲がある二次最小化

二次式を最小化する x を求めます。

$$\frac{1}{2}{x}^{T}Hx+f^{T}x$$

ここで、

$\mathit{H}=\left[\begin{array}{ccc}1& -1& 1\\ -1& 2& -2\\ 1& -2& 4\end{array}\right]$, $\mathit{f}=\left[\begin{array}{c}2\\ -3\\ 1\end{array}\right]$

以下の制約に従います。

$$0\le x\le 1$$, $$\sum x=1/2$$

この問題を解くため、まず係数を入力します。

H = [1,-1,1
    -1,2,-2
    1,-2,4];
f = [2;-3;1];
lb = zeros(3,1);
ub = ones(size(lb));
Aeq = ones(1,3);
beq = 1/2;

入力 A および b に [] を指定して quadprog を呼び出します。

x = quadprog(H,f,[],[],Aeq,beq,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.

x = 3×1

    0.0000
    0.5000
    0.0000

既定以外のオプションによる二次最小化

quadprog の進行状況を監視するオプションを設定します。

options = optimoptions('quadprog','Display','iter');

二次目的関数と線形不等式制約がある問題を定義します。

H = [1 -1; -1 2]; 
f = [-2; -6];
A = [1 1; -1 2; 2 1];
b = [2; 2; 3];

関数 quadprog の呼び出しの記述に役立てるため、不要な入力を [] に設定します。

Aeq = [];
beq = [];
lb = [];
ub = [];
x0 = [];

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

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)

 Iter            Fval  Primal Infeas    Dual Infeas  Complementarity  
    0   -8.884885e+00   3.214286e+00   1.071429e-01     1.000000e+00  
    1   -8.331868e+00   1.321041e-01   4.403472e-03     1.910489e-01  
    2   -8.212804e+00   1.676295e-03   5.587652e-05     1.009601e-02  
    3   -8.222204e+00   8.381476e-07   2.793826e-08     1.809485e-05  
    4   -8.222222e+00   3.019807e-14   1.352696e-12     7.525735e-13  

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.

x = 2×1

    0.6667
    1.3333

prob2struct からの二次問題

問題ベースのワークフローを使用して構造体 problem を作成します。線形制約がある二次計画法と等価な最適化問題を作成します。

x = optimvar('x',2);
objec = x(1)^2/2 + x(2)^2 - x(1)*x(2) - 2*x(1) - 6*x(2);
prob = optimproblem('Objective',objec);
prob.Constraints.cons1 = sum(x) <= 2;
prob.Constraints.cons2 = -x(1) + 2*x(2) <= 2;
prob.Constraints.cons3 = 2*x(1) + x(2) <= 3;

prob を構造体 problem に変換します。

problem = prob2struct(prob);

quadprog を使用して、問題を解きます。

[x,fval] = quadprog(problem)

Warning: Your Hessian is not symmetric. Resetting H=(H+H')/2.

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.

x = 2×1

    0.6667
    1.3333

fval = -8.2222

quadprog の目的関数の値の取得

二次計画法を解き、解と目的関数の値の両方を取得します。

H = [1,-1,1
    -1,2,-2
    1,-2,4];
f = [-7;-12;-15];
A = [1,1,1];
b = 3;
[x,fval] = quadprog(H,f,A,b)

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.

x = 3×1

   -3.5714
    2.9286
    3.6429

fval = -47.1786

返された目的関数の値と quadprog の目的関数定義から計算された値が一致するかどうかをチェックします。

fval2 = 1/2*x'*H*x + f'*x

fval2 = -47.1786

quadprog の最適化プロセスの確認

quadprog の最適化プロセスを表示するため、反復表示を行うオプションを設定し、4 つの出力を取得します。問題は、次を最小化することです。

$$\frac{1}{2}{x}^{T}Hx+f^{T}x$$

制約条件

$$0\le x\le 1$$

ここで、

$\mathit{H}=\left[\begin{array}{ccc}2& 1& -1\\ 1& 3& \frac{1}{2}\\ -1& \frac{1}{2}& 5\end{array}\right]$, $\mathit{f}=\left[\begin{array}{c}4\\ -7\\ 12\end{array}\right]$

問題の係数を入力します。

H = [2 1 -1
    1 3 1/2
    -1 1/2 5];
f = [4;-7;12];
lb = zeros(3,1);
ub = ones(3,1);

ソルバーの反復処理の進行状況を表示するオプションを設定します。

options = optimoptions('quadprog','Display','iter');

4 つの出力で quadprog を呼び出します。

[x fval,exitflag,output] = quadprog(H,f,[],[],[],[],lb,ub,[],options)

 Iter            Fval  Primal Infeas    Dual Infeas  Complementarity  
    0    2.691769e+01   1.582123e+00   1.712849e+01     1.680447e+00  
    1   -3.889430e+00   0.000000e+00   8.564246e-03     9.971731e-01  
    2   -5.451769e+00   0.000000e+00   4.282123e-06     2.710131e-02  
    3   -5.499997e+00   0.000000e+00   1.221903e-10     6.939689e-07  
    4   -5.500000e+00   0.000000e+00   5.842173e-14     3.469847e-10  

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.

x = 3×1

    0.0000
    1.0000
    0.0000

fval = -5.5000

exitflag = 1

output = struct with fields:
            message: '...'
          algorithm: 'interior-point-convex'
      firstorderopt: 1.5921e-09
    constrviolation: 0
         iterations: 4
       linearsolver: 'dense'
       cgiterations: []

quadprog のラグランジュ乗数の取得

二次計画問題を解き、ラグランジュ乗数を取得します。

H = [1,-1,1
    -1,2,-2
    1,-2,4];
f = [-7;-12;-15];
A = [1,1,1];
b = 3;
lb = zeros(3,1);
[x,fval,exitflag,output,lambda] = quadprog(H,f,A,b,[],[],lb);

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.

ラグランジュ乗数の構造体 lambda を確認します。

disp(lambda)

    ineqlin: 12.0000
      eqlin: [0x1 double]
      lower: [3x1 double]
      upper: [3x1 double]

線形不等式制約に関連付けられたラグランジュ乗数は 12 です。

下限に関連付けられた乗数を表示します。

disp(lambda.lower)

    5.0000
    0.0000
    0.0000

lambda.lower の 1 番目の成分のみで乗数が非ゼロです。一般に、これは x の 1 番目の成分のみが下限ゼロにあることを意味します。x の成分を表示して確認します。

disp(x)

    0.0000
    1.5000
    1.5000

入力引数

H — 目的関数の二次項

対称実数行列

目的関数の二次項。対称実数行列を指定します。H は、式 1/2*x'*H*x + f'*x の二次項を表します。H が対称ではない場合、quadprog は警告を生成し、対称化されたバージョンの (H + H')/2 を代わりに使用します。

二次項行列 H がスパースである場合、既定により 'interior-point-convex' アルゴリズムは、H が密である場合とは多少異なるアルゴリズムを使用します。一般に、スパースのアルゴリズムは大規模なスパース問題でより高速で、密のアルゴリズムは密または小規模な問題でより高速です。詳細については、LinearSolver オプションの説明とinterior-point-convex quadprog アルゴリズムを参照してください。

例: [2,1;1,3]

データ型: double

f — 目的関数の線形項

実数ベクトル

目的関数の線形項。実数ベクトルを指定します。f は、式 1/2*x'*H*x + f'*x の線形項を表します。

例: [1;3;2]

データ型: double

A — 線形不等式制約

実数行列

実数行列として指定される線形不等式制約です。A は M 行 N 列の行列で、M は不等式の数、N は変数の数 (x0 の要素数) です。大規模な問題の場合は、A をスパース行列として渡します。

A は M 個の線形不等式を符号化します。

A*x <= b

ここで、x は N 個の変数 x(:) の列ベクトル、b は M 個の要素をもつ列ベクトルです。

たとえば、次を指定します。

x₁ + 2x₂ ≤ 10
3x₁ + 4x₂ ≤ 20
5x₁ + 6x₂ ≤ 30,

次の制約を入力します。

A = [1,2;3,4;5,6];
b = [10;20;30];

例: x の成分の和が 1 以下であることを指定するには、A = ones(1,N) と b = 1 を使用します。

データ型: double

b — 線形不等式制約

実数ベクトル

実数ベクトルで指定される線形不等式制約です。b は、行列 A に関連する M 要素ベクトルです。b を行ベクトルとして渡す場合、ソルバーは b を列ベクトル b(:) に内部的に変換します。大規模な問題の場合は、b をスパース ベクトルとして渡します。

b は M 個の線形不等式を符号化します。

A*x <= b

ここで、x は N 個の変数 x(:) の列ベクトル、A は M 行 N 列の行列です。

たとえば、次を指定します。

x₁ + 2x₂ ≤ 10
3x₁ + 4x₂ ≤ 20
5x₁ + 6x₂ ≤ 30,

次の制約を入力します。

A = [1,2;3,4;5,6];
b = [10;20;30];

例: x の成分の和が 1 以下であることを指定するには、A = ones(1,N) と b = 1 を使用します。

データ型: double

Aeq — 線形等式制約

実数行列

実数行列として指定される線形等式制約です。Aeq は Me 行 N 列の行列で、Me は等式の数、N は変数の数 (x0 の要素数) です。大規模な問題の場合は、Aeq をスパース行列として渡します。

Aeq は Me 個の線形等式を符号化します。

Aeq*x = beq

ここで、x は N 個の変数 x(:) の列ベクトル、beq は Me 個の要素をもつ列ベクトルです。

たとえば、次を指定します。

x₁ + 2x₂ + 3x₃ = 10
2x₁ + 4x₂ + x₃ = 20,

次の制約を入力します。

Aeq = [1,2,3;2,4,1];
beq = [10;20];

例: x の成分の和が 1 であることを指定するには、Aeq = ones(1,N) と beq = 1 を使用します。

データ型: double

beq — 線形等式制約

実数ベクトル

実数ベクトルで指定される線形等式制約です。beq は、行列 Aeq に関連する Me 要素ベクトルです。beq を行ベクトルとして渡す場合、ソルバーは beq を列ベクトル beq(:) に内部的に変換します。大規模な問題の場合は、beq をスパース ベクトルとして渡します。

beq は Me 個の線形等式を符号化します。

Aeq*x = beq

ここで、x は N 個の変数 x(:) の列ベクトル、Aeq は Me 行 N 列の行列です。

たとえば、次を指定します。

x₁ + 2x₂ + 3x₃ = 10
2x₁ + 4x₂ + x₃ = 20,

次の制約を入力します。

Aeq = [1,2,3;2,4,1];
beq = [10;20];

例: x の成分の和が 1 であることを指定するには、Aeq = ones(1,N) と beq = 1 を使用します。

データ型: double

lb — 下限

実数ベクトル | 実数配列

下限。実数ベクトルまたは実数配列として指定されます。x0 の要素数と lb の要素数が等しい場合、lb は次を指定します。

x(i) >= lb(i) (すべての i について)

numel(lb) < numel(x0) の場合、lb は次を指定します。

x(i) >= lb(i) (1 <= i <= numel(lb))

x0 より lb の要素数が少ない場合、ソルバーは警告を生成します。

例: x のすべての成分が正であることを指定するには、lb = zeros(size(x0)) を使用します。

データ型: double

ub — 上限

実数ベクトル | 実数配列

実数ベクトルまたは実数配列として指定される上限です。x0 の要素数と ub の要素数が等しい場合、ub は次を指定します。

x(i) <= ub(i) (すべての i について)

numel(ub) < numel(x0) の場合、ub は次を指定します。

x(i) <= ub(i) (1 <= i <= numel(ub))

x0 より ub の要素数が少ない場合、ソルバーは警告を生成します。

例: x のすべての成分が 1 未満であることを指定するには、ub = ones(size(x0)) を使用します。

データ型: double

x0 — 初期点

実数ベクトル

初期点。実数ベクトルを指定します。この入力はオプションです。範囲制約しかない場合、x0 は 'trust-region-reflective' アルゴリズムのみに適用されます。

x0 を指定しない場合、quadprog では x0 のすべての成分が、範囲によって定義される四角形内部の点に設定されます。'interior-point-convex' アルゴリズムと、等式制約をもつ 'trust-region-reflective' アルゴリズムでは、quadprog は x0 を無視します。

例: [1;2;1]

データ型: double

options — 最適化オプション

optimoptions の出力 | optimset などによって返される構造体

最適化オプション。optimoptions の出力、または optimset などによって返される構造体として指定されます。

一部のオプションは、optimoptions に表示されません。このようなオプションは、次の表ではイタリックで示されています。詳細は、表示オプションを参照してください。

すべてのアルゴリズム

Algorithm	アルゴリズムを選択します。 'interior-point-convex' (既定の設定) 'trust-region-reflective' 'interior-point-convex' アルゴリズムは凸問題のみを扱います。'trust-region-reflective' アルゴリズムは、範囲制約のみがある問題または線形等式制約のみがある問題を扱いますが、両方がある問題には対応しません。詳細は、アルゴリズムの選択を参照してください。
Diagnostics	最小化または計算する関数に関する情報を表示します。選択肢は 'on' または 'off' (既定の設定) です。
Display	表示レベル (反復表示を参照): 'off' または 'none' — 出力を表示しない。 'final' (既定) — 最終出力のみを表示する。 'interior-point-convex' アルゴリズムでは、次の値も指定できます。 'iter' は反復表示を指定します。 'iter-detailed' は反復表示と詳細な終了メッセージを指定します。 'final-detailed' は最終出力のみと詳細な終了メッセージを表示します。
MaxIterations	可能な最大反復回数。正の整数。 'trust-region-reflective' 等式制約付き問題の場合、既定値は 2*(numberOfVariables - numberOfEqualities) です。 他のすべてのアルゴリズムおよび問題については、既定値は 200 です。 optimset の場合、オプションの名前は MaxIter です。詳細は、オプション名の新旧対照表を参照してください。
OptimalityTolerance	1 次の最適性に対する終了許容誤差。正のスカラー。 'trust-region-reflective' 等式制約付き問題の場合、既定値は 1e-6 です。 範囲制約付きの 'trust-region-reflective' 問題の場合、既定値は 100*eps、約 2.2204e-14 です。 'interior-point-convex' アルゴリズムの場合、既定値は 1e-8 です。 詳細は、許容誤差と停止条件を参照してください。 optimset の場合、オプションの名前は TolFun です。詳細は、オプション名の新旧対照表を参照してください。
StepTolerance	x に対する許容誤差。正のスカラー。 'trust-region-reflective' の場合、既定値は 100*eps、約 2.2204e-14 です。 'interior-point-convex' の場合、既定値は 1e-12 です。 optimset の場合、オプションの名前は TolX です。詳細は、オプション名の新旧対照表を参照してください。

'trust-region-reflective' アルゴリズムのみ

FunctionTolerance	関数値に対する終了許容誤差。正のスカラー。既定値は問題のタイプに依存します。範囲制約付き問題では 100*eps が、線形等式制約付き問題では 1e-6 が使用されます。詳細は、許容誤差と停止条件を参照してください。 optimset の場合、オプションの名前は TolFun です。詳細は、オプション名の新旧対照表を参照してください。
HessianMultiplyFcn	ヘッセ乗算関数。関数ハンドルとして指定されます。大規模構造問題に対して、この関数は実際に H を作らずにヘッセ行列の乗数 H*Y を計算します。関数は次に示す形式になります。 W = hmfun(Hinfo,Y) Hinfo (および一部の追加パラメーター) には、H*Y の計算に使用される行列を格納します。 たこのオプションを使用する例は 密な構造化されたヘッシアンを使った二次最小化 を参照してください。 optimset の場合、オプションの名前は HessMult です。詳細は、オプション名の新旧対照表を参照してください。
MaxPCGIter	PCG (前処理付き共役勾配) 法の最大反復回数。正のスカラー。範囲制約付き問題の場合の既定値は max(1,floor(numberOfVariables/2)) です。等式制約付き問題の場合、quadprog は MaxPCGIter を無視し、MaxIterations を使用して PCG の反復回数を制限します。詳細は、前処理付き共役勾配法を参照してください。
PrecondBandWidth	PCG に対する前提条件子の帯域幅の上限。非負の整数。既定の設定では、quadprog は対角型をした前提条件を使用します (帯域幅の上限 0)。一部の問題では、帯域幅を上げることで、PCG 法の反復回数を減らします。PrecondBandWidth を Inf に設定すると、共役勾配 (CG) ではなく、直接因子分解 (コレスキー因子) が使用されます。直接因子分解では CG より計算量が増加しますが、解を求めるためのステップの質が向上します。
SubproblemAlgorithm	反復ステップの計算方法を定義します。既定の設定である 'cg' のステップは 'factorization' より高速ですが、精度の点で劣ります。詳細は、trust-region-reflective quadprog アルゴリズムを参照してください。
TolPCG	PCG の反復に対する終了許容誤差。正のスカラー。既定値は 0.1 です。
TypicalX	典型的な x の値です。TypicalX の要素数は、開始点 x0 の要素数と等しくなります。既定値は ones(numberOfVariables,1) です。quadprog はスケーリング用に TypicalX を内部的に使用します。TypicalX は、x に非有界の成分をもつ場合や、非有界の成分 TypicalX 値が 1 より大きい場合にのみ有効です。

'interior-point-convex' アルゴリズムのみ

ConstraintTolerance	制約違反に対する許容誤差。正のスカラー。既定値は 1e-8 です。 optimset の場合、オプションの名前は TolCon です。詳細は、オプション名の新旧対照表を参照してください。
LinearSolver	アルゴリズムの内部的な線形ソルバーのタイプ 'auto' (既定) — 行列 H がスパースである場合は 'sparse'、そうでない場合は 'dense' を使用。 'sparse' — スパースな線形代数を使用。詳細は、スパース行列 (MATLAB)を参照してください。 'dense' — 密な線形代数を使用。

problem — 問題構造体

構造体

問題構造体。次のフィールドをもつ構造体を指定します。

H	1/2*x'*H*x の対称行列
f	線形項 f'*x のベクトル
Aineq	線形不等式制約 Aineq*x ≤ bineq の行列
bineq	線形不等式制約 Aineq*x ≤ bineq のベクトル
Aeq	線形等式制約 Aeq*x = beq の行列
beq	線形等式制約 Aeq*x = beq のベクトル
lb	下限のベクトル
ub	上限のベクトル
x0	x の初期点
solver	'quadprog'
options	optimoptions または最適化アプリを使用して作成されるオプション

必須フィールドは H、f、solver および options です。quadprog は、解を求めるときに、リストされているもの以外の problem のフィールドを無視します。

データ型: struct

出力引数

x — 解

実数ベクトル

解。実数ベクトルとして返されます。x は、すべての範囲制約および線形制約に従って 1/2*x'*H*x + f'*x を最小化するベクトルです。非凸問題の場合、x は局所的最小値である可能性があります。凸問題の場合、x は大域的最小値です。詳細は、大域的最適解と局所的最適解を参照してください。

fval — 解での目的関数値

実数スカラー

解における目的関数の値。実数スカラーとして返されます。fval は、解 x における 1/2*x'*H*x + f'*x の値です。

exitflag — quadprog の停止理由

整数

quadprog の停止理由。次の表で説明する整数として返されます。

すべてのアルゴリズム
1	関数が解 x に収束したことを示します。
0	反復数が options.MaxIterations を超過しています。
-2	問題が実行不可能です。または、'interior-point-convex' の場合、ステップ サイズは options.StepTolerance より小さいが、制約は満たされませんでした。
-3	問題が非有界です。
'interior-point-convex' アルゴリズム
2	ステップ サイズが options.StepTolerance より小さく、制約が満たされました。
-6	非凸問題が検出されました。
-8	ステップ方向を計算できません。
'trust-region-reflective' アルゴリズム
4	局所的最小値が見つかりました。最小値は一意ではありません。
3	目的関数値の変更が options.FunctionTolerance よりも小さくなったことを示します。
-4	現在の探索方向は減少の方向ではなく、これ以上進むことができないことを示します。

output — 最適化プロセスに関する情報

構造体

最適化プロセスに関する情報。次のフィールドをもつ構造体として返されます。

iterations	実行した反復回数
algorithm	使用される最適化アルゴリズム
cgiterations	PCG 法の合計反復回数 ('trust-region-reflective' アルゴリズムのみ)
constrviolation	制約関数の最大値
firstorderopt	1 次の最適性の尺度
linearsolver	内部的な線形ソルバーのタイプ、'dense' または 'sparse' ('interior-point-convex' アルゴリズムのみ)
message	終了メッセージ

lambda — 解におけるラグランジュ乗数

構造体

解におけるラグランジュ乗数。次のフィールドをもつ構造体として返されます。

lower	下限 lb
upper	上限 ub
ineqlin	線形不等式
eqlin	線形等式

詳細は、ラグランジュ乗数構造体を参照してください。

アルゴリズム

'interior-point-convex'

'interior-point-convex' アルゴリズムは、厳密に制約内にある経路をたどろうと試みます。このアルゴリズムは前処理モジュールを使用して重複を取り除き、簡単な要素について問題を解くことによって問題を単純化します。

アルゴリズムは、スパース ヘッセ行列 H の場合と、密行列の場合では、実装が異なります。一般に、スパース実装は大規模なスパース問題でより高速で、密実装は密または小規模な問題でより高速です。詳細は、interior-point-convex quadprog アルゴリズムを参照してください。

'trust-region-reflective'

'trust-region-reflective' アルゴリズムは部分空間の信頼領域法であり、[1] で説明されている interior-reflective ニュートン法に基づいています。各反復は、前処理付き共役勾配 (PCG) 法を使用する大型線形システムの近似解を伴います。詳細は、trust-region-reflective quadprog アルゴリズムを参照してください。

代替機能

アプリ

二次計画法には最適化アプリを使用できます。MATLAB^® のコマンド ラインに optimtool と入力し、[quadprog - 二次計画法] ソルバーを選択してください。詳細は、最適化アプリを参照してください。

問題ベースのアプローチ

問題ベースの最適化の設定を使用して二次計画問題を解くことができます。例については、二次計画法を参照してください。

参照

[1] Coleman, T. F., and Y. Li. “A Reflective Newton Method for Minimizing a Quadratic Function Subject to Bounds on Some of the Variables.” SIAM Journal on Optimization. Vol. 6, Number 4, 1996, pp. 1040–1058.

[2] Gill, P. E., W. Murray, and M. H. Wright. Practical Optimization. London: Academic Press, 1981.

[3] Gould, N., and P. L. Toint. “Preprocessing for quadratic programming.” Mathematical Programming. Series B, Vol. 100, 2004, pp. 95–132.

参考

linprog | lsqlin | optimoptions | prob2struct

トピック

• ソルバーベースの最適化問題の設定
• 最適化の結果
• 二次計画法
• 混合整数二次計画法ポートフォリオ最適化問題: ソルバーベース

R2006a より前に導入

×

Open Example (ja_JP)

A modified version of this example exists on your system. Do you want to open this version instead? (ja_JP)

No, overwrite the modified version (ja_JP) Yes (ja_JP)