지역 최적해

편집 역사 토론
최적설계 수치해석 마지막 수정: 2026-07-25 04:42:11

1. 개요[편집]

지역 최적해
Local Optimum
정의 범위어떤 근방 안에서만 최적
1차 필요조건$\nabla f = \mathbf{0}$ (또는 KKT)
전역성 보장일반적으로 없음 — 볼록 문제만 예외
주 원인비볼록 목적함수 · 초기값 의존성
실무 대응다중 시작, 메타휴리스틱, 연속화

최적화 알고리즘이 멈췄다는 건 “최적을 찾았다”가 아니라 “더 내려갈 방향을 못 찾았다”는 뜻이다. 이 둘의 차이가 이 문서 전부다.

지역 최적해(local optimum, 국소 최적해)는 정의역 전체가 아니라 자기 주변의 어떤 근방 안에서만 목적함수를 최소(또는 최대)로 만드는 점이다. 형식적으로 실행가능 집합 Ω\Omega 위의 점 x∗\mathbf{x}^*가 국소 최소라는 것은, 어떤 ε>0\varepsilon > 0이 존재해

f(x∗)≤f(x)∀ x∈Ω∩B(x∗,ε)f(\mathbf{x}^*) \le f(\mathbf{x}) \quad \forall\, \mathbf{x} \in \Omega \cap B(\mathbf{x}^*, \varepsilon)

가 성립한다는 뜻이다. 부등식이 x≠x∗\mathbf{x} \ne \mathbf{x}^*에 대해 엄격하면 엄격 국소 최소(strict local minimum), 근방 조건 없이 Ω\Omega 전체에서 성립하면 전역 최소(global minimum)다.

이 문서는 특정 알고리즘이 아니라 “지역 대 전역”이라는 개념 자체를 다룬다. 알고리즘별 이야기는 경사하강법, 유전 알고리즘, 담금질 모사, 입자 군집 최적화 문서에, 설계 문제로의 적용은 최적설계에 있다.

다봉 함수의 유인 영역 지도. 120×80 격자의 모든 셀을 시작점으로 고정 보폭 경사하강을 끝까지 돌려, 도착한 극소에 따라 셀을 색칠한다(성긴 격자에서 시작해 점진적으로 세분한다). 상단 막대는 각 극소가 차지한 넓이 비율이고, 흰 테두리를 두른 초록 구간이 전역 최적해의 몫이다 — 함수값은 가장 낮은데 유인 영역은 가장 좁다. 무작위 시작점 28개를 얹으면 대부분이 얕은 극소로 빨려 들어가는 것이 그대로 보인다. 보폭 α를 전역 극소의 안정 한계 2/λmax 위로 올리면 가장 좁고 가파른 그 우물에 안착하지 못해 해당 영역이 미수렴(회색)으로 바뀐다. 셀 명암은 수렴까지 걸린 반복 수라 분수령 부근이 어둡게 드러난다.

2. 최적성 조건은 국소성만 증명한다[편집]

미분 가능한 무제약 문제에서 국소 최소의 1차 필요조건은 ∇f(x∗)=0\nabla f(\mathbf{x}^*) = \mathbf{0}이다. 제약이 붙으면 라그랑주 승수법을 부등식으로 확장한 카루시-쿤-터커 조건이 그 자리를 대신한다. 2차 충분조건은 헤세 행렬이 양정치, 즉 ∇2f(x∗)≻0\nabla^2 f(\mathbf{x}^*) \succ 0인 것이다.

여기서 반드시 짚어야 할 점은 이 조건들이 하나같이 국소적이라는 사실이다. 조건은 전부 x∗\mathbf{x}^*에서의 미분값만 본다. 함수가 지구 반대편에서 무슨 짓을 하는지는 미분이 알 리 없다. 그래서 1차·2차 조건을 완벽히 만족하는 점을 손에 쥐고도 “이게 전역해인가?”라는 질문에는 원리적으로 답할 수 없다. 답하려면 정의역 전체를 훑거나, 함수의 전역 구조에 대한 추가 가정(볼록성, 립시츠 상수 상한 등)을 도입해야 한다.

이건 게으름의 문제가 아니라 계산 복잡도의 문제다. 비볼록 문제에서 전역 최적성 판정은 일반적으로 NP-난해이며, 심지어 비볼록 이차함수에 대해 “주어진 점이 국소 최소인지” 판정하는 것조차 NP-난해임이 알려져 있다(Murty & Kabadi, 1987).1

3. 볼록성이 사주는 것[편집]

이 모든 우울함이 한 번에 걷히는 경우가 있다. 목적함수가 볼록(convex)이고 실행가능 집합도 볼록이면,

f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y),∀λ∈[0,1]f(\lambda \mathbf{x} + (1-\lambda)\mathbf{y}) \le \lambda f(\mathbf{x}) + (1-\lambda) f(\mathbf{y}), \qquad \forall \lambda \in [0,1]

이 성립하고, 이로부터 모든 국소 최소는 곧 전역 최소임이 곧바로 따라 나온다. 증명은 세 줄이다. 국소 최소 x∗\mathbf{x}^*보다 더 낮은 점 y\mathbf{y}가 있다면 둘을 잇는 선분 위의 점들이 볼록 부등식에 의해 f(x∗)f(\mathbf{x}^*)보다 낮아지는데, 그 선분은 x∗\mathbf{x}^*의 임의로 작은 근방까지 파고들 수 있으므로 국소 최소라는 가정과 모순이다.

여기에 강볼록성까지 붙으면 최적해가 유일하다. 이차계획법이나 최소자승 문제가 “일단 풀리면 끝”인 이유, 그리고 볼록 최적화가 별도의 학문 분과로 대접받는 이유가 이것이다. 문제를 볼록하게 정식화할 수 있다면 그것 자체가 최고의 전역 최적화 전략이다. 불행히도 위상 최적화의 중간밀도 벌점, 난류 모델의 비선형성, 역문제의 데이터 오차 같은 현실 요소들이 이 축복을 매번 걷어차 간다.

4. 끌림 분지와 초기값 의존성[편집]

국소 알고리즘 A\mathcal{A}(경사하강, 뉴턴 계열, 신뢰 영역 방법 등)를 초기값 x0\mathbf{x}_0에서 출발시켰을 때 도달하는 국소해가 x∗\mathbf{x}^*가 되는 x0\mathbf{x}_0들의 집합을 x∗\mathbf{x}^*의 끌림 분지(basin of attraction)라 부른다. 그러면 최적화 문제의 정의역은 국소해 개수만큼의 분지로 쪼개지고, “어느 해를 얻느냐”는 사실상 “어느 분지에서 출발했느냐”로 결정된다.

분지가 얼마나 많을 수 있는지는 벤치마크 함수 하나로 실감할 수 있다. 라스트리진 함수

f(x)=10n+∑i=1n[xi2−10cos⁡(2πxi)]f(\mathbf{x}) = 10n + \sum_{i=1}^{n}\left[x_i^2 - 10\cos(2\pi x_i)\right]

는 표준 정의역 [−5.12, 5.12]n[-5.12,\,5.12]^n에서 차원당 약 11개의 국소 최소를 가지므로, 전체 개수가 대략 11n11^n으로 폭증한다. n=10n=10이면 이미 2.6×10102.6 \times 10^{10}개다. 이 안에서 원점 하나를 순수한 국소 탐색으로 찾을 확률은 사실상 로또다.

주의할 점은 분지가 알고리즘에 딸린 개념이라는 것이다. 같은 함수라도 스텝 크기가 크면 분지 경계가 흐려지고 때로는 이웃 골짜기로 튕겨 나가며, 관성(모멘텀)이나 확률적 잡음이 있으면 분지를 넘나든다. 확률적 경사하강법이 얕은 국소해를 곧잘 탈출하는 것이 대표적인 예다. 고정 보폭 경사하강만 놓고 보면 이 의존성은 정량적으로도 선명하다. 극소 x∗\mathbf{x}^*에서 헤세 행렬의 최대 고유값이 λmax⁡\lambda_{\max}일 때 x←x−α∇f(x)x \leftarrow x - \alpha \nabla f(x)의 국소 수렴 조건은 α<2/λmax⁡\alpha < 2/\lambda_{\max}이므로, 좁고 가파른 골짜기일수록 허용 보폭이 작다. 보폭을 그 한계 위로 올리면 가장 깊은 해가 하필 가장 먼저 잡히지 않게 된다 — 위 지도에서 전역 최적해의 분지가 통째로 사라지는 것이 그 경우다.

5. 실무의 대응 전략[편집]

전역해를 증명할 수 없다면, 남는 건 “충분히 좋은 해를 확보할 확률을 높이는” 공학적 처방들이다.

  • 다중 시작(multi-start): 초기값을 여러 개 뿌리고 전부 국소 최적화한 뒤 제일 좋은 걸 취한다. 무식하지만 병렬화가 완벽하고, 어떤 정교한 기법보다 먼저 시도해야 하는 기준선이다. 초기점을 소볼 수열이나 라틴 하이퍼큐브(실험계획법)로 깔면 커버리지가 개선된다.
  • 메타휴리스틱: 유전 알고리즘, 입자 군집 최적화, 담금질 모사처럼 확률적으로 언덕을 되올라가는 것을 허용하는 계열. 담금질 모사는 온도를 충분히 천천히 낮추면 전역해 수렴이 확률 1로 보장되지만, 그 “충분히 천천히”가 지수 시간이라 현실에서는 그냥 좋은 휴리스틱으로 쓴다.2
  • 분지 도약(basin hopping): 국소 최적화 → 무작위 도약 → 다시 국소 최적화를 반복하며 분지 사이만 건너뛰는 방식. 원자 클러스터 구조 탐색(포텐셜 에너지 표면의 국소 최소 사냥)에서 표준 도구다. 온도를 갈아 끼우는 병렬 템퍼링도 같은 계열의 문제의식에서 나왔다.
  • 연속화(continuation, homotopy): 풀기 쉬운(대개 볼록에 가까운) 문제에서 출발해 파라미터를 서서히 원래 문제로 옮기며 해를 따라간다. 위상 최적화의 벌점 지수를 3까지 단계적으로 올리는 관행, 영상 처리의 graduated non-convexity, 다중 해상도로 거친 격자에서 먼저 풀고 세밀한 격자로 넘기는 전략이 전부 같은 아이디어다.
  • 대리 모델 기반 전역 탐색: 대리 모델과 베이지안 최적화는 탐험-이용 균형을 명시적으로 관리해 예산 안에서 전역 탐색을 시도한다. 해석 한 번이 3시간 걸리는 최적설계 문제에서 다중 시작이 감당 안 될 때의 대안이다.

6. 고차원의 반전 — 진짜 적은 안장점[편집]

고전적 서사는 “고차원 비볼록 지형은 나쁜 국소 최소로 가득하다”였다. 그런데 딥러닝 쪽에서 나온 논의는 그 서사를 상당히 뒤집었다. 임계점에서 헤세 행렬의 고유값 부호가 대략 무작위라고 보면, nn개가 전부 양수일 확률은 차원이 커질수록 지수적으로 줄어든다. 즉 고차원에서 무작위로 만난 임계점은 압도적인 확률로 안장점이지 국소 최소가 아니다. 가우시안 랜덤 필드에 대한 분석(Bray & Dean, 2007)과 신경망 손실 지형 연구(Dauphin et al., 2014)가 이 그림을 뒷받침한다.

더구나 존재하는 국소 최소들은 목적함수 값이 서로 비슷한 층에 몰려 있는 경향이 있어서, “나쁜 국소 최소에 갇혀 망했다”보다 “안장점 근처 평지에서 기울기가 죽어 학습이 기어간다”가 실제 병목에 가깝다. 여기에 대한 처방은 전역 최적화가 아니라 음의 곡률 방향을 쓰는 방법(신뢰 영역, 음곡률 탐색)이나 잡음 주입이다. 다만 이 결론을 설계 최적화에 그대로 수입하면 안 된다. 설계 변수 수십 개짜리 저차원 문제에서는 여전히 국소 최소가 진짜 적이고, 응력집중 제약처럼 지형을 험하게 만드는 요소도 많다.

7. 공학에서의 현실적 태도[편집]

정직하게 말하면, 산업 현장의 최적설계 결과 대부분은 전역해라는 보장이 없다. 그래도 프로젝트가 굴러가는 이유는 목표가 “증명된 전역해”가 아니라 “현행 설계보다 확실히 나으면서 제약을 다 만족하는, 재현 가능한 해”이기 때문이다. 그래서 보고서에 써야 할 것은 최적해 하나가 아니라 어떤 초기값 집합에서 몇 개의 서로 다른 국소해가 나왔고 그 성능 산포가 얼마인가다. 이 산포 자체가 불확실성 정량화의 재료이며, 신뢰성 해석에서 요구하는 여유(margin) 설정의 근거가 된다. 그리고 이 모든 절차의 신뢰도는 결국 검증 및 확인이 받쳐 준다 — 전역해라고 우기는 것보다 “이 해가 어떤 조건에서 얻어졌는지”를 남기는 쪽이 훨씬 공학답다.3

8. 관련 문서[편집]

9. Footnotes[편집]

  1. 이 결과가 주는 교훈이 은근히 살벌하다. “전역해인지 확인만 해봐”라는 요청은 물론이고 “국소해인 것만이라도 확인해줘”조차 일반적으로는 다항시간에 불가능하다. 최적화 코드가 출력하는 Optimization terminated successfully는 “1차 조건 잔차가 문턱값 아래로 내려갔다”는 뜻일 뿐, 그 이상의 어떤 것도 아니다. ↩

  2. 담금질 모사의 전역 수렴 정리는 온도를 Tk∝1/log⁡kT_k \propto 1/\log k로 낮출 때 성립한다. 로그의 역수라는 건 정확도 한 자리를 더 얻으려면 반복수가 지수적으로 늘어난다는 뜻이라, 현실 시간 안에서는 아무 의미가 없다. 이론이 보장해 주는 것과 목요일 퇴근 전까지 돌려야 하는 것 사이의 거리를 보여주는 대표 사례. ↩

  3. 최적화 결과를 놓고 “이게 전역해 맞냐”고 물어오는 사람에게 정색하고 “비볼록이라 증명 못 합니다”라고 답하면 회의가 얼어붙는다. 실무 화법은 “서로 다른 초기값 200개에서 상위 5개 해의 성능 편차가 0.8% 이내였습니다” 쪽이다. 같은 이야기지만 이쪽이 예산을 딴다. ↩