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 は、ソルバーベースのアプローチのみに適用されます。問題ベースのアプローチの場合は、solve を使用してください。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.

<stopping criteria details>

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

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.

<stopping criteria details>

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

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.

<stopping criteria details>

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   4.190781e-11   1.396827e-12     9.047989e-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.

<stopping criteria details>

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.

<stopping criteria details>

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.

<stopping criteria details>

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.499995e+00   0.000000e+00   2.878422e-10     1.750743e-06  
    4   -5.500000e+00   0.000000e+00   1.454808e-13     8.753723e-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.

<stopping criteria details>

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.↵↵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>↵↵Optimization completed: The relative dual feasibility, 1.212340e-14,↵is less than options.OptimalityTolerance = 1.000000e-08, the complementarity measure,↵8.753723e-10, is less than options.OptimalityTolerance, and the relative maximum constraint↵violation, 0.000000e+00, is less than options.ConstraintTolerance = 1.000000e-08.'
          algorithm: 'interior-point-convex'
      firstorderopt: 2.3577e-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.

<stopping criteria details>

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

disp(lambda)

    ineqlin: 12.0000
      eqlin: [0×1 double]
      lower: [3×1 double]
      upper: [3×1 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]

データ型: single | double

f — 目的関数の線形項

実数ベクトル

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

例: [1;3;2]

データ型: single | 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 を使用します。

データ型: single | double

b — 線形不等式制約

実数ベクトル

実数ベクトルで指定される線形不等式制約です。b は、行列 A に関連する M 要素ベクトルです。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 を使用します。

データ型: single | double

Aeq — 線形等式制約

実数行列

実数行列として指定される線形等式制約です。Aeq は Me 行 N 列の行列で、Me は等式の数、N は変数の数 (x0 の要素数) です。スパース データをサポートするアルゴリズムを使用する大規模な問題の場合は、A をスパース行列として渡します。最適化アルゴリズムのスパース性を参照してください。

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 を使用します。

データ型: single | double

beq — 線形等式制約

実数ベクトル

実数ベクトルで指定される線形等式制約です。beq は、行列 Aeq に関連する Me 要素ベクトルです。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 を使用します。

データ型: single | 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)) を使用します。

データ型: single | 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)) を使用します。

データ型: single | 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]

データ型: single | 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' — 密な線形代数を使用。
ScaleProblem	true の場合、内部スケーリングを実行して問題の調整を改善し、場合によってはより迅速または正確に解を得ます。既定値は false です。 適切にスケール化されていない線形制約 (A または Aeq) または二次目的係数 (H) 行列をもつ一部の問題では、true に設定すると、顕著な高速化が実現したり解の精度が向上したりする場合があります。ただし、ScaleProblem=true を使用するとソルバーに時間的なオーバーヘッドがわずかに加わる可能性があり、場合によっては収束性が低下することがあります。

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

ConstraintTolerance	制約違反に関する許容誤差 (非負のスカラー)。既定値は 1e-8 です。 optimset の場合、オプションの名前は TolCon です。新旧のオプション名を参照してください。
ObjectiveLimit	スカラーの許容誤差 (停止条件) です。目的関数値が ObjectiveLimit を下回り、現在の点が実行可能な場合、問題が非有界であると推定されるため、その反復は中止されます。既定値は -1e20 です。
UseCodegenSolver	ターゲット ハードウェアで実行されているバージョンのソフトウェアを使用するための指定。true または false (既定の設定) として指定します。このオプションは、コードを生成する前にデスクトップ環境でコードをテストするために使用します。このオプションは、コード生成時に渡すことはできますが、コード生成には影響しません。

単精度コード生成

Algorithm	'active-set' でなければなりません。
ConstraintTolerance	制約違反に関する許容誤差 (正のスカラー)。既定値は 1e-4 です。 optimset の場合、オプションの名前は TolCon です。新旧のオプション名を参照してください。
MaxIterations	反復の最大許容回数 (非負の整数)。既定値は 10*(nVar + mConstr) です。ここで、nVar は問題変数の数、mConstr は制約の数です。
ObjectiveLimit	スカラーの許容誤差 (停止条件) です。目的関数値が ObjectiveLimit を下回り、現在の点が実行可能な場合、問題が非有界であると推定されるため、その反復は中止されます。既定値は -1e20 です。
OptimalityTolerance	1 次の最適性に関する終了許容誤差 (正のスカラー)。既定値は 1e-4 です。1 次の最適性の尺度を参照してください。 optimset の場合、名前は TolFun です。新旧のオプション名を参照してください。
StepTolerance	x に関する許容誤差 (正のスカラー)。既定値は 1e-4 です。 optimset の場合、オプションの名前は TolX です。新旧のオプション名を参照してください。
UseCodegenSolver	ターゲット ハードウェアで実行されているバージョンのソフトウェアを使用するための指定。true または false (既定の設定) として指定します。このオプションは、コードを生成する前にデスクトップ環境でコードをテストするために使用します。このオプションは、コード生成時に渡すことはできますが、コード生成には影響しません。

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	線形等式

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

詳細

より詳細な終了メッセージ

次のいくつかの項目は、quadprog から表示される可能性がある、より詳細な終了メッセージをリストしたものです。より詳細な終了メッセージでは、詳細な情報のリンクがメッセージの最初の文として提供されます。

制約を満たす局所的最小値が見つかりました

ソルバーがすべての範囲制約および線形制約を満たす最小化点を見つけました。問題が "凸" なので、最小化点は大域的最小値です。詳細については、大域的最適解と局所的最適解を参照してください。

ソルバーが停止し、制約は満たされました

ソルバーは、最後のステップが小さすぎたために停止しました。相対ステップ サイズがStepTolerance 許容誤差を下回った時点で反復は終了します。これは、ソルバーが最小値を見つけたことを意味している場合があります。ただし、1 次の最適性の尺度がOptimalityToleranceより小さくなかったため、結果が不正確である可能性があります。すべての制約が満たされました。

続行するには、次を試してみましょう。

• output 構造体の 1 次の最適性の尺度を調べます。1 次の最適性の尺度が小さい場合、返される解は正確である可能性があります。

• StepTolerance オプションを 0 に設定します。この設定がソルバーの続行に役立つ場合もあれば、他の問題のためにソルバーが停止したままの場合もあります。

• 別のアルゴリズムを試してください。ソルバーでアルゴリズムを選択できる場合は、別のアルゴリズムで成功する場合もあります。

• 従属制約を削除してみます。つまり、冗長な線形制約がないようにします。

問題が非有界です

quadprog は、すべての制約を満たす方向が見つかり、制限なく目的関数が減少するように見えるため、停止しました。

続行するには、次を行います。

• 各成分に有限範囲があることを確認します。

• 厳密に凸である (二次の行列が厳密に正の固有値をもつ) ことが確保されているか目的関数を確認します。

• 関連付けられた線形計画問題 (二次の項のない元の問題) に有限解があるかどうかを確認します。

ステップ方向を計算できない

ソルバーは、最小値へつながる方向を計算できなかったため、続行できませんでした。この問題は、冗長な線形制約または小さすぎる許容誤差が原因の可能性があります。

続行するには、次を行います。

• 線形制約行列の冗長性を確認します。冗長な線形制約の特定と削除を試みます。

• FunctionTolerance、OptimalityTolerance および ConstraintTolerance オプションが 1e-14 を上回り、できれば 1e-12 を上回るようにしてください。許容誤差と停止条件を参照してください。

問題が凸ではありません

quadprog が、問題は凸ではないと判断しました。別のアルゴリズムを試してください。詳細については、二次計画法のアルゴリズムを参照してください。

解決の前処理で解が見つかりました

ソルバーが解決の前処理段階で解を見つけました。これは、範囲、線形制約、および f (線形目的係数) から直ちに解が導かれたことを意味します。詳細については、解決の前処理と後処理を参照してください。

問題は実行不可能です

解決の前処理中に、ソルバーは問題に矛盾する定式が含まれていることを検出しました。矛盾とは、単一の点 x で制約がすべて満たされるとは限らないことを意味します。詳細については、解決の前処理と後処理を参照してください。

問題が非有界です

解決の前処理中にソルバーが見つけた実行可能な方向では、目的関数が制限なく減少します。詳細については、解決の前処理と後処理を参照してください。

実行不可能な点に収束

quadprog が収束した点では、ConstraintToleranceと呼ばれる制約の許容誤差内で満たされていない制約がありました。quadprog が停止した理由は、最後のステップが小さすぎたためです。相対ステップ サイズがStepTolerance許容誤差を下回った時点で反復は終了します。

作業の進め方については、quadprog の実行不可能点への収束を参照してください。

実行可能解が見つかりません

ソルバーが収束した点では、ConstraintToleranceと呼ばれる制約の許容誤差内で満たされていない制約がありました。ソルバーが停止した理由は、最後のステップが小さすぎたためです。相対ステップ サイズがStepTolerance許容誤差を下回った時点で反復は終了します。

実行可能解が見つかりません

範囲制約と線形制約すべてを満たす点がありません。矛盾する線形制約について検証するには、線形実行不可能性の調査を参照してください。

見つかった最適解

実行可能点は 1 つだけです。独立線形等式制約の数は、問題内の変数の数と同じです。

見つかった最適解

"1 次の最適性尺度" が "許容誤差" OptimalityTolerance 未満であるため、ソルバーは停止しました。

1 次の最適性尺度は、射影勾配の無限大ノルムです。投影は、線形等式行列 Aeq のヌル空間に行われます。

局所的最小値が見つかりました

ソルバーは、局所的最小値となる 0 曲率の点で停止しました。他にも、同じ目的関数値を持つ実行可能点があります。

問題が非有界です

0 または負の曲率の方向があり、それに沿って目的関数は無制限に減少します。したがって、ターゲット値には、ターゲットより小さい目的値をもつ実行可能点が存在します。すべての変数の範囲など、問題に十分な制約を含めたかどうかを確認します。

見つかった最適解

1 次の最適性尺度が許容誤差 OptimalityTolerance未満であるため、ソルバーは停止しました。

局所的最小値の可能性

関数値の相対変化が許容誤差 FunctionTolerance を下回ったため、ソルバーは停止しました。解の質を確認するには、局所的最小値の可能性を参照してください。

局所的最小値の可能性

関数値の相対変化が許容誤差 FunctionTolerance の平方根を下回ったためソルバーは停止しました。前の反復での関数値の変化率は、1/3.5 未満に減少しています。この条件では、目的関数値の差が比較的小さいが、十分に早く 0 に減少しない場合に、ソルバーが停止します。解の質を確認するには、局所的最小値の可能性を参照してください。

終了メッセージの定義

次のいくつかの項目は、quadprog の終了メッセージに含まれる用語の定義を示したものです。

許容誤差

許容誤差は、一般的に、それを超えた場合にソルバーの反復を停止するしきい値です。許容誤差の詳細については、許容誤差と停止条件を参照してください。

凸

二次計画は、負の曲率方向の実行可能な方向がない場合に、任意の実行可能点から凸となります。凸問題の局所的最小値は 1 つのみであり、その値は大域的最小値でもあります。

実行可能な方向

実行可能点 x からの実行可能な方向は、a が十分に小さい正の数値の場合、x + av が実行可能なベクトル v です。

実行可能点は、すべての制約を満たす点です。

StepTolerance

StepTolerance は、最後のステップのサイズの許容誤差、つまり、fsolveが評価された位置での変化のサイズを表します。

OptimalityTolerance

OptimalityTolerance と呼ばれる許容誤差は 1 次の最適性の尺度に対応します。反復計算は、1 次の最適性の尺度が OptimalityTolerance 未満の場合に終了します。

制約問題では、1 次の最適性の尺度は、次の 2 つの数量の最大値です。

$$\begin{array}{l}\Vert {\nabla }_{x}L(x,\lambda \Vert =\Vert \nabla f(x)+A^T{\lambda }_{ineqlin}+Ae{q}^T{\lambda }_{eqlin}\\ +{\displaystyle \sum {\lambda }_{ineqnonlin,i}\nabla c_i(x)+{\displaystyle \sum {\lambda }_{eqnonlin,i}\nabla ce{q}_i(x)}}\Vert ,\end{array}$$

$$\Vert \overrightarrow{\left|l_i-x_i\right|{\lambda }_{lower,i}},\overrightarrow{\left|x_i-u_i\right|{\lambda }_{upper,i}},\overrightarrow{\left|{(Ax-b)}_i\right|{\lambda }_{ineqlin,i}},\overrightarrow{\left|c_i(x)\right|{\lambda }_{ineqnonlin,i}}\Vert .$$

制約なしの問題では、1 次の最適性の尺度は、勾配ベクトルの成分の最大絶対値 (無限大ノルムとも呼ばれる) です。

1 次の最適性の尺度は、最小化点ではゼロになります。

これらの方程式のすべての変数の定義など、詳細については1 次の最適性の尺度を参照してください。

問題が有界の場合の 1 次の最適性の尺度

制約なしの問題では、1 次の最適性の尺度は、勾配ベクトルの成分の最大絶対値 (勾配の無限大ノルムとも呼ばれる) です。これは最小化点ではゼロになります。

問題が有界の場合、1 次の最適性の尺度は、|v_i*g_i| の i に対する最大値です。ここで、g_i は勾配の i 番目の要素、x は現在の点です。

$$v_i=\{\begin{array}{ll}\left|x_i-b_i\right|\hfill & \text{if the negative gradient points toward bound }{b}_i\hfill \\ 1\hfill & \text{otherwise}\text{.}\hfill \end{array}$$

x_i が境界にある場合は、v_i はゼロです。x_i が境界にない場合は、最小化点で勾配 g_i はゼロになります。このため、1 次の最適性の尺度は、最小化点ではゼロになります。

詳細については、1 次の最適性の尺度を参照してください。

ConstraintTolerance

ConstraintTolerance と呼ばれる制約の許容誤差は、現在の点でのすべての制約関数の最大値です。

ConstraintTolerance は他の許容誤差とは別に処理されます。ConstraintTolerance の条件が満たされない場合 (すなわち制約関数の大きさが ConstraintTolerance を超えた場合) は、他の理由で中止されない限りソルバーは計算を続行しようとします。ソルバーが単純に計算を中止しないのは、続行することで ConstraintTolerance の条件が満たされるためです。

相対的双対実行可能性

双対実行可能性 r_d は、問題のKKT 条件に関して定義されます。相対的双対実行可能性の停止状態は次のとおりです。

rd ≤ ρOptimalityTolerance

(1)

ここで、ρ は "スケール係数" です。

詳細については、予測子修正子を参照してください。

双対実行可能性

KKT 条件は最適解 x において、次の条件を満たすラグランジュ乗数 $${\overline{\lambda }}_{\text{ineq}}$$ および λ_eq を提示します。

$$\begin{array}{c}Hx+c+A_{\text{eq}}^T{\lambda }_{\text{eq}}+{\overline{A}}^T{\overline{\lambda }}_{\text{ineq}}=0\\ \overline{A}x-\overline{b}+s=0\\ A_{\text{eq}}x-b_{\text{eq}}=0\\ s_i{\overline{\lambda }}_{\text{ineq},i}=0\\ s_i\ge 0\\ {\overline{\lambda }}_{\text{ineq},i}\ge 0.\end{array}$$

変数 $$\overline{A}$$、$${\overline{\lambda }}_{\text{ineq}}$$、および $$\overline{b}$$ が、線形不等式の一部として範囲を含んでいる。

双対実行可能性 r_d が $$r_{\text{d}}=Hx+c+A_{\text{eq}}^T{\lambda }_{\text{eq}}+{\overline{A}}^T{\overline{\lambda }}_{\text{ineq}}$$ の絶対値である。

スケール係数

スケール係数 ρ は次のとおりです。

$$\rho =\max \left(1,\Vert H\Vert ,\Vert \overline{A}\Vert ,\Vert A_{eq}\Vert ,\Vert c\Vert ,\Vert \overline{b}\Vert ,\Vert b_{eq}\Vert \right).$$

ノルム $$\Vert \cdot \Vert$$ は式内の要素の絶対値の最大値です。

相補性測度

"相補性測度" は、問題のKKT 条件に関して定義されます。最適解 x でラグランジュ乗数 $${\overline{\lambda }}_{\text{ineq}}$$ および λ_eq が次の条件を満たします。

$$\begin{array}{c}Hx+c+A_{\text{eq}}^T{\lambda }_{\text{eq}}+{\overline{A}}^T{\overline{\lambda }}_{\text{ineq}}=0\\ \overline{A}x-\overline{b}+s=0\\ A_{\text{eq}}x-b_{\text{eq}}=0\\ s_i{\overline{\lambda }}_{\text{ineq},i}=0\\ s_i\ge 0\\ {\overline{\lambda }}_{\text{ineq},i}\ge 0.\end{array}$$

変数 $$\overline{A}$$、$${\overline{\lambda }}_{\text{ineq}}$$、および $$\overline{b}$$ が、線形不等式の一部として範囲を含んでいる。

相補性測度は次のとおりです。

$${\displaystyle \sum _i{s}_i{\overline{\lambda }}_{\text{ineq},i}}.$$

詳細については、予測子修正子を参照してください。

総相対誤差

総相対誤差は、問題の KKT 条件に関して定義されます。総相対誤差の停止状態は、メリット関数 φ が次の条件を満たしたときに成り立ちます。

φ ≥ max(OptimalityTolerance,105φmin)

(2)

この停止条件が満たされると、ソルバーは二次計画が実行不可能であると判断します。

メリット関数

KKT 条件は最適解 x において、次の条件を満たすラグランジュ乗数 $${\overline{\lambda }}_{\text{ineq}}$$ および λ_eq を提示します。

$$\begin{array}{c}Hx+c+A_{\text{eq}}^T{\lambda }_{\text{eq}}+{\overline{A}}^T{\overline{\lambda }}_{\text{ineq}}=0\\ \overline{A}x-\overline{b}+s=0\\ A_{\text{eq}}x-b_{\text{eq}}=0\\ s_i{\overline{\lambda }}_{\text{ineq},i}=0\\ s_i\ge 0\\ {\overline{\lambda }}_{\text{ineq},i}\ge 0.\end{array}$$

変数 $$\overline{A}$$、$${\overline{\lambda }}_{\text{ineq}}$$、および $$\overline{b}$$ が、線形不等式の一部として範囲を含んでいる。

メリット関数 φ は次のようになります。

$$\frac{1}{\rho }\left(\max \left({\Vert r_{\text{eq}}\Vert }_{\infty },{\Vert r_{\text{ineq}}\Vert }_{\infty },{\Vert r_{\text{d}}\Vert }_{\infty }\right)+g\right).$$

φ の定義の中の項は次のとおりです。

$$\begin{array}{c}\rho =\max \left(1,\Vert H\Vert ,\Vert \overline{A}\Vert ,\Vert A_{eq}\Vert ,\Vert c\Vert ,\Vert \overline{b}\Vert ,\Vert b_{eq}\Vert \right)\\ r_{\text{eq}}=A_{\text{eq}}x-b_{\text{eq}}\\ r_{\text{ineq}}=\overline{A}x-\overline{b}+s\\ r_{\text{d}}=Hx+c+A_{\text{eq}}^T{\lambda }_{\text{eq}}+{\overline{A}}^T{\overline{\lambda }}_{\text{ineq}}\\ g=x^{T}Hx+f^{T}x-\overline{b}{\overline{\lambda }}_{\text{ineq}}-b_{\text{eq}}{\lambda }_{\text{eq}}.\end{array}$$

式 φ_min は、すべての反復に見られる φ の最小値を意味します。

解決の前処理

解決の前処理は、線形計画問題または二次計画問題を単純化する一連のアルゴリズムです。これらのアルゴリズムは、矛盾する範囲制約や線形制約などの単純な矛盾を探索します。さらに、重複する範囲および線形不等式も探索します。詳細については、解決の前処理と後処理を参照してください。

悪条件と思われる問題

内部計算された探索方向では、目的関数値は減少しません。おそらく、問題が適切にスケール化されていないか、問題に悪条件の行列 (quadprog に対する H、lsqlin に対する C) があります。作業の進め方については、ソルバーが失敗する場合または局所的最小値の可能性を参照してください。

アルゴリズム

'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 ソルバーと同じ数学カーネル ライブラリを使用しません。そのため、コード生成解法は、特に、条件付けが不十分な問題の場合に、ソルバー解法と異なる可能性があります。

• コードを生成する前に MATLAB でコードをテストするには、UseCodegenSolver オプションを true に設定します。これにより、ソルバーがコード生成で作成されるものと同じコードを使用するようになります。

• コード生成の場合、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

  • UseCodegenSolver

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

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

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

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

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

バージョン履歴

R2006a より前に導入

R2025a: コード生成前のテスト

新しい UseCodegenSolver オプションを true に設定すると、quadprog は、コード生成で作成されるものと同じバージョンのソフトウェアを使用します。このオプションを使用すると、コードを生成する前またはコードをハードウェアに展開する前に、ソルバーの動作を確認できます。単精度コード生成をサポートするソルバーの場合は、生成されたコードでも単精度ハードウェアをサポートできます。コード生成時にこのオプションを含めることができます。このオプションはコード生成には影響しませんが、オプションを含めたままにしておくと、削除する手間が省けます。生成されるコードは MATLAB コードと同じですが、リンクされている数学ライブラリが異なる可能性があるため、結果は若干異なる場合があります。

R2025a: quadprog の ScaleProblem オプション

quadprog ソルバーの "interior-point-convex" アルゴリズムに、一部の適切にスケール化されていない問題の解を迅速に得ることができる ScaleProblem オプションが追加されました。詳細については、quadprog の options 引数の説明を参照してください。

R2024b: 単精度コードの生成

quadprog を使用して単精度浮動小数点ハードウェア用のコードを生成できます。手順については、単精度コード生成を参照してください。

参考

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

トピック

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