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

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

intlinprog を使用して線形計画法を解く

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 向けであることを示しています。

入力引数

prob — 最適化問題

OptimizationProblem オブジェクト

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

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

x0 — 初期点

構造体

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

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

例: prob に変数 x と y がある場合: 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 によって作成されたオブジェクト | オプション構造体

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

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

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

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

'solver' — 最適化ソルバー

'intlinprog' | 'linprog' | 'lsqlin' | 'lsqnonneg' | 'quadprog'

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

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

注意

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

例: 'intlinprog'

データ型: char | string

出力引数

sol — 解

構造体

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

fval — 解での目的関数値

実数

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

ヒント

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

fval = evaluate(prob.Objective,sol)

exitflag — ソルバーの停止理由

カテゴリカル変数

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

intlinprog の終了フラグ	相当する数字	意味
IntegerFeasible	2	intlinprog が途中で停止しました。整数実行可能点が検出されました。
OptimalSolution	1	ソルバーが解 x に収束しました。
SolverLimitExceeded	0	intlinprog が次の許容誤差のいずれかを超えました。 LPMaxIterations MaxNodes MaxTime RootLPMaxIterations 詳細は、許容誤差と停止条件を参照してください。solve は、ルート ノードでメモリ不足となったときにもこの終了フラグを返します。
OutputFcnStop	-1	intlinprog が出力関数またはプロット関数によって停止されました。
NoFeasiblePointFound	-2	実行可能な点が見つかりません。
Unbounded	-3	問題が非有界です。
FoundNaN	-4	アルゴリズムの実行中に NaN の値があったことを示します。
PrimalDualInfeasible	-5	主問題 および 双対問題とも実行不可能です。
DirectionTooSmall	-7	探索方向が小さくなりすぎました。これ以上進むことができないことを示します。

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

linprog の終了フラグ	相当する数字	意味
OptimalSolution	1	ソルバーが解 x に収束しました。
SolverLimitExceeded	0	反復数が options.MaxIterations を超過しています。
NoFeasiblePointFound	-2	実行可能な点が見つかりません。
Unbounded	-3	問題が非有界です。
FoundNaN	-4	アルゴリズムの実行中に NaN の値があったことを示します。
PrimalDualInfeasible	-5	主問題 および 双対問題とも実行不可能です。
DirectionTooSmall	-7	探索方向が小さくなりすぎました。これ以上進むことができないことを示します。

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

lsqlin の終了フラグ	相当する数字	意味
FunctionChangeBelowTolerance	3	残差の変化が、指定された許容誤差 options.FunctionTolerance より小さい値でした。(trust-region-reflective アルゴリズム)。
StepSizeBelowTolerance	2	ステップ サイズが options.StepTolerance より小さく、制約は満たされました (interior-point アルゴリズム)。
OptimalSolution	1	ソルバーが解 x に収束しました。
SolverLimitExceeded	0	反復数が options.MaxIterations を超過しています。
NoFeasiblePointFound	-2	問題が実行不可能。また、interior-point アルゴリズムの場合、ステップ サイズは options.StepTolerance より小さいが、制約は満たされません。
IllConditioned	-4	悪条件のため、さらに最適化を行うことができないことを示します。
NoDescentDirectionFound	-8	探索方向が小さくなりすぎました。これ以上進むことができないことを示します。(interior-point アルゴリズム)。

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

quadprog の終了フラグ	相当する数字	意味
LocalMinimumFound	4	局所的最小値が見つかりました。最小値は一意ではありません。
FunctionChangeBelowTolerance	3	目的関数の値の変化が、指定された許容誤差 options.FunctionTolerance より小さい値でした。(trust-region-reflective アルゴリズム)。
StepSizeBelowTolerance	2	ステップ サイズが options.StepTolerance より小さく、制約は満たされました (interior-point-convex アルゴリズム)。
OptimalSolution	1	ソルバーが解 x に収束しました。
SolverLimitExceeded	0	反復数が options.MaxIterations を超過しています。
NoFeasiblePointFound	-2	問題が実行不可能。また、interior-point アルゴリズムの場合、ステップ サイズは options.StepTolerance より小さいが、制約は満たされません。
IllConditioned	-4	悪条件のため、さらに最適化を行うことができないことを示します。
Nonconvex	-6	非凸問題が検出されました。(interior-point-convex アルゴリズム)。
NoDescentDirectionFound	-8	ステップ方向を計算できません。(interior-point-convex アルゴリズム)。

output — 最適化プロセスに関する情報

構造体

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

• 'intlinprog' output

• 'linprog' output

• 'lsqlin' output

• 'lsqnonneg' output

• 'quadprog' output

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

lambda — 解におけるラグランジュ乗数

構造体

解におけるラグランジュ乗数。構造体として返されます。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) と記述します。内部パーサーは、明示的な二乗和のみを認識します。例については、非負の最小二乗法、問題ベースを参照してください。

互換性の考慮事項

solve(prob,solver)、solve(prob,options) および solve(prob,solver,options) 構文の削除

R2018b での開始でエラー

solve のオプションおよび基礎となるソルバーを選択するには、名前と値のペアを使用します。たとえば、

sol = solve(prob,'options',opts,'solver','quadprog');

上記の構文は、名前と値のペアのような柔軟性、標準性、拡張性がありませんでした。

参考

OptimizationProblem | evaluate | findindex | intlinprog | linprog | lsqlin | lsqnonneg | optimoptions | prob2struct | quadprog

トピック

• 問題ベースのワークフロー
• 名前付きインデックス変数による最適化の初期点の作成

R2017b で導入