Klein Appendix A.1 — Univariate Methods for Maximization

1 도입 — 단변수 최적화의 위치

Klein 책 본문에서 단변수 최적화가 등장하는 자리:

본문 위치	단변수 모수	비고
Ch.4 — Confidence band 의 critical value	\(c_\alpha\)	분포함수의 분위수 찾기
Ch.7 — Renyi 검정의 sup statistic	\(t^*\)	시간 영역 sup 점
Ch.8 — 단일 공변량 Cox PH	\(\beta\) (\(p = 1\))	단순 사례
Ch.12 — 단일 분포 모수 (Weibull \(\alpha\) 만, \(\lambda\) 알려진 경우)	\(\alpha\)	Example A.1
Ch.13 — Frailty EM 의 \(\theta\) update	\(\theta\)	M-step 내부
Profile likelihood 일반	profile 모수	다른 모수를 max-out

각각의 경우 score 방정식 \(f'(x) = 0\) 의 영점을 찾는 1 차원 문제 로 환원된다. 이는 다변수 최적화 (§ A.2) 의 building block 이기도 하다 — steepest ascent 의 step size 결정, profile likelihood 의 inner loop, line search 모두 1D 영점 찾기를 사용한다.

§ A.1 의 위치

§ A.1 의 세 방법은 단변수 영점 찾기의 표준 도구 이다. 각각의 trade-off:

방법	정보 요구	수렴 차수	견고성	사용 시점
Bisection	\(f'\) 부호 만	1 (선형)	매우 강	안전한 시작, \(f'\) 거칠 때
Secant	\(f'\) 만 (두 점)	\(\phi \approx 1.618\)	중간	\(f''\) 비싼 경우
Newton-Raphson	\(f', f''\)	2 (이차)	약	좋은 시작값 + 빠른 수렴

본 sub-post 는 세 방법의 알고리즘을 의사코드로 정리하고, 수렴 차수의 수학적 유도, 발산 사례, 그리고 Klein 의 Weibull MLE 예제 (Example A.1) 의 step-by-step trace 로 수렴 속도를 비교한다.

2 문제 정의 — Score 영점 찾기

목적 함수 \(f: \mathbb{R} \to \mathbb{R}\) 의 최대값을 찾는다:

\[ \hat{x} = \arg\max_x f(x) . \]

정칙 조건 (\(f\) 가 두 번 미분 가능, 단봉) 하에서 일계 조건:

\[ f'(\hat{x}) = 0 \quad \text{and} \quad f''(\hat{x}) < 0 . \]

따라서 \(f'\) 의 영점 (root) 을 찾는 문제 로 환원. 이를 위해 다음을 알고 있다고 가정한다:

• \(f'(x)\) 의 함수 형태 (수치적 또는 해석적 평가 가능)
• 일부 방법에서는 \(f''(x)\) 도 평가 가능

영점 = 최대값? — 검증 필수

세 방법 모두 \(f'(x) = 0\) 의 해를 찾을 뿐, 그 해가 최대인지 최소인지 변곡점인지 알지 못한다. 우도 함수가 단봉이면 안전하지만, 그렇지 않으면 다음을 점검:

1. \(f''(\hat{x}) < 0\) (음의 정칙) 확인
2. 인접한 두 점의 \(f\) 값 비교
3. 다른 시작값으로 재시도해 같은 해 도달

특히 frailty 모수 \(\theta\) 처럼 모수 공간 경계 (\(\theta \geq 0\)) 에 가까운 경우, score 영점이 경계에 있을 수 있어 일반 정칙 이론이 약하다.

3 § A.1.1 Bisection — 가장 견고한 방법

3.1 알고리즘

\(f'(x)\) 의 영점이 구간 \([x_L, x_U]\) 안에 있다는 정보가 있다고 가정 — 양 끝의 부호가 다름:

\[ f'(x_L) \cdot f'(x_U) < 0 . \]

(중간값 정리에 의해 \(f'\) 가 연속이면 그 사이에 적어도 하나의 영점 존재.)

3.1.1 의사코드

INPUT: f', x_L, x_U (with f'(x_L)·f'(x_U) < 0), tol
WHILE (x_U - x_L) > tol:
    x_N ← (x_L + x_U) / 2
    fp_N ← f'(x_N)
    IF f'(x_L) · fp_N > 0:        # 영점이 [x_N, x_U] 에 있음
        x_L ← x_N
    ELSE:                          # 영점이 [x_L, x_N] 에 있음
        x_U ← x_N
RETURN (x_L + x_U) / 2

직관 — 매 step 절반씩 좁힘

각 step 에서 구간 길이가 정확히 절반으로 줄어든다. \(k\) step 후 길이:

\[ \text{Length}_k = \frac{x_U^{(0)} - x_L^{(0)}}{2^k} . \]

따라서 정확도 \(\epsilon\) 도달까지:

\[ k = \left\lceil \log_2 \frac{x_U^{(0)} - x_L^{(0)}}{\epsilon} \right\rceil . \]

예: 초기 폭 1.0, 정확도 \(10^{-6}\) 원하면 \(k = 20\) step 필요. \(10^{-12}\) 원하면 \(k = 40\) step.

이는 선형 수렴 (linear convergence) — 매 step 정확도가 일정 비율 (1/2) 로 줄어든다.

3.2 수렴 보장과 견고성

Bisection 의 강점 — 수렴 보장

중간값 정리 가 보장: \(f'\) 가 \([x_L, x_U]\) 에서 연속이고 양 끝 부호가 다르면 그 사이에 적어도 한 영점이 존재. Bisection 은 그 영점을 반드시 찾는다.

따라서 함수의 모양과 무관하게 수렴 보장. 다른 방법이 발산하거나 잘못된 방향으로 갈 수 있는 험한 함수 (잡음, 평탄 영역, 다봉) 에서도 안전하게 작동.

비유: 산속에서 길을 잃었을 때 나침반 (bisection) 만으로 천천히 가지만 반드시 도착. 빠른 차 (Newton) 는 길이 좋을 때만 빠르고, 길이 나쁘면 멈추거나 절벽으로 갈 수 있음.

비용: 선형 수렴은 다른 방법 (super-linear, quadratic) 보다 느리다. 그러나 수렴 보장은 매우 큰 가치.

3.3 한계

한계	설명
초기 구간 필요	\(f'(x_L)\) 와 \(f'(x_U)\) 의 부호가 달라야. 우도 함수 score 의 부호를 사전에 알기 어려운 경우 있음
다중 영점	구간 안에 영점이 여러 개면 그중 하나만 찾음 (어느 것일지 예측 불가)
미분 불가 / 불연속	중간값 정리가 깨지면 작동 안 함 — 우도가 PMF 같은 이산 함수면 부적합
선형 수렴	\(2^{-k}\) → 정밀도 \(10^{-12}\) 위해 40+ step. Newton 의 quadratic 보다 훨씬 많음

3.4 사용 시점

• 초기값 정보 부실: Newton-Raphson 의 시작값을 잘 모르는 경우 bisection 으로 거친 영역 좁힘.
• 함수가 거칠다: 우도 함수에 잡음·미분 불가 점이 있을 때.
• 하이브리드 알고리즘의 안전장치: Brent’s method 가 secant + bisection 결합으로 양쪽 장점 취함.

4 § A.1.2 Secant Method — 식 (A.1)

4.1 알고리즘

두 초기값 \(x_0, x_1\) 에서 시작 (영점을 사이에 둘 필요 없음, 자유). 각 step 에서:

\[ x_{i+1} = x_i - f'(x_i) \cdot \frac{x_i - x_{i-1}}{f'(x_i) - f'(x_{i-1})} . \tag{식 A.1} \]

4.1.1 의사코드

INPUT: f', x_0, x_1, tol
fp_0 ← f'(x_0)
fp_1 ← f'(x_1)
WHILE |fp_1| > tol:
    x_new ← x_1 - fp_1 · (x_1 - x_0) / (fp_1 - fp_0)
    x_0 ← x_1
    fp_0 ← fp_1
    x_1 ← x_new
    fp_1 ← f'(x_1)
RETURN x_1

(정지 기준은 \(|f'(x_1)|\) 외에 \(|x_1 - x_0|\) 또는 \(|x_1 - x_0|/|x_0|\) 등 사용 가능.)

직관 — 할선 (Secant) 의 영점

\(f'\) 의 두 점 \((x_{i-1}, f'(x_{i-1}))\), \((x_i, f'(x_i))\) 을 잇는 직선 (할선, secant line) 을 그린다. 이 할선의 방정식:

\[ y - f'(x_i) = \frac{f'(x_i) - f'(x_{i-1})}{x_i - x_{i-1}} (x - x_i) . \]

이 직선의 \(x\)-intercept (\(y = 0\) 점) 가 다음 후보:

\[ x_{i+1} = x_i - f'(x_i) \cdot \frac{x_i - x_{i-1}}{f'(x_i) - f'(x_{i-1})} . \]

이게 식 (A.1).

아이디어: \(f'\) 가 부드러운 곡선이면 두 점 사이에서 거의 직선에 가깝다. 그 직선 근사로 영점을 추정 → 빠르게 수렴.

4.2 수렴 차수 — 황금 비율 \(\phi\) 의 등장

\(\phi \approx 1.618\) 의 유도

오차 \(e_i = x_i - \hat{x}\) 를 정의. Taylor 전개로 (자세한 유도는 Numerical Recipes Ch.9 참조):

\[ e_{i+1} \approx \frac{f''(\hat{x})}{2 f'(\hat{x})} \cdot e_i \cdot e_{i-1} . \]

오차 점화식 \(e_{i+1} = C \cdot e_i \cdot e_{i-1}\) 에서 차수 \(p\) 를 찾는다. 가정 \(e_{i+1} = K \cdot e_i^p\) 면:

\[ K e_i^p = C \cdot e_i \cdot e_{i-1} . \]

\(e_i = K \cdot e_{i-1}^p\) 에서 \(e_{i-1} = (e_i/K)^{1/p}\) 대입:

\[ K e_i^p = C \cdot e_i \cdot (e_i/K)^{1/p} \;\Rightarrow\; K^{1+1/p} e_i^{p - 1 - 1/p} = C . \]

이 식이 \(e_i\) 무관하려면 지수 \(p - 1 - 1/p = 0\), 즉:

\[ p^2 - p - 1 = 0 \;\Rightarrow\; p = \frac{1 + \sqrt{5}}{2} = \phi \approx 1.618 . \]

황금 비율 이 자연스럽게 등장 — 피보나치 점화식 \(F_{i+1} = F_i + F_{i-1}\) 와 같은 구조 (\(e_{i+1}\) 가 직전 두 항의 곱) 에서 \(\phi\) 가 나오는 것은 같은 수학적 원리.

4.3 Secant 의 장단점

측면	Bisection	Secant	Newton-Raphson
수렴 차수	1 (선형)	\(\phi \approx 1.618\)	2 (이차)
정보 요구	\(f'\) 만	\(f'\) 만 (두 점)	\(f', f''\)
초기값	부호 다른 두 점	두 점 (자유)	한 점
견고성	매우 강	중간	약

Secant 의 결정적 장점 — \(f''\) 불필요

Newton-Raphson 보다 약간 느리지만 (\(\phi < 2\)), 2 차 도함수 \(f''\) 계산이 불필요 하다는 점이 결정적 장점이다.

왜 중요한가:

• Cox 부분우도의 \(f''\) 는 위험집합의 가중 공분산 — 큰 데이터에서 매 step \(O(n^2)\) 비용.
• Frailty marginal 우도의 \(f''\) 는 digamma 함수의 도함수 (trigamma) 등 복잡 함수.
• 일반화 감마의 \(f''\) 는 표현식이 매우 복잡.

이런 경우 Newton 의 quadratic 수렴 (2 step) 이 secant 의 super-linear (3-4 step) 보다 느릴 수 있다 — Hessian 한 번 계산 비용이 secant step 두 번보다 큼.

Quasi-Newton 의 다변수 일반화 (BFGS 등) 는 secant 의 다변수 버전 — Hessian 을 score 변화로 근사.

4.4 발산 사례

Secant 가 실패하는 경우

1. \(f'(x_i) \approx f'(x_{i-1})\): 분모 \((f'(x_i) - f'(x_{i-1}))\) 가 0 에 가까워 step 이 폭발. 평탄 영역에서 발생.

2. \(f''\) 부호 변화: 변곡점 부근에서 할선 근사가 부정확 → 잘못된 방향으로 점프.

3. 다중 영점: 두 시작값이 다른 영점 사이에 있으면 어느 영점에 수렴할지 예측 불가.

대처: - 정지 기준에 \(|x_{i+1} - x_i|\) 추가 (모수 변화도 점검). - 분모 절댓값이 임계 이하면 bisection 으로 fallback. - 함수 값 모니터링 — \(f(x_{i+1}) \geq f(x_i)\) 위반 시 반대 방향으로 이동 안 함.

5 § A.1.3 Newton-Raphson — 식 (A.2)

5.1 알고리즘

단일 초기값 \(x_0\) 에서 시작:

\[ x_{i+1} = x_i - \frac{f'(x_i)}{f''(x_i)} . \tag{식 A.2} \]

5.1.1 의사코드

INPUT: f', f'', x_0, tol
x ← x_0
fp ← f'(x)
WHILE |fp| > tol:
    fpp ← f''(x)
    IF fpp ≈ 0:
        ABORT (수치 불안정)
    x ← x - fp / fpp
    fp ← f'(x)
RETURN x

직관 — Taylor 1차 근사 = 접선

\(x_i\) 근처에서 \(f'\) 의 1 차 Taylor 근사:

\[ f'(x) \approx f'(x_i) + f''(x_i) \cdot (x - x_i) . \]

이는 \(f'\) 의 그래프에 점 \((x_i, f'(x_i))\) 에서 접선을 그은 것 (기울기 = \(f''(x_i)\)).

이 접선의 \(x\)-intercept (\(f'(x) = 0\)) 를 풀면:

\[ x_{i+1} = x_i - \frac{f'(x_i)}{f''(x_i)} . \]

이게 식 (A.2). 즉 \(f'\) 의 접선의 영점 을 다음 후보로 삼는다.

Secant 와 비교: - Secant: 두 점을 잇는 할선의 영점. 두 점 사이의 평균 기울기 사용. - Newton: 한 점에서 그은 접선의 영점. 그 점의 정확한 기울기 (\(f''\)) 사용.

따라서 Newton 이 더 정확한 1차 근사 → 더 빠른 수렴.

5.2 수렴 차수 — 2차 (Quadratic) 의 유도

Quadratic 수렴 유도

영점 \(\hat{x}\) 근처에서 \(f'(\hat{x}) = 0\). Taylor 전개:

\[ f'(x_i) = f''(\hat{x}) \cdot (x_i - \hat{x}) + \frac{1}{2} f'''(\hat{x}) (x_i - \hat{x})^2 + O(e_i^3) , \]

\[ f''(x_i) = f''(\hat{x}) + f'''(\hat{x}) (x_i - \hat{x}) + O(e_i^2) , \]

여기서 \(e_i = x_i - \hat{x}\).

Newton 갱신 \(x_{i+1} = x_i - f'(x_i)/f''(x_i)\) 에서:

\[ \begin{aligned} e_{i+1} &= e_i - \frac{f'(x_i)}{f''(x_i)} \\ &\approx e_i - \frac{f''(\hat{x}) e_i + \frac{1}{2} f'''(\hat{x}) e_i^2}{f''(\hat{x}) + f'''(\hat{x}) e_i} \\ &= e_i - e_i \cdot \frac{1 + \frac{1}{2} \frac{f'''(\hat{x})}{f''(\hat{x})} e_i}{1 + \frac{f'''(\hat{x})}{f''(\hat{x})} e_i} \\ &\approx e_i \cdot \left[1 - \left(1 - \frac{1}{2} \frac{f'''(\hat{x})}{f''(\hat{x})} e_i\right)\right] = \frac{1}{2} \frac{f'''(\hat{x})}{f''(\hat{x})} e_i^2 . \end{aligned} \]

따라서:

\[ \boxed{ e_{i+1} \approx \frac{f'''(\hat{x})}{2 f''(\hat{x})} \cdot e_i^2 } . \]

오차가 매 step 제곱 된다. 정확도 변화:

Step	오차
0	\(10^{-2}\)
1	\(10^{-4}\)
2	\(10^{-8}\)
3	\(10^{-16}\) (기계 정밀도 도달)

3 step 만에 16 자리 정밀도. 이것이 Newton 의 폭발적 가속의 원천.

5.3 발산 사례 — Newton 의 약점

Newton-Raphson 이 실패하는 경우

1. \(f''(x_i) \approx 0\) — 접선이 거의 수평: Step 크기가 폭발. 변곡점 근처에서 발생.

2. Overshoot — 접선이 영점을 너무 멀리 가리킴: \(|f'(x_i)/f''(x_i)|\) 가 크면 새 점이 영점 반대편 멀리 점프. 그 새 점에서 또 잘못된 방향 → 발산.

3. 잘못된 방향 — \(f\) 값 감소: \(f(x_{i+1}) < f(x_i)\) 면 최대화에 반대 방향 진행. Newton 식은 root 를 찾을 뿐, 값의 증가를 보장 안 함.

4. 다중 영점에서의 cycle: 시작값에 따라 두 영점 사이를 왔다갔다하는 cycle 가능 (드뭄).

대처 — Step Halving:

\(f(x_{i+1}) < f(x_i)\) 검출 시 step 크기 절반:

\[ x_{i+1} = x_i - \frac{1}{2} \cdot \frac{f'(x_i)}{f''(x_i)} . \]

다시 안 되면 또 절반 (\(1/4\), \(1/8\), …). 이는 SAS Cox 회귀의 표준 안전장치이다.

대안 — Levenberg-Marquardt (다변수): \(f''\) 에 작은 양의 상수를 더해 안정화. 다변수 최적화의 표준 (§ A.2 참조).

5.4 Newton-Raphson 의 사용 시점

조건	Newton 이 적합
좋은 초기값 (영점 근처)	O — 빠른 quadratic 수렴
\(f''\) 평가 가능·저렴	O — Hessian 정보 활용
함수 부드러움 (\(C^2\), 단봉)	O — Taylor 근사 정확
단일 영점	O — 다중 영점 cycle 회피

6 세 방법의 비교 — 정량적

\(k\) step 후 정확도

초기 오차 \(e_0 = 0.1\) 이라고 하자. 각 방법의 \(k\) step 후 오차:

Step	Bisection (\(\times 1/2\))	Secant (\(e_i^{1.618}\))	Newton (\(e_i^2\))
0	\(10^{-1}\)	\(10^{-1}\)	\(10^{-1}\)
1	\(5 \times 10^{-2}\)	\(\approx 10^{-1.62} \approx 2.4 \times 10^{-2}\)	\(10^{-2}\)
2	\(2.5 \times 10^{-2}\)	\(\approx 10^{-2.62}\)	\(10^{-4}\)
3	\(1.25 \times 10^{-2}\)	\(\approx 10^{-4.24}\)	\(10^{-8}\)
4	\(6.25 \times 10^{-3}\)	\(\approx 10^{-6.86}\)	\(10^{-16}\)

Newton 의 압도적 우위: 4 step 만에 기계 정밀도 도달. Bisection 은 같은 정밀도까지 약 50 step 필요.

Secant 도 매우 빠름: 4 step 으로 \(10^{-7}\) 수준 — 실용적으로 Newton 과 큰 차이 없음.

그러나 Newton 의 한 step 비용이 Secant 보다 클 수 있다 (\(f''\) 계산). 따라서 한 step 의 wallclock 시간을 비교하면 Secant 가 유리할 수 있다 — 특히 Hessian 비싼 우도에서.

7 Example A.1 — Weibull 단모수 MLE

7.1 데이터와 모형

10 개 비검열 관측 (단순화된 생존시간):

t = (2.57, 0.58, 0.82, 1.02, 0.78, 0.46, 1.04, 0.43, 0.69, 1.37)

\(\sum t_j \approx 9.76\), \(\sum \ln t_j \approx -0.94\).

진짜 분포: Weibull, \(\lambda = 1\) 고정, \(\alpha\) 만 추정. 생존함수 \(S(t) = e^{-t^\alpha}\), 위험률 \(h(t) = \alpha t^{\alpha-1}\).

7.1.1 Log-likelihood, Score, Hessian

\[ \ell(\alpha) = n \ln \alpha + (\alpha - 1) \sum \ln t_j - \sum t_j^\alpha . \]

\[ f'(\alpha) = \frac{n}{\alpha} + \sum \ln t_j - \sum t_j^\alpha \ln t_j . \]

\[ f''(\alpha) = -\frac{n}{\alpha^2} - \sum t_j^\alpha (\ln t_j)^2 . \]

\(f''(\alpha) < 0\) for all \(\alpha > 0\) → 우도가 단봉, 어떤 영점이든 최대.

7.2 Bisection — 8 step Trace (Klein 본문 표)

초기 구간 \([\alpha_L, \alpha_U] = [1.5, 2]\). 정지 기준 \(|f'(\alpha)| < 0.01\).

Step	\(\alpha_L\)	\(\alpha_U\)	\(\alpha_N\)	\(f'(\alpha_L)\)	\(f'(\alpha_U)\)	\(f'(\alpha_N)\)
1	1.5	2.0	1.75	1.798	\(-2.589\)	\(-0.387\)
2	1.5	1.75	1.625	1.798	\(-0.387\)	0.697
3	1.625	1.75	1.6875	0.697	\(-0.387\)	0.154
4	1.6875	1.75	1.71875	0.154	\(-0.387\)	\(-0.116\)
5	1.6875	1.71875	1.70313	0.154	\(-0.116\)	0.019
6	1.70313	1.71875	1.71094	0.019	\(-0.116\)	\(-0.049\)
7	1.70313	1.71094	1.70704	0.019	\(-0.049\)	\(-0.015\)
8	1.70313	1.70704	1.70509	0.019	\(-0.015\)	0.002

8 step 후 \(\hat{\alpha} = 1.705\). \(|f'(1.705)| < 0.01\) 충족.

Trace 의 패턴

• 구간 길이: 0.5 → 0.25 → 0.125 → … → 0.0039 (정확히 절반씩).
• \(f'\) 부호 변동: 매 step 에서 새 중점의 부호가 한쪽 끝과 일치하면 다른 끝을 그 중점으로 대체. step 1 의 \(f'(1.75) = -0.387\) (음수) 이 \(f'(2) = -2.589\) (음수) 와 같은 부호 → \(x_U \leftarrow 1.75\).
• 수렴 패턴: 안정적, 진동 없음. 매 step 정확히 절반의 진전.

8 step 으로 정밀도 \(0.5/2^8 \approx 0.002\) 도달 — 정지 기준 부합.

7.3 Secant Method — 2 step Trace

초기값 \(\alpha_0 = 1.0, \alpha_1 = 1.5\). 같은 정지 기준.

Step	\(\alpha_{i-1}\)	\(\alpha_i\)	\(f'(\alpha_{i-1})\)	\(f'(\alpha_i)\)	\(\alpha_{i+1}\)	\(f'(\alpha_{i+1})\)
1	1.0	1.5	7.065	1.798	1.671	0.300
2	1.5	1.671	1.798	0.300	1.705	0.004

2 step 후 \(\hat{\alpha} = 1.705\). \(|f'(1.705)| = 0.004 < 0.01\) 충족.

식 (A.1) 의 직접 적용

Step 1: \(\alpha_2 = 1.5 - 1.798 \cdot \frac{1.5 - 1.0}{1.798 - 7.065} = 1.5 - 1.798 \cdot \frac{0.5}{-5.267} = 1.5 + 0.171 = 1.671\).

Step 2: \(\alpha_3 = 1.671 - 0.300 \cdot \frac{1.671 - 1.5}{0.300 - 1.798} = 1.671 - 0.300 \cdot \frac{0.171}{-1.498} = 1.671 + 0.034 = 1.705\).

Bisection 8 step → Secant 2 step: 동일 정밀도 도달에 4 배 빠름.

7.4 Newton-Raphson — 2 step Trace

초기값 \(\alpha_0 = 1.5\). \(f'(1.5) = 1.798\), \(f''(1.5) = -8.947\).

Step	\(\alpha_{i-1}\)	\(f'(\alpha_{i-1})\)	\(f''(\alpha_{i-1})\)	\(\alpha_i\)	\(f'(\alpha_i)\)
1	1.5	1.798	\(-8.947\)	1.701	0.038
2	1.701	0.038	\(-8.655\)	1.705	\(2 \times 10^{-6}\)

2 step 후 \(\hat{\alpha} = 1.705\).

Newton 의 한 step 의 정확도

Step 1: \(\alpha_1 = 1.5 - 1.798/(-8.947) = 1.5 + 0.201 = 1.701\). 첫 step 만에 정답에 매우 가까움 (\(1.701\) vs \(1.705\), 차이 \(0.004\)).

Secant 의 첫 step 결과는 \(1.671\) — Newton 보다 \(0.030\) 더 멀다. Newton 의 정확한 곡률 정보 (\(f''\)) 가 첫 step 부터 더 좋은 추정을 만든다.

그러나 같은 2 step 으로 Secant 도 도달. 정지 기준이 \(|f'| < 0.01\) 로 너그러우면 두 방법 동등.

만약 \(|f'| < 10^{-10}\) 같은 엄격한 기준이면: - Newton: 3-4 step 으로 도달 (quadratic). - Secant: 5-6 step 필요 (super-linear \(\phi\)).

차이가 점점 벌어진다. 그러나 어느 쪽이든 Bisection (선형) 보다 압도적.

7.5 세 방법 종합 비교

방법	Step	\(\hat{\alpha}\)	마지막 \(|f'|\)	비고
Bisection	8	1.705	0.002	견고하지만 느림
Secant	2	1.705	0.004	빠르고 \(f''\) 불필요
Newton-Raphson	2	1.705	\(2 \times 10^{-6}\)	가장 빠르고 정확

같은 답, 다른 길

세 방법 모두 같은 \(\hat{\alpha} = 1.705\) 에 수렴. 단순한 1D 단봉 우도라 어느 방법이든 OK. 실제 차이:

• Step 수: 8 → 2 → 2.
• 마지막 \(f'\) 값: 0.002 → 0.004 → \(10^{-6}\) (Newton 이 가장 정확).
• Computation:
  • Bisection: \(f'\) 8 회 평가.
  • Secant: \(f'\) 3 회 평가 (초기 2 + 매 step 1 추가).
  • Newton: \(f'\) 2 회 + \(f''\) 2 회 평가.

만약 \(f''\) 가 \(f'\) 의 5 배 비용이면 Newton 의 총 비용은 \(2 + 2 \times 5 = 12\) vs Secant 의 3 — Secant 가 더 빠르다.

결론: 한 step 의 wallclock 가 아닌 step 수만 보면 Newton 우위. 비용까지 고려하면 함수 의존. 일반 가이드: Newton 시도 → 발산 시 Secant 또는 Bisection 으로 fallback.

8 Brent’s Method — 결합 알고리즘 (Klein 미언급)

표준 라이브러리의 default

Klein 본문은 세 방법을 별도로 다루지만, 실제 통계 패키지의 default 는 Brent’s method (1973) — 세 방법의 장점을 결합.

알고리즘: 1. Bisection 으로 초기 구간 좁힘 (안전). 2. 영점 근처에서 inverse quadratic interpolation (3 점의 2 차 근사) 시도. 3. Inverse quadratic 이 실패하면 secant. 4. Secant 도 실패하면 bisection. 5. 매 step 진행도 검증 — bisection 보다 못하면 fallback.

보장: 항상 수렴 (bisection 의 견고성). 그리고 함수가 부드러우면 super-linear 수렴 (secant + quadratic).

구현: - Python: scipy.optimize.brentq, scipy.optimize.brent - R: uniroot(), optimize() - C: GSL gsl_root_fsolver_brent

실무 권고: 직접 Newton 구현보다 라이브러리의 Brent 호출이 안전. 단변수 영점 / 최적화는 거의 항상 Brent 가 최적.

9 코드 예시

9.1 Step 1 — Python: scipy 의 통합 API

import numpy as np
from scipy.optimize import brentq, newton, minimize_scalar

# Example A.1 데이터
t = np.array([2.57, 0.58, 0.82, 1.02, 0.78, 0.46, 1.04, 0.43, 0.69, 1.37])
n = len(t)

# Score 와 Hessian
def score(alpha):
    return n / alpha + np.sum(np.log(t)) - np.sum(t**alpha * np.log(t))

def hessian(alpha):
    return -n / alpha**2 - np.sum(t**alpha * (np.log(t))**2)

# 1. Bisection (scipy.optimize.brentq — 사실은 Brent's method)
alpha_b = brentq(score, a=1.0, b=2.0, xtol=1e-6)
print(f"Brent: α̂ = {alpha_b:.6f}")

# 2. Newton-Raphson (직접)
alpha_n = newton(score, x0=1.5, fprime=hessian, tol=1e-6, maxiter=20)
print(f"Newton: α̂ = {alpha_n:.6f}")

# 3. Secant (scipy.optimize.newton with fprime=None — secant 으로 fallback)
alpha_s = newton(score, x0=1.0, x1=1.5, tol=1e-6, maxiter=20)
print(f"Secant: α̂ = {alpha_s:.6f}")

# 4. minimize_scalar — log-likelihood 최대화 (음의 lik 최소화)
def neg_loglik(alpha):
    return -(n*np.log(alpha) + (alpha-1)*np.sum(np.log(t)) - np.sum(t**alpha))

res = minimize_scalar(neg_loglik, bracket=(0.5, 3.0), method='brent')
print(f"minimize_scalar: α̂ = {res.x:.6f}, iterations = {res.nit}")

9.2 Step 2 — R: uniroot / optimize

# Example A.1 데이터
t <- c(2.57, 0.58, 0.82, 1.02, 0.78, 0.46, 1.04, 0.43, 0.69, 1.37)
n <- length(t)

# Score function
score <- function(alpha) n/alpha + sum(log(t)) - sum(t^alpha * log(t))

# 1. uniroot (Brent's method — score 의 영점)
res_uniroot <- uniroot(score, interval = c(0.5, 3.0), tol = 1e-6)
cat("uniroot: α̂ =", res_uniroot$root,
    ", iterations =", res_uniroot$iter, "\n")

# 2. optimize (single-variable function maximization)
loglik <- function(alpha) {
  n*log(alpha) + (alpha-1)*sum(log(t)) - sum(t^alpha)
}
res_opt <- optimize(loglik, interval = c(0.5, 3.0), maximum = TRUE, tol = 1e-6)
cat("optimize: α̂ =", res_opt$maximum, "\n")

9.3 Step 3 — 직접 구현 (학습용)

# Bisection 직접 구현 — 식 (A.2)
def bisection(f, x_L, x_U, tol=1e-4, max_iter=50):
    fp_L = f(x_L); fp_U = f(x_U)
    assert fp_L * fp_U < 0, "양 끝의 부호가 같음"
    for k in range(max_iter):
        x_N = (x_L + x_U) / 2
        fp_N = f(x_N)
        if abs(fp_N) < tol or (x_U - x_L) < tol:
            return x_N, k
        if fp_L * fp_N > 0:
            x_L, fp_L = x_N, fp_N
        else:
            x_U, fp_U = x_N, fp_N
    return (x_L + x_U) / 2, max_iter

# Secant 직접 구현 — 식 (A.1)
def secant(f, x0, x1, tol=1e-4, max_iter=50):
    fp0 = f(x0); fp1 = f(x1)
    for k in range(max_iter):
        if abs(fp1) < tol:
            return x1, k
        if abs(fp1 - fp0) < 1e-12:
            return x1, k  # 분모 0 방지
        x_new = x1 - fp1 * (x1 - x0) / (fp1 - fp0)
        x0, fp0 = x1, fp1
        x1 = x_new
        fp1 = f(x1)
    return x1, max_iter

# Newton-Raphson 직접 구현 — 식 (A.2) + step-halving
def newton_safe(f, fp, x0, tol=1e-4, max_iter=50, f_obj=None):
    x = x0
    for k in range(max_iter):
        fx = f(x)
        if abs(fx) < tol:
            return x, k
        fpx = fp(x)
        if abs(fpx) < 1e-12:
            return x, k  # f'' = 0 방지
        step = fx / fpx
        x_new = x - step
        # step-halving: f_obj 가 감소하면 step 줄임
        if f_obj is not None:
            while f_obj(x_new) < f_obj(x) and abs(step) > 1e-10:
                step /= 2
                x_new = x - step
        x = x_new
    return x, max_iter

# Example A.1 적용
alpha_b, k_b = bisection(score, 1.5, 2.0)
alpha_s, k_s = secant(score, 1.0, 1.5)
alpha_n, k_n = newton_safe(score, hessian, 1.5)
print(f"Bisection: α̂={alpha_b:.4f}, iters={k_b}")
print(f"Secant:    α̂={alpha_s:.4f}, iters={k_s}")
print(f"Newton:    α̂={alpha_n:.4f}, iters={k_n}")

10 핵심 요약

§ A.1 한 줄 요약

단변수 score 영점 찾기는 Bisection (절반씩 좁힘, 선형 수렴 \(\text{length}/2^k\), 매우 견고하지만 느림), Secant (식 A.1, 할선의 영점, 황금비 \(\phi \approx 1.618\) 차 수렴, \(f''\) 불필요), Newton-Raphson (식 A.2, 접선의 영점, 2차 수렴 \(e_{i+1} \propto e_i^2\), 초기값 의존) 의 세 방법이 표준이다. Klein 의 Weibull α MLE 예제 (10 obs, \(\hat{\alpha} = 1.705\)) 에서 bisection 8 step, secant·Newton 모두 2 step. 실무에서는 라이브러리의 Brent’s method (scipy.brentq, R uniroot) 가 세 방법을 결합한 안전한 default 이다.

방법	식	수렴 차수	정보 요구	견고성	Example A.1 step
Bisection	절반씩 좁힘	1 (선형)	\(f'\) 부호만	매우 강	8
Secant	식 (A.1)	\(\phi \approx 1.618\)	\(f'\) (두 점)	중간	2
Newton-Raphson	식 (A.2)	2 (이차)	\(f', f''\)	약	2

5 가지 실무 권고

1. 라이브러리 우선: 직접 Newton 구현보다 scipy.brentq 또는 R uniroot (Brent’s method) 가 안전. 발산·cycle 의 사전 처리 포함.

2. 좋은 시작값이 가장 중요: Newton 의 quadratic 수렴은 시작값이 영점 근처일 때만. Method-of-moments 등으로 사전 추정.

3. 단봉 검증: \(f''(x) < 0\) 이 모든 영역에서 성립하는지 (또는 적어도 영점 근처에서). 단봉 아니면 다른 시작값으로 다중 영점 점검.

4. 정지 기준 다중: \(|f'|\) + \(|x_{i+1} - x_i|\) 둘 다 점검. 한 가지만 보면 가짜 수렴 가능.

5. Step-halving 으로 발산 방지: Newton 의 단순 구현은 위험. \(f\) 값 모니터링 + step 절반 fallback 추가.

11 관련 주제

Klein Appendix A 시리즈

• Appendix A — Numerical Techniques for Maximization — overview (단변수 + 다변수 종합)
• § A.2 — Multivariate Methods — Steepest Ascent·Newton-Raphson 다변수·Marquardt 절충, 지그재그·Hessian 정규화 직관

본문 응용

• Ch.8 — Cox 비례위험 모형 — 단일 공변량 부분우도 (단변수 NR)
• Ch.12 — 모수적 회귀 모형 — Weibull/LL/LN MLE
• § 13.3-13.4 — Gamma Frailty EM & Marginal Model — EM M-step 의 1D θ 업데이트

관련 개념

• Brent’s method (Wikipedia) — 결합 알고리즘
• Convergence rate 일반 (Wikipedia)
• Numerical Recipes Ch.9 — Bisection, Secant, Newton 의 실용 구현

12 참고 문헌

• Klein, J. P., & Moeschberger, M. L. (2003). Survival Analysis: Techniques for Censored and Truncated Data (2nd ed.). Springer. Appendix A.1.
• Brent, R. P. (1973). Algorithms for Minimization without Derivatives. Prentice-Hall. (Brent’s method 의 원전)
• Press, W. H., Teukolsky, S. A., Vetterling, W. T., & Flannery, B. P. (2007). Numerical Recipes (3rd ed.). Cambridge. (Bisection, Secant, Newton, Brent 의 실용 구현 + 수렴 차수 유도)
• Thisted, R. A. (1988). Elements of Statistical Computing: Numerical Computation. Chapman and Hall. (Klein 인용 표준 교재)
• Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer. (현대 표준, line search + trust region 포괄)