7.84 좌표 하강법과 직접 탐색법

1. 도함수 불요 최적화의 동기

그래디언트 기반 최적화 방법은 목적 함수의 도함수 정보를 요구한다. 그러나 로봇 공학의 일부 문제에서는 도함수를 해석적으로 구할 수 없거나, 목적 함수가 시뮬레이션이나 실험에 의해서만 평가되어 미분 불가능한 경우가 있다. 좌표 하강법과 직접 탐색법은 도함수 없이 함수값만을 이용하여 최적화를 수행하는 방법이다.

2. 좌표 하강법

2.1 기본 원리

좌표 하강법(coordinate descent)은 $n$ 차원 최적화 문제를 $n$ 개의 1차원 최적화 하위 문제로 분해하는 방법이다. 각 반복에서 하나의 좌표 방향을 선택하고, 나머지 변수를 고정한 채 해당 변수에 대해서만 목적 함수를 최소화한다.

알고리즘: $\mathbf{e}_i$ 를 $i$ 번째 표준 단위 벡터라 하자.

초기점 $\mathbf{x}_0$ 를 설정한다.
$k = 0, 1, 2, \ldots$ 에 대해:
$\quad$ $i = 1, 2, \ldots, n$ 에 대해 순환적으로:
$\quad\quad$ $\alpha_i^* = \arg\min_{\alpha} f(\mathbf{x} + \alpha \mathbf{e}_i)$
$\quad\quad$ $x_i \leftarrow x_i + \alpha_i^*$
$\quad$ 수렴 판정

각 좌표 방향에서의 1차원 최소화는 직선 탐색이나 분석적 해법으로 수행된다.

2.2 수렴 성질

목적 함수 $f$ 가 연속 미분 가능하고 각 좌표 방향에서의 최소화가 유일하면, 좌표 하강법의 반복열의 모든 극한점은 정류점이다. 그러나 일반적인 매끄러운 함수에서 좌표 하강법의 수렴은 보장되지 않을 수 있다. 반례로, 로젠브록(Rosenbrock) 함수와 같이 좁은 곡선 형태의 골(valley)을 갖는 함수에서는 좌표 축이 골의 방향과 정렬되지 않아 극도로 느린 수렴을 보인다.

볼록 함수에서의 수렴: $f$ 가 볼록이고 미분 가능하면, 좌표 하강법은 전역 최적해로 수렴한다. 특히 $f$ 가 강볼록(strongly convex)이면 선형 수렴이 보장된다.

분리 가능 구조의 활용: $f(\mathbf{x}) = \sum_{i=1}^{n} f_i(x_i) + g(\mathbf{x})$ 와 같이 분리 가능한 항이 존재하면, 좌표 하강법이 특히 효율적이다. LASSO 회귀의 $\ell_1$ 정규화 항이 대표적인 예이다.

2.3 블록 좌표 하강법

결정 변수를 개별 좌표가 아닌 블록(block)으로 분할하여, 각 블록을 교대로 최적화하는 변형이다.

$\mathbf{x} = [\mathbf{x}_1^T, \mathbf{x}_2^T, \ldots, \mathbf{x}_B^T]^T$

$k$ 번째 반복에서 블록 $b$ 를 제외한 나머지 블록을 고정하고, 다음을 풀어 $\mathbf{x}_b$ 를 갱신한다.

$\mathbf{x}_b^{(k+1)} = \arg\min_{\mathbf{x}_b} f(\mathbf{x}_1^{(k+1)}, \ldots, \mathbf{x}_{b-1}^{(k+1)}, \mathbf{x}_b, \mathbf{x}_{b+1}^{(k)}, \ldots, \mathbf{x}_B^{(k)})$

블록 분할은 문제의 구조를 활용하여 각 하위 문제를 효��적으로 풀 수 있게 한다.

3. 직접 탐색법의 개요

직접 탐색법(direct search method)은 도함수를 사용하지 않고, 목적 함수의 값만을 비교하여 최적점을 탐색하는 방법의 총칭이다. 도함수 불요(derivative-free) 최적화라고도 한다.

4. 넬더-미드 방법

4.1 알고리즘 구조

넬더-미드(Nelder-Mead) 방법은 단체법(simplex method)이라고도 불리며(선형 계획법의 단체법과는 다름), $n$ 차원 공간에서 $n+1$ 개의 꼭짓점으로 구성된 단체(simplex)를 반복적으로 변형하여 최적점을 탐색한다.

$n+1$ 개의 꼭짓점 $\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_{n+1}$ 을 목적 함수값에 따라 정렬한다.

$f(\mathbf{x}_1) \leq f(\mathbf{x}_2) \leq \cdots \leq f(\mathbf{x}_{n+1})$

$\mathbf{x}_1$ 이 최선(best), $\mathbf{x}_{n+1}$ 이 최악(worst)의 꼭짓점이다. 최악의 꼭짓점을 제외한 나머지 꼭짓점들의 중심(centroid)을 $\bar{\mathbf{x}} = \frac{1}{n}\sum_{i=1}^{n}\mathbf{x}_i$ 로 계산한다.

4.2 기본 연산

넬더-미드 방법은 네 가지 기본 연산을 통해 단체를 변형한다.

반사(reflection): 최악의 꼭짓점을 중심에 대해 반사한다.

$\mathbf{x}_r = \bar{\mathbf{x}} + \alpha_r(\bar{\mathbf{x}} - \mathbf{x}_{n+1}), \quad \alpha_r > 0$

팽창(expansion): 반사점이 최선보다 좋으면 더 멀리 확장한다.

$\mathbf{x}_e = \bar{\mathbf{x}} + \alpha_e(\mathbf{x}_r - \bar{\mathbf{x}}), \quad \alpha_e > 1$

수축(contraction): 반사점이 개선을 가져오지 못하면 중심 쪽으로 수축한다.

$\mathbf{x}_c = \bar{\mathbf{x}} + \alpha_c(\mathbf{x}_{n+1} - \bar{\mathbf{x}}), \quad 0 < \alpha_c < 1$

축소(shrink): 모든 연산이 실패하면 최선의 꼭짓점을 향해 전체 단체를 축소한다.

$\mathbf{x}_i \leftarrow \mathbf{x}_1 + \sigma(\mathbf{x}_i - \mathbf{x}_1), \quad 0 < \sigma < 1, \quad i = 2, \ldots, n+1$

표준 매개변수는 $\alpha_r = 1$ , $\alpha_e = 2$ , $\alpha_c = 1/2$ , $\sigma = 1/2$ 이다.

4.3 수렴 특성

넬더-미드 방법은 실용적으로 매우 효과적이지만, 이론적 수렴 보장이 제한적이다. $n \geq 2$ 인 일반적인 경우에 정류점으로의 수렴이 보장되지 않으며, 반복열이 비최적점에 정체되는 반례가 알려져 있다. 그럼에도 불구하고 저차원( $n \leq 10$ ) 문제에서 실용적 성능이 우수하여 널리 사용된다.

5. 패턴 탐색법

5.1 후크-지브스 방법(Hooke-Jeeves Method)

탐색과 이동의 두 단계를 교대하는 방법이다.

탐색 단계(exploratory move): 현재 기저점에서 각 좌표 방향으로 $\pm \delta$ 만큼 이동하여 목적 함수를 개선하는 방향을 식별한다.

패턴 이동(pattern move): 탐색 단계에서 결정된 성공 방향을 따라 더 큰 폭으로 이동한다.

$\mathbf{x}_{k+1}^{base} = \mathbf{x}_k^{base} + (\mathbf{x}_k^{explore} - \mathbf{x}_{k-1}^{base})$

탐색이 실패하면 스텝 크기 $\delta$ 를 축소한다. 이 방법은 좌표 하강법의 단순한 확장으로, 패턴 이동을 통해 좌표 축에 정렬되지 않은 방향으로도 진행할 수 있다.

5.2 일반화 패턴 탐색(Generalized Pattern Search, GPS)

GPS는 패턴 탐색의 이론적 기반을 강화한 방법으로, 탐색 방향의 집합 $\mathcal{D}$ 가 양의 생성 집합(positive spanning set)을 형성해야 한다. 양의 생성 집합이란, 임의의 벡터 $\mathbf{v} \in \mathbb{R}^n$ 을 $\mathcal{D}$ 의 원소들의 비음 선형 결합으로 표현할 수 있는 집합이다. 최소한 $n+1$ 개의 방향이 필요하며, 표준 좌표 방향과 그 음의 방향 $\{\pm \mathbf{e}_1, \ldots, \pm \mathbf{e}_n\}$ 은 $2n$ 개의 원소를 갖는 양의 생성 집합이다.

GPS가 $f$ 에 대해 양의 생성 집합 $\mathcal{D}$ 와 충분 감소 조건을 만족하면, 모든 극한점은 $\mathcal{D}$ 방향에서의 정류점임이 보장된다. $f$ 가 연속 미분 가능하면 이는 $\nabla f = \mathbf{0}$ 을 함의한다.

6. 메시 적응적 직접 탐색(MADS)

메시 적응적 직접 탐색(Mesh Adaptive Direct Search, MADS)은 GPS의 확장으로, 탐색 방향이 반복에 따라 점차 조밀해지도록 허용한다. GPS에서는 탐색 방향이 고정된 유한 집합이지만, MADS에서는 메시의 정밀화에 따라 탐색 방향의 다양성이 증가한다. 이를 통해 GPS보다 강한 수렴 결과를 얻을 수 있으며, 비매끄러운 함수에 대해서도 클라크(Clarke) 정류점으로의 수렴이 보장된다.

7. 로봇 공학에서의 응용

7.1 시뮬레이션 기반 최적화

로봇 시스템의 성능이 물리 시뮬레이터를 통해서만 평가되고 해석적 그래디언트를 사용할 수 없는 경우, 직접 탐색법이 자연스러운 선택이다. 보행 로봇의 보행 매개변수 튜닝, 그리퍼 설계 변수의 최적화 등에서 넬더-미드 방법이나 패턴 탐색법이 적용된다.

7.2 실험 기반 최적화

실물 로봇 실험에서 목적 함수(예: 작업 성공률, 이동 속도)가 실험을 통해서만 측정 가능한 경우, 직접 탐색법이 유용하다. 함수 평가에 상당한 시간과 비용이 소요되므로, 평가 횟수를 최소화하는 것이 핵심이다.

7.3 좌표 하강법의 교대 최적화 응용

로봇 캘리브레이션에서 외부 파라미터(외인성 매개변수)와 내부 파라미터(고유 매개변수)를 교대로 최적화하는 블록 좌표 하강 방식이 사용된다. 각 블록의 최적화가 폐쇄형 해(closed-form solution)를 갖거나 효율적으로 풀 수 있는 경우, 전체 문제를 동시에 푸는 것보다 효율적일 수 있다.

8. 직접 탐색법의 한계

직접 탐색법은 도함수를 요구하지 않는 유연성을 갖지만, 다음의 한계를 인식해야 한다.

수렴 속도: 일반적으로 그래디언트 기반 방법보다 수렴이 현저히 느리다. 차원이 증가함에 따라 이 격차는 더 벌어진다.
확장성: 결정 변수의 수가 수십을 넘으면 실용적 수렴을 기대하기 어렵다. 대규모 문제에는 적합하지 않다.
수렴 보장의 약화: 넬더-미드 방법과 같이 이론적 수렴이 보장되지 않는 방법도 존재한다.

따라서 도함수를 계산할 수 있는 경우에는 자동 미분(automatic differentiation) 등을 활용하여 그래디언트 기반 방법을 적용하는 것이 일반적으로 권장된다.

9. 참고 문헌

Nelder, J. A., & Mead, R. (1965). “A Simplex Method for Function Minimization.” The Computer Journal, 7(4), 308–313.
Hooke, R., & Jeeves, T. A. (1961). “‘Direct Search’ Solution of Numerical and Statistical Problems.” Journal of the ACM, 8(2), 212–229.
Torczon, V. (1997). “On the Convergence of Pattern Search Algorithms.” SIAM Journal on Optimization, 7(1), 1–25.
Audet, C., & Dennis, J. E. (2006). “Mesh Adaptive Direct Search Algorithms for Constrained Optimization.” SIAM Journal on Optimization, 17(1), 188–217.
Wright, S. J. (2015). “Coordinate Descent Algorithms.” Mathematical Programming, 151(1), 3–34.
Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.

version: 1.0