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