非線形計画

C言語によるサンプルソースコード : 使用関数名:nag_opt_nlp (e04ucc)

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 予測されるヘッセ近似行列の条件数の下限
    66行目には、QP子問題 (subproblem)が中心差分勾配とヤコビ行列を用いて再度解かれていることが示されており、67行目の右端の"C"は、不特定の目的関数と制約の勾配を計算するのに中心差分が使用されたことを示しています。
  • 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;
}


関連情報
© 日本ニューメリカルアルゴリズムズグループ株式会社 2024
Privacy Policy  /  Trademarks