Keyword: 非線形計画
概要
本サンプルは非線形計画を行うC言語によるサンプルプログラムです。 本サンプルは以下に示される非線形関数を最小化する解を求めて出力します。
※本サンプルはnAG Cライブラリに含まれる関数 nag_opt_nlp() のExampleコードです。本サンプル及び関数の詳細情報は nag_opt_nlp のマニュアルページをご参照ください。
ご相談やお問い合わせはこちらまで
オプション・パラメータ
（本関数の詳細はnag_opt_nlp のマニュアルページを参照）| このオプション・パラメータをダウンロード |
nag_opt_nlp (e04ucc) Example Program Optional Parameters Begin e04ucc con_deriv = Nag_FALSE obj_deriv = Nag_FALSE End
- １行目はタイトル行で読み飛ばされます。
- ３行目にe04uccのパラメータの開始を示しています。
- ４行目にcon_derivの値として"Nag_FALSE"を指定しています。関数confunによって提供される導関数がないか、もしくはわずかである場合にこれを指定します。
- ５行目にobj_derivの値として"Nag_FALSE"を指定しています。関数objfunによって提供される導関数がないか、もしくはわずかである場合にこれを指定します。
- ６行目にパラメータの終わりを示しています。
入力データ
（本関数の詳細はnag_opt_nlp のマニュアルページを参照）| このデータをダウンロード |
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
- １行目はタイトル行で読み飛ばされます。
- ２行目に変数の数(n)、線形制約の数(nclin)と非線形制約の数(ncnln)を指定しています。
- ３行目に行列Aの要素を指定しています。
- ４行目に変数の下限と制約の下限(bl)を指定しています。
- ５行目に変数の上限と制約の上限(bu)を指定しています。
- ６行目にxの初期値を指定しています。
出力結果
（本関数の詳細はnag_opt_nlp のマニュアルページを参照）| この出力例をダウンロード |
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
- ６行目にオプション・パラメータ用のファイルe04ucce.optが読み込まれていることが示されています。
- ８行目にcon_derivに"Nag_FALSE"が設定されていることが示されています。
- ９行目にobj_derivに"Nag_FALSE"が設定されていることが示されています。
- １４行目に変数の数が出力されています。
- １６行目に線形制約の数と非線形制約の数が出力されています。
- １７〜２９行目に以下に示すプログラムのオプション引数が出力されています。
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 結果が出力されるファイル名。 - ３２〜３６行目には目的関数の勾配の検証結果が出力されています。
- ３９〜４３行目には制約の勾配の検証結果が出力されています。
- ４７行目には制約のヤコビ行列に問題ないことが出力されています。
- ４９行目には最大の相対誤差が出力されています。
- ５４〜５８行目には以下が出力されています。
j 反復のカウント x[j] xの要素 Forward dx[j] 前進差分 Central dx[j] 中心差分 Error Est. 誤差推定 - ６０〜６７行目には以下が出力されています。
６６行目には、QP子問題 （subproblem）が中心差分勾配とヤコビ行列を用いて再度解かれていることが示されており、６７行目の右端の"C"は、不特定の目的関数と制約の勾配を計算するのに中心差分が使用されたことを示しています。Maj 大きな反復の回数 Mnr 実行可能解生成フェーズや最適化フェーズで必要とされる小さな反復の回数 Step 探索方向に進んだステップ幅 Merit Function ラグランジュメリット関数の値 Violtn 違反した制約の残差のユークリッド・ノルム Norm Gz 予測される勾配のユークリッド・ノルム Cond Hz 予測されるヘッセ近似行列の条件数の下限 - ６８行目にはNP問題を解くのに５回の大きな反復と１１回の小さな反復が行われたことが示されています。
- ７１〜７５行目には以下が出力されています。
Varbl 変数を示す"V"、インデックス State 変数の状態（LLは下限であることを意味し、FRは下限も上限もワーキングセットにはないことを意味します） Value 最後の反復の変数の値 Lower Bound 下限 Upper Bound 上限 Lagr Mult 関連する境界制約のラグランジュ乗数 Residual 残差（変数の値と上限／下限の近いほうとの差） - ７８から７９行目には以下が出力されています。
L Con 線形制約を示す"L"、インデックス State 線形制約の状態（FRは下限も上限もワーキングセットにはないことを意味します） Value 最後の反復の制約の値 Lower Bound 下限 Upper Bound 上限 Lagr Mult 関連する境界制約のラグランジュ乗数 Residual 残差（制約の値と上限／下限の近いほうとの差） - ８２〜８４行目には以下が出力されています。
N Con 非線形制約を示す"N"、インデックス State 非線形制約の状態（ULは上限であることを意味し、LLは下限であることを意味します） Value 最後の反復の制約の値 Lower Bound 下限 Upper Bound 上限 Lagr Mult 関連する境界制約のラグランジュ乗数 Residual 残差（制約の値と上限／下限の近いほうとの差） - ８６行目にNPの最適解が見つかったことが示されています。
- ８８行目にNPの最終的な目的関数値が出力されています。
ソースコード
（本関数の詳細はnag_opt_nlp のマニュアルページを参照）
※本サンプルソースコードはnAG数値計算ライブラリ（Windows, Linux, MAC等に対応）の関数を呼び出します。
サンプルのコンパイル及び実行方法
| このソースコードをダウンロード |
/* 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;
}