quadprog
二次計画法
構文
説明
線形制約がある二次目的関数のソルバーです。
quadprog は、次によって指定される問題の最小値を求めます。
H、A、Aeq は行列、f、b、beq、lb、ub、x はベクトルです。
f、lb および ub はベクトルまたは行列として渡すことができます。行列引数を参照してください。
メモ
quadprog
は、ソルバーベースのアプローチのみに適用されます。問題ベースのアプローチの場合は、solve
を使用してください。2 つの最適化アプローチの詳細については、はじめに問題ベース アプローチまたはソルバーベース アプローチを選択を参照してください。
は、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(problem
)problem
で説明されている構造体 problem
の最小値を返します。ドット表記または struct
関数を使用して problem
構造体を作成します。または、prob2struct
を使用して OptimizationProblem
オブジェクトから構造体 problem
を作成します。
例
次の関数の最小値を求めます。
以下の制約に従います。
quadprog
の構文では、この問題は次を最小化することです。
,
ここで、
これには線形制約が適用されます。
この問題を解くため、まず係数行列を入力します。
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
次の関数の最小値を求めます。
制約は以下になります。
quadprog
の構文では、この問題は次を最小化することです。
,
ここで、
これには線形制約が適用されます。
この問題を解くため、まず係数行列を入力します。
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 を求めます。
ここで、
, ,
以下の制約に従います。
, .
この問題を解くため、まず係数を入力します。
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
問題ベースの最適化ワークフローを使用して構造体 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
二次計画法を解き、解と目的関数の値の両方を取得します。
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
の最適化プロセスを表示するため、反復表示を行うオプションを設定し、4 つの出力を取得します。問題は、次を最小化することです。
制約条件
,
ここで、
, .
問題の係数を入力します。
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: []
二次計画問題を解き、ラグランジュ乗数を取得します。
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
は、式 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
は、式 1/2*x'*H*x + f'*x
の線形項を表します。
例: [1;3;2]
データ型: single
| double
実数行列として指定される線形不等式制約です。A
は M
行 N
列の行列で、M
は不等式の数、N
は変数の数 (x0
の要素数) です。スパース データをサポートするアルゴリズムを使用する大規模な問題の場合は、A
をスパース行列として渡します。最適化アルゴリズムのスパース性を参照してください。
A
は M
個の線形不等式を符号化します。
A*x <= b
,
ここで、x
は N
個の変数 x(:)
の列ベクトル、b
は M
個の要素をもつ列ベクトルです。
たとえば、次の不等式を考えてみましょう。
x1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30,
次の制約を入力することによって、不等式を指定します。
A = [1,2;3,4;5,6]; b = [10;20;30];
例: x の成分の和が 1 以下であることを指定するには、A = ones(1,N)
と b = 1
を使用します。
データ型: single
| double
実数ベクトルで指定される線形不等式制約です。b
は、行列 A
に関連する M
要素ベクトルです。b
を行ベクトルとして渡す場合、ソルバーは b
を列ベクトル b(:)
に内部的に変換します。
b
は M
個の線形不等式を符号化します。
A*x <= b
,
ここで、x
は N
個の変数 x(:)
の列ベクトル、A
は M
行 N
列の行列です。
たとえば、次の不等式を考えてみましょう。
x1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30.
次の制約を入力することによって、不等式を指定します。
A = [1,2;3,4;5,6]; b = [10;20;30];
例: x の成分の和が 1 以下であることを指定するには、A = ones(1,N)
と b = 1
を使用します。
データ型: single
| double
実数行列として指定される線形等式制約です。Aeq
は Me
行 N
列の行列で、Me
は等式の数、N
は変数の数 (x0
の要素数) です。スパース データをサポートするアルゴリズムを使用する大規模な問題の場合は、A
をスパース行列として渡します。最適化アルゴリズムのスパース性を参照してください。
Aeq
は Me
個の線形等式を符号化します。
Aeq*x = beq
,
ここで、x
は N
個の変数 x(:)
の列ベクトル、beq
は Me
個の要素をもつ列ベクトルです。
たとえば、次の不等式を考えてみましょう。
x1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x3 = 20,
次の制約を入力することによって、不等式を指定します。
Aeq = [1,2,3;2,4,1]; beq = [10;20];
例: x の成分の和が 1 であることを指定するには、Aeq = ones(1,N)
と beq = 1
を使用します。
データ型: single
| double
実数ベクトルで指定される線形等式制約です。beq
は、行列 Aeq
に関連する Me
要素ベクトルです。beq
を行ベクトルとして渡す場合、ソルバーは beq
を列ベクトル beq(:)
に内部的に変換します。
beq
は Me
個の線形等式を符号化します。
Aeq*x = beq
,
ここで、x
は N
個の変数 x(:)
の列ベクトル、Aeq
は Me
行 N
列の行列です。
たとえば、次の等式を考えてみましょう。
x1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x3 = 20.
次の制約を入力することによって、等式を指定します。
Aeq = [1,2,3;2,4,1]; beq = [10;20];
例: x の成分の和が 1 であることを指定するには、Aeq = ones(1,N)
と beq = 1
を使用します。
データ型: single
| double
下限。実数ベクトルまたは実数配列として指定されます。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
実数ベクトルまたは実数配列として指定される上限です。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
の長さは、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
最適化オプション。optimoptions
の出力、または optimset
などによって返される構造体として指定されます。
一部のオプションは、optimoptions
に表示されません。このようなオプションは、次の表ではイタリックで示されています。詳細については、最適化オプションの表示を参照してください。
すべてのアルゴリズム
Algorithm | アルゴリズムを選択します。
|
Diagnostics | 最小化または計算する関数に関する情報を表示します。選択肢は |
Display | 表示レベル (反復表示を参照):
|
MaxIterations | 反復の最大許容回数 (非負の整数)。
|
OptimalityTolerance | 1 次の最適性に関する終了許容誤差 (非負のスカラー)。
許容誤差と停止条件を参照してください。
|
StepTolerance |
|
'trust-region-reflective'
アルゴリズムのみ
FunctionTolerance | 関数値に関する終了許容誤差 (非負のスカラー)。既定値は問題のタイプに依存します。範囲制約付き問題では
|
| ヘッセ乗算関数。関数ハンドルとして指定されます。大規模構造問題に対して、この関数は実際に W = hmfun(Hinfo,Y)
たこのオプションを使用する例は 密な構造化されたヘッシアンを使った二次最小化 を参照してください。
|
MaxPCGIter | PCG (前処理付き共役勾配) 法の最大反復回数。正のスカラー。範囲制約付き問題の場合の既定値は |
PrecondBandWidth | PCG に対する前提条件子の帯域幅の上限。非負の整数。既定の設定では、 |
SubproblemAlgorithm | 反復ステップの計算方法を定義します。既定の設定である |
TolPCG | PCG の反復に対する終了許容誤差。正のスカラー。既定値は |
TypicalX | 典型的な |
'interior-point-convex'
アルゴリズムのみ
ConstraintTolerance | 制約違反に関する許容誤差 (非負のスカラー)。既定値は
|
LinearSolver | アルゴリズムの内部的な線形ソルバーのタイプ
|
ScaleProblem |
適切にスケール化されていない線形制約 ( |
'active-set'
アルゴリズムのみ
ConstraintTolerance | 制約違反に関する許容誤差 (非負のスカラー)。既定値は
|
ObjectiveLimit | スカラーの許容誤差 (停止条件) です。目的関数値が |
UseCodegenSolver | ターゲット ハードウェアで実行されているバージョンのソフトウェアを使用するための指定。 |
単精度コード生成
Algorithm |
|
ConstraintTolerance | 制約違反に関する許容誤差 (正のスカラー)。既定値は
|
MaxIterations | 反復の最大許容回数 (非負の整数)。既定値は |
ObjectiveLimit | スカラーの許容誤差 (停止条件) です。目的関数値が |
OptimalityTolerance | 1 次の最適性に関する終了許容誤差 (正のスカラー)。既定値は
|
StepTolerance |
|
UseCodegenSolver | ターゲット ハードウェアで実行されているバージョンのソフトウェアを使用するための指定。 |
問題構造体。次のフィールドをもつ構造体を指定します。
| 1/2*x'*H*x の対称行列 |
| 線形項 f'*x のベクトル |
| 線形不等式制約 Aineq*x ≤ bineq の行列 |
| 線形不等式制約 Aineq*x ≤ bineq のベクトル |
| 線形等式制約 Aeq*x = beq の行列 |
| 線形等式制約 Aeq*x = beq のベクトル |
lb | 下限のベクトル |
ub | 上限のベクトル |
| x の初期点 |
| 'quadprog' |
| optimoptions または optimset を使用して作成されたオプション |
必須フィールドは H
、f
、solver
および options
です。quadprog
は、解を求めるときに、リストされているもの以外の problem
のフィールドを無視します。
メモ
引数 problem
とウォーム スタートを一緒に使用することはできません。
データ型: struct
ウォーム スタート オブジェクト。optimwarmstart
で作成したオブジェクトとして指定します。ウォーム スタート オブジェクトには、開始点とオプションに加え、コード生成におけるメモリ サイズ用のオプション データが含まれます。ウォーム スタートのベスト プラクティスを参照してください。
例: ws = optimwarmstart(x0,options)
出力引数
解。実数ベクトルとして返されます。x
は、すべての範囲制約および線形制約に従って 1/2*x'*H*x + f'*x
を最小化するベクトルです。非凸問題の場合、x
は局所的最小値である可能性があります。凸問題の場合、x
は大域的最小値です。詳細については、大域的最適解と局所的最適解を参照してください。
解ウォーム スタート オブジェクト。QuadprogWarmStart
オブジェクトとして返されます。解点は wsout.X
です。
この後の quadprog
の呼び出しでは、wsout
を入力ウォーム スタート オブジェクトとして使用できます。
解における目的関数の値。実数スカラーとして返されます。fval
は、解 x
における 1/2*x'*H*x + f'*x
の値です。
quadprog
の停止理由。次の表で説明する整数として返されます。
すべてのアルゴリズム | |
| 関数が解 |
| 反復数が |
| 問題が実行不可能です。または、 |
| 問題が非有界です。 |
| |
| ステップ サイズが |
| 非凸問題が検出されました。 |
| ステップ方向を計算できません。 |
| |
| 局所的最小値が見つかりました。最小値は一意ではありません。 |
| 目的関数値の変更が |
| 現在の探索方向は減少の方向ではなく、これ以上進むことができないことを示します。 |
| |
|
メモ
問題が実際には非有界のとき、'active-set'
アルゴリズムは終了フラグ 0
で停止することがあります。反復制限を高く設定した場合も、終了フラグ 0
になります。
最適化プロセスに関する情報。次のフィールドをもつ構造体として返されます。
| 実行した反復回数 |
| 使用される最適化アルゴリズム |
| PCG 法の合計反復回数 ( |
constrviolation | 制約関数の最大値 |
firstorderopt | 1 次の最適性の尺度 |
linearsolver | 内部的な線形ソルバーのタイプ、 |
message | 終了メッセージ |
解におけるラグランジュ乗数。次のフィールドをもつ構造体として返されます。
| 下限 |
| 上限 |
| 線形不等式 |
| 線形等式 |
詳細については、ラグランジュ乗数構造体を参照してください。
詳細
次のいくつかの項目は、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
は、最後のステップのサイズの許容誤差、つまり、fsolve
が評価された位置での変化のサイズを表します。
OptimalityTolerance
と呼ばれる許容誤差は 1 次の最適性の尺度に対応します。反復計算は、1 次の最適性の尺度が OptimalityTolerance
未満の場合に終了します。
制約問題では、1 次の最適性の尺度は、次の 2 つの数量の最大値です。
制約なしの問題では、1 次の最適性の尺度は、勾配ベクトルの成分の最大絶対値 (無限大ノルムとも呼ばれる) です。
1 次の最適性の尺度は、最小化点ではゼロになります。
これらの方程式のすべての変数の定義など、詳細については1 次の最適性の尺度を参照してください。
制約なしの問題では、1 次の最適性の尺度は、勾配ベクトルの成分の最大絶対値 (勾配の無限大ノルムとも呼ばれる) です。これは最小化点ではゼロになります。
問題が有界の場合、1 次の最適性の尺度は、|vi*gi| の i に対する最大値です。ここで、gi は勾配の i 番目の要素、x は現在の点です。
xi が境界にある場合は、vi はゼロです。xi が境界にない場合は、最小化点で勾配 gi はゼロになります。このため、1 次の最適性の尺度は、最小化点ではゼロになります。
詳細については、1 次の最適性の尺度を参照してください。
ConstraintTolerance
と呼ばれる制約の許容誤差は、現在の点でのすべての制約関数の最大値です。
ConstraintTolerance
は他の許容誤差とは別に処理されます。ConstraintTolerance
の条件が満たされない場合 (すなわち制約関数の大きさが ConstraintTolerance
を超えた場合) は、他の理由で中止されない限りソルバーは計算を続行しようとします。ソルバーが単純に計算を中止しないのは、続行することで ConstraintTolerance
の条件が満たされるためです。
KKT 条件は最適解 x において、次の条件を満たすラグランジュ乗数 および λeq を提示します。
変数 、、および が、線形不等式の一部として範囲を含んでいる。
双対実行可能性 rd が の絶対値である。
スケール係数 ρ は次のとおりです。
ノルム は式内の要素の絶対値の最大値です。
KKT 条件は最適解 x において、次の条件を満たすラグランジュ乗数 および λeq を提示します。
変数 、、および が、線形不等式の一部として範囲を含んでいる。
メリット関数 φ は次のようになります。
φ の定義の中の項は次のとおりです。
式 φmin は、すべての反復に見られる φ の最小値を意味します。
解決の前処理は、線形計画問題または二次計画問題を単純化する一連のアルゴリズムです。これらのアルゴリズムは、矛盾する範囲制約や線形制約などの単純な矛盾を探索します。さらに、重複する範囲および線形不等式も探索します。詳細については、解決の前処理と後処理を参照してください。
内部計算された探索方向では、目的関数値は減少しません。おそらく、問題が適切にスケール化されていないか、問題に悪条件の行列 (quadprog
に対する H
、lsqlin
に対する C
) があります。作業の進め方については、ソルバーが失敗する場合または局所的最小値の可能性を参照してください。
アルゴリズム
'interior-point-convex'
アルゴリズムは、厳密に制約内にある経路をたどろうと試みます。このアルゴリズムは前処理モジュールを使用して重複を取り除き、簡単な要素について問題を解くことによって問題を単純化します。
アルゴリズムは、スパース ヘッセ行列 H
の場合と、密行列の場合では、実装が異なります。一般に、スパース実装は大規模なスパース問題でより高速で、密実装は密または小規模な問題でより高速です。詳細については、interior-point-convex quadprog アルゴリズムを参照してください。
'trust-region-reflective'
アルゴリズムは部分空間の信頼領域法であり、[1] で説明されている interior-reflective ニュートン法に基づいています。各反復は、前処理付き共役勾配 (PCG) 法を使用する大型線形システムの近似解を伴います。詳細については、trust-region-reflective quadprog アルゴリズムを参照してください。
'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.
拡張機能
使用上の注意および制限:
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 より前に導入新しい UseCodegenSolver
オプションを true
に設定すると、quadprog
は、コード生成で作成されるものと同じバージョンのソフトウェアを使用します。このオプションを使用すると、コードを生成する前またはコードをハードウェアに展開する前に、ソルバーの動作を確認できます。単精度コード生成をサポートするソルバーの場合は、生成されたコードでも単精度ハードウェアをサポートできます。コード生成時にこのオプションを含めることができます。このオプションはコード生成には影響しませんが、オプションを含めたままにしておくと、削除する手間が省けます。生成されるコードは MATLAB コードと同じですが、リンクされている数学ライブラリが異なる可能性があるため、結果は若干異なる場合があります。
quadprog
を使用して単精度浮動小数点ハードウェア用のコードを生成できます。手順については、単精度コード生成を参照してください。
MATLAB Command
You clicked a link that corresponds to this MATLAB command:
Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.
Web サイトの選択
Web サイトを選択すると、翻訳されたコンテンツにアクセスし、地域のイベントやサービスを確認できます。現在の位置情報に基づき、次のサイトの選択を推奨します:
また、以下のリストから Web サイトを選択することもできます。
最適なサイトパフォーマンスの取得方法
中国のサイト (中国語または英語) を選択することで、最適なサイトパフォーマンスが得られます。その他の国の MathWorks のサイトは、お客様の地域からのアクセスが最適化されていません。
南北アメリカ
- América Latina (Español)
- Canada (English)
- United States (English)
ヨーロッパ
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)