ドキュメンテーション

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

構文

x = quadprog(H,f)
x = quadprog(H,f,A,b)
x = quadprog(H,f,A,b,Aeq,beq)
x = quadprog(H,f,A,b,Aeq,beq,lb,ub)
x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)
x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)
x = quadprog(problem)
[x,fval] = quadprog(H,f,...)
[x,fval,exitflag] = quadprog(H,f,...)
[x,fval,exitflag,output] = quadprog(H,f,...)
[x,fval,exitflag,output,lambda] = quadprog(H,f,...)

説明

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

minx12xTHx+fTx such that {Axb,Aeqx=beq,lbxub.

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

f、lb および ub はベクトルまたは行列として渡すことができます。行列引数を参照してください。

x = quadprog(H,f)1/2*x'*H*x + f'*x を最小にするベクトル x を返します。H は有限の最小値をもつ問題の正定でなければなりません。

x = quadprog(H,f,A,b) は制約 A*x  b に従って 1/2*x'*H*x + f'*x を最小化します。A は double 型の行列で、b は double 型のベクトルです。

x = quadprog(H,f,A,b,Aeq,beq) は追加の制約 Aeq*x = beq に従って上記の問題を解きます。Aeq は double 型の行列で、beq は double 型のベクトルです。不等式が存在しない場合は A = [] および b = [] と設定してください。

x = quadprog(H,f,A,b,Aeq,beq,lb,ub) は追加の制約 lb  x  ub に従って上記の問題を解きます。lbub は double 型のベクトルで、制約は x の各要素に対して適用されます。等式が存在しない場合には Aeq = []beq = [] を設定してください。

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

    範囲 lb  x  ub に違反する x0 の要素は、quadprog によって、この範囲で定義されたボックスの内部にリセットされます。quadprog では範囲内の要素は変更されません。

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0) は上記の問題をまず x0 から解いていきます。範囲が存在しない場合には lb = [] および ub = [] を設定します。一部の quadprog アルゴリズムでは x0 が無視されます。入力引数を参照してください。

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options) は、options で指定された最適化オプションを使用して上記の問題を解きます。optimoptions を使用して options を作成してください。初期点を与えない場合は x0 = [] を設定します。

x = quadprog(problem) は、problem の最小値を返します。ここで、problem入力引数で説明されている構造体です。最適化アプリケーションを使用して問題をエクスポートすることで problem を作成します。作業のエクスポートを参照してください。

[x,fval] = quadprog(H,f,...) は、x における目的関数の値を返します。

fval = 0.5*x'*H*x + f'*x

[x,fval,exitflag] = quadprog(H,f,...) exitflagquadprog の終了条件を記述するスカラーです。

[x,fval,exitflag,output] = quadprog(H,f,...) output は最適化の情報を含む構造体です。

[x,fval,exitflag,output,lambda] = quadprog(H,f,...) lambda は、解 x におけるラグランジュ乗数をフィールドに含む構造体です。

入力引数

H

double 型の対称行列。式 1/2*x'*H*x + f'*x における二次項を表します。

f

double 型のベクトル。式 1/2*x'*H*x + f'*x における線形項を表します。

A

double 型の行列。制約 A*x  b における線形係数を表します。

b

double 型のベクトル。制約 A*x  b における定数ベクトルを表します。

Aeq

double 型の行列。制約 Aeq*x = beq における線形係数を表します。

beq

double 型のベクトル。制約 Aeq*x = beq における定数ベクトルを表します。

lb

double 型のベクトル。lb  x  ub における要素ごとの下限を表します。

ub

double 型のベクトル。lb  x  ub における要素ごとの上限を表します。

x0

double 型のベクトル。オプションです。一部の quadprog アルゴリズムに対する初期点は次のとおりです。

  • active-set

  • trust-region-reflective (範囲制約のみがある場合)

x0 を指定しない場合、quadprog では x0 のすべての成分を、範囲によって定義される四角形内部の点に設定します。interior-point-convex アルゴリズムと、等式制約をもつ trust-region-reflective アルゴリズムでは、quadprogx0 を無視します。

options

optimoptions または最適化アプリケーションを使用して作成されるオプション。

すべてのアルゴリズム

Algorithm

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

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

  • 'trust-region-reflective'

  • 'active-set'

'trust-region-reflective' アルゴリズムは、範囲のみをもつ問題、または線形等式制約のみをもつ問題を扱いますが、両方には対応しません。'interior-point-convex' アルゴリズムは凸問題のみを扱います。詳細は、アルゴリズムの選択を参照してください。

Diagnostics

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

Display

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

  • 'off' または 'none' は出力を表示しません。

  • 'final' では最終出力を表示します (既定の設定)。

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

  • 'iter' を指定すると、反復表示を設定できます。

  • 'iter-detailed' を指定すると、反復表示と詳細な終了メッセージの表示を設定できます。

  • 'final-detailed' を指定すると、最終出力のみを詳細な終了メッセージと共に表示するように設定できます。

MaxIter

可能な反復の最大数 (正の整数)。

  • 'trust-region-reflective' 等式制約付き問題の場合、既定値は 2*(numberOfVariables - numberOfEqualities) です。

  • 他のすべてのアルゴリズムおよび問題については、既定値は 200 です。

有効制約法以外のすべてのアルゴリズム

TolFun

関数値に関する終了許容誤差 (正のスカラー)。

  • 'trust-region-reflective' 等式制約付き問題の場合、既定値は 1e-6 です。

  • 範囲制約付きの 'trust-region-reflective' 問題の場合、既定値は 100*eps、約 2.2204e-14 です。

  • 'interior-point-convex' の場合、既定値は 1e-8 です。

TolX

x に関する許容誤差 (正のスカラー)。

  • 'trust-region-reflective' の場合、既定値は 100*eps、約 2.2204e-14 です。

  • 'interior-point-convex' の場合、既定値は 1e-8 です。

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

HessMult

ヘッセ行列乗算関数用の関数ハンドル。大規模構造問題に対して、この関数は実際に H を作らずにヘッセ行列の乗数 H*Y を計算します。関数は次に示す形式になります。

W = hmfun(Hinfo,Y)

ここで Hinfo と追加パラメーターは、H*Y を計算するために使われる行列を含んでいます。

たこのオプションを使用する例は 密な構造化されたヘッセ行列を使った二次最小化 を参照してください。

MaxPCGIter

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

PrecondBandWidth

PCG に対する前提条件子の帯域幅の上限 (非負の整数)。既定の設定では、quadprog は対角型をした前提条件を使用します (帯域幅の上限 0)。一部の問題では、帯域幅を上げることで、PCG 法の反復回数を減らします。PrecondBandWidthInf に設定すると、共役勾配 (CG) ではなく、直接因数分解 (コレスキー因子) を使用します。直接因数分解は CG より計算量が増加しますが、解を求めるためのステップの質が向上します。

TolPCG

PCG 反復に関する終了許容誤差 (正のスカラー)。既定値は 0.1 です。

TypicalX

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

内点法凸アルゴリズムのみ

TolCon

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

problem

quadprog 入力とオプションをカプセル化する構造体。

H

1/2*x'*H*x の対称行列

f

線形項 f'*x のベクトル

Aineq

線形不等式制約 Aineq*x  bineq の行列

bineq

線形不等式制約 Aineq*x  bineq のベクトル

Aeq

線形等式制約 Aeq*x = beq の行列

beq

線形等式制約 Aeq*x = beq のベクトル
lb下限のベクトル
ub上限のベクトル

x0

x の初期点

solver

'quadprog'

options

optimoptions または最適化アプリケーションを使用して作成されるオプション

出力引数

x

すべての範囲制約および線形制約に従って 1/2*x'*H*x + f'*x を最小化するベクトル。非凸問題の場合、x は局所的最小値である場合があります。凸問題の場合、x は大域的最小値です。詳細は、大域的最適解と局所的最適解を参照してください。

fval

x における 1/2*x'*H*x + f'*x の値 (double 型)。

exitflag

アルゴリズムが停止した理由を示す整数。以下の表は exitflag の値とそれに対応したアルゴリズムが終了した理由を示します。

すべてのアルゴリズム

1

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

0

反復数が options.MaxIter を超えたことを示します。

-2

問題が実行不可能です。

-3

問題が非有界です。

interior-point-convex アルゴリズム

-6

非凸問題が検出されました。

trust-region-reflective アルゴリズム

3

目的関数値の変更が options.TolFun よりも小さくなったことを示します。

-4

現在の探索方向は減少の方向ではなく、これ以上進むことができないことを示します。

active-set アルゴリズム

4

局所的な minimizer が見つかりました。

-7

探索方向の大きさが小さくなりすぎ、これ以上進むことができないことを示します。問題の設定または条件が不適切です。

output

最適化に関する情報を含む構造体。フィールドは次のとおりです。

iterations

実行した反復回数

algorithm

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

cgiterations

PCG 法の合計反復回数 (信頼領域 Reflective 法アルゴリズムのみ)

constrviolation

制約関数の最大値

firstorderopt

1 次の最適性の尺度

message

終了メッセージ

lambda

x でのラグランジュ乗数を含む構造体 (制約タイプにより分類) です。フィールドは次のとおりです。

lower

下限 lb

upper

上限 ub

ineqlin

線形不等式

eqlin

線形等式

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

シンプルな二次計画法を解きます。以下を最小化する x の値を探します。

f(x)=12x12+x22x1x22x16x2,

制約条件

x1 + x2 ≤ 2
–x1 + 2x2 ≤ 2
2x1 + x2 ≤ 3
0 ≤ x1, 0 ≤ x2

行列の表記法では、これは次のようになります。

f(x)=12xTHx+fTx,

ここで、

H=[1112],  f=[26],  x=[x1x2].

  1. 係数行列を入力します。

    H = [1 -1; -1 2]; 
    f = [-2; -6];
    A = [1 1; -1 2; 2 1];
    b = [2; 2; 3];
    lb = zeros(2,1);
  2. 表示なしで 'active-set' アルゴリズムを使用するようにオプションを設定します。

    opts = optimoptions('quadprog','Algorithm','active-set','Display','off');
  3. quadprog を呼び出します。

    [x,fval,exitflag,output,lambda] = ...
       quadprog(H,f,A,b,[],[],lb,[],[],opts);
  4. 最終点、関数の値、および終了フラグを調べます。

     x,fval,exitflag
    
    x =
        0.6667
        1.3333
    
    fval =
       -8.2222
    
    exitflag =
         1
  5. 終了フラグが 1 の場合、その結果は局所的最小値です。H は正定行列であるため、この問題は凸であり、最小値は大域的最小値です。H が正定であることは、その固有値がすべて正であることを見ればわかります。

    eig(H)
    ans =
        0.3820
        2.6180

'interior-point-convex' アルゴリズムを使用してスパース二次計画を解きます。

  1. 二次式のためのスパース対称行列を生成します。

    v = sparse([1,-.25,0,0,0,0,0,-.25]);
    H = gallery('circul',v);
  2. 問題の線形項を含めます。

    f = -4:3;
  3. x での各項の合計が -2 未満でなければならないという制約を含めます。

    A = ones(1,8);b = -2;
  4. 'interior-point-convex' アルゴリズムと反復表示を使用するようにオプションを設定します。

    opts = optimoptions('quadprog',...
        'Algorithm','interior-point-convex','Display','iter');
  5. quadprog ソルバーを実行し、反復を観察します。

    [x fval eflag output lambda] = quadprog(H,f,A,b,[],[],[],[],[],opts);
    
                                        First-order	 Total relative
     Iter         f(x)     Feasibility   optimality	     error
        0  -2.000000e+000   1.000e+001   4.500e+000   1.200e+001   
        1  -2.630486e+001   0.000e+000   9.465e-002   9.465e-002   
        2  -2.639877e+001   0.000e+000   3.914e-005   3.914e-005   
        3  -2.639881e+001   0.000e+000   3.069e-015   6.883e-015   
    
    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 function tolerance, and constraints are satisfied to within 
    the default value of the constraint tolerance.
  6. 解の検証:

    fval,eflag
    
    fval =
      -26.3988
    
    eflag =
         1

    'interior-point-convex' アルゴリズムの場合、終了フラグ 1 は結果が大域的最小値であることを意味します。

代替方法

二次計画法には最適化アプリケーションを使用できます。MATLAB® のコマンド ラインに「optimtool」と入力し、[quadprog - 二次計画法] ソルバーを選択してください。詳細は、「最適化アプリケーション」を参照してください。

詳細

すべて折りたたむ

アルゴリズム

trust-region-reflective

'trust-region-reflective' アルゴリズムは部分空間の信頼領域法であり、[1] で説明されている interior-reflective ニュートン法に基づいています。各反復は、前処理付き共役勾配 (PCG) 法を使用する大型線形システムの近似解を伴います。詳細は、trust-region-reflective quadprog アルゴリズムを参照してください。

active-set

quadprog は、[2] の説明と類似した射影法でもある、有効制約法を使用しています。最初に線形計画法を解くことにより、実行可能な初期解を求めます。詳細は、active-set quadprog アルゴリズムを参照してください。

interior-point-convex

'interior-point-convex' アルゴリズムは、厳密に制約内にある経路をたどろうと試みます。このアルゴリズムは前処理モジュールを使用して重複を取り除き、簡単な要素について問題を解くことによって問題を単純化します。詳細は、interior-point-convex quadprog アルゴリズムを参照してください。

参考文献

[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.

[3] Gould, N. and P. L. Toint. “Preprocessing for quadratic programming.” Math. Programming, Series B, Vol. 100, pp. 95–132, 2004.

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