Keyword: 2次計画問題, 密な
概要
本サンプルは2次計画問題(密な)を解くC言語によるサンプルプログラムです。 本サンプルは以下に示される制約条件を満たす2次関数を最小化する解を求めて出力します。
※本サンプルはnAG Cライブラリに含まれる関数 nag_opt_qp() のExampleコードです。本サンプル及び関数の詳細情報は nag_opt_qp のマニュアルページをご参照ください。
ご相談やお問い合わせはこちらまで
オプション・パラメータ
(本関数の詳細はnag_opt_qp のマニュアルページを参照)1 2 3 4 5 6 7 8 9 10
このデータをダウンロード |
nag_opt_qp (e04nfc) Example Program Optional Parameters Following options for e04nfc are read by e04xyc. begin e04nfc fmax_iter = 30 /* Set maximum number of iterations in feasiblity phase */ max_iter = 50 /* Set maximum total number of iterations */ end
- 1行目はタイトル行で読み飛ばされます。
- 5~10行目にe04xycによって読み込まれる、e04nfcに渡すオプショナル引数を指定しています。
fmax_iter 実行可能フェーズでの最大反復数。 max_iter 最大反復数。
入力データ
(本関数の詳細はnag_opt_qp のマニュアルページを参照)1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
このデータをダウンロード |
nag_opt_qp (e04nfc) Example Program Data Linear term of f(x), c. -0.02 -0.2 -0.2 -0.2 -0.2 0.04 0.04 Linear constraint matrix, A. 1.0 1.0 1.0 1.0 1.0 1.0 1.0 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.0 0.02 0.04 0.01 0.02 0.02 0.0 0.0 0.02 0.03 0.0 0.0 0.01 0.0 0.0 0.70 0.75 0.80 0.75 0.80 0.97 0.0 0.02 0.06 0.08 0.12 0.02 0.01 0.97 Lower bounds -0.01 -0.1 -0.01 -0.04 -0.1 -0.01 -0.01 -0.13 -1.0e21 -1.0e21 -1.0e21 -1.0e21 -0.0992 -0.003 Upper bounds 0.01 0.15 0.03 0.02 0.05 1.0e21 1.0e21 -0.13 -0.0049 -0.0064 -0.0037 -0.0012 1.0e21 0.002 Initial estimate of x -0.01 -0.03 0.0 -0.01 -0.1 0.02 0.01
- 1行目はタイトル行で読み飛ばされます。
- 3行目にf(x)の線形項(cvec)を指定しています。
- 5~11行目には線形制約行列Aの要素を指定しています。
- 13~14行目には変数と制約の下限(bl)を指定しています。
- 16~17行目には変数と制約の上限(bu)を指定しています。
- 19行目にはxの初期推定値を指定しています。
出力結果
(本関数の詳細はnag_opt_qp のマニュアルページを参照)1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128
この出力例をダウンロード |
nag_opt_qp (e04nfc) Example Program Results Optional parameter setting for e04nfc. -------------------------------------- Option file: e04nfce.opt fmax_iter set to 30 max_iter set to 50 Parameters to e04nfc -------------------- Linear constraints............ 7 Number of variables........... 7 prob.................... Nag_QP2 start................... Nag_Cold ftol.................... 1.05e-08 reset_ftol.............. 5 rank_tol................ 1.11e-14 crash_tol............... 1.00e-02 fcheck.................. 50 max_df.................. 7 inf_bound............... 1.00e+21 inf_step................ 1.00e+21 fmax_iter............... 30 max_iter................ 50 hrows................... 7 machine precision....... 1.11e-16 optim_tol............... 1.72e-13 min_infeas.............. Nag_FALSE print_level......... Nag_Soln_Iter outfile................. stdout Memory allocation: state................... Nag ax...................... Nag lambda.................. Nag Results from e04nfc: ------------------- Itn Jdel Jadd Step Ninf Sinf/Obj Bnd Lin Nart Nrz Norm Gz 0 0 0 0.0e+00 3 1.0380e-01 3 4 0 0 0.00e+00 1 9 U 13 L 4.1e-02 1 3.0000e-02 3 4 0 0 0.00e+00 2 12 U 4 L 4.2e-02 0 0.0000e+00 4 3 0 0 0.00e+00 (User-supplied callback qphess1, first invocation.) Itn 2 -- Feasible point found. 2 0 0 0.0e+00 0 4.5800e-02 4 3 0 0 0.00e+00 3 5 L 14 L 1.3e-01 0 4.1616e-02 3 4 0 0 0.00e+00 4 11 U 0 1.0e+00 0 3.9362e-02 3 3 0 1 3.82e-17 5 3 L 10 U 4.1e-01 0 3.7589e-02 2 4 0 1 1.19e-02 6 0 0 1.0e+00 0 3.7554e-02 2 4 0 1 3.47e-18 7 4 L 0 1.0e+00 0 3.7032e-02 1 4 0 2 3.37e-17 Final solution: Varbl State Value Lower Bound Upper Bound Lagr Mult Residual V 1 LL -1.00000e-02 -1.0000e-02 1.0000e-02 4.700e-01 0.000e+00 V 2 FR -6.98646e-02 -1.0000e-01 1.5000e-01 0.000e+00 3.014e-02 V 3 FR 1.82592e-02 -1.0000e-02 3.0000e-02 0.000e+00 1.174e-02 V 4 FR -2.42608e-02 -4.0000e-02 2.0000e-02 0.000e+00 1.574e-02 V 5 FR -6.20056e-02 -1.0000e-01 5.0000e-02 0.000e+00 3.799e-02 V 6 FR 1.38054e-02 -1.0000e-02 None 0.000e+00 2.381e-02 V 7 FR 4.06650e-03 -1.0000e-02 None 0.000e+00 1.407e-02 LCon State Value Lower Bound Upper Bound Lagr Mult Residual L 1 EQ -1.30000e-01 -1.3000e-01 -1.3000e-01 -1.908e+00 0.000e+00 L 2 FR -5.87990e-03 None -4.9000e-03 0.000e+00 9.799e-04 L 3 UL -6.40000e-03 None -6.4000e-03 -3.144e-01 0.000e+00 L 4 FR -4.53732e-03 None -3.7000e-03 0.000e+00 8.373e-04 L 5 FR -2.91600e-03 None -1.2000e-03 0.000e+00 1.716e-03 L 6 LL -9.92000e-02 -9.9200e-02 None 1.955e+00 -1.388e-17 L 7 LL -3.00000e-03 -3.0000e-03 2.0000e-03 1.972e+00 -3.036e-18 Exit after 7 iterations. Optimal QP solution found. Final QP objective value = 3.7031646e-02 A run of the same example with a warm start: Parameters to e04nfc -------------------- Linear constraints............ 7 Number of variables........... 7 prob.................... Nag_QP2 start................... Nag_Warm ftol.................... 1.05e-08 reset_ftol.............. 5 rank_tol................ 1.11e-14 crash_tol............... 1.00e-02 fcheck.................. 50 max_df.................. 7 inf_bound............... 1.00e+21 inf_step................ 1.00e+21 fmax_iter............... 30 max_iter................ 50 hrows................... 7 machine precision....... 1.11e-16 optim_tol............... 1.72e-13 min_infeas.............. Nag_FALSE print_level......... Nag_Soln outfile................. stdout Memory allocation: state................... Nag ax...................... Nag lambda.................. Nag (User-supplied callback qphess2, first invocation.) Final solution: Varbl State Value Lower Bound Upper Bound Lagr Mult Residual V 1 LL -1.00000e-02 -1.0000e-02 1.0000e-02 4.700e-01 0.000e+00 V 2 FR -6.98646e-02 -1.0000e-01 1.5000e-01 0.000e+00 3.014e-02 V 3 FR 1.82592e-02 -1.0000e-02 3.0000e-02 0.000e+00 1.174e-02 V 4 FR -2.42608e-02 -4.0000e-02 2.0000e-02 0.000e+00 1.574e-02 V 5 FR -6.20056e-02 -1.0000e-01 5.0000e-02 0.000e+00 3.799e-02 V 6 FR 1.38054e-02 -1.0000e-02 None 0.000e+00 2.381e-02 V 7 FR 4.06650e-03 -1.0000e-02 None 0.000e+00 1.407e-02 LCon State Value Lower Bound Upper Bound Lagr Mult Residual L 1 EQ -1.30000e-01 -1.3000e-01 -1.3000e-01 -1.908e+00 0.000e+00 L 2 FR -5.87990e-03 None -4.9000e-03 0.000e+00 9.799e-04 L 3 UL -6.40000e-03 None -6.4000e-03 -3.144e-01 8.674e-19 L 4 FR -4.53732e-03 None -3.7000e-03 0.000e+00 8.373e-04 L 5 FR -2.91600e-03 None -1.2000e-03 0.000e+00 1.716e-03 L 6 LL -9.92000e-02 -9.9200e-02 None 1.955e+00 1.388e-17 L 7 LL -3.00000e-03 -3.0000e-03 2.0000e-03 1.972e+00 0.000e+00 Exit after 0 iterations. Optimal QP solution found. Final QP objective value = 3.7031646e-02
- 6行目にオプション・ファイルe04nfce.optが読み込まれたことが示されています。
- 8行目にfmax_iter が30に設定されたことが示されています。
- 9行目にmax_iter が30に設定されたことが示されています。
- 14行目に線形制約の数、変数の数が出力されています。
- 16~25行目に以下に示すプログラムのオプション引数が出力されています。
prob 最小化される目的関数の種類。"Nag_QP2"は2次計画問題であることを意味します。 start 初期のワーキングセットがどのように選ばれるかを示しています。"Nag_Cold"は変数や制約の値に基づいて初期のワーキングセットが選ばれていることを意味します。 ftol 実行可能解での許容可能な制約違反の最大値。 reset_ftol 問題を解くためにこの反復数を超えた反復が必要な場合に、新たに反復が開始されます。 fcheck この反復回数の時に現在の解がワーキングセットにある制約を満たしているか確認されます。 max_df 縮小へシアン(Reduced Hessian)の三角因子Rに割り当てられた記憶域の上限。 crash_tol 初期のワーキングセットに含まれる不等式制約が下限/上限のこの範囲内にあることを示しています。 inf_bound 無限の境界。この値以上の上限は+∞と見なされます。またこの値を負に反転させた値以下の下限は−∞と見なされます。 inf_step 無限解へのステップと見なされる変数の変化の大きさ。 fmax_iter 実行可能フェーズでの最大反復数。 max_iter 最適化フェーズの最大反復数。 hrows QP目的関数の二次項Hの行数。 machine precision マシンの精度。 optim_tol 境界値や制約に正しい符号がついているかを判断するのに使用される許容値。 min_infeas 制約に対して実行可能解がない場合、実行不可能性を最小化すべきかを指定するフラグ。 "Nag_FALSE" を指定した場合、問題が実行不可能とわかり次第ルーチンは終了します。 print_level 結果出力のレベル。"Nag_Soln_Iter"は最終解と各反復の結果を出力することを意味します。 outfile 結果が出力されるファイル名。"stdout"は標準出力を意味します。 - 27~29行目には、オプション引数state、ax、lambdaに必要なメモリがnAGライブラリの関数によって自動的に割り当てられたことを示しています。
- 34~46行目には以下が出力されています。また40行目に2回目の反復で実行可能点が見つかったことが示されています。
Itn 反復回数。 Jdel ワーキングセットから削除される制約のインデックス。"U"は上限、"L"は下限を意味します。 Jadd ワーキングセットに追加される制約のインデックス。"U"は上限、"L"は下限を意味します。 Step 探索方向に進んだステップ幅。 Ninf 違反した制約の数。 Sinf/Obj 制約違反の大きさの加重和(xが実行可能でない場合)もしくは目的関数の値(xが実行可能な場合)。 Bnd 現在のワーキングセットの簡易境界制約の数。 Lin 現在のワーキングセットの一般線形制約の数。 Nart ワーキングセットの人為的制約の数。 Nrz 目的関数が最小化される部分空間の次元数。 Norm Gz 縮小勾配のユークリッド・ノルム。 - 50~58行目には以下が出力されています。
Varbl 変数を示す"V"、インデックス。 State 変数の状態。FRは下限も上限もワーキングセットにはないことを意味し、LLは下限であることを意味します。 Value 最後の反復での変数の値。 Lower Bound 下限。 Upper Bound 上限。 Lagr Mult 関連する境界制約のラグランジュ乗数。 Residual 残差(変数の値と上限/下限の近いほうとの差)。 - 60~68行目には以下が出力されています。
LCon 線形制約を示す"L"、インデックス。 State 制約の状態。EQは固定制約を意味し、LLは下限であることを意味し、ULは上限であることを意味し、FRは下限も上限もワーキングセットにはないことを意味します。 Value 最後の反復での制約の値。 Lower Bound 下限。 Upper Bound 上限。 Lagr Mult 関連する境界制約のラグランジュ乗数。 Residual 残差(制約の値と上限/下限の近いほうとの差)。 - 70行目に7回の反復を行ったことが示されています。
- 72行目にQPの最適解が見つかったことが示されています。
- 74行目にQPの最終的な目的関数値が出力されています。
- 77行目にwarm startで同じQP問題を解くことが示されています。
- 82行目に線形制約の数、変数の数が出力されています。
- 84~93行目にプログラムのオプション引数が出力されています。
- 95~97行目には、オプション引数state、ax、lambdaに必要なメモリがnAGライブラリの関数によって自動的に割り当てられたことを示しています。
- 101~109行目には以下が出力されています。
Varbl 変数を示す"V"、インデックス。 State 変数の状態。FRは下限も上限もワーキングセットにはないことを意味し、LLは下限であることを意味します。 Value 最後の反復での変数の値。 Lower Bound 下限。 Upper Bound 上限。 Lagr Mult 関連する境界制約のラグランジュ乗数。 Residual 残差(変数の値と上限/下限の近いほうとの差)。 - 111~119行目には以下が出力されています。
LCon 線形制約を示す"L"、インデックス。 State 制約の状態。EQは固定制約を意味し、LLは下限であることを意味し、ULは上限であることを意味し、FRは下限も上限もワーキングセットにはないことを意味します。 Value 最後の反復での制約の値。 Lower Bound 下限。 Upper Bound 上限。 Lagr Mult 関連する境界制約のラグランジュ乗数。 Residual 残差(制約の値と上限/下限の近いほうとの差。) - 121行目に反復せずに終了したことが示されています。
- 123行目にQPの最適解が見つかったことが示されています。
- 125行目にQPの最終的な目的関数値が出力されています。
ソースコード
(本関数の詳細はnag_opt_qp のマニュアルページを参照)
※本サンプルソースコードはnAG数値計算ライブラリ(Windows, Linux, MAC等に対応)の関数を呼び出します。
サンプルのコンパイル及び実行方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263
このソースコードをダウンロード |
/* nag_opt_qp (e04nfc) Example Program. * * CLL6I261D/CLL6I261DL Version. * * Copyright 2017 Numerical Algorithms Group. * * Mark 26.1, 2017. * */ #include <nag.h> #include <stdio.h> #include <string.h> #include <nag_stdlib.h> #include <nag_string.h> #include <nage04.h> #ifdef __cplusplus extern "C" { #endif static void nAG_CALL qphess1(Integer n, Integer jthcol, const double h[], Integer tdh, const double x[], double hx[], Nag_Comm *comm); static void nAG_CALL qphess2(Integer n, Integer jthcol, const double h[], Integer tdh, const double x[], double hx[], Nag_Comm *comm); #ifdef __cplusplus } #endif #define A(I, J) a[(I) *tda + J] #define H(I, J) h[(I) *tdh + J] int main(void) { const char *optionsfile = "e04nfce.opt"; static double ruser[2] = { -1.0, -1.0 }; Nag_Boolean print; Integer exit_status = 0, i, j, n, nbnd, nclin, tda, tdh; Nag_E04_Opt options; double *a = 0, *bl = 0, *bu = 0, *cvec = 0, *h = 0, objf, *x = 0; Nag_Comm comm; NagError fail; INIT_FAIL(fail); printf("nag_opt_qp (e04nfc) Example Program Results\n"); /* For communication with user-supplied functions: */ comm.user = ruser; fflush(stdout); scanf(" %*[^\n]"); /* Skip heading in data file */ /* Set the actual problem dimensions. * n = the number of variables. * nclin = the number of general linear constraints (may be 0). */ n = 7; nclin = 7; if (n > 0 && nclin >= 0) { nbnd = n + nclin; if (!(x = nAG_ALLOC(n, double)) || !(cvec = nAG_ALLOC(n, double)) || !(a = nAG_ALLOC(nclin * n, double)) || !(h = nAG_ALLOC(n * n, double)) || !(bl = nAG_ALLOC(nbnd, double)) || !(bu = nAG_ALLOC(nbnd, double))) { printf("Allocation failure\n"); exit_status = -1; goto END; } tda = n; tdh = n; } else { printf("Invalid n or nclin.\n"); exit_status = 1; return exit_status; } /* cvec = the coefficients of the explicit linear term of f(x). * a = the linear constraint matrix. * bl = the lower bounds on x and A*x. * bu = the upper bounds on x and A*x. * x = the initial estimate of the solution. */ /* Read the coefficients of the explicit linear term of f(x). */ scanf(" %*[^\n]"); /* Skip heading in data file */ for (i = 0; i < n; ++i) scanf("%lf", &cvec[i]); /* Read the linear constraint matrix A. */ scanf(" %*[^\n]"); /* Skip heading in data file */ for (i = 0; i < nclin; ++i) for (j = 0; j < n; ++j) scanf("%lf", &A(i, j)); /* Read the bounds. */ nbnd = n + nclin; scanf(" %*[^\n]"); /* Skip heading in data file */ for (i = 0; i < nbnd; ++i) scanf("%lf", &bl[i]); scanf(" %*[^\n]"); /* Skip heading in data file */ for (i = 0; i < nbnd; ++i) scanf("%lf", &bu[i]); /* Read the initial estimate of x. */ scanf(" %*[^\n]"); /* Skip heading in data file */ for (i = 0; i < n; ++i) scanf("%lf", &x[i]); /* nag_opt_init (e04xxc). * Initialization function for option setting */ nag_opt_init(&options); /* Initialize options structure */ /* Set one option directly * Bounds >= inf_bound will be treated as plus infinity. * Bounds <= -inf_bound will be treated as minus infinity. */ options.inf_bound = 1.0e21; /* Read remaining option values from file */ print = Nag_TRUE; /* nag_opt_read (e04xyc). * Read options from a text file */ nag_opt_read("e04nfc", optionsfile, &options, print, "stdout", &fail); if (fail.code != NE_NOERROR) { printf("Error from nag_opt_read (e04xyc).\n%s\n", fail.message); exit_status = 1; goto END; } /* Solve the problem from a cold start. * The Hessian is defined implicitly by function qphess1. */ /* nag_opt_qp (e04nfc), see above. */ nag_opt_qp(n, nclin, a, tda, bl, bu, cvec, (double *) 0, tdh, qphess1, x, &objf, &options, &comm, &fail); if (fail.code != NE_NOERROR) { printf("Error from nag_opt_qp (e04nfc).\n%s\n", fail.message); exit_status = 1; goto END; } /* The following is for illustrative purposes only. We do a warm * start with the final working set of the previous run. * This time we store the Hessian explicitly in h[][], and use * the corresponding function qphess2(). * Only the final solution from the results is printed. */ printf("\nA run of the same example with a warm start:\n"); fflush(stdout); options.start = Nag_Warm; options.print_level = Nag_Soln; for (i = 0; i < n; ++i) { for (j = 0; j < n; ++j) H(i, j) = 0.0; if (i <= 4) H(i, i) = 2.0; else H(i, i) = -2.0; } H(2, 3) = 2.0; H(3, 2) = 2.0; H(5, 6) = -2.0; H(6, 5) = -2.0; /* Solve the problem again. */ /* nag_opt_qp (e04nfc), see above. */ nag_opt_qp(n, nclin, a, tda, bl, bu, cvec, h, tdh, qphess2, x, &objf, &options, &comm, &fail); if (fail.code != NE_NOERROR) { printf("Error from nag_opt_qp (e04nfc).\n%s\n", fail.message); exit_status = 1; } /* Free memory allocated by nag_opt_qp (e04nfc) to pointers in options */ /* nag_opt_free (e04xzc). * Memory freeing function for use with option setting */ nag_opt_free(&options, "all", &fail); if (fail.code != NE_NOERROR) { printf("Error from nag_opt_free (e04xzc).\n%s\n", fail.message); exit_status = 1; goto END; } END: nAG_FREE(x); nAG_FREE(cvec); nAG_FREE(a); nAG_FREE(h); nAG_FREE(bl); nAG_FREE(bu); return exit_status; } static void nAG_CALL qphess1(Integer n, Integer jthcol, const double h[], Integer tdh, const double x[], double hx[], Nag_Comm *comm) { /* In this version of qphess the Hessian matrix is implicit. * The array h[] is not accessed. There is no special coding * for the case jthcol > 0. */ if (comm->user[0] == -1.0) { printf("(User-supplied callback qphess1, first invocation.)\n"); fflush(stdout); comm->user[0] = 0.0; } hx[0] = 2.0 * x[0]; hx[1] = 2.0 * x[1]; hx[2] = 2.0 * (x[2] + x[3]); hx[3] = hx[2]; hx[4] = 2.0 * x[4]; hx[5] = -2.0 * (x[5] + x[6]); hx[6] = hx[5]; } /* qphess1 */ #undef H static void nAG_CALL qphess2(Integer n, Integer jthcol, const double h[], Integer tdh, const double x[], double hx[], Nag_Comm *comm) { /* In this version of qphess, the matrix H is stored in h[] * as a full two-dimensional array. */ #define H(I, J) h[(I) *tdh + (J)] Integer i, j; if (comm->user[1] == -1.0) { printf("(User-supplied callback qphess2, first invocation.)\n"); fflush(stdout); comm->user[1] = 0.0; } if (jthcol != 0) { /* Special case -- extract one column of H. */ j = jthcol - 1; for (i = 0; i < n; ++i) hx[i] = H(i, j); } else { /* Normal Case. */ for (i = 0; i < n; ++i) hx[i] = 0.0; for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) hx[i] += H(i, j) * x[j]; } } /* qphess2 */