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(___)

[wsout,fval,exitflag,output,lambda] = quadprog(H,f,A,b,Aeq,beq,lb,ub,ws)

説明

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

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 を参照してください。

メモ

x0 は 'active-set' アルゴリズムに必須の引数です。

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

x = quadprog(problem) は、problemで説明されている構造体 problem の最小値を返します。ドット表記または struct 関数を使用して 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 も返します。

[wsout,fval,exitflag,output,lambda] = quadprog(H,f,A,b,Aeq,beq,lb,ub,ws) は、ws のオプションを使用し、ウォーム スタート オブジェクト ws の中のデータから quadprog を起動します。返された引数 wsout は、wsout.X の解点を含みます。この後のソルバーの呼び出しで、最初のウォーム スタート オブジェクトとして wsout を使用することにより、quadprog の動作は速くなります。

例

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

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

$$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.064216e-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: 'Minimum found that satisfies the constraints....'
          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

ウォーム スタート オブジェクトを返す

この後の quadprog の呼び出しを高速化するために、ウォーム スタート オブジェクトを作成します。

options = optimoptions('quadprog','Algorithm','active-set');
x0 = [1 2 3];
ws = optimwarmstart(x0,options);

ws を使用して二次計画法を解きます。

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

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.

<stopping criteria details>

toc

Elapsed time is 0.060411 seconds.

目的関数を変更し、再び問題を解きます。

f = [-10;-15;-20];

tic
[ws,fval,exitflag,output,lambda] = quadprog(H,f,A,b,[],[],lb,[],ws);

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.

<stopping criteria details>

toc

Elapsed time is 0.010756 seconds.

入力引数

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))

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

例: 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))

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

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

データ型: double

x0 — 初期点

実数ベクトル

初期点。実数ベクトルを指定します。x0 の長さは、H の行数または列数です。

問題に範囲制約のみがある場合、x0 は 'trust-region-reflective' アルゴリズムに適用されます。x0 は、'active-set' アルゴリズムにも適用されます。

メモ

x0 は 'active-set' アルゴリズムに必須の引数です。

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

'active-set' アルゴリズムのみ

ConstraintTolerance	制約違反に関する許容誤差 (非負のスカラー)。既定値は 1e-8 です。 optimset の場合、オプションの名前は TolCon です。詳細については、新旧のオプション名を参照してください。
ObjectiveLimit	スカラーの許容誤差 (停止条件) です。目的関数値が ObjectiveLimit を下回り、現在の点が実行可能な場合、問題が非有界であると推定されるため、その反復は中止されます。既定値は -1e20 です。

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 または optimset を使用して作成されたオプション

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

メモ

引数 problem とウォーム スタートを一緒に使用することはできません。

データ型: struct

ws — ウォーム スタート オブジェクト

optimwarmstart を使用して作成されたオブジェクト

ウォーム スタート オブジェクト。optimwarmstart で作成したオブジェクトとして指定します。ウォーム スタート オブジェクトには、開始点とオプションに加え、コード生成におけるメモリ サイズ用のオプション データが含まれます。詳細については、ウォーム スタートのベスト プラクティスを参照してください。

例: ws = optimwarmstart(x0,options)

出力引数

x — 解

実数ベクトル

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

wsout — 解ウォーム スタート オブジェクト

QuadprogWarmStart オブジェクト

解ウォーム スタート オブジェクト。QuadprogWarmStart オブジェクトとして返されます。解点は wsout.X です。

この後の quadprog の呼び出しでは、wsout を入力ウォーム スタート オブジェクトとして使用できます。

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	現在の探索方向は減少の方向ではなく、これ以上進むことができないことを示します。
'active-set' アルゴリズム
-6	非凸問題が検出されました。Aeq のヌル空間に対する H の投影が半正定値ではありません。

メモ

問題が実際には非有界のとき、'active-set' アルゴリズムは終了フラグ 0 で停止することがあります。反復制限を高く設定した場合も、終了フラグ 0 になります。

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 アルゴリズムを参照してください。

'active-set'

'active-set' アルゴリズムは、[2]で説明されているものと同様の投影方法です。このアルゴリズムは大規模ではありません。大規模アルゴリズムと中規模アルゴリズムを参照してください。詳細については、active-set quadprog アルゴリズムを参照してください。

ウォーム スタート

ウォーム スタート オブジェクトは、前回解いた問題のアクティブな制約のリストを維持します。ソルバーは、アクティブな制約情報を可能な限り多く引き継いで、現在の問題を解きます。前回の問題と現在の問題が違いすぎる場合、アクティブ セットの情報は再利用されません。この場合、ソルバーは効率的にコールド スタートを実行して、アクティブな制約のリストを再構築します。

代替機能

アプリ

[最適化] ライブ エディター タスクが 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.

拡張機能

C/C++ コード生成

MATLAB® Coder™ を使用して C および C++ コードを生成します。

使用上の注意および制限

• quadprog は、関数 codegen (MATLAB Coder) または MATLAB^® Coder™ アプリを使用したコード生成をサポートしています。コードを生成するには MATLAB Coder ライセンスが必要です。

• ターゲット ハードウェアは、標準的な倍精度浮動小数点計算をサポートしていなければなりません。単精度計算や固定小数点計算のコードは生成できません。

• コード生成ターゲットは、MATLAB ソルバーと同じ数学カーネル ライブラリを使用しません。そのため、コード生成解法は、特に、条件付けが不十分な問題の場合に、ソルバー解法と異なる可能性があります。

• コード生成の場合、quadprog は problem 引数をサポートしていません。

  [x,fval] = quadprog(problem) % Not supported

• quadprog の入力行列 (A、Aeq、lb、ub など) はすべてフル (非スパース) でなければなりません。関数 full を使用することで、スパース行列を非スパースに変換できます。

• lb 引数と ub 引数は、H の列数と同じ数のエントリをもつか、空 [] でなければなりません。

• ターゲット ハードウェアが無限境界をサポートしていない場合は、optim.coder.infbound を使用します。

• 組み込みプロセッサを使用する高度なコード最適化には、Embedded Coder^® ライセンスも必要です。

• quadprog のオプションを含め、関数 optimoptions を使用して指定しなければなりません。オプションには Algorithm オプションを含め、'active-set' に設定しなければなりません。

  options = optimoptions('quadprog','Algorithm','active-set');
  [x,fval,exitflag] = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options);

• コード生成では次のオプションをサポートしています。

  • Algorithm — 'active-set' でなければなりません

  • ConstraintTolerance

  • MaxIterations

  • ObjectiveLimit

  • OptimalityTolerance

  • StepTolerance

• 生成コードでは、オプションに対して限られたエラー チェックしか行われません。オプションの更新方法として、ドット表記ではなく、optimoptions を使用することを推奨します。

  opts = optimoptions('quadprog','Algorithm','active-set');
  opts = optimoptions(opts,'MaxIterations',1e4); % Recommended
  opts.MaxIterations = 1e4; % Not recommended

• オプションはファイルから読み込まないでください。そうした場合、コード生成に失敗することがあります。代わりに、コード内でオプションを作成してください。

• サポートされていないオプションを指定すると、通常はコード生成の際にそのオプションは無視されます。信頼できる結果を得るために、サポートされているオプションのみを指定します。

例については、quadprog のコード生成を参照してください。

バージョン履歴

R2006a より前に導入

参考

linprog | lsqlin | optimoptions | prob2struct | 最適化 | optimwarmstart

トピック

• ソルバーベースの最適化問題の設定
• 最適化の結果
• 二次計画法と錐計画法
• ウォーム スタートのベスト プラクティス
• 混合整数二次計画法ポートフォリオ最適化問題: ソルバーベース