ドキュメンテーション

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

solve

構文

sol = solve(prob)
sol = solve(prob,x0)
sol = solve(___,Name,Value)
[sol,fval] = solve(___)
[sol,fval,exitflag,output,lambda] = solve(___)

説明

sol = solve(prob) は、最適化問題 prob を解きます。

sol = solve(prob,x0) は、点 x0 から始めて prob を解きます。

sol = solve(___,Name,Value) は、前の構文の入力引数に加え、1 つ以上の名前と値のペア引数を使用してオプションを指定します。

また、[sol,fval] = solve(___) は、前の構文の入力引数のいずれかを使用して、解における目的関数の値を返します。

[sol,fval,exitflag,output,lambda] = solve(___) は、終了条件を説明する終了フラグ、解法プロセスに関する追加情報を含む output 構造体、および非整数問題の場合はラグランジュ乗数構造体も返します。

すべて折りたたむ

最適化問題によって定義された線形計画問題を解きます。

x = optimvar('x');
y = optimvar('y');
prob = optimproblem;
prob.Objective = -x - y/3;
prob.Constraints.cons1 = x + y <= 2;
prob.Constraints.cons2 = x + y/4 <= 1;
prob.Constraints.cons3 = x - y <= 2;
prob.Constraints.cons4 = x/4 + y >= -1;
prob.Constraints.cons5 = x + y >= 1;
prob.Constraints.cons6 = -x + y <= 2;

sol = solve(prob)
Optimal solution found.
sol = struct with fields:
    x: 0.6667
    y: 1.3333

初期実行可能点がある場合とない場合の両方について整数計画問題を解くためのステップ数を比較します。問題には 8 つの整数変数と 4 つの線形等式制約があり、すべての変数が正になるように制限されています。

prob = optimproblem;
x = optimvar('x',8,1,'LowerBound',0,'Type','integer');

4 つの線形等式制約を作成し、問題に含めます。

Aeq = [22    13    26    33    21     3    14    26
    39    16    22    28    26    30    23    24
    18    14    29    27    30    38    26    26
    41    26    28    36    18    38    16    26];
beq = [ 7872
       10466
       11322
       12058];
cons = Aeq*x == beq;
prob.Constraints.cons = cons;

目的関数を作成し、問題に含めます。

f = [2    10    13    17     7     5     7     3];
prob.Objective = f*x;

初期点を使用せずに問題を解き、表示を調べて分枝限定ノードの数を確認します。

[x1,fval1,exitflag1,output1] = solve(prob);
LP:                Optimal objective value is 1554.047531.                                          

Cut Generation:    Applied 8 strong CG cuts.                                                        
                   Lower bound is 1590.479592.                                                      

Branch and Bound:

   nodes     total   num int        integer       relative                                          
explored  time (s)  solution           fval        gap (%)                                         
   10000      0.77         0              -              -                                          
   10947      0.83         1   2.481000e+03   3.585818e+01                                          
   14148      1.07         2   2.073000e+03   2.319190e+01                                          
   17131      1.31         3   1.854000e+03   1.180593e+01                                          
   17777      1.36         3   1.854000e+03   0.000000e+00                                          

Optimal solution found.

Intlinprog stopped because the objective value is within a gap tolerance of the
optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon
variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the
default value).

比較するため、初期実行可能点を使用して解を求めます。

x0.x = [8 62 23 103 53 84 46 34]';
[x2,fval2,exitflag2,output2] = solve(prob,x0);
LP:                Optimal objective value is 1554.047531.                                          

Cut Generation:    Applied 8 strong CG cuts.                                                        
                   Lower bound is 1590.479592.                                                      
                   Relative gap is 59.21%.                                                         

Branch and Bound:

   nodes     total   num int        integer       relative                                          
explored  time (s)  solution           fval        gap (%)                                         
    4535      0.56         2   2.262000e+03   2.965091e+01                                          
    6516      0.73         3   1.854000e+03   1.412399e+01                                          
    7795      0.83         3   1.854000e+03   2.695418e-01                                          
    7825      0.83         3   1.854000e+03   0.000000e+00                                          

Optimal solution found.

Intlinprog stopped because the objective value is within a gap tolerance of the
optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon
variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the
default value).
fprintf('Without an initial point, solve took %d steps.\nWith an initial point, solve took %d steps.',output1.numnodes,output2.numnodes)
Without an initial point, solve took 17777 steps.
With an initial point, solve took 7825 steps.

初期点を与えることが常に問題を改善するとは限りません。この問題の場合、初期点を使用すると、時間と計算ステップが節減されます。ただし、問題によっては、初期点によって solve がより多くのステップを必要とする場合があります。

問題を解く

反復表示を使用しません。

x = optimvar('x',2,1,'LowerBound',0);
x3 = optimvar('x3','Type','integer','LowerBound',0,'UpperBound',1);
prob = optimproblem;
prob.Objective = -3*x(1) - 2*x(2) - x3;
prob.Constraints.cons1 = x(1) + x(2) + x3 <= 7;
prob.Constraints.cons2 = 4*x(1) + 2*x(2) + x3 == 12;

options = optimoptions('intlinprog','Display','off');

sol = solve(prob,'Options',options)
sol = struct with fields:
     x: [2x1 double]
    x3: 1

解を検証します。

sol.x
ans = 2×1

         0
    5.5000

sol.x3
ans = 1

solve に線形計画問題のソルバーとして intlinprog を使用するように強制します。

x = optimvar('x');
y = optimvar('y');
prob = optimproblem;
prob.Objective = -x - y/3;
prob.Constraints.cons1 = x + y <= 2;
prob.Constraints.cons2 = x + y/4 <= 1;
prob.Constraints.cons3 = x - y <= 2;
prob.Constraints.cons4 = x/4 + y >= -1;
prob.Constraints.cons5 = x + y >= 1;
prob.Constraints.cons6 = -x + y <= 2;

sol = solve(prob,'Solver', 'intlinprog')
LP:                Optimal objective value is -1.111111.                                            


Optimal solution found.

No integer variables specified. Intlinprog solved the linear problem.
sol = struct with fields:
    x: 0.6667
    y: 1.3333

既定ではないオプションによる整数計画問題を解くで説明されている混合整数線形計画問題を解いて、すべての出力データを検証します。

x = optimvar('x',2,1,'LowerBound',0);
x3 = optimvar('x3','Type','integer','LowerBound',0,'UpperBound',1);
prob = optimproblem;
prob.Objective = -3*x(1) - 2*x(2) - x3;
prob.Constraints.cons1 = x(1) + x(2) + x3 <= 7;
prob.Constraints.cons2 = 4*x(1) + 2*x(2) + x3 == 12;

[sol,fval,exitflag,output] = solve(prob)
LP:                Optimal objective value is -12.000000.                                           


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap
tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default
value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).
sol = struct with fields:
     x: [2x1 double]
    x3: 1

fval = -12
exitflag = 
    OptimalSolution

output = struct with fields:
        relativegap: 0
        absolutegap: 0
      numfeaspoints: 1
           numnodes: 0
    constrviolation: 0
            message: 'Optimal solution found....'
             solver: 'intlinprog'

整数制約のない問題の場合は、5 番目の出力として空でないラグランジュ乗数構造体も取得できます。

名前付きインデックス変数を使用して、最適化問題を作成して解きます。問題は、収益で重み付けされた、さまざまな空港へのフルーツのフローを最大化することです。これはそれぞれの重み付きフローへの制約に従います。

rng(0) % For reproducibility
p = optimproblem('ObjectiveSense', 'maximize');
flow = optimvar('flow', ...
    {'apples', 'oranges', 'bananas', 'berries'}, {'NYC', 'BOS', 'LAX'}, ...
    'LowerBound',0,'Type','integer');
p.Objective = sum(sum(rand(4,3).*flow));
p.Constraints.NYC = rand(1,4)*flow(:,'NYC') <= 10;
p.Constraints.BOS = rand(1,4)*flow(:,'BOS') <= 12;
p.Constraints.LAX = rand(1,4)*flow(:,'LAX') <= 35;
sol = solve(p);
LP:                Optimal objective value is -1027.472366.                                         

Heuristics:        Found 1 solution using rounding.                                                 
                   Upper bound is -1027.233133.                                                     
                   Relative gap is 0.02%.                                                          

Cut Generation:    Applied 1 mir cut, and 2 strong CG cuts.                                         
                   Lower bound is -1027.233133.                                                     
                   Relative gap is 0.00%.                                                          


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap
tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default
value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).

ニューヨークとロサンゼルスへのオレンジとベリーの最適フローを求めます。

[idxFruit,idxAirports] = findindex(flow, {'oranges','berries'}, {'NYC', 'LAX'})
idxFruit = 1×2

     2     4

idxAirports = 1×2

     1     3

orangeBerries = sol.flow(idxFruit, idxAirports)
orangeBerries = 2×2

         0  980.0000
   70.0000         0

この表示は、NYC 向けのオレンジは 0、70 のベリーが NYC 向け、980 のオレンジが LAX 向けで、LAX 向けのベリーは 0 であることを示しています。

次の最適なフローをリストします。

Fruit Airports

----- --------

Berries NYC

Apples BOS

Oranges LAX

idx = findindex(flow, {'berries', 'apples', 'oranges'}, {'NYC', 'BOS', 'LAX'})
idx = 1×3

     4     5    10

optimalFlow = sol.flow(idx)
optimalFlow = 1×3

   70.0000   28.0000  980.0000

この表示は、70 のベリーが NYC 向け、28 のアップルが BOS 向けで、980 のオレンジが LAX 向けであることを示しています。

入力引数

すべて折りたたむ

最適化問題。OptimizationProblem オブジェクトとして指定します。

例: prob = optimproblem; prob.Objective = obj; prob.Constraints.cons1 = cons1;

初期点。prob の変数名に等しいフィールド名をもつ構造体として指定します。

名前付きインデックス変数と共に x0 を使用する例については、名前付きインデックス変数による最適化の初期点の作成を参照してください。

例: prob に変数 xy がある場合: x0.x = [3,2,17]; x0.y = [pi/3,2*pi/3]

データ型: struct

名前と値のペアの引数

引数 Name,Value のオプションのコンマ区切りペアを指定します。Name は引数名、Value は対応する値です。Name は引用符で囲まなければなりません。Name1,Value1,...,NameN,ValueN のように、複数の名前と値のペアの引数を任意の順番で指定できます。

例: solve(prob,'options',opts)

最適化オプション。'options' と、optimoptions で作成したオブジェクト、またはオプション構造体 (optimset で作成したものなど) から構成されるコンマ区切りのペアとして指定します。

関数 solve は、内部的に linprogintlinprogquadproglsqlin または lsqnonneg を呼び出します。既定のソルバーについては、'solver' を参照してください。

intlinprog の解または解を求める速度を改善するためのオプション設定については、整数線形計画法の調整を参照してください。linprog の場合、既定の 'dual-simplex' アルゴリズムの方が、一般にメモリ効率が高く、迅速です。状況によっては、Algorithm オプションが 'interior-point' の場合に、linprog が大規模な問題をより迅速に解くことがあります。

例: options = optimoptions('intlinprog','Display','none')

最適化ソルバー。'solver' およびリストされているソルバーの名前で構成されるコンマ区切りのペアとして指定します。

問題のタイプ既定のソルバー他の可能なソルバー
線形目的関数、線形制約linprogintlinprogquadprog
線形目的関数、線形制約および整数制約intlinproglinprogquadprog (整数制約は無視)
二次目的関数、線形制約quadproglsqlinlsqnonneg (目的関数を変換しても ||C*x - d||^2 を最小化できない場合、これらのソルバーについて solve でエラーが発生)
線形制約に従って ||C*x - d||^2 を最小化線形式の二乗和に定数を加算した和が目的関数である場合は lsqlinquadproglsqnonneg (lsqnonneg では x >= 0 以外の制約を無視)
X >= 0 に従って ||C*x - d||^2 を最小化lsqlinquadproglsqnonneg

注意

最大化問題の場合、lsqlin ソルバーと lsqnonneg ソルバーは指定しないでください。これらのソルバーは最大化を実行できないので、指定すると solve でエラーが発生します。

例: 'intlinprog'

データ型: char | string

出力引数

すべて折りたたむ

解。構造体として返されます。構造体のフィールドは、最適化変数の名前です。詳細は、optimvar を参照してください。

解での目的関数値。実数として返されます。

ヒント

fval を要求しなかった場合は、次を使用してそれを計算できます。

fval = evaluate(prob.Objective,sol)

ソルバーの停止理由。カテゴリカル変数として返されます。この表は、intlinprog ソルバーの終了フラグを説明しています。

intlinprog の終了フラグ相当する数字意味
IntegerFeasible2intlinprog が途中で停止しました。整数実行可能点が検出されました。
OptimalSolution

1

ソルバーが解 x に収束しました。

SolverLimitExceeded

0

intlinprog が次の許容誤差のいずれかを超えました。

  • LPMaxIterations

  • MaxNodes

  • MaxTime

  • RootLPMaxIterations

詳細は、許容誤差と停止条件を参照してください。solve は、ルート ノードでメモリ不足となったときにもこの終了フラグを返します。

OutputFcnStop-1intlinprog が出力関数またはプロット関数によって停止されました。
NoFeasiblePointFound

-2

実行可能な点が見つかりません。

Unbounded

-3

問題が非有界です。

FoundNaN

-4

アルゴリズムの実行中に NaN の値があったことを示します。

PrimalDualInfeasible

-5

主問題 および 双対問題とも実行不可能です。

DirectionTooSmall

-7

探索方向が小さくなりすぎました。これ以上進むことができないことを示します。

この表は、linprog ソルバーの終了フラグを説明しています。

linprog の終了フラグ相当する数字意味
OptimalSolution1

ソルバーが解 x に収束しました。

SolverLimitExceeded0

反復数が options.MaxIterations を超過しています。

NoFeasiblePointFound-2

実行可能な点が見つかりません。

Unbounded-3

問題が非有界です。

FoundNaN-4

アルゴリズムの実行中に NaN の値があったことを示します。

PrimalDualInfeasible-5

主問題 および 双対問題とも実行不可能です。

DirectionTooSmall-7

探索方向が小さくなりすぎました。これ以上進むことができないことを示します。

この表は、lsqlin ソルバーの終了フラグを説明しています。

lsqlin の終了フラグ相当する数字意味
FunctionChangeBelowTolerance3

残差の変化が、指定された許容誤差 options.FunctionTolerance より小さい値でした。(trust-region-reflective アルゴリズム)。

StepSizeBelowTolerance

2

ステップ サイズが options.StepTolerance より小さく、制約は満たされました (interior-point アルゴリズム)。

OptimalSolution1

ソルバーが解 x に収束しました。

SolverLimitExceeded0

反復数が options.MaxIterations を超過しています。

NoFeasiblePointFound-2

問題が実行不可能。また、interior-point アルゴリズムの場合、ステップ サイズは options.StepTolerance より小さいが、制約は満たされません。

IllConditioned-4

悪条件のため、さらに最適化を行うことができないことを示します。

NoDescentDirectionFound-8

探索方向が小さくなりすぎました。これ以上進むことができないことを示します。(interior-point アルゴリズム)。

この表は、quadprog ソルバーの終了フラグを説明しています。

quadprog の終了フラグ相当する数字意味
LocalMinimumFound4

局所的最小値が見つかりました。最小値は一意ではありません。

FunctionChangeBelowTolerance3

目的関数の値の変化が、指定された許容誤差 options.FunctionTolerance より小さい値でした。(trust-region-reflective アルゴリズム)。

StepSizeBelowTolerance

2

ステップ サイズが options.StepTolerance より小さく、制約は満たされました (interior-point-convex アルゴリズム)。

OptimalSolution1

ソルバーが解 x に収束しました。

SolverLimitExceeded0

反復数が options.MaxIterations を超過しています。

NoFeasiblePointFound-2

問題が実行不可能。また、interior-point アルゴリズムの場合、ステップ サイズは options.StepTolerance より小さいが、制約は満たされません。

IllConditioned-4

悪条件のため、さらに最適化を行うことができないことを示します。

Nonconvex

-6

非凸問題が検出されました。(interior-point-convex アルゴリズム)。

NoDescentDirectionFound-8

ステップ方向を計算できません。(interior-point-convex アルゴリズム)。

最適化プロセスに関する情報。構造体として返されます。出力構造体に含まれるフィールドには、solve がどのソルバーを呼び出したかに応じて、関連する基となるソルバーの出力フィールドが含まれます。

solve は、使用したソルバー ('intlinprog' など) を示す追加フィールド Solver を構造体 output に含めます。

解におけるラグランジュ乗数。構造体として返されます。intlinprog ソルバーの場合、lambda は空 [] です。他のソルバーの場合、lambda には次のフィールドがあります。

  • Variables - 各問題変数のフィールドを含みます。各問題変数名は、次の 2 つのフィールドをもつ構造体です。

    • Lower – 変数の LowerBound プロパティに関連付けられたラグランジュ乗数。変数と同じサイズの配列として返されます。非ゼロのエントリは、解が下限であることを意味しています。これらの乗数は、構造体 lambda.Variables.variablename.Lower に含まれています。

    • Upper – 変数の UpperBound プロパティに関連付けられたラグランジュ乗数。変数と同じサイズの配列として返されます。非ゼロのエントリは、解が上限であることを意味しています。これらの乗数は、構造体 lambda.Variables.variablename.Upper に含まれています。

  • Constraints - 各問題制約のフィールドを含みます。各問題制約は、制約名と同じ名前で、値が制約と同じサイズの数値配列である構造体に含まれています。非ゼロのエントリは、制約が解においてアクティブであることを意味しています。これらの乗数は、構造体 lambda.Constraints.constraintname に含まれています。

アルゴリズム

関数 solve は、内部的に以下のソルバーを呼び出して最適化問題を解きます。

  • 線形目的関数と線形制約の場合は linprog

  • 線形目的関数と線形制約および整数制約の場合は intlinprog

  • 二次目的関数と線形制約の場合は quadprog

  • 線形制約がある線形最小二乗の場合は lsqlin または lsqnonneg

solve がこれらの関数を呼び出せるためには、solve か、他のいくつかの関連付けられている関数やオブジェクトが事前に問題をソルバー形式に変換しなければなりません。この変換には、たとえば、最適化変数式ではなく行列表現をもつ線形制約が必要になります。

最適化式を問題に含めると、アルゴリズムの最初のステップが発生します。OptimizationProblem オブジェクトは、その式で使用される変数の内部リストを保持しています。変数ごとに、式の線形インデックスとサイズが 1 つずつあります。そのため、問題変数は暗黙的に行列形式となります。関数 prob2struct は、問題形式からソルバー形式への変換を実行します。例については、問題の構造体への変換を参照してください。

問題の目的関数と制約に応じて solve が呼び出す既定ソルバーおよび許容されるソルバーについては、'solver' を参照してください。solve を呼び出すときに、'solver' の名前と値のペア引数を使用することで、この既定をオーバーライドできます。

intlinprog が MILP 問題を解くために使用するアルゴリズムについては、intlinprog アルゴリズムを参照してください。linprog が線形計画問題を解くために使用するアルゴリズムについては、線形計画法のアルゴリズムを参照してください。二次計画問題を解くために quadprog が使用するアルゴリズムについては、二次計画法のアルゴリズムを参照してください。線形最小二乗問題を解くために lsqlin が使用するアルゴリズムについては、最小二乗 (モデル当てはめ) アルゴリズムを参照してください。

メモ

目的関数が二乗和である場合に solve にそのように認識させるには、expr'*expr ではなく sum(expr.^2) と記述します。内部パーサーは、明示的な二乗和のみを認識します。例については、非負の最小二乗法、問題ベースを参照してください。

互換性の考慮事項

すべて展開する

R2018b での開始でエラー

R2017b で導入