【C言語】数値的最適化の実装
目次
数値的最適化とは
数値的最適化とは、関数の最小値や最大値を求めるアルゴリズムのことを指します。 解析的に解くことが難しい問題に対して、数値的な手法を用いて最適解を近似的に求めます。 最適化手法は、大きく「導関数を用いる方法」と「導関数を用いない方法」に分類されます。 本記事では、C言語を用いて代表的な最適化手法を実装する方法を解説します。
勾配降下法
勾配降下法は、最適化問題において最も基本的な手法の一つです。 目的関数 \( f(x) \) の勾配（微分）を利用し、少しずつ最小値へと近づいていきます。 一般的な更新式は次のように表されます：
\[ x_{k+1} = x_k – \alpha \nabla f(x_k) \]
ここで、\(\alpha\) は学習率（ステップサイズ）です。
実装例
#include <stdio.h>
#include <math.h>
double f(double x) {
return x * x - 4 * x + 4; // (x-2)^2 の最小値は x=2
}
double df(double x) {
return 2 * x - 4; // f(x) の導関数
}
void gradient_descent(double x0, double alpha, int iterations) {
double x = x0;
for (int i = 0; i < iterations; i++) {
x = x - alpha * df(x);
printf("Iteration %d: x = %f, f(x) = %f\n", i, x, f(x));
}
}
int main() {
gradient_descent(0.0, 0.1, 10);
return 0;
}ニュートン法
ニュートン法は、関数の2階微分（ヘッセ行列）を利用して収束を早める手法です。 更新式は次のようになります：
\[ x_{k+1} = x_k - \frac{\nabla f(x_k)}{\nabla^2 f(x_k)} \]
実装例
#include <stdio.h>
#include <math.h>
double f(double x) {
return x * x - 4 * x + 4;
}
double df(double x) {
return 2 * x - 4;
}
double ddf(double x) {
return 2;
}
void newton_method(double x0, int iterations) {
double x = x0;
for (int i = 0; i < iterations; i++) {
x = x - df(x) / ddf(x);
printf("Iteration %d: x = %f, f(x) = %f\n", i, x, f(x));
}
}
int main() {
newton_method(0.0, 5);
return 0;
}準ニュートン法
準ニュートン法は、ニュートン法のヘッセ行列を直接求めずに近似する手法です。 代表的なものに BFGS 法があります。
BFGS 法の概要
BFGS 法では、逆ヘッセ行列 \( H_k \) を更新していきます：
\[ H_{k+1} = H_k + \frac{y_k y_k^T}{y_k^T s_k} - \frac{H_k s_k s_k^T H_k}{s_k^T H_k s_k} \]
制約付き最適化
制約付き最適化では、制約条件を満たしながら最適解を求める必要があります。 代表的な手法として「ラグランジュ乗数法」「投影勾配法」「内点法」などがあります。
投影勾配法の実装
#include <stdio.h>
#include <math.h>
double f(double x) {
return x * x;
}
double df(double x) {
return 2 * x;
}
double project(double x, double lower, double upper) {
if (x < lower) return lower;
if (x > upper) return upper;
return x;
}
void projected_gradient_descent(double x0, double alpha, int iterations, double lower, double upper) {
double x = x0;
for (int i = 0; i < iterations; i++) {
x = project(x - alpha * df(x), lower, upper);
printf("Iteration %d: x = %f, f(x) = %f\n", i, x, f(x));
}
}
int main() {
projected_gradient_descent(5.0, 0.1, 10, 0.0, 2.0);
return 0;
}まとめ
本記事では、C言語による数値的最適化の基本的な手法を解説しました。 勾配降下法、ニュートン法、準ニュートン法、制約付き最適化の実装を通して、それぞれの特性と適用範囲を理解することが重要です。