ドキュメンテーション

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

lsqlin

制約付き線形最小二乗問題を解く

範囲制約と線形制約をもつ線形最小二乗法問題のソルバー。

以下の形式の最小二乗曲線近似問題を解きます。

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

メモ

lsqlin は、ソルバーベースのアプローチのみに適用されます。2 つの最適化アプローチの詳細については、はじめに問題ベース アプローチまたはソルバーベース アプローチを選択を参照してください。

構文

x = lsqlin(C,d,A,b)
x = lsqlin(C,d,A,b,Aeq,beq,lb,ub)
x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0,options)
x = lsqlin(problem)
[x,resnorm,residual,exitflag,output,lambda] = lsqlin(___)

説明

x = lsqlin(C,d,A,b) は、A*x ≤ b の制約の下で線形システム C*x = d を最小二乗法的に解きます。

x = lsqlin(C,d,A,b,Aeq,beq,lb,ub) は、線形等式制約 Aeq*x = beq と範囲 lb ≤ x ≤ ub を追加します。Aeqbeq など特定の制約が必要でない場合、これらを [] に設定します。x(i) の下に非有界の場合は lb(i) = -Inf を設定してください。x(i) の上に非有界の場合は ub(i) = Inf を設定してください。

x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0,options) は、初期点 x0 および options で指定された最適化オプションを使用して最小化を行います。optimoptions を使用してこれらのオプションを設定してください。初期点を含めない場合は引数 x0[] に設定します。

x = lsqlin(problem) は、problem の最小値を求めます。problem は構造体です。作業のエクスポートで説明されているように、最適化アプリから問題をエクスポートして problem 構造体を作成します。または、prob2struct を使用して OptimizationProblem オブジェクトから構造体 problem を作成します。

[x,resnorm,residual,exitflag,output,lambda] = lsqlin(___) は、前述のすべての入力引数に対して次を返します。

  • 残差の 2 乗ノルム resnorm = Cxd22

  • 残差 residual = C*x - d

  • 終了条件を指定する値 exitflag

  • 最適化プロセスに関する情報を含む構造体 output

  • ラグランジュ乗数を含む構造体 lambda

    問題の定義の因子 ½ は、lambda 構造体の値に影響します。

すべて折りたたむ

線形不等式制約のある過決定問題について、C*x - d のノルムを最小化する x を求めます。

問題と制約を指定します。

C = [0.9501    0.7620    0.6153    0.4057
    0.2311    0.4564    0.7919    0.9354
    0.6068    0.0185    0.9218    0.9169
    0.4859    0.8214    0.7382    0.4102
    0.8912    0.4447    0.1762    0.8936];
d = [0.0578
    0.3528
    0.8131
    0.0098
    0.1388];
A = [0.2027    0.2721    0.7467    0.4659
    0.1987    0.1988    0.4450    0.4186
    0.6037    0.0152    0.9318    0.8462];
b = [0.5251
    0.2026
    0.6721];

lsqlin を呼び出してこの問題を解きます。

x = lsqlin(C,d,A,b)
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the default value of the optimality tolerance,
and constraints are satisfied to within the default value of the constraint tolerance.
x = 4×1

    0.1299
   -0.5757
    0.4251
    0.2438

線形等式制約と線形不等式制約および範囲指定のある過決定問題について、C*x - d のノルムを最小化する x を求めます。

問題と制約を指定します。

C = [0.9501    0.7620    0.6153    0.4057
    0.2311    0.4564    0.7919    0.9354
    0.6068    0.0185    0.9218    0.9169
    0.4859    0.8214    0.7382    0.4102
    0.8912    0.4447    0.1762    0.8936];
d = [0.0578
    0.3528
    0.8131
    0.0098
    0.1388];
A =[0.2027    0.2721    0.7467    0.4659
    0.1987    0.1988    0.4450    0.4186
    0.6037    0.0152    0.9318    0.8462];
b =[0.5251
    0.2026
    0.6721];
Aeq = [3 5 7 9];
beq = 4;
lb = -0.1*ones(4,1);
ub = 2*ones(4,1);

lsqlin を呼び出してこの問題を解きます。

x = lsqlin(C,d,A,b,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 default value of the optimality tolerance,
and constraints are satisfied to within the default value of the constraint tolerance.
x = 4×1

   -0.1000
   -0.1000
    0.1599
    0.4090

この例では、線形最小二乗法に対して既定ではないオプションを使用する方法を説明します。

'interior-point' アルゴリズムを使用し、反復表示を提供するようにオプションを設定します。

options = optimoptions('lsqlin','Algorithm','interior-point','Display','iter');

線形最小二乗問題を設定します。

C = [0.9501    0.7620    0.6153    0.4057
    0.2311    0.4564    0.7919    0.9354
    0.6068    0.0185    0.9218    0.9169
    0.4859    0.8214    0.7382    0.4102
    0.8912    0.4447    0.1762    0.8936];
d = [0.0578
    0.3528
    0.8131
    0.0098
    0.1388];
A = [0.2027    0.2721    0.7467    0.4659
    0.1987    0.1988    0.4450    0.4186
    0.6037    0.0152    0.9318    0.8462];
b = [0.5251
    0.2026
    0.6721];

問題を実行します。

x = lsqlin(C,d,A,b,[],[],[],[],[],options)
 Iter            Fval  Primal Infeas    Dual Infeas  Complementarity  
    0   -7.687420e-02   1.600492e+00   6.150431e-01     1.000000e+00  
    1   -7.687419e-02   8.002458e-04   3.075216e-04     2.430833e-01  
    2   -3.162837e-01   4.001229e-07   1.537608e-07     5.945636e-02  
    3   -3.760545e-01   2.000616e-10   2.036997e-08     1.370933e-02  
    4   -3.912129e-01   1.000866e-13   1.006816e-08     2.548273e-03  
    5   -3.948062e-01   2.220446e-16   2.955102e-09     4.295807e-04  
    6   -3.953277e-01   2.775558e-17   1.237758e-09     3.102850e-05  
    7   -3.953581e-01   2.775558e-17   1.645862e-10     1.138719e-07  
    8   -3.953582e-01   2.775558e-17   2.399608e-13     5.693290e-11  

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the default value of the optimality tolerance,
and constraints are satisfied to within the default value of the constraint tolerance.
x = 4×1

    0.1299
   -0.5757
    0.4251
    0.2438

lsqlin のすべての出力を取得して解釈します。

線形不等式制約と範囲指定のある問題を定義します。行列 C は 4 つの列をもちますが、行が 5 つあるので過決定問題となります。これは、問題に線形制約と範囲指定を含める以前に、4 つの未知数と 5 つの条件があることを意味します。

C = [0.9501    0.7620    0.6153    0.4057
    0.2311    0.4564    0.7919    0.9354
    0.6068    0.0185    0.9218    0.9169
    0.4859    0.8214    0.7382    0.4102
    0.8912    0.4447    0.1762    0.8936];
d = [0.0578
    0.3528
    0.8131
    0.0098
    0.1388];
A = [0.2027    0.2721    0.7467    0.4659
    0.1987    0.1988    0.4450    0.4186
    0.6037    0.0152    0.9318    0.8462];
b = [0.5251
    0.2026
    0.6721];
lb = -0.1*ones(4,1);
ub = 2*ones(4,1);

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

options = optimoptions('lsqlin','Algorithm','interior-point');

'interior-point' アルゴリズムは初期点を使用しないので、x0[] に設定します。

x0 = [];

すべての出力をもつ lsqlin を呼び出します。

[x,resnorm,residual,exitflag,output,lambda] = ...
    lsqlin(C,d,A,b,[],[],lb,ub,x0,options)
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the default value of the optimality tolerance,
and constraints are satisfied to within the default value of the constraint tolerance.
x = 4×1

   -0.1000
   -0.1000
    0.2152
    0.3502

resnorm = 0.1672
residual = 5×1

    0.0455
    0.0764
   -0.3562
    0.1620
    0.0784

exitflag = 1
output = struct with fields:
            message: 'Minimum found that satisfies the constraints....'
          algorithm: 'interior-point'
      firstorderopt: 4.3374e-11
    constrviolation: 0
         iterations: 6
       linearsolver: 'dense'
       cgiterations: []

lambda = struct with fields:
    ineqlin: [3x1 double]
      eqlin: [0x1 double]
      lower: [4x1 double]
      upper: [4x1 double]

ゼロでないラグランジュ乗数フィールドを詳しく検査します。まず、線形不等式制約のラグランジュ乗数を確認します。

lambda.ineqlin
ans = 3×1

    0.0000
    0.2392
    0.0000

ラグランジュ乗数は、解が対応する制約の境界上にある場合のみ、ゼロ以外の値を取ります。言い換えれば、対応する制約がアクティブなときはラグランジュ乗数が非ゼロとなります。lambda.ineqlin(2) は非ゼロです。したがって、制約がアクティブであるため、A*x の第 2 要素が b の第 2 要素に等しいことを意味します。

[A(2,:)*x,b(2)]
ans = 1×2

    0.2026    0.2026

次に、範囲制約の下限と上限のラグランジュ乗数を確認します。

lambda.lower
ans = 4×1

    0.0409
    0.2784
    0.0000
    0.0000

lambda.upper
ans = 4×1

     0
     0
     0
     0

lambda.lower の最初の 2 つの要素は非ゼロです。x(1)x(2) の値はその下限 -0.1 になっているのがわかります。基本的に lambda.upper の全要素がゼロであり、x の要素はすべてその上限である 2 より低いことがわかります。

入力引数

すべて折りたたむ

乗数行列は double の行列として指定されます。C は、式 C*x - d における解 x の乗数を表します。CMN 列で、M は方程式の数、Nx の要素数です。

例: C = [1,4;2,5;7,8]

データ型: double

定数ベクトルは double のベクトルとして指定されます。d は、式 C*x - d 内の加法定数項を表します。dM1 列で、M は方程式の数です。

例: d = [5;0;-12]

データ型: double

線形不等式制約行列。double 型の行列として指定します。A は制約 A*x  b の線形係数を表します。AMineqN 列のサイズをもちます。ここで、Mineq は制約の数、Nx の要素数です。メモリを節約する場合は A をスパース行列として渡します。

例: A = [4,3;2,0;4,-1]; は、2 つの決定変数 (2 列) 対する 3 つの線形不等式 (3 行) を意味します。

データ型: double

線形不等式制約ベクトル。double 型のベクトルとして指定します。b は、制約 A*x  b の定数ベクトルを表します。b は長さ Mineq をもちます。ここで、AMineqN 列です。

例: [4,0]

データ型: double

線形等式制約行列。double 型の行列として指定します。Aeq は制約 Aeq*x = beq の線形係数を表します。AeqMeqN 列のサイズをもちます。ここで、Meq は制約の数、Nx の要素数です。メモリを節約する場合は Aeq をスパース行列として渡します。

例: A = [4,3;2,0;4,-1]; は、2 つの決定変数 (2 列) 対する 3 つの線形不等式 (3 行) を意味します。

データ型: double

線形等式制約ベクトル。double 型のベクトルとして指定します。beq は、制約 Aeq*x = beq の定数ベクトルを表します。beq は長さ Meq をもちます。ここで、AeqMeqN 列です。

例: [4,0]

データ型: double

下限。double 型のベクトルまたは配列として指定します。lblb  x  ub の要素ごとの下限を表します。

lsqlin は配列 lb をベクトル lb(:) に内部的に変換します。

例: lb = [0;-Inf;4]x(1) ≥ 0, x(3) ≥ 4 を意味します。

データ型: double

上限。double 型のベクトルまたは配列として指定します。ublb  x  ub の要素ごとの上限を表します。

lsqlin は配列 ub をベクトル ub(:) に内部的に変換します。

例: ub = [Inf;4;10]x(2) ≤ 4, x(3) ≤ 10 を意味します。

データ型: double

解法プロセスの初期点は double のベクトルまたは配列として指定されます。x0'trust-region-reflective' アルゴリズムでのみ使用されます。オプションです。

'trust-region-reflective' アルゴリズムに x0 を指定しない場合、lsqlinx0 をゼロ ベクトルに設定します。このゼロ ベクトル x0 のいずれかの要素が範囲に違反すると、lsqlinx0 を、その範囲で定義されるボックス内の点に設定します。

例: x0 = [4;-3]

データ型: double

lsqlin のオプションは、関数 optimoptions または最適化アプリの出力として指定されます。

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

すべてのアルゴリズム

Algorithm

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

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

  • 'trust-region-reflective'

'trust-region-reflective' アルゴリズムは上限と下限 "のみ" を許可します。よって線形不等式や線形等式は必要ありません。'trust-region-reflective' と線形制約の両方を指定した場合、lsqlin'interior-point' アルゴリズムを使用します。

'trust-region-reflective' アルゴリズムは上限と下限を同じ値に設定できません。

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

Diagnostics

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

Display

コマンド ラインに返される表示のレベル。

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

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

'interior-point' アルゴリズムでは、次の値も指定できます。

  • 'iter' — 各反復の出力を表示する。

  • 'iter-detailed' — 各反復の出力を表示し、詳細な終了メッセージを与える。

  • 'final-detailed' — 最終出力のみを表示し、詳細な終了メッセージを与える。

MaxIterations

可能な反復の最大数 (正の整数)。既定値は 200 です。

optimset の場合、名前は MaxIter です。詳細は、オプション名の新旧対照表を参照してください。

trust-region-reflective アルゴリズムのオプション

FunctionTolerance

関数値に関する終了許容誤差 (正のスカラー)。既定値は 100*eps、約 2.2204e-14 です。

optimset の場合、名前は TolFun です。詳細は、オプション名の新旧対照表を参照してください。

JacobianMultiplyFcn

ヤコビ乗算関数。関数ハンドルとして指定されます。大規模構造化問題に対して、この関数は実際に C を計算しないで、ヤコビ行列乗算 C*YC'*YC'*(C*Y) のいずれかを計算します。以下の形式で関数を記述します。

W = jmfun(Jinfo,Y,flag)

ここで、JinfoC*Y (または C'*YC'*(C*Y)) の計算に使用される行列を含んでいます。

jmfun は、lsqlin が渡す flag の値によって、3 種類の乗算のうち、1 つを計算しなければなりません。

  • flag == 0 の場合、W = C'*(C*Y) です。

  • flag > 0 の場合、W = C*Y です。

  • flag < 0 の場合、W = C'*Y です。

どの場合でも jmfunC の形式を陽的に必要としません。lsqlinJinfo を使用して前提条件子を計算します。必要に応じて余分なパラメーターを与える方法については 追加パラメーターの受け渡し を参照してください。

例については、線形最小二乗付きヤコビ乗算関数 を参照してください。

optimset の場合、名前は JacobMult です。詳細は、オプション名の新旧対照表を参照してください。

MaxPCGIter

PCG (前処理付き共役勾配) 法の反復の最大回数です (正のスカラー)。既定値は max(1,floor(numberOfVariables/2)) です。詳細は、信頼領域 Reflective 法アルゴリズムを参照してください。

OptimalityTolerance

1 次の最適性に関する終了許容誤差 (正のスカラー)。既定値は 100*eps、約 2.2204e-14 です。詳細は、1 次の最適性の尺度を参照してください。

optimset の場合、名前は TolFun です。詳細は、オプション名の新旧対照表を参照してください。

PrecondBandWidth

PCG (前処理を使用した共役勾配法) における前提条件子の帯域幅の上限。既定では、対角型の前提条件を使用します (帯域幅の上限 0)。一部の問題では、帯域幅を上げることで、PCG 法の反復回数を減らします。PrecondBandWidthInf に設定すると、共役勾配 (CG) ではなく、直接因子分解 (コレスキー因子) が使用されます。直接因子分解では CG より計算量が増加しますが、解を求めるためのステップの質が向上します。詳細は、信頼領域 Reflective 法アルゴリズムを参照してください。

SubproblemAlgorithm

反復ステップの計算方法を定義します。既定の設定である 'cg' のステップは 'factorization' より高速ですが、精度の点で劣ります。詳細は、信頼領域 Reflective 法の最小二乗を参照してください。

TolPCG

PCG (前処理を使用した共役勾配法) 反復に関する終了許容誤差 (正のスカラー)。既定値は 0.1 です。

TypicalX

典型的な x の値です。TypicalX の要素数は、変数の数と等しくなります。既定値は ones(numberofvariables,1) です。lsqlin はスケーリング用に TypicalX を内部的に使用します。TypicalX は、x が非有界の成分をもつ場合や、非有界の成分 TypicalX 値が 1 より大きい場合にのみ有効です。

interior-point アルゴリズムのオプション

ConstraintTolerance

制約違反に関する許容誤差 (正のスカラー)。既定値は 1e-8 です。

optimset の場合、名前は TolCon です。詳細は、オプション名の新旧対照表を参照してください。

LinearSolver

アルゴリズムの内部的な線形ソルバーのタイプ

  • 'auto' (既定) — 行列 C がスパースである場合は 'sparse'、そうでない場合は 'dense' を使用。

  • 'sparse' — スパースな線形代数を使用。詳細は、スパース行列 (MATLAB)を参照してください。

  • 'dense' — 密な線形代数を使用。

OptimalityTolerance

1 次の最適性に関する終了許容誤差 (正のスカラー)。既定値は 1e-8 です。詳細は、1 次の最適性の尺度を参照してください。

optimset の場合、名前は TolFun です。詳細は、オプション名の新旧対照表を参照してください。

StepTolerance

x に関する許容誤差 (正のスカラー)。既定値は 1e-12 です。

optimset の場合、名前は TolX です。詳細は、オプション名の新旧対照表を参照してください。

最適化問題は、次のフィールドを含む構造体として指定されます。

C

行列乗数 (項 C*x - d)

d

加法定数 (項 C*x - d)

Aineq

線形不等式制約の行列

bineq

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

Aeq

線形等式制約の行列

beq

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

x0

x の初期点

solver

'lsqlin'

options

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

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

データ型: struct

出力引数

すべて折りたたむ

解は、すべての範囲制約および線形制約に従って C*x-d のノルムを最小化するベクトルとして返されます。

目的値はスカラー値 norm(C*x-d)^2 として返されます。

解の残差はベクトル C*x-d として返されます。

アルゴリズムの停止条件。アルゴリズムの停止理由を識別する整数として返されます。exitflag の値と lsqlin が停止した対応する理由を以下に示します。

3

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

2

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

1

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

0

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

-2

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

-4

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

-8

ステップ方向を計算できません。

interior-point アルゴリズムの終了メッセージは、許容誤差の超過など、lsqlin が停止した理由に関する情報をより詳細に提供します。詳細は、終了フラグと終了メッセージを参照してください。

最適化プロセスに関する情報を含む構造体として返された解法プロセスの概要。

iterations

ソルバーが実行した反復の回数。

algorithm

次のいずれかのアルゴリズム。

  • 'interior-point'

  • 'trust-region-reflective'

constrviolation

違反された制約について明らかな制約違反 ('trust-region-reflective' アルゴリズムについては返されない)。

constrviolation = max([0;norm(Aeq*x-beq, inf);(lb-x);(x-ub);(A*x-b)])

message

終了メッセージ。

firstorderopt

解における 1 次の最適性。詳細は、1 次の最適性の尺度を参照してください。

linearsolver

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

cgiterations

ソルバーが実行した共役勾配反復の回数。値が空でないのは 'trust-region-reflective' アルゴリズムの場合のみです。

詳細は、出力構造体を参照してください。

ラグランジュ乗数は以下のフィールドを含む構造体として返されます。

lower

下限 lb

upper

上限 ub

ineqlin

線形不等式

eqlin

線形等式

詳細は、ラグランジュ乗数構造体を参照してください。

ヒント

  • 制約のない問題では mldivide (行列の左除算) を使用できます。制約がない場合、lsqlinx = C\d を返します。

  • 解かれる問題が常に凸型なので、lsqlin は必ずしも一意ではないがグローバルな解を見つけます。

  • lb および ub を陰的に使用する代わりに、Aeq および beq を陽的に使用することで等式を指定する場合、より良い数値結果が出力されます。

  • trust-region-reflective アルゴリズムは上限と下限を同じ値に設定できません。そのような場合は別のアルゴリズムを使用してください。

  • 問題の指定された入力範囲が矛盾する場合、出力 xx0、出力 resnormresidual[] です。

  • 行列 C が大きすぎてメモリが不足する場合など、一部の大規模な構造の問題は、trust-region-reflective アルゴリズムでヤコビ乗算関数を使用して解くことができます。詳細は、trust-region-reflective アルゴリズムのオプション を参照してください。

アルゴリズム

すべて折りたたむ

信頼領域 Reflective 法アルゴリズム

この方法は、部分空間信頼領域法であり、[1] で説明する interior-reflective ニュートン法に基づいています。各反復は、前処理付き共役勾配 (PCG) 法を使用する大型線形システムの近似解を伴います。信頼領域 Reflective 法の最小二乗と、特に大規模な線形最小二乗法を参照してください。

内点法アルゴリズム

'interior-point' アルゴリズムは quadprog 'interior-point-convex' アルゴリズムに基づいています。詳細は、内点線形最小二乗法を参照してください。

参照

[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, pp. 1040–1058, 1996.

[2] Gill, P. E., W. Murray, and M. H. Wright. Practical Optimization, Academic Press, London, UK, 1981.

R2006a より前に導入