Main Content

このページの内容は最新ではありません。最新版の英語を参照するには、ここをクリックします。

quadprog

説明

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

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

minx12xTHx+fTx such that {Axb,Aeqx=beq,lbxub.

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 = [] を設定してください。

メモ

問題の指定された入力範囲が矛盾する場合、出力 xx0、出力 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)=12x12+x22-x1x2-2x1-6x2

以下の制約に従います。

x1+x22-x1+2x222x1+x23.

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

f(x)=12xTHx+fTx,

ここで、

H=[1-1-12]f=[-2-6],

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

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

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)=12x12+x22-x1x2-2x1-6x2

制約は以下になります。

x1+x2=0.

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

f(x)=12xTHx+fTx,

ここで、

H=[1-1-12]f=[-2-6],

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

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

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 を求めます。

12xTHx+fTx

ここで、

H=[1-11-12-21-24], f=[2-31],

以下の制約に従います。

0x1, 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

問題ベースの最適化ワークフローを使用して構造体 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

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

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

12xTHx+fTx

制約条件

0x1,

ここで、

H=[21-11312-1125], f=[4-712].

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

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: []

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

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);
toc
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.
Elapsed time is 0.021717 seconds.

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

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

tic
[ws,fval,exitflag,output,lambda] = quadprog(H,f,A,b,[],[],lb,[],ws);
toc
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.
Elapsed time is 0.018485 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]

データ型: double

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

例: [1;3;2]

データ型: double

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

AM 個の線形不等式を符号化します。

A*x <= b,

ここで、xN 個の変数 x(:) の列ベクトル、bM 個の要素をもつ列ベクトルです。

たとえば、次の不等式を考えてみましょう。

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

データ型: double

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

bM 個の線形不等式を符号化します。

A*x <= b,

ここで、xN 個の変数 x(:) の列ベクトル、AMN 列の行列です。

たとえば、次の不等式を考えてみましょう。

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

データ型: double

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

AeqMe 個の線形等式を符号化します。

Aeq*x = beq,

ここで、xN 個の変数 x(:) の列ベクトル、beqMe 個の要素をもつ列ベクトルです。

たとえば、次の不等式を考えてみましょう。

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

データ型: double

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

beqMe 個の線形等式を符号化します。

Aeq*x = beq,

ここで、xN 個の変数 x(:) の列ベクトル、AeqMeN 列の行列です。

たとえば、次の等式を考えてみましょう。

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

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

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

データ型: double

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

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

メモ

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

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

例: [1;2;1]

データ型: double

最適化オプション。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)) です。等式制約付き問題の場合、quadprogMaxPCGIter を無視し、MaxIterations を使用して PCG の反復回数を制限します。詳細については、前処理付き共役勾配法を参照してください。

PrecondBandWidth

PCG に対する前提条件子の帯域幅の上限。非負の整数。既定の設定では、quadprog は対角型をした前提条件を使用します (帯域幅の上限 0)。一部の問題では、帯域幅を上げることで、PCG 法の反復回数を減らします。PrecondBandWidthInf に設定すると、共役勾配 (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 です。

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

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

必須フィールドは Hfsolver および 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 の停止理由。次の表で説明する整数として返されます。

すべてのアルゴリズム

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 になります。

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

iterations

実行した反復回数

algorithm

使用される最適化アルゴリズム

cgiterations

PCG 法の合計反復回数 ('trust-region-reflective' アルゴリズムのみ)

constrviolation

制約関数の最大値

firstorderopt

1 次の最適性の尺度

linearsolver

内部的な線形ソルバーのタイプ、'dense' または 'sparse' ('interior-point-convex' アルゴリズムのみ)

message

終了メッセージ

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

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.

拡張機能

バージョン履歴

R2006a より前に導入