ドキュメンテーション

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

linprog

線形計画法ソルバー

以下で指定された問題の最小値を見つけます。

minxfTx such that {Axb,Aeqx=beq,lbxub.

f、x、b、beq、lb、ub はベクトル、A と Aeq は行列です。

構文

  • x = linprog(f,A,b)
  • x = linprog(f,A,b,Aeq,beq)
  • x = linprog(f,A,b,Aeq,beq,lb,ub)
  • x = linprog(f,A,b,Aeq,beq,lb,ub,x0)
  • x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)
  • x = linprog(problem)
  • [x,fval] = linprog(___)
  • [x,fval,exitflag,output] = linprog(___)
  • [x,fval,exitflag,output,lambda] = linprog(___)

説明

x = linprog(f,A,b)A*x  b となるような最小の f'*x を解きます。

x = linprog(f,A,b,Aeq,beq) には等式制約 Aeq*x = beq が含まれます。不等式が存在しない場合は A = [] および b = [] と設定してください。

x = linprog(f,A,b,Aeq,beq,lb,ub) は、解が常に lb ≤ x ≤ ub の範囲に存在するように、設計変数 x に上限と下限を定義します。等式が存在しない場合には Aeq = [] および beq = [] と設定してください。

    メモ:   問題の指定された入力範囲に矛盾がない場合、出力 xx0、出力 fval[] です。

x = linprog(f,A,b,Aeq,beq,lb,ub,x0) は初期点を x0 に設定します。

    メモ:   linprog'active-set' アルゴリズムでのみ x0 を使用します。他のすべてのアルゴリズムでは、linprogx0 を無視します。

x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options) は、options で指定された最適化オプションを使って最小化します。optimoptions を使用してこれらのオプションを設定してください。

x = linprog(problem) は、problem の最小値を求めます。ここで、problem入力引数に説明されている構造体です。

作業のエクスポートで説明されているように、最適化アプリから問題をエクスポートして problem 構造体を作成します。mpsread を使用して MPS ファイルから problem 構造体をインポートできます。

[x,fval] = linprog(___) は、すべての入力引数に対して、解 x での目的関数 fun の値 (fval = f'*x) を返します。

[x,fval,exitflag,output] = linprog(___) は上記に加え、終了条件を記述する値 exitflag、および最適化プロセスに関する情報を含む構造体 output を返します。

[x,fval,exitflag,output,lambda] = linprog(___) は上記に加え、解 x におけるラグランジュ乗数をフィールドに含む、構造体 lambda を返します。

すべて折りたたむ

線形不等式で定義された単純な線形計画法を解きます。

この例では、次の線形不等式制約を使用します。

$$ x(1) + x(2) \le 2$$

$$x(1) + x(2)/4 \le 1$$

$$x(1) - x(2) \le 2$$

$$-x(1)/4 - x(2) \le 1$$

$$-x(1) - x(2) \le -1$$

$$-x(1) + x(2) \le 2$$

A = [1 1
    1 1/4
    1 -1
    -1/4 -1
    -1 -1
    -1 1];

b = [2 1 2 1 -1 2];

目的関数 $-x(1) - x(2)/3$ を使用します。

f = [-1 -1/3];

線形計画法を解きます。

x = linprog(f,A,b)
Optimization terminated.

x =

    0.6667
    1.3333

線形不等式および線形等式で定義される単純な線形計画法を解きます。

この例では、次の線形不等式制約を使用します。

$$ x(1) + x(2) \le 2$$

$$x(1) + x(2)/4 \le 1$$

$$x(1) - x(2) \le 2$$

$$-x(1)/4 - x(2) \le 1$$

$$-x(1) - x(2) \le -1$$

$$-x(1) + x(2) \le 2$$

A = [1 1
    1 1/4
    1 -1
    -1/4 -1
    -1 -1
    -1 1];

b = [2 1 2 1 -1 2];

線形等式制約 $x(1) + x(2)/4 = 1/2$ を使用します。

Aeq = [1 1/4];
beq = 1/2;

目的関数 $-x(1) - x(2)/3$ を使用します。

f = [-1 -1/3];

線形計画法を解きます。

x = linprog(f,A,b,Aeq,beq)
Optimization terminated.

x =

    0.0000
    2.0000

線形不等式、線形等式、および範囲を含む単純な線形計画法を解きます。

この例では、次の線形不等式制約を使用します。

$$ x(1) + x(2) \le 2$$

$$x(1) + x(2)/4 \le 1$$

$$x(1) - x(2) \le 2$$

$$-x(1)/4 - x(2) \le 1$$

$$-x(1) - x(2) \le -1$$

$$-x(1) + x(2) \le 2$$

A = [1 1
    1 1/4
    1 -1
    -1/4 -1
    -1 -1
    -1 1];

b = [2 1 2 1 -1 2];

線形等式制約 $x(1) + x(2)/4 = 1/2$ を使用します。

Aeq = [1 1/4];
beq = 1/2;

次の範囲を設定します。

$$-1 \le x(1) \le 1.5$$

$$-0.5 \le x(2) \le 1.25$$

lb = [-1,-0.5];
ub = [1.5,1.25];

目的関数 $-x(1) - x(2)/3$ を使用します。

f = [-1 -1/3];

線形計画法を解きます。

x = linprog(f,A,b,Aeq,beq,lb,ub)
Optimization terminated.

x =

    0.1875
    1.2500

'dual-simplex' アルゴリズムを使用して線形計画法を解きます。

この例では、次の線形不等式制約を使用します。

$$ x(1) + x(2) \le 2$$

$$x(1) + x(2)/4 \le 1$$

$$x(1) - x(2) \le 2$$

$$-x(1)/4 - x(2) \le 1$$

$$-x(1) - x(2) \le -1$$

$$-x(1) + x(2) \le 2$$

A = [1 1
    1 1/4
    1 -1
    -1/4 -1
    -1 -1
    -1 1];

b = [2 1 2 1 -1 2];

線形等式制約 $x(1) + x(2)/4 = 1/2$ を使用します。

Aeq = [1 1/4];
beq = 1/2;

次の範囲を設定します。

$$-1 \le x(1) \le 1.5$$

$$-0.5 \le x(2) \le 1.25$$

lb = [-1,-0.5];
ub = [1.5,1.25];

目的関数 $-x(1) - x(2)/3$ を使用します。

f = [-1 -1/3];

'dual-simplex' アルゴリズムを使用するためのオプションを設定します。

options = optimoptions('linprog','Algorithm','dual-simplex');

dual-simplex アルゴリズムは初期点を受け入れないため、初期点 x0[] に設定します。

x0 = [];

'dual-simplex' アルゴリズムを使用して線形計画法を解きます。

x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)
Optimal solution found.


x =

    0.1875
    1.2500

単純な線形計画法の解および目的関数値を計算します。

非線形制約は次のとおりです。

$$ x(1) + x(2) \le 2$$

$$x(1) + x(2)/4 \le 1$$

$$x(1) - x(2) \le 2$$

$$-x(1)/4 - x(2) \le 1$$

$$-x(1) - x(2) \le -1$$

$$-x(1) + x(2) \le 2$$

A = [1 1
    1 1/4
    1 -1
    -1/4 -1
    -1 -1
    -1 1];

b = [2 1 2 1 -1 2];

目的関数は $-x(1) - x(2)/3$ です。

f = [-1 -1/3];

問題を解き、目的関数値を返します。

[x,fval] = linprog(f,A,b)
Optimization terminated.

x =

    0.6667
    1.3333


fval =

   -1.1111

終了フラグおよび出力構造体を取得することによって、解法プロセスと解の質をよりよく把握できます。

この例では、次の線形不等式制約を使用します。

$$ x(1) + x(2) \le 2$$

$$x(1) + x(2)/4 \le 1$$

$$x(1) - x(2) \le 2$$

$$-x(1)/4 - x(2) \le 1$$

$$-x(1) - x(2) \le -1$$

$$-x(1) + x(2) \le 2$$

A = [1 1
    1 1/4
    1 -1
    -1/4 -1
    -1 -1
    -1 1];

b = [2 1 2 1 -1 2];

線形等式制約 $x(1) + x(2)/4 = 1/2$ を使用します。

Aeq = [1 1/4];
beq = 1/2;

次の範囲を設定します。

$$-1 \le x(1) \le 1.5$$

$$-0.5 \le x(2) \le 1.25$$

lb = [-1,-0.5];
ub = [1.5,1.25];

目的関数 $-x(1) - x(2)/3$ を使用します。

f = [-1 -1/3];

'dual-simplex' アルゴリズムを使用するためのオプションを設定します。

options = optimoptions('linprog','Algorithm','dual-simplex');

dual-simplex アルゴリズムは初期点を受け入れないため、初期点 x0[] に設定します。

x0 = [];

線形計画法を解き、関数値、終了フラグ、および出力構造体を要求します。

[x,fval,exitflag,output] = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)
Optimal solution found.


x =

    0.1875
    1.2500


fval =

   -0.6042


exitflag =

     1


output = 

         iterations: 0
    constrviolation: 0
            message: 'Optimal solution found.'
          algorithm: 'dual-simplex'
      firstorderopt: 0

  • 目的関数値 fval は、より多くの制約があるため、「目的関数値を返す」の場合より大きくなります。

  • exitflag = 1 は、解が信頼できることを示します。

  • output.iterations = 0 は、linprog が解決の前処理で解を見つけ、反復がまったく必要なかったことを示します。

単純な線形計画法を解き、解およびラグランジュ乗数を検証します。

次の目的関数を使用します。

$$f(x) = -5x_1-4x_2-6x_3$$

f = [-5; -4; -6];

次の線形不等式制約を使用します。

$$ x_1 - x_2 + x_3 \le 20$$

$$ 3x_1 + 2x_2 + 4x_3 \le 42$$

$$ 3x_1 + 2x_2 \le 30$$

A =  [1 -1  1
      3  2  4
      3  2  0];
b = [20;42;30];

すべての変数が正になるように制約します。

$$x_1\ge 0$$

$$x_2\ge 0$$

$$x_3\ge 0$$

lb = zeros(3,1);

Aeq および beq[] に設定します。これは、線形等式制約がないことを示します。

Aeq = [];
beq = [];

linprog を呼び出し、ラグランジュ乗数を取得します。

[x,fval,exitflag,output,lambda] = linprog(f,A,b,Aeq,beq,lb);
Optimization terminated.

解とラグランジュ乗数を検証します。

x,lambda.ineqlin,lambda.lower
x =

    0.0000
   15.0000
    3.0000


ans =

    0.0000
    1.5000
    0.5000


ans =

    1.0000
    0.0000
    0.0000

lambda.ineqlin は、x の 2 番目および 3 番目の成分について非ゼロです。これは、2 番目および 3 番目の線形不等式制約が次の等式で満たされることを示します。

$$ 3x_1 + 2x_2 + 4x_3 = 42$$

$$ 3x_1 + 2x_2 = 30$$

これが真であることを確認します。

A*x
ans =

  -12.0000
   42.0000
   30.0000

lambda.lower は、x の 1 番目の成分について非ゼロです。これは、x(1) が下限の 0 になっていることを示します。

関連する例

入力引数

すべて折りたたむ

目的関数。実数ベクトルとして指定されます。linprog は、次の目的関数を最小化する x を求めようとします。

f'*x = f(1)*x(1) + ... + f(N)*x(N)

ここで、N は問題の変数の数です。

例: f = [1,3,5,-6]

データ型: 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(:) の列ベクトル、AeqMeqN 列の行列です。

たとえば、次を指定します。

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))

この場合、ソルバーによって警告が発行されます。

例: すべての 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))

この場合、ソルバーによって警告が発行されます。

例: すべての x 成分が 1 未満になるように指定するため、ub = ones(size(x0)) とします。

データ型: double

初期点。実数ベクトルまたは実数配列として指定されます。x0'active-set' アルゴリズムのみで使用され、他のすべてのソルバーではこの値は無視されます。

例: x0 = ones(size(f))

データ型: double

最適化オプション。optimoptions の出力、または optimset によって返される構造体として指定されます。

いくつかのオプションはすべてのアルゴリズムに適用することができ、その他のオプションは特定のアルゴリズムに関連します。詳細は、最適化オプション リファレンスを参照してください。

一部のオプションは、optimoptions に表示されません。このようなオプションはイタリックで記載されています。詳細は、表示オプションを参照してください。

すべてのアルゴリズム
Algorithm

最適化アルゴリズムを選択します。

  • 'interior-point-legacy' (既定の設定)

  • 'interior-point'

  • 'dual-simplex'

  • 'active-set' (将来のリリースでは削除される予定)

  • 'simplex' (将来のリリースでは削除される予定)

アルゴリズムの選択についての詳細は、線形計画法のアルゴリズムを参照してください。

Diagnostics

最小化または計算する関数に関する情報を表示します。'off' (既定の設定) または 'on' を選択します。

Display

表示レベル (反復表示を参照):

  • 'final' (既定の設定) — 最終出力のみを表示する。

  • 'off' または 'none' — 出力を表示しない。

  • 'iter' — 各反復の出力を表示する。'iter' オプションは 'active-set' アルゴリズムでは使用できません。

LargeScale

代わりに Algorithm を使用します。

既定値の 'on' に設定されている場合は 'interior-point-legacy' アルゴリズムを使用します。'off' に設定されている場合は中規模アルゴリズムを使用します (optionsSimplex を参照)。詳細は、アルゴリズムの選択を参照してください。

MaxIterations

可能な反復の最大数 (正の整数)。既定値は以下のとおりです。

  • 'interior-point-legacy' アルゴリズムの場合は 85

  • 'interior-point' アルゴリズムの場合は 200

  • 'dual-simplex' アルゴリズムの場合は 10*(numberOfEqualities + numberOfInequalities + numberOfVariables)

  • 'simplex' アルゴリズムの場合は 10*numberOfVariables

  • 'active-set' アルゴリズムの場合は 10*max(numberOfVariables, numberOfInequalities + numberOfBounds)

詳細は、許容誤差と停止条件反復と関数計算回数を参照してください。

OptimalityTolerance

双対実行可能性に関する終了許容誤差 (正のスカラー)。既定値は以下のとおりです。

  • 'interior-point-legacy' アルゴリズムの場合は 1e-8

  • 'dual-simplex' アルゴリズムの場合は 1e-7

  • 'interior-point' アルゴリズムおよび 'simplex' アルゴリズムの場合は 1e-6

  • 'active-set' アルゴリズムの場合はオプションの使用なし

内点法アルゴリズム
ConstraintTolerance

制約の実行可能性の許容誤差で 1e-10 から 1e-3 のスカラー。ConstraintTolerance は、主実行可能性の許容誤差を測定します。既定の設定は 1e-6 です。

Preprocess

アルゴリズムの反復前に行われる LP の前処理のレベル。'basic' (既定の設定) または 'none' を指定します。

双対シンプレックス法アルゴリズム
ConstraintTolerance

制約の実行可能性の許容誤差で 1e-10 から 1e-3 のスカラー。ConstraintTolerance は、主実行可能性の許容誤差を測定します。既定値は 1e-4 です。

MaxTime

アルゴリズムを実行する秒単位の最長時間。既定値は Inf です。

Preprocess

双対シンプレックス法アルゴリズムの反復前に行われる LP の前処理のレベル。'basic' (既定の設定) または 'none' を指定します。

シンプレックス アルゴリズム

Simplex

代わりに Algorithm を使用します。

'on' の場合、LargeScale'off' であれば、linprog はシンプレックス アルゴリズムを使用します。シンプレックス アルゴリズムは組み込みの出発点を使用し、開始点 x0 が与えられた場合は無視します。既定値は 'off'、すなわち linprog は有効制約法アルゴリズムを使用します。

例: options = optimoptions('linprog','Algorithm','interior-point','Display','iter')

次のフィールドをもつ構造体として指定される問題構造体です。

フィールド名エントリ

f

線形目的関数ベクトル f

Aineq

線形不等式制約の行列

bineq

線形不等式制約のベクトル

Aeq

線形等式制約の行列

beq

線形等式制約のベクトル
lb下限のベクトル
ub上限のベクトル

x0

x の初期点、有効制約法アルゴリズムのみ

solver

'linprog'

options

optimoptions で作成されたオプション

problem 構造体では、少なくとも solver フィールドを指定しなければなりません。

problem 構造体を取得する最も簡単な方法は、最適化アプリから問題をエクスポートすることです。

データ型: struct

出力引数

すべて折りたたむ

実数ベクトルまたは実数配列として返される解です。x のサイズは、f または x0 のサイズと同じです。

解での目的関数値。実数として返されます。一般的に、fval = f'*x になります。

linprog の停止理由。整数として返されます。

1

関数が解 x に収束したことを示します。

0

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

-2

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

-3

問題が非有界です。

-4

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

-5

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

-7

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

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

iterations

反復回数

algorithm

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

cgiterations

0 (内点法アルゴリズムのみ。下位互換性のために含められます)

message

終了メッセージ

constrviolation

制約関数の最大値

firstorderopt

1 次の最適性の尺度

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

lower

lb に対応する下限

upper

ub に対応する上限

ineqlin

A および b に対応する線形不等式

eqlin

Aeq および beq に対応する線形等式

制限

  • 'active-set' アルゴリズムの Display オプションは 'off' および 'final' のみです。反復表示オプション 'iter' は選択できません。

詳細

すべて折りたたむ

アルゴリズム

レガシ内点法アルゴリズム

'interior-point-legacy' 法は LIPSOL (Linear Interior Point Solver、[3]) をベースにしています。この方法は、主双対内点法である Mehrotra 予測子修正子アルゴリズム [2] に変更を加えたものです。アルゴリズムの中で、反復が始まる前に、いくつかの前処理手順が行われます。詳細は、レガシ内点線形計画法を参照してください。

アルゴリズムの第 1 ステージでは、何らかの制約の前処理を伴います(レガシ内点線形計画法 を参照してください)。いくつかの条件では linprog が実行不可能であるメッセージで終了する可能性があります。いずれの場合でも、linprog は負の exitflag を返し、失敗したことを示します。

  • Aeq 内のある行のすべての要素がゼロであり、その行に対応する beq の要素がゼロでない場合、終了メッセージは次のようになります。

    Exiting due to infeasibility: An all-zero row in the
    constraint matrix does not have a zero in corresponding
    right-hand-side entry.
  • x の要素の 1 つが制約の下限を満たしていない場合、終了メッセージは次のようになります。

    Exiting due to infeasibility: Objective f'*x is unbounded below.
  • Aeq の行の中で、非ゼロ要素が 1 つしかない場合、x の中でそれに対応する値を "シングルトン" 変数と言います。この場合、x のその構成要素の値を Aeq および beq から計算することができます。計算した値が別の制約に違反する場合、終了メッセージは次のようになります。

    Exiting due to infeasibility: Singleton variables in
    equality constraints are not feasible.
  • シングルトン変数が、上限または下限のどちらかの制約に違反する状態で解かれる場合、終了メッセージは次のようになります。

    Exiting due to infeasibility: Singleton variables in
    the equality constraints are not within bounds.

    メモ:   前処理手順は累積的な性質をもちます。そのため、制約行列に行全体がすべてゼロであるような行が存在しない場合でさえ、他の前処理手順により、すべての要素がゼロになる可能性もあります。

前処理が終了すると、停止条件を満たすまで、反復部分のアルゴリズムが始まります(残差、主問題、双対問題、および関連する停止条件の詳細は レガシ内点線形計画法 を参照してください)。残差が少なくならずに大きくなる場合、または残差が大きくも小さくもならない場合、次の 2 つの終了メッセージのどちらかが表示されます。

One or more of the residuals, duality gap, or total relative error 
has grown 100000 times greater than its minimum value so far:

または

One or more of the residuals, duality gap, or total relative error 
has stalled:

これらのメッセージの 1 つを表示した後、双対、主、またはその両方が実行不可能である場合、そのいずれかを示す次のメッセージの中の 1 つが表示されます。

  • The dual appears to be infeasible (and the primal unbounded). (The primal residual < OptimalityTolerance.)

  • The primal appears to be infeasible (and the dual unbounded). (The dual residual < OptimalityTolerance.)

  • The dual appears to be infeasible (and the primal unbounded) since the dual residual > sqrt(OptimalityTolerance). (The primal residual < 10*OptimalityTolerance.)

  • The primal appears to be infeasible (and the dual unbounded) since the primal residual > sqrt(OptimalityTolerance). (The dual residual < 10*OptimalityTolerance.)

  • The dual appears to be infeasible and the primal unbounded since the primal objective < -1e+10 and the dual objective < 1e+6.

  • The primal appears to be infeasible and the dual unbounded since the dual objective > 1e+10 and the primal objective > -1e+6.

  • Both the primal and the dual appear to be infeasible.

たとえば、主 (目的) 関数が非有界になるか、また主残差 (これは主制約の満足度の尺度) が小さくなる可能性があります。

内点法アルゴリズム

'interior-point' アルゴリズムは 'interior-point-legacy' とよく似ていますが、より効率的な因子分解ルーチンがあり、前処理が異なります。詳細は、linprog 内点法アルゴリズムを参照してください。

双対シンプレックス法アルゴリズム

詳細は、双対シンプレックス法アルゴリズム を参照してください。

有効制約法アルゴリズムとシンプレックス アルゴリズム

'active-set' アルゴリズムは quadprog アルゴリズムで使用するものと同じ射影法を使用します。linprog は有効制約法であり、線形計画法 [1] として有名な "シンプレックス" 法を変更したものです。最初に別の線形計画法を解くことで、初期の実行可能解を求めます。詳細は、linprog 有効制約法アルゴリズムを参照してください。

'simplex' アルゴリズムについては、linprog シンプレックス アルゴリズム を参照してください。

linprog は問題が実行不可能な場合に警告を表示します。

Warning: The constraints are overly stringent;
there is no feasible solution.

この場合、linprog は最悪のケースの制約違反を最小化する結果を出力します。

等式制約に矛盾する場合 linprog は次のように出力します。

Warning: The equality constraints are overly
stringent; there is no feasible solution.

解が非有界の場合は、以下の警告が表示されます。

Warning: The solution is unbounded and at infinity;
the constraints are not restrictive enough.

この場合、linprog は制約を満たす x の値を返します。

参照

[1] Dantzig, G.B., A. Orden, and P. Wolfe. “Generalized Simplex Method for Minimizing a Linear Form Under Linear Inequality Restraints.” Pacific Journal Math., Vol. 5, 1955, pp. 183–195.

[2] Mehrotra, S. “On the Implementation of a Primal-Dual Interior Point Method.” SIAM Journal on Optimization, Vol. 2, 1992, pp. 575–601.

[3] Zhang, Y., “Solving Large-Scale Linear Programs by Interior-Point Methods Under the MATLAB Environment.” Technical Report TR96-01, Department of Mathematics and Statistics, University of Maryland, Baltimore County, Baltimore, MD, July 1995.

R2006a より前に導入

この情報は役に立ちましたか?