공암경사하법(Conjugate Gradient Method)은 대규모 선형 시스템과 비선형 최적화 문제를 해결하는 데 효과적인 반복법입니다. 특히 2차 형식의 함수에서 n번의 반복으로 최적해를 찾을 수 있다는 장점이 있습니다.
다음은 공암경사하법의 기본 절차입니다:
- 초기 추정값 x0를 설정하고 초기 방향 벡터 p0를 -g0(그래디언트)로 설정합니다.
- 각 반복에서 현재 위치 xi에서 pi 방향으로 1차원 최적화를 수행하여 해당 방향의 최소점 x_를 찾습니다.
- 새로운 위치 x_{i+1}에서 그래디언트 g_{i+1}를 계산하고 alpha = N[g_{i+1}] / N[g_i]를 구합니다.
- 새로운 방향 벡터 p_{i+1} = alpha * p_i - g_i를 계산합니다.
- 그래디언트의 노름이 특정 임계값보다 작아지면 반복을 종료합니다.
다음은 공암경사하법을 구현한 C++ 코드 예제입니다:
#include <iostream>
#include <cmath>
#include <vector>
#define MAX_ITERATIONS 100
#define TOLERANCE 1e-8
// 목적 함수 정의
double objectiveFunction(int dimensions, const std::vector<double>& variables) {
// 10*(x-1)^2 + 20*(y-2)^2 + 30 형식의 2차 함수
return 10.0 * (variables[0]-1) * (variables[0]-1) +
20.0 * (variables[1]-2) * (variables[1]-2) + 30;
}
// 그래디언트 계산 함수
void calculateGradient(int dimensions, const std::vector<double>& variables, std::vector<double>& gradient) {
gradient[0] = 20.0 * (variables[0]-1);
gradient[1] = 40.0 * (variables[1]-2);
}
// 벡터 출력 함수
void printVector(const std::string& name, const std::vector<double>& vec) {
std::cout << name << " = [ ";
for(size_t i = 0; i < vec.size(); i++) {
std::cout << vec[i] << " ";
}
std::cout << "]" << std::endl;
}
// 벡터 내적 계산
double dotProduct(const std::vector<double>& a, const std::vector<double>& b) {
double result = 0.0;
for(size_t i = 0; i < a.size(); i++) {
result += a[i] * b[i];
}
return result;
}
// 벡터 노름 계산
double vectorNorm(const std::vector<double>& vec) {
return sqrt(dotProduct(vec, vec));
}
// 1차원 최적화 함수 (황금 분할법 사용)
double oneDimensionalOptimization(
double (*func)(int, const std::vector<double>&),
int dimensions,
std::vector<double>& currentPoint,
const std::vector<double>& direction,
double initialStep,
double precision
) {
std::vector<double> a = currentPoint;
double fa = func(dimensions, a);
std::vector<double> b = a;
for(int i = 0; i < dimensions; i++) {
b[i] += initialStep * direction[i] / vectorNorm(direction);
}
double fb = func(dimensions, b);
// 초기 단계 조정
for(int i = 0; i < 10; i++) {
if(fb > fa) {
initialStep /= 10;
for(int j = 0; j < dimensions; j++) {
b[j] = a[j] + initialStep * direction[j] / vectorNorm(direction);
}
fb = func(dimensions, b);
} else {
break;
}
}
if(fb > fa) {
std::cout << "1차원 최적화: 이미 극소점에 가까운 상태입니다." << std::endl;
return fa;
}
// 의심 구간 찾기
std::vector<double> c(dimensions);
double fc;
int iterations = 0;
do {
for(int i = 0; i < dimensions; i++) {
c[i] = b[i] + 1.618 * (b[i] - a[i]);
}
fc = func(dimensions, c);
iterations++;
if(fc > fb) break;
for(int i = 0; i < dimensions; i++) {
a[i] = b[i];
b[i] = c[i];
}
fa = fb;
fb = fc;
} while(iterations < MAX_ITERATIONS);
if(iterations == MAX_ITERATIONS) {
std::cout << "1차원 최적화: 의심 구간을 찾지 못했습니다." << std::endl;
return fa;
}
std::cout << iterations << "번 반복 후 의심 구간 발견:" << std::endl;
printVector("a", a);
printVector("b", b);
printVector("c", c);
// 의심 구간 좁히기
std::vector<double> d(dimensions);
double fd;
iterations = 0;
do {
for(int i = 0; i < dimensions; i++) {
d[i] = a[i] + 0.618 * (c[i] - a[i]);
}
fd = func(dimensions, d);
if(dotProduct(d, a) < dotProduct(d, b)) {
if(fd < fb) {
for(int i = 0; i < dimensions; i++) {
c[i] = b[i];
b[i] = d[i];
}
fc = fb;
fb = fd;
} else {
for(int i = 0; i < dimensions; i++) {
a[i] = d[i];
}
fa = fd;
}
} else {
if(fd < fb) {
for(int i = 0; i < dimensions; i++) {
a[i] = b[i];
b[i] = d[i];
}
fa = fb;
fb = fd;
} else {
for(int i = 0; i < dimensions; i++) {
c[i] = d[i];
}
fc = fd;
}
}
iterations++;
} while(vectorNorm(c) - vectorNorm(a) > precision && iterations < MAX_ITERATIONS);
for(int i = 0; i < dimensions; i++) {
currentPoint[i] = (a[i] + c[i]) / 2;
}
std::cout << iterations << "번 반복 후 1차원 최소점 발견:" << std::endl;
return func(dimensions, currentPoint);
}
// 공암경사하법 메인 함수
void conjugateGradientMethod(
double (*func)(int, const std::vector<double>&),
void (*gradFunc)(int, const std::vector<double>&, std::vector<double>&),
int dimensions,
std::vector<double>& initialPoint,
double initialStep,
double precision,
double gradientTolerance
) {
std::vector<double> gradient(dimensions);
gradFunc(dimensions, initialPoint, gradient);
std::vector<double> direction = gradient;
for(int i = 0; i < dimensions; i++) {
direction[i] = -direction[i];
}
int iterations = 0;
for(iterations = 0; iterations < MAX_ITERATIONS; iterations++) {
double alpha = 1.0 / vectorNorm(gradient);
std::cout << "----------------------------------------" << std::endl;
printVector("하강 방향", direction);
double minValue = oneDimensionalOptimization(func, dimensions, initialPoint, direction, initialStep, precision);
printVector("최소점 위치", initialPoint);
std::cout << "1차원 최소값: " << minValue << std::endl;
std::cout << "----------------------------------------" << std::endl;
gradFunc(dimensions, initialPoint, gradient);
if(vectorNorm(gradient) < gradientTolerance) {
break;
}
alpha *= vectorNorm(gradient);
for(int i = 0; i < dimensions; i++) {
direction[i] = alpha * direction[i] - gradient[i];
}
}
if(iterations == MAX_ITERATIONS) {
std::cout << "공암경사하법: " << MAX_ITERATIONS << "번 반복 후에도 최소점을 찾지 못했습니다." << std::endl;
} else {
std::cout << "공암경사하법: " << iterations+1 << "번의 1차원 최적화로 최소점을 찾았습니다." << std::endl;
std::cout << "\t최소값: " << func(dimensions, initialPoint) << ", 위치: ";
printVector("", initialPoint);
}
}
int main() {
std::vector<double> startPoint = {4.0, 0.0};
conjugateGradientMethod(
objectiveFunction,
calculateGradient,
2,
startPoint,
100.0,
1e-8,
1e-5
);
return 0;
}
실행 결과:
----------------------------------------
하강 방향 = [ -60 80 ]
2번 반복 후 의심 구간 발견:
a = [ 3.4 0.8 ]
b = [ 2.4292 2.0944 ]
c = [ 0.858446 4.18874 ]
3번 반복 후 1차원 최소점 발견:
1차원 최소값: 47.561
최소점 위치 = [ 2.17073 2.43902 ]
----------------------------------------
----------------------------------------
하강 방향 = [ -28.5544 -10.7079 ]
1번 반복 후 의심 구간 발견:
a = [ 2.17073 2.43902 ]
b = [ 1.2344 2.0879 ]
c = [ -0.280578 1.51978 ]
3번 반복 후 1차원 최소점 발견:
1차원 최소값: 30
최소점 위치 = [ 1 2 ]
----------------------------------------
공암경사하법: 2번의 1차원 최적화로 최소점을 찾았습니다.
최소값: 30, 위치 = [ 1 2 ]
결과에서 볼 수 있듯이, 이 2차 함수의 경우 2번의 1차원 최적화로 최소점을 찾았습니다. 이는 이론적으로 예상되는 n차원 2차 함수에 대한 n번의 최적화와 일치합니다.