Keyword: ２次計画問題, 密な
概要
本サンプルは２次計画問題（密な）を解くFortranによるサンプルプログラムです。 本サンプルは以下に示される制約条件を満たす２次関数を最小化する解を求めて出力します。
※本サンプルはnAG Fortranライブラリに含まれるルーチン e04nff() のExampleコードです。本サンプル及びルーチンの詳細情報は e04nff のマニュアルページをご参照ください。
ご相談やお問い合わせはこちらまで
入力データ
（本ルーチンの詳細はe04nff のマニュアルページを参照）| このデータをダウンロード |
E04NFF Example Program Data 7 7 :Values of N and NCLIN -0.02 -0.20 -0.20 -0.20 -0.20 0.04 0.04 :End of CVEC 1.00 1.00 1.00 1.00 1.00 1.00 1.00 0.15 0.04 0.02 0.04 0.02 0.01 0.03 0.03 0.05 0.08 0.02 0.06 0.01 0.00 0.02 0.04 0.01 0.02 0.02 0.00 0.00 0.02 0.03 0.00 0.00 0.01 0.00 0.00 0.70 0.75 0.80 0.75 0.80 0.97 0.00 0.02 0.06 0.08 0.12 0.02 0.01 0.97 :End of matrix A -0.01 -0.10 -0.01 -0.04 -0.10 -0.01 -0.01 -0.13 -1.0D+25 -1.0D+25 -1.0D+25 -1.0D+25 -9.92D-02 -3.0D-03 :End of BL 0.01 0.15 0.03 0.02 0.05 1.0D+25 1.0D+25 -0.13 -4.9D-03 -6.4D-03 -3.7D-03 -1.2D-03 1.0D+25 2.0D-03 :End of BU -0.01 -0.03 0.00 -0.01 -0.10 0.02 0.01 :End of X 2.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 2.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 2.00 2.00 0.00 0.00 0.00 0.00 0.00 2.00 2.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 2.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 -2.00 -2.00 0.00 0.00 0.00 0.00 0.00 -2.00 -2.00 :End of matrix H
- １行目はタイトル行で読み飛ばされます。
- ２行目に変数の数（n=7）と一般線形制約の数（nclin=7）を指定しています。
- ３行目にf(x)の線形項(cvec)を指定しています。
- ４〜１０行目には線形制約行列Aの要素を指定しています。
- １１〜１２行目には変数と制約の下限(bl)を指定しています。
- １３〜１４行目には変数と制約の上限(bu)を指定しています。
- １５行目にはxの初期推定値を指定しています。
- １６〜２２行目には行列Hの値を指定しています。
出力結果
（本ルーチンの詳細はe04nff のマニュアルページを参照）| この出力例をダウンロード |
E04NFF Example Program Results
*** E04NFF
Parameters
----------
Problem type........... QP2
Linear constraints..... 7 Feasibility tolerance.. 1.05E-08
Variables.............. 7 Optimality tolerance... 1.05E-08
Hessian rows........... 7 Rank tolerance......... 1.11E-14
Infinite bound size.... 1.00E+20 COLD start.............
Infinite step size..... 1.00E+20 EPS (machine precision) 1.11E-16
Check frequency........ 50 Expand frequency....... 5
Minimum sum of infeas.. NO Crash tolerance........ 1.00E-02
Max degrees of freedom. 7 Print level............ 10
Feasibility phase itns. 70 Monitoring file........ -1
Optimality phase itns. 70
Workspace provided is IWORK( 17), WORK( 189).
To solve problem we need IWORK( 17), WORK( 189).
Itn Step Ninf Sinf/Objective Norm Gz
0 0.0E+00 3 1.038000E-01 0.0E+00
1 4.1E-02 1 3.000000E-02 0.0E+00
2 4.2E-02 0 0.000000E+00 0.0E+00
Itn 2 -- Feasible point found.
2 0.0E+00 0 4.580000E-02 0.0E+00
3 1.3E-01 0 4.161596E-02 0.0E+00
4 1.0E+00 0 3.936227E-02 4.2E-17
5 4.1E-01 0 3.758935E-02 1.2E-02
6 1.0E+00 0 3.755377E-02 3.5E-18
7 1.0E+00 0 3.703165E-02 1.8E-17
Varbl State Value Lower Bound Upper Bound Lagr Mult Slack
V 1 LL -1.000000E-02 -1.000000E-02 1.000000E-02 0.4700 .
V 2 FR -6.986465E-02 -0.100000 0.150000 . 3.0135E-02
V 3 FR 1.825915E-02 -1.000000E-02 3.000000E-02 . 1.1741E-02
V 4 FR -2.426081E-02 -4.000000E-02 2.000000E-02 . 1.5739E-02
V 5 FR -6.200564E-02 -0.100000 5.000000E-02 . 3.7994E-02
V 6 FR 1.380544E-02 -1.000000E-02 None . 2.3805E-02
V 7 FR 4.066496E-03 -1.000000E-02 None . 1.4066E-02
L Con State Value Lower Bound Upper Bound Lagr Mult Slack
L 1 EQ -0.130000 -0.130000 -0.130000 -1.908 -5.5511E-17
L 2 FR -5.879898E-03 None -4.900000E-03 . 9.7990E-04
L 3 UL -6.400000E-03 None -6.400000E-03 -0.3144 .
L 4 FR -4.537323E-03 None -3.700000E-03 . 8.3732E-04
L 5 FR -2.915996E-03 None -1.200000E-03 . 1.7160E-03
L 6 LL -9.920000E-02 -9.920000E-02 None 1.955 2.7756E-17
L 7 LL -3.000000E-03 -3.000000E-03 2.000000E-03 1.972 5.2042E-18
Exit E04NFF - Optimal QP solution.
Final QP objective value = 0.3703165E-01
Exit from QP problem after 7 iterations.
- ８〜２２行目に以下に示すプログラムのオプション引数が出力されています。
Problem type 最小化される目的関数の種類。"QP2"は２次計画問題であることを意味します。 Linear constraints 線形制約の数。 Feasibility tolerance 実行可能解での許容可能な制約違反の最大値。 Variables 変数の数。 Optimality tolerance 境界値や制約に正しい符号がついているかを判断するのに使用される許容値。 Hessian rows へシアン行列の行数。 Rank tolerance 三角因子の条件数を制御します。 Infinite bound size 無限の境界。この値以上の上限は+∞と見なされます。またこの値を負に反転させた値以下の下限は−∞と見なされます。 COLD start "COLD Start"は変数や制約の値に基づいて初期のワーキングセットが選ばれていることを示してします。 Infinite step size 無限解へのステップと見なされる変数の変化の大きさ。 EPS (machine precision) マシンの精度。 Check frequency この反復回数の時に現在の解がワーキングセットにある制約を満たしているか確認されます。 Expand frequency 問題を解くためにこの反復数を超えた反復が必要な場合に、新たに反復が開始されます。 Minimum sum of infeas 制約に対して実行可能解がない場合、実行不可能性を最小化すべきかを指定するフラグ。 "NO" を指定した場合、問題が実行不可能とわかり次第ルーチンは終了します。 Crash tolerance 初期のワーキングセットに含まれる不等式制約が下限／上限のこの範囲内にあることを示しています。 Max degrees of freedom 縮小へシアン（Reduced Hessian）の三角因子Rに割り当てられた記憶域の上限。 Print level 結果出力のレベル。"10"は最終解と各反復の結果を出力することを意味します。 Feasibility phase itns 実行可能フェーズでの最大反復数。 Monitoring file 結果が出力されるファイル名。"-1"はモニタリング情報が出力されないことを意味します。 Optimality phase itns 最適化フェーズの最大反復数。 - ２４〜２５行目には、与えられた作業領域の大きさと問題を解くのに必要とされた作業領域の大きさが出力されています。
- ２８〜３８行目には以下が出力されています。また３２行目に２回目の反復で実行可能点が見つかったことが示されています。
Itn 反復回数。 Step 探索方向に進んだステップ幅。 Ninf 違反した制約の数。 Sinf/Objective 制約違反の大きさの加重和（xが実行可能でない場合）もしくは目的関数の値（xが実行可能な場合）。 Norm Gz 縮小勾配のユークリッド・ノルム。 - ４１〜４９行目には以下が出力されています。
Varbl 変数を示す"V"、インデックス。 State 変数の状態。FRは下限も上限もワーキングセットにはないことを意味し、LLは下限であることを意味します。 Value 最後の反復での変数の値。 Lower Bound 下限。 Upper Bound 上限。 Lagr Mult 関連する境界制約のラグランジュ乗数。 Slack スラック（変数の値と上限／下限の近いほうとの差）。 - ５２〜６０行目には以下が出力されています。
L Con 線形制約を示す"L"、インデックス。 State 制約の状態。EQは固定制約を意味し、LLは下限であることを意味し、ULは上限であることを意味し、FRは下限も上限もワーキングセットにはないことを意味します。 Value 最後の反復での制約の値。 Lower Bound 下限。 Upper Bound 上限。 Lagr Mult 関連する境界制約のラグランジュ乗数。 Slack スラック（制約の値と上限／下限の近いほうとの差）。 - ６４行目にQPの最終的な目的関数値が出力されています。
- ６６行目に７回の反復後に終了したことが示されています。
ソースコード
（本ルーチンの詳細はe04nff のマニュアルページを参照）
※本サンプルソースコードは科学技術・統計計算ライブラリである「nAG Fortranライブラリ」のルーチンを呼び出します。
サンプルのコンパイル及び実行方法
| このソースコードをダウンロード |
PROGRAM e04nffe
! E04NFF Example Program Text
! Mark 23 Release. nAG Copyright 2011.
! .. Use Statements ..
USE nag_library, ONLY : e04nff, e04nfu, nag_wp
! .. Implicit None Statement ..
IMPLICIT NONE
! .. Parameters ..
INTEGER, PARAMETER :: nin = 5, nout = 6
! .. Local Scalars ..
REAL (KIND=nag_wp) :: obj
INTEGER :: i, ifail, iter, lda, ldh, liwork, &
lwork, n, nclin, sda
! .. Local Arrays ..
REAL (KIND=nag_wp), ALLOCATABLE :: a(:,:), ax(:), bl(:), bu(:), &
clamda(:), cvec(:), h(:,:), work(:), &
x(:)
INTEGER, ALLOCATABLE :: istate(:), iwork(:)
! .. Intrinsic Functions ..
INTRINSIC max
! .. Executable Statements ..
WRITE (nout,*) 'E04NFF Example Program Results'
FLUSH (nout)
! Skip heading in data file
READ (nin,*)
READ (nin,*) n, nclin
liwork = 2*n + 3
lda = max(1,nclin)
IF (nclin>0) THEN
sda = n
ELSE
sda = 1
END IF
! This particular example problem is of type QP2 with H stored explicitly,
! so we allocate CVEC(N) and H(LDH,N), and define LDH and LWORK as below
ldh = n
IF (nclin>0) THEN
lwork = 2*n**2 + 8*n + 5*nclin
ELSE
lwork = n**2 + 8*n
END IF
ALLOCATE (istate(n+nclin),ax(max(1,nclin)),iwork(liwork),h(ldh,n),bl(n+ &
nclin),bu(n+nclin),cvec(n),x(n),a(lda,sda),clamda(n+nclin), &
work(lwork))
READ (nin,*) cvec(1:n)
READ (nin,*) (a(i,1:sda),i=1,nclin)
READ (nin,*) bl(1:(n+nclin))
READ (nin,*) bu(1:(n+nclin))
READ (nin,*) x(1:n)
READ (nin,*) (h(i,1:n),i=1,n)
! Solve the problem
ifail = 0
CALL e04nff(n,nclin,a,lda,bl,bu,cvec,h,ldh,e04nfu,istate,x,iter,obj,ax, &
clamda,iwork,liwork,work,lwork,ifail)
END PROGRAM e04nffe