Keyword: 非線形計画
概要
本サンプルは非線形計画を行うC言語によるサンプルプログラムです。 本サンプルは以下に示される非線形関数を最小化する解を求めて出力します。
※本サンプルはnAG Cライブラリに含まれる関数 nag_opt_nlp() のExampleコードです。本サンプル及び関数の詳細情報は nag_opt_nlp のマニュアルページをご参照ください。
ご相談やお問い合わせはこちらまで
オプション・パラメータ
(本関数の詳細はnag_opt_nlp のマニュアルページを参照)1 2 3 4 5 6
このオプション・パラメータをダウンロード |
nag_opt_nlp (e04ucc) Example Program Optional Parameters Begin e04ucc con_deriv = Nag_FALSE obj_deriv = Nag_FALSE End
- 1行目はタイトル行で読み飛ばされます。
- 3行目にe04uccのパラメータの開始を示しています。
- 4行目にcon_derivの値として"Nag_FALSE"を指定しています。関数confunによって提供される導関数がないか、もしくはわずかである場合にこれを指定します。
- 5行目にobj_derivの値として"Nag_FALSE"を指定しています。関数objfunによって提供される導関数がないか、もしくはわずかである場合にこれを指定します。
- 6行目にパラメータの終わりを示しています。
入力データ
(本関数の詳細はnag_opt_nlp のマニュアルページを参照)1 2 3 4 5 6
このデータをダウンロード |
nag_opt_nlp (e04ucc) Example Program Data 4 1 2 :Values of n, nclin and ncnlin 1.0 1.0 1.0 1.0 :End of matrix A 1.0 1.0 1.0 1.0 -1.0E+25 -1.0E+25 25.0 :End of bl 5.0 5.0 5.0 5.0 20.0 40.0 1.0E+25 :End of bu 1.0 5.0 5.0 1.0 :End of x
- 1行目はタイトル行で読み飛ばされます。
- 2行目に変数の数(n)、線形制約の数(nclin)と非線形制約の数(ncnln)を指定しています。
- 3行目に行列Aの要素を指定しています。
- 4行目に変数の下限と制約の下限(bl)を指定しています。
- 5行目に変数の上限と制約の上限(bu)を指定しています。
- 6行目にxの初期値を指定しています。
出力結果
(本関数の詳細はnag_opt_nlp のマニュアルページを参照)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
この出力例をダウンロード |
nag_opt_nlp (e04ucc) Example Program Results Optional parameter setting for e04ucc. -------------------------------------- Option file: e04ucce.opt con_deriv set to Nag_FALSE obj_deriv set to Nag_FALSE Parameters to e04ucc -------------------- Number of variables........... 4 Linear constraints............ 1 Nonlinear constraints......... 2 start................... Nag_Cold step_limit.............. 2.00e+00 machine precision....... 1.11e-16 lin_feas_tol............ 1.05e-08 nonlin_feas_tol......... 1.05e-08 optim_tol............... 3.26e-12 linesearch_tol.......... 9.00e-01 crash_tol............... 1.00e-02 f_prec.................. 4.37e-15 inf_bound............... 1.00e+20 inf_step................ 1.00e+20 max_iter................ 50 minor_max_iter.......... 50 hessian................. Nag_FALSE f_diff_int.............. Automatic c_diff_int.............. Automatic obj_deriv............... Nag_FALSE con_deriv............... Nag_FALSE verify_grad....... Nag_SimpleCheck print_deriv............ Nag_D_Full print_level......... Nag_Soln_Iter minor_print_level..... Nag_NoPrint outfile................. stdout Verification of the objective gradients. ---------------------------------------- The user sets 0 out of 4 objective gradient elements. Each iteration 4 gradient elements will be estimated numerically. Verification of the constraint gradients. ----------------------------------------- The user sets 3 out of 8 constraint gradient elements. Each iteration, 5 gradient elements will be estimated numerically. Simple Check: The Jacobian seems to be ok. The largest relative error was 5.22e-09 in constraint 1 Finite difference intervals. ---------------------------- j x[j] Forward dx[j] Central dx[j] Error Est. 1 1.00e+00 6.479651e-07 2.645420e-06 2.592083e-06 2 5.00e+00 7.825142e-07 7.936259e-06 1.565074e-06 3 5.00e+00 7.936259e-06 7.936259e-05 1.873839e-08 4 1.00e+00 9.163610e-07 2.645420e-06 1.832879e-06 Maj Mnr Step Merit function Violtn Norm Gz Cond Hz 0 5 0.0e+00 1.738281e+01 1.2e+01 7.1e-01 1.0e+00 1 1 1.0e+00 1.703169e+01 1.9e+00 4.6e-02 1.0e+00 2 1 1.0e+00 1.701442e+01 8.8e-02 2.1e-02 1.0e+00 3 1 1.0e+00 1.701402e+01 5.4e-04 3.1e-04 1.0e+00 4 1 1.0e+00 1.701402e+01 9.9e-08 7.0e-06 1.0e+00 Minor itn 1 -- Re-solve QP subproblem. 5 2 1.0e+00 1.701402e+01 4.7e-11 6.4e-08 1.0e+00 C Exit from NP problem after 5 major iterations, 11 minor iterations. Varbl State Value Lower Bound Upper Bound Lagr Mult Residual V 1 LL 1.00000e+00 1.00000e+00 5.00000e+00 1.0879e+00 0.0000e+00 V 2 FR 4.74300e+00 1.00000e+00 5.00000e+00 0.0000e+00 2.5700e-01 V 3 FR 3.82115e+00 1.00000e+00 5.00000e+00 0.0000e+00 1.1789e+00 V 4 FR 1.37941e+00 1.00000e+00 5.00000e+00 0.0000e+00 3.7941e-01 L Con State Value Lower Bound Upper Bound Lagr Mult Residual L 1 FR 1.09436e+01 None 2.00000e+01 0.0000e+00 9.0564e+00 N Con State Value Lower Bound Upper Bound Lagr Mult Residual N 1 UL 4.00000e+01 None 4.00000e+01 -1.6147e-01 -3.7218e-11 N 2 LL 2.50000e+01 2.50000e+01 None 5.5229e-01 -2.8766e-11 Optimal solution found. Final objective value = 1.7014017e+01
- 6行目にオプション・パラメータ用のファイルe04ucce.optが読み込まれていることが示されています。
- 8行目にcon_derivに"Nag_FALSE"が設定されていることが示されています。
- 9行目にobj_derivに"Nag_FALSE"が設定されていることが示されています。
- 14行目に変数の数が出力されています。
- 16行目に線形制約の数と非線形制約の数が出力されています。
- 17~29行目に以下に示すプログラムのオプション引数が出力されています。
start 初期のワーキングセットがどのように選ばれるかを示しています。"Nag_Cold"は変数や制約の値に基づいて初期のワーキングセットが選ばれていることを意味します。 step_limit 行探索の最初のステップでの変数の変化の最大値。 machine precision マシンの精度。 lin_feas_tol 実行可能解での許容可能な最大の線形制約違反。 nonlin_feas_tol 実行可能解での許容可能な最大の非線形制約違反。 optim_tol 最後の反復で解を近似する際の正確さ。 linesearch_tol 反復時に探索方向に進むステップがメリット関数の最小値を近似する際の正確さ。 crash_tol 初期のワーキングセットに含まれる不等式制約が境界値のこの範囲内にあることを示しています。 f_prec 問題関数の正確さの度合い。 inf_bound 無限の境界。この値以上の上限は+∞と見なされます。またこの値を負に反転させた値以下の下限は−∞と見なされます。 inf_step 無限解へのステップと見なされる変数の変化の大きさ。 max_iter 大きな反復の最大反復数。 minor_max_iter 最適化フェーズの小さな反復の最大反復数。 hessian プログラムの引数hの内容を制御します。"Nag_FALSE"は引数hが行列HQのコレスキー因子を含むことを意味しています。 f_diff_int 有限差分による導関数の推定に使用される区間。"Automatic"は自動的に計算されることを意味します。 c_diff_int xの各要素に対する差分区間。"Automatic"は自動的に計算されることを意味します。 obj_deriv 目的関数の全ての導関数が関数objfunで定義されているかどうかを示します。"Nag_FALSE" は関数objfunによって提供される導関数がないか、もしくはわずかであることを意味します。 con_deriv 制約のヤコビ行列の全ての導関数が関数confunで定義されているかどうかを示します。 "Nag_FALSE" は関数confunによって提供される導関数がないか、もしくはわずかであることを意味します。 verify_glad 導関数チェックのレベルを示します。"Nag_SimpleCheck"は、目的関数と制約の両方の勾配を簡易チェックすることを意味します。 print_deriv 導関数のチェックの結果を出力するかどうかを制御します。"Nag_D_Full"はチェックの結果の詳細を全て出力することを意味します。 print_level 結果出力のレベル。"Nag_Soln_Iter"は最終解と各反復の結果を出力することを意味します。 minor_print_level 小さな反復によって生成される結果の出力のレベル。"Nag_NoPrint"は何も出力しないことを意味します。 outfile 結果が出力されるファイル名。 - 32~36行目には目的関数の勾配の検証結果が出力されています。
- 39~43行目には制約の勾配の検証結果が出力されています。
- 47行目には制約のヤコビ行列に問題ないことが出力されています。
- 49行目には最大の相対誤差が出力されています。
- 54~58行目には以下が出力されています。
j 反復のカウント x[j] xの要素 Forward dx[j] 前進差分 Central dx[j] 中心差分 Error Est. 誤差推定 - 60~67行目には以下が出力されています。
Maj 大きな反復の回数 Mnr 実行可能解生成フェーズや最適化フェーズで必要とされる小さな反復の回数 Step 探索方向に進んだステップ幅 Merit Function ラグランジュメリット関数の値 Violtn 違反した制約の残差のユークリッド・ノルム Norm Gz 予測される勾配のユークリッド・ノルム Cond Hz 予測されるヘッセ近似行列の条件数の下限 - 68行目にはNP問題を解くのに5回の大きな反復と11回の小さな反復が行われたことが示されています。
- 71~75行目には以下が出力されています。
Varbl 変数を示す"V"、インデックス State 変数の状態(LLは下限であることを意味し、FRは下限も上限もワーキングセットにはないことを意味します) Value 最後の反復の変数の値 Lower Bound 下限 Upper Bound 上限 Lagr Mult 関連する境界制約のラグランジュ乗数 Residual 残差(変数の値と上限/下限の近いほうとの差) - 78から79行目には以下が出力されています。
L Con 線形制約を示す"L"、インデックス State 線形制約の状態(FRは下限も上限もワーキングセットにはないことを意味します) Value 最後の反復の制約の値 Lower Bound 下限 Upper Bound 上限 Lagr Mult 関連する境界制約のラグランジュ乗数 Residual 残差(制約の値と上限/下限の近いほうとの差) - 82~84行目には以下が出力されています。
N Con 非線形制約を示す"N"、インデックス State 非線形制約の状態(ULは上限であることを意味し、LLは下限であることを意味します) Value 最後の反復の制約の値 Lower Bound 下限 Upper Bound 上限 Lagr Mult 関連する境界制約のラグランジュ乗数 Residual 残差(制約の値と上限/下限の近いほうとの差) - 86行目にNPの最適解が見つかったことが示されています。
- 88行目にNPの最終的な目的関数値が出力されています。
ソースコード
(本関数の詳細はnag_opt_nlp のマニュアルページを参照)
※本サンプルソースコードは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
このソースコードをダウンロード |
/* nag_opt_nlp (e04ucc) 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 <nage04.h> #ifdef __cplusplus extern "C" { #endif static void nAG_CALL objfun(Integer n, const double x[], double *objf, double objgrd[], Nag_Comm *comm); static void nAG_CALL confun(Integer n, Integer ncnlin, const Integer needc[], const double x[], double conf[], double conjac[], Nag_Comm *comm); #ifdef __cplusplus } #endif static void nAG_CALL objfun(Integer n, const double x[], double *objf, double objgrd[], Nag_Comm *comm) { /* Routine to evaluate objective function and its 1st derivatives. */ if (comm->flag == 0 || comm->flag == 2) *objf = x[0] * x[3] * (x[0] + x[1] + x[2]) + x[2]; /* Note, elements of the objective gradient have not been specified. */ } /* objfun */ static void nAG_CALL confun(Integer n, Integer ncnlin, const Integer needc[], const double x[], double conf[], double conjac[], Nag_Comm *comm) { #define CONJAC(I, J) conjac[((I) -1)*n + (J) -1] /* Routine to evaluate the nonlinear constraints and * their 1st derivatives. */ /* Function Body */ if (needc[0] > 0) { if (comm->flag == 0 || comm->flag == 2) conf[0] = x[0] * x[0] + x[1] * x[1] + x[2] * x[2] + x[3] * x[3]; if (comm->flag == 2) { CONJAC(1, 3) = x[2] * 2.0; /* Note only one constraint gradient has been specified * in the first row of the constraint Jacobian. */ } } if (needc[1] > 0) { if (comm->flag == 0 || comm->flag == 2) conf[1] = x[0] * x[1] * x[2] * x[3]; if (comm->flag == 2) { CONJAC(2, 2) = x[0] * x[2] * x[3]; CONJAC(2, 3) = x[0] * x[1] * x[3]; /* Note only two constraint gradients have been specified * in the second row of the constraint Jacobian. */ } } } /* confun */ #define A(I, J) a[(I) *tda + J] int main(void) { const char *optionsfile = "e04ucce.opt"; Integer exit_status = 0, i, j, n, nclin, ncnlin, tda, totalvars; Nag_Comm comm; NagError fail; Nag_E04_Opt options; double *a = 0, *bl = 0, *bu = 0, objf, *objgrd = 0, *x = 0; INIT_FAIL(fail); printf("nag_opt_nlp (e04ucc) Example Program Results\n"); fflush(stdout); scanf(" %*[^\n]"); /* Skip heading in data file */ scanf("%ld%ld%ld%*[^\n]", &n, &nclin, &ncnlin); if (n > 0 && nclin >= 0 && ncnlin >= 0) { totalvars = n + nclin + ncnlin; if (!(x = nAG_ALLOC(n, double)) || !(a = nAG_ALLOC(nclin * n, double)) || !(bl = nAG_ALLOC(totalvars, double)) || !(bu = nAG_ALLOC(totalvars, double)) || !(objgrd = nAG_ALLOC(n, double))) { printf("Allocation failure\n"); exit_status = -1; goto END; } tda = n; } else { printf("Invalid n or nclin or ncnlin.\n"); exit_status = 1; return exit_status; } /* Read a, bl, bu and x from data file */ /* Read the matrix of linear constraint coefficients */ if (nclin > 0) { for (i = 0; i < nclin; ++i) for (j = 0; j < n; ++j) scanf("%lf", &A(i, j)); } scanf("%*[^\n]"); /* Remove remainder of line */ /* Read lower bounds */ for (i = 0; i < n + nclin + ncnlin; ++i) scanf("%lf", &bl[i]); scanf("%*[^\n]"); /* Read upper bounds */ for (i = 0; i < n + nclin + ncnlin; ++i) scanf("%lf", &bu[i]); scanf("%*[^\n]"); /* Read the initial point x */ for (i = 0; i < n; ++i) scanf("%lf", &x[i]); scanf("%*[^\n]"); /* nag_opt_init (e04xxc). * Initialization function for option setting */ nag_opt_init(&options); /* nag_opt_read (e04xyc). * Read options from a text file */ nag_opt_read("e04ucc", optionsfile, &options, (Nag_Boolean) Nag_TRUE, "stdout", &fail); if (fail.code != NE_NOERROR) { printf("Error from nag_opt_read (e04xyc).\n%s\n", fail.message); exit_status = 1; goto END; } /* nag_opt_nlp (e04ucc), see above. */ nag_opt_nlp(n, nclin, ncnlin, a, tda, bl, bu, objfun, confun, x, &objf, objgrd, &options, &comm, &fail); if (fail.code != NE_NOERROR) { printf("Error from nag_opt_nlp (e04ucc).\n%s\n", fail.message); exit_status = 1; } /* 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(a); nAG_FREE(bl); nAG_FREE(bu); nAG_FREE(objgrd); return exit_status; }