문제를 식으로 세우기

최적화는 “가능한 선택지 중에서 무엇이 가장 좋은가?”를 수학의 언어로 묻는 일이다. 보통 결정변수 \(x\), 목적함수 \(f\), 허용 가능한 영역 \(\mathcal{X}\)를 정해 \(\min_{x \in \mathcal{X}} f(x)\) 또는 \(\max_{x \in \mathcal{X}} f(x)\)처럼 쓴다. 여기서 핵심은 좋은 알고리즘보다 먼저 좋은 문제 정의다. 비용을 줄이고 싶은지, 위험을 피하고 싶은지, 정확도를 높이고 싶은지에 따라 같은 현실도 전혀 다른 함수가 된다.

해의 종류와 지형 감각

최적화 지형을 산과 계곡으로 상상하면 편하다. 전체에서 가장 낮은 곳은 전역 최소점이고, 주변만 보면 낮지만 더 멀리 가면 더 낮은 곳이 있는 점은 국소 최소점이다. 볼록 문제에서는 임의의 두 점을 잇는 선분이 지형 위로 솟지 않으므로, 국소 최소점이 곧 전역 최소점이 되는 멋진 일이 일어난다. 반대로 비볼록 문제에서는 알고리즘이 어느 계곡에 먼저 들어가느냐가 결과를 크게 좌우한다.

알고리즘을 고를 때 보는 것

좋은 최적화 알고리즘은 매번 더 나은 답을 향해 움직이되, 계산 예산 안에서 멈출 줄 알아야 한다. 함수값만 볼 수 있는지, 그래디언트를 구할 수 있는지, 제약조건이 단순한지, 잡음이 있는지에 따라 선택지가 달라진다. 실패는 대개 세 가지에서 온다. 모델이 현실을 잘못 담았거나, 지형이 지나치게 거칠거나, 수치 스케일이 나빠서 작은 계산 오차가 큰 방향 착각으로 증폭되는 경우다.

작은 움직임이 알려 주는 것

도함수는 “아주 조금 움직였을 때 함수가 얼마나 변하는가”를 말한다. 다변수 함수에서는 그래디언트 \(\nabla f(x)\)가 그 역할을 맡고, 작은 변위 \(d\)에 대해 \(f(x+d) \approx f(x) + \nabla f(x)^\top d\)라고 읽는다. 이 식은 계산 이상의 의미가 있다. \(\nabla f(x)^\top d < 0\)인 방향으로 가면 적어도 충분히 작은 보폭에서는 함수값이 내려갈 가능성이 크다.

가장 가파른 방향

유클리드 거리로 보폭을 재면 가장 빠르게 감소하는 방향은 \(-\nabla f(x)\)다. 단, “가장 빠르다”는 말은 어떤 거리 감각을 쓰는지에 묶여 있다. 변수 하나가 미터 단위이고 다른 하나가 밀리미터 단위라면, 같은 그래디언트라도 실제 움직임은 기묘하게 찌그러진다. 그래서 스케일 조정, 정규화, 전처리는 화려한 장식이 아니라 방향 감각을 되찾는 기본 장비다.

도함수를 얻는 방법과 함정

도함수는 손으로 계산할 수도 있고, 유한차분 \(\frac{f(x+h)-f(x)}{h}\), 자동미분, 심볼릭 계산으로 얻을 수도 있다. 유한차분은 간단하지만 \(h\)가 너무 크면 근사가 거칠고, 너무 작으면 반올림 오차가 커진다. 함수가 뾰족하거나 끊기거나 잡음이 많으면 그래디언트는 친절한 안내자가 아니라 흔들리는 신호가 된다. 이때는 매끄러운 근사, 확률적 평균, 서브그래디언트 같은 우회로가 필요하다.

한 줄 위에서 최소점을 가두기

브래키팅은 1차원 탐색에서 최소점이 있을 법한 구간을 먼저 확보하는 전략이다. 예를 들어 세 점 \(a < b < c\)가 있고 \(f(b) < f(a)\), \(f(b) < f(c)\)라면, 매끄럽고 단봉형인 상황에서는 최소점이 \([a,c]\) 안에 있다고 기대할 수 있다. 이 구간은 정확한 답이 아니라 “이 안을 집중해서 파 보자”는 작업 공간이다.

구간을 넓히고 줄이는 감각

처음부터 알맞은 구간을 알기는 어렵다. 그래서 작은 보폭으로 시작해 함수값이 내려가는 동안 한 방향으로 보폭을 키우고, 다시 올라가기 시작하면 그 주변을 괄호처럼 감싼다. 이후에는 황금분할 탐색이나 포물선 보간처럼 새 평가점을 영리하게 골라 구간을 줄인다. 목표는 매번 정답을 맞히는 것이 아니라, 비싼 함수 평가 횟수를 아끼며 불확실성을 줄이는 것이다.

브래키팅이 흔들리는 경우

브래키팅은 함수가 어느 정도 질서 있게 생겼다는 기대 위에 서 있다. 구간 안에 골짜기가 여러 개 있거나, 함수값에 잡음이 있거나, 최소점이 경계에 붙어 있으면 \(f(b) < f(a), f(c)\) 같은 간단한 신호가 오해를 부른다. 또한 다변수 문제에서 선탐색으로 브래키팅을 쓸 때는, 현재 방향이 좋지 않으면 아무리 1차원 탐색을 잘해도 큰 진전을 얻기 어렵다.

현재 위치에서 한 걸음

국소 하강은 현재 위치 \(x_k\)에서 더 나아 보이는 방향 \(d_k\)와 보폭 \(\alpha_k\)를 골라 \(x_{k+1}=x_k+\alpha_k d_k\)로 움직이는 틀이다. 방향은 그래디언트, 좌표축, 무작위 샘플, 근사 모델에서 나올 수 있다. 중요한 조건은 적어도 충분히 작은 보폭에서 \(f(x_{k+1}) < f(x_k)\)를 기대할 수 있느냐이다.

보폭 선택과 멈춤

방향이 좋아도 보폭이 나쁘면 실패한다. 너무 작으면 계산은 성실하지만 제자리걸음이고, 너무 크면 골짜기를 뛰어넘어 함수값이 올라간다. 선탐색은 한 방향에서 적당한 \(\alpha_k\)를 찾고, 신뢰영역 방법은 “내 근사 모델을 믿을 수 있는 반경” 안에서만 움직인다. 멈춤 기준은 \(\|\nabla f(x_k)\|\), 함수값 변화량, 반복 횟수, 시간 예산처럼 여러 신호를 함께 보는 편이 안전하다.

제약과 실패 양상

제약조건이 있으면 단순히 내려가는 것만으로는 부족하다. 이동 후 허용 영역 밖으로 나갔다면 투영 \(x \leftarrow \Pi_{\mathcal{X}}(x)\)을 하거나, 애초에 제약을 만족하는 방향만 골라야 한다. 국소 하강은 안장점, 평평한 고원, 날카로운 협곡, 나쁜 초기값에 약하다. 특히 비볼록 문제에서는 “더 이상 내려가지 않는다”가 “좋은 답이다”와 같은 말이 아니다.

그래디언트 하강의 기본형

1차 방법은 함수값과 그래디언트처럼 1차 정보에 기대어 움직인다. 대표적인 갱신식은 \(x_{k+1}=x_k-\alpha_k \nabla f(x_k)\)이다. \(f\)가 \(L\)-매끄럽고 \(\alpha_k \le 1/L\)이면, 적절한 조건에서 한 걸음이 함수값을 낮춘다는 보장을 얻을 수 있다. 이 단순함 덕분에 차원이 크고 헤시안을 다루기 어려운 문제에서 1차 방법은 매우 실용적이다.

속도를 좌우하는 조건수

그래디언트 하강은 둥근 그릇에서는 시원하게 내려가지만, 길고 좁은 골짜기에서는 좌우로 튀며 느려진다. 이 현상은 대략 조건수 \(\kappa = L/\mu\)가 클수록 심해진다. 여기서 \(L\)은 기울기가 얼마나 빨리 변할 수 있는지, \(\mu\)는 바닥이 얼마나 단단히 휘어 있는지를 나타내는 상수로 볼 수 있다. 모멘텀, 적응적 보폭, 전처리는 이 지그재그를 줄이려는 시도다.

확률적 방법과 현실의 데이터

대규모 데이터 문제에서는 전체 목적함수의 그래디언트를 매번 계산하기 비싸다. 확률적 그래디언트 방법은 일부 샘플로 만든 추정 그래디언트 \(g_k\)를 사용해 \(x_{k+1}=x_k-\alpha_k g_k\)로 갱신한다. 이 방식은 빠르게 움직이지만 잡음 때문에 최적점 근처에서 흔들린다. 학습률을 줄이거나 미니배치를 키우거나 평균화 기법을 쓰는 이유가 바로 여기에 있다.

곡률까지 보는 뉴턴 관점

2차 방법은 그래디언트뿐 아니라 곡률 정보, 즉 헤시안 \(\nabla^2 f(x)\)를 사용한다. 현재 위치 주변에서 목적함수를 \(m_k(p)=f(x_k)+\nabla f(x_k)^\top p+\frac{1}{2}p^\top \nabla^2 f(x_k)p\)로 근사하면, 이 이차 모델의 최소점을 향한 뉴턴 방향은 \(\nabla^2 f(x_k)p_k=-\nabla f(x_k)\)를 풀어 얻는다. 지형이 정말 이차식에 가깝다면 매우 빠르게 수렴한다.

빠르지만 무거운 방법

2차 방법의 매력은 방향 품질이다. 그래디언트 하강이 좁은 골짜기에서 흔들릴 때, 뉴턴 방향은 골짜기의 휘어짐을 반영해 더 직접적인 길을 제안한다. 그러나 헤시안을 만들고 선형시스템을 푸는 비용은 크다. 그래서 큰 문제에서는 정확한 헤시안 대신 제한된 메모리 준뉴턴 방법, 헤시안-벡터 곱, 켤레그래디언트 같은 절충이 자주 쓰인다.

감쇠와 신뢰영역

뉴턴 방향이 항상 하강 방향인 것은 아니다. 헤시안이 양의 정부호가 아니면 이차 모델은 아래로 열린 그릇이 아니라 안장 모양일 수 있고, 그때 \(p_k\)는 함수값을 키우는 방향이 될 수 있다. 실무에서는 감쇠 뉴턴 \(x_{k+1}=x_k+\alpha_k p_k\), 신뢰영역, 헤시안 보정처럼 조심스러운 장치를 붙인다. 빠른 방법일수록 잘못 믿었을 때 크게 빗나갈 수 있다는 점을 기억해야 한다.

7.1 미분 없이 길을 찾기

직접 방법은 목적함수 \(f(x)\)의 기울기나 헤세 행렬을 믿기 어려울 때 꺼내는 탐색 도구다. 함수값을 몇 번 찍어 보고, 더 낮아지는 방향으로 이동하고, 나빠지면 발을 빼는 식이다. 실험 장비, 시뮬레이터, 블랙박스 모델처럼 “값은 주지만 내부는 안 보여 주는” 문제에서 특히 쓸모가 있다.

핵심 감각은 겸손한 시행착오다. 좌표 방향 탐색은 한 변수씩 움직여 보며 \(f(x+\alpha e_i)\)와 \(f(x)\)를 비교하고, 패턴 탐색은 좋은 이동이 반복되면 더 크게 움직인다. 단체로 산을 내려가기보다 손전등 하나 들고 발밑을 확인하는 느낌에 가깝다.

7.2 단체 사진으로 보는 단체점: 단체체 탐색

넬더-미드 같은 단체체(simplex) 방법은 여러 후보점을 한꺼번에 들고 다닌다. 현재 후보들 중 가장 나쁜 점을 반사, 확대, 수축시키면서 더 그럴듯한 모양으로 바꿔 간다. \(n\)차원에서는 보통 \(n+1\)개의 점이 움직이므로, 점 하나만 보는 탐색보다 지형의 기울어진 분위기를 더 잘 느낄 수 있다.

다만 이 방법들은 “느낌은 좋은데 보증은 약한” 편이다. 매끄럽지 않은 함수나 잡음 있는 함수에서는 꽤 끈질기지만, 차원이 커지면 후보점들이 서로 멀어지고 한 번의 판단에 필요한 함수 평가가 부담스러워진다. 실패 모드는 대개 조용하다. 겉보기에는 열심히 움직이는데 실제로는 평평한 고원에서 제자리 체조를 하는 식이다.

7.3 언제 직접 방법을 고를까

직접 방법은 함수 평가가 싸고 미분 정보가 비싸거나 불안정할 때 빛난다. 반대로 함수 평가가 매우 비싸다면 무작정 많이 찍는 방식은 곧 예산을 태운다. 이때는 평가 횟수 제한, 초기 스케일 조정, 여러 시작점, 조기 종료 기준을 함께 설계해야 한다.

좋은 습관은 변수의 단위를 먼저 맞추는 것이다. 한 좌표는 \(10^{-3}\)만 움직여도 큰 변화가 나고 다른 좌표는 \(10^3\)쯤 움직여야 반응한다면, 탐색 알고리즘은 방향 감각을 잃기 쉽다. 직접 방법에서 전처리는 장식이 아니라 지도 접기다.

8.1 무작위성은 게으름이 아니라 전략이다

확률적 방법은 일부러 무작위성을 넣어 탐색 공간을 흔든다. 결정적 알고리즘이 같은 시작점에서 늘 같은 길로 가는 반면, 확률적 알고리즘은 “이번에는 다른 골목도 보자”는 태도를 가진다. 목적함수가 울퉁불퉁하고 지역 최솟값이 많은 경우, 이 흔들림은 탈출 장치가 된다.

가장 간단한 그림은 무작위 탐색이다. 후보 \(x\) 주변에서 \(x' = x + \epsilon\)을 뽑고, 좋아지면 이동한다. 여기서 \(\epsilon\)의 분포와 크기는 탐색의 성격을 정한다. 너무 작으면 꼼꼼하지만 갇히고, 너무 크면 호방하지만 좋은 골짜기를 지나쳐 버린다.

8.2 나빠도 가끔은 간다

담금질 기법의 매력은 나쁜 이동을 완전히 금지하지 않는다는 데 있다. 예를 들어 새 후보가 \(\Delta f = f(x') - f(x)\)만큼 나쁘더라도, 어떤 온도 \(T\)에서는 대략 \(\exp(-\Delta f/T)\) 같은 확률로 받아들일 수 있다. 온도가 높을 때는 과감히 돌아다니고, 낮아질수록 얌전하게 다듬는다.

이 원리는 실전에서 꽤 인간적이다. 처음부터 완벽히 신중하면 첫 번째 괜찮은 동네에 눌러앉는다. 처음에는 약간 무모하게, 뒤로 갈수록 엄격하게 가는 일정이 필요하다. 실패 모드는 온도 일정에서 많이 나온다. 너무 빨리 식히면 성격 급한 탐욕법이 되고, 너무 천천히 식히면 밤새 산책만 한다.

8.3 표본 평균과 잡음 많은 목적함수

어떤 문제에서는 \(f(x)\) 자체가 기대값이다. 예를 들어 \(\min_x \mathbb{E}[L(x, Z)]\)처럼 데이터 \(Z\)에 대한 평균 손실을 줄이고 싶을 수 있다. 이때 모든 데이터를 매번 쓰는 대신 작은 표본으로 기울기나 함수값을 추정하면 계산량을 크게 줄일 수 있다.

확률적 방법의 장점은 큰 문제를 조금씩 씹어 먹는 능력이다. 하지만 추정 잡음 때문에 수렴 곡선이 깔끔하지 않다. “어제보다 오늘이 꼭 좋아야 한다”는 마음으로 보면 불안하지만, 긴 평균으로 보면 내려가는 경우가 많다. 그래서 이동 크기 감소, 반복 평균, 난수 시드 관리가 중요한 운영 기술이 된다.

9.1 한 명보다 여러 명이 보는 지형

집단 방법은 여러 후보해를 동시에 유지한다. 한 점이 아니라 한 무리의 점이 탐색 공간을 돌아다니기 때문에, 서로 다른 지역을 나눠 보고 좋은 단서를 공유할 수 있다. 진화 알고리즘, 입자 군집 최적화, 차분 진화는 모두 이 생각을 다른 방식으로 구현한다.

집단의 장점은 다양성이다. 목적함수가 비볼록이고 지역 최솟값이 많을 때, 후보 하나는 쉽게 갇히지만 여러 후보는 적어도 몇 명쯤 다른 계곡을 확인할 수 있다. 단점도 바로 그 다양성에서 온다. 후보가 많으면 함수 평가가 많이 필요하고, 서로 너무 닮아지면 집단이라는 장점이 사라진다.

9.2 진화 연산자의 감각

진화 알고리즘은 선택, 변이, 교차 같은 연산자로 후보 집단을 바꾼다. 성능이 좋은 후보를 더 자주 남기되, 변이로 새로운 가능성을 만든다. 교차는 두 후보의 일부 구조를 섞어 더 나은 조합을 기대하는 장치다. 수식으로 쓰면 단순히 \(x_{\text{new}} = x_a + \eta(x_b - x_c)\)처럼 차이를 이용해 새 점을 만들 수도 있다.

여기서 중요한 것은 “좋은 것만 남기면 좋다”가 아니라는 점이다. 선택 압력이 너무 세면 집단이 일찍 한 방향으로 몰린다. 변이가 너무 약하면 새 정보가 안 들어오고, 너무 강하면 학습한 구조가 매번 깨진다. 결국 집단 방법은 탐험과 활용 사이의 사회생활이다.

9.3 입자와 속도, 그리고 단체 분위기

입자 군집 최적화에서는 각 후보가 위치와 속도를 가진 입자처럼 움직인다. 보통 자기 자신이 봤던 최고 위치와 집단이 공유하는 최고 위치 쪽으로 끌린다. 한 입자는 “내 경험”과 “남들의 소문” 사이에서 이동하며, 그 균형이 탐색 성능을 만든다.

실패 모드는 선명하다. 집단 최고점이 사실 별로인 지역 최솟값이면 모두가 그쪽으로 빨려 들어간다. 반대로 끌림이 약하면 각자 흩어져 오래 헤맨다. 그래서 관성, 사회적 끌림, 개인 기억의 가중치를 조심스럽게 잡아야 한다.

10.1 좋은 해는 가능한 해여야 한다

제약조건이 있는 최적화에서는 목적함수만 낮다고 끝이 아니다. 해 \(x\)가 \(g_i(x) \le 0\), \(h_j(x)=0\) 같은 조건을 만족해야 한다. 현실 문제에서는 예산, 물리 법칙, 안전 한계, 재고, 시간표가 모두 제약으로 들어오므로, 제약은 귀찮은 부속품이 아니라 문제의 뼈대다.

제약을 무시하고 먼저 최적화한 뒤 나중에 고치려 하면 대개 비싼 값을 치른다. 목적함수가 좋아지는 방향이 가능 영역 바깥으로 향할 수 있기 때문이다. 가능 영역 \(\mathcal{F} = \{x : g_i(x)\le 0,\ h_j(x)=0\}\)의 모양을 이해하는 것이 첫 번째 일이다.

10.2 벌점, 장벽, 투영

제약을 다루는 쉬운 방법은 위반을 목적함수에 더하는 것이다. 예를 들어 \(\phi(x)=f(x)+\rho \sum_i \max(0,g_i(x))^2\)처럼 벌점을 주면, 제약을 어길수록 값이 커진다. \(\rho\)가 작으면 제약을 대충 넘기고, 너무 크면 수치적으로 뻣뻣해진다.

장벽 방법은 가능 영역 안쪽에서 경계에 가까워질수록 큰 비용을 느끼게 한다. 투영 방법은 한 걸음 이동한 뒤 다시 가능 영역으로 되돌린다. 예를 들어 \(x^+ = \Pi_{\mathcal{F}}(y)\)는 \(y\)에서 가장 가까운 가능해를 찾는 연산이다. 세 방법 모두 “경계를 어떻게 존중할 것인가”에 대한 서로 다른 태도다.

10.3 활성 제약과 경계의 드라마

최적해에서는 모든 제약이 똑같이 중요하지 않다. 어떤 제약은 여유가 있고, 어떤 제약은 딱 붙어 있다. \(g_i(x^\star)=0\)인 제약을 활성 제약이라고 부르며, 이들이 실제 해의 모양을 결정하는 경우가 많다. 최저점이 내부에 있으면 기울기가 사라지는 그림이 맞지만, 경계 위에서는 기울기가 경계를 따라 더 이상 내려갈 수 없는 형태가 된다.

제약 문제의 실패 모드는 제약 위반을 너무 늦게 발견하는 것이다. 알고리즘이 아름다운 목적함수 감소를 보여 줘도, 가능 영역 밖에서 일어난 일이라면 실전에서는 무효표다. 그래서 로그에는 목적함수뿐 아니라 최대 제약 위반량 \(\max_i g_i(x)\)도 함께 봐야 한다.

11.1 원문제의 그림자를 읽기

쌍대성은 제약 최적화 문제를 다른 각도에서 보는 방법이다. 원래 문제를 원문제라고 하면, 쌍대문제는 제약을 가격표처럼 붙여 만든 보조 문제다. 라그랑주 함수 \(L(x,\lambda,\nu)=f(x)+\sum_i \lambda_i g_i(x)+\sum_j \nu_j h_j(x)\)가 그 출발점이다.

여기서 \(\lambda_i\)는 부등식 제약의 위반에 매기는 가격이다. 제약을 어기면 비용이 올라가고, 제약을 만족하면 원래 목적함수와 조화를 이룬다. \(\lambda_i \ge 0\)이라는 조건은 “위반을 보상으로 바꾸지 않겠다”는 안전장치다.

11.2 약한 쌍대성과 강한 쌍대성

쌍대 함수는 \(q(\lambda,\nu)=\inf_x L(x,\lambda,\nu)\)로 정의할 수 있다. 많은 최소화 문제에서 이 값은 원문제의 최적값보다 작거나 같다. 이것을 약한 쌍대성이라고 하며, 아직 최적해를 몰라도 “적어도 이보다 낮을 수는 없다”는 하한을 준다.

운이 좋고 조건이 맞으면 원문제와 쌍대문제의 최적값이 같아진다. 이때 강한 쌍대성이 성립한다고 말한다. 볼록 최적화에서 적절한 정칙 조건이 있으면 강한 쌍대성이 자주 나타난다. 이 순간 쌍대문제는 단순한 그림자가 아니라 원문제를 푸는 우회로가 된다.

11.3 민감도와 가격의 언어

쌍대 변수는 단지 계산 장치가 아니다. 자원 제약 \(a^\top x \le b\)가 있을 때, 해당 쌍대 변수는 \(b\)를 조금 늘렸을 때 최적값이 얼마나 좋아질지 알려 주는 그림자 가격으로 해석할 수 있다. 병목 자원의 가격은 높고, 남아도는 자원의 가격은 보통 0에 가깝다.

상보성 조건 \(\lambda_i g_i(x^\star)=0\)은 특히 예쁘다. 제약이 여유 있으면 가격이 0이고, 가격이 양수라면 제약은 딱 붙어 있다. 시장 이야기처럼 들리지만, 실제로는 최적해의 구조를 압축해서 말하는 문법이다.

12.1 직선들이 만든 다면체 위의 최적화

선형계획법은 선형 목적함수를 선형 제약 아래에서 최적화한다. 표준적인 모습은 \(\min_x c^\top x\) subject to \(Ax \le b\) 같은 형태다. 목적도 직선, 제약도 직선이라 단순해 보이지만, 물류, 배합, 일정, 자원 배분의 엄청난 양을 이 틀 안에 넣을 수 있다.

가능한 해들의 집합은 다면체가 된다. 중요한 사실은 선형 목적함수의 최적해가 보통 꼭짓점에서 발견된다는 점이다. 평평한 판 위에서 한쪽 방향으로 계속 밀면 마지막으로 걸리는 모서리나 꼭짓점에서 멈추는 그림을 떠올리면 된다.

12.2 심플렉스와 내부점의 두 성격

심플렉스 방법은 꼭짓점에서 꼭짓점으로 이동한다. 현재 꼭짓점에서 목적함수를 더 좋게 만드는 인접 꼭짓점을 찾아 이동하고, 더 좋아질 방향이 없으면 멈춘다. 실전에서는 매우 강력하지만, 퇴화된 문제에서는 같은 값의 꼭짓점 주변을 맴도는 일이 생길 수 있다.

내부점 방법은 경계 위를 걷기보다 다면체 내부를 지나간다. 장벽항을 이용해 경계에 부딪히지 않으면서 중심 경로를 따라 최적해 근처로 접근한다. 심플렉스가 도시의 교차로를 따라가는 택시라면, 내부점은 넓은 공원 안쪽을 가로질러 가는 느낌이다.

12.3 쌍대, 민감도, 그리고 모델링 실수

선형계획법은 쌍대성이 특히 깔끔하게 작동하는 무대다. 원문제의 자원 제약은 쌍대문제의 변수로 바뀌고, 그 값은 자원의 그림자 가격을 알려 준다. 생산 계획에서 어떤 재료의 쌍대 가격이 높다면, 그 재료가 전체 이익을 막고 있는 병목일 가능성이 크다.

가장 흔한 실패는 알고리즘보다 모델링에서 온다. 단위를 섞거나, 빠뜨린 제약이 있거나, 실제로는 정수여야 하는 결정을 연속 변수로 둔 경우 답은 빠르게 나오지만 현장에서는 이상해진다. 또 \(Ax \le b\)의 부호 하나가 바뀌면 “현실적인 계획”이 “무제한 돈 복사기”로 변할 수 있다.

이차식은 곡률을 가진 선형 모델이다

이차계획법(QP)은 목적함수에 이차항이 있고, 제약식은 보통 선형인 최적화 문제다. 표준적인 모양은 \[ \min_x \; \frac{1}{2}x^\top Qx + c^\top x \quad \text{s.t.} \quad Ax \le b,\; Ex = f \] 로 쓴다. 선형계획법이 평평한 책상 위에서 가장 낮은 모서리를 찾는 느낌이라면, 이차계획법은 살짝 휘어진 그릇 위에서 제약이 허락하는 낮은 지점을 찾는 느낌에 가깝다.

핵심은 행렬 \(Q\)의 성질이다. \(Q \succeq 0\)이면 목적함수는 볼록이고, 국소해가 곧 전역해가 된다. 반대로 \(Q\)가 음의 곡률을 포함하면 문제는 비볼록이 되어, 한 골짜기에서 얻은 해가 전체에서 가장 좋은 해라는 보장이 사라진다. 실전에서는 이 차이가 알고리즘 선택, 종료 조건 해석, 결과 신뢰도까지 모두 바꾼다.

KKT 조건과 활성 제약

볼록 QP에서는 KKT 조건이 해를 설명하는 강력한 언어가 된다. 부등식 제약 \(g_i(x) \le 0\)에 대한 승수 \(\lambda_i\)는 제약이 얼마나 강하게 최적해를 밀어내는지를 나타낸다. 조건은 대략 \[ Qx^\star + c + A^\top \lambda^\star + E^\top \nu^\star = 0,\quad Ax^\star \le b,\quad \lambda^\star \ge 0,\quad \lambda_i^\star(Ax^\star-b)_i=0 \] 처럼 정리된다. 마지막 상보성 조건은 재미있는 신호다. 제약이 느슨하면 그 제약의 가격은 0이고, 가격이 양수라면 제약은 딱 붙어서 활성화된다.

활성집합 방법은 이 관찰을 정면으로 사용한다. 지금 어떤 제약이 등식처럼 작동하는지 맞혀 보고, 그 가정 아래에서 작은 선형 시스템을 푼다. 반면 내부점 방법은 가능한 영역의 안쪽을 따라 움직이며 경계에 부드럽게 접근한다. 작은 문제나 따뜻한 시작이 있는 반복 제어 문제에서는 활성집합 방법이 매력적이고, 큰 희소 문제에서는 내부점 방법이 안정적인 선택이 되는 경우가 많다.

모델링 감각과 흔한 함정

QP는 포트폴리오 최적화, 모델 예측 제어, 최소제곱 추정, 마진 기반 분류기 등에서 자주 등장한다. 예를 들어 위험을 \(\frac{1}{2}w^\top \Sigma w\), 기대수익을 \(\mu^\top w\)로 두면, 위험과 보상의 절충을 하나의 이차 목적함수로 다룰 수 있다. 이때 공분산 행렬 \(\Sigma\)가 양의 준정부호라는 사실이 볼록성을 지켜 준다.

함정은 수치 스케일에서 자주 나온다. 변수 하나는 \(10^{-3}\) 단위이고 다른 변수는 \(10^6\) 단위라면, 이론상 쉬운 QP도 계산기 입장에서는 미끄러운 문제가 된다. 또 \(Q\)가 거의 특이하거나 제약들이 거의 중복되면 승수 해석이 불안정해진다. 모델이 맞아도 단위와 정규화가 틀리면 해가 이상해 보일 수 있으니, QP에서는 수학만큼 계량 감각도 중요하다.

볼록성을 문법으로 검사한다

규율 볼록 프로그래밍(DCP)은 "이 식이 볼록인가?"라는 어려운 질문을 문법 규칙으로 바꾼 모델링 방식이다. 사용자는 변수, 상수, 매개변수, 그리고 검증된 원자 함수(atom)를 조립한다. 시스템은 각 조각의 곡률과 단조성을 추적해 전체 목적함수와 제약식이 볼록 최적화 문제인지 확인한다.

예를 들어 \(\|Ax-b\|_2\), \(\sum_i \exp(x_i)\), \(-\sum_i \log(x_i)\) 같은 표현은 적절한 영역과 조합 규칙 안에서 안전하게 다룰 수 있다. 하지만 볼록 함수끼리 아무렇게나 합성하면 항상 볼록이 되는 것은 아니다. DCP의 장점은 이 위험한 자유도를 줄여, 모델을 쓰는 순간부터 해석 가능한 계산 문제로 내려보내는 데 있다.

표현력보다 검증 가능성을 먼저 둔다

DCP에서는 목적함수가 최소화 문제라면 볼록이어야 하고, 최대화 문제라면 오목이어야 한다. 부등식 제약은 보통 \[ \text{convex expression} \le \text{concave expression} \] 꼴이어야 안전하다. 등식 제약은 양쪽이 아핀일 때 허용되는 경우가 많다. 이 규칙들은 다소 엄격해 보이지만, 바로 그 엄격함 덕분에 모델링 도구가 문제를 원뿔계획법 같은 표준 형태로 변환할 수 있다.

중요한 점은 "볼록인 식"과 "DCP 규칙으로 증명 가능한 식"이 같지 않다는 것이다. 어떤 식은 실제로 볼록이지만 DCP 문법으로는 인정받지 못할 수 있다. 이럴 때는 식을 다시 쓰는 능력이 필요하다. 예컨대 직접 곱셈으로 표현한 제곱합 대신 \(\|x\|_2^2\)나 허용된 제곱 원자를 사용하면 모델러가 의도를 더 잘 이해한다.

실전 모델링의 좋은 습관

DCP 기반 도구는 빠른 실험에 좋다. 제약을 몇 줄 추가하고, 가중치를 바꾸고, 정규화 항을 붙이며 모델을 탐색할 수 있다. 예를 들어 회귀 문제에 희소성을 원하면 \[ \min_x \; \|Ax-b\|_2^2 + \lambda\|x\|_1 \] 처럼 쓸 수 있다. 이 식은 잔차를 줄이면서도 불필요한 계수를 0으로 밀어 넣는 전형적인 볼록 모델이다.

함정은 모델링 도구가 마법사가 아니라 번역가라는 점이다. 입력한 식이 DCP 규칙을 통과해도, 스케일이 나쁘거나 매개변수 값이 극단적이면 솔버가 고생한다. 또 도메인 제약을 잊으면 \(\log(x)\), \(1/x\), 행렬 역수 같은 표현이 엉뚱한 곳에서 정의되려 할 수 있다. 좋은 DCP 모델은 수학적으로 볼록하고, 단위가 자연스럽고, 데이터 범위가 솔버에게 친절하다.

좋은 해가 하나가 아닐 때

다목적 최적화는 여러 목표가 동시에 존재하는 문제를 다룬다. 비용은 낮추고 싶고, 성능은 높이고 싶고, 위험은 줄이고 싶고, 공정성도 지키고 싶을 때 하나의 숫자로 모든 판단을 압축하기 어렵다. 일반적으로 \[ \min_x \; \big(f_1(x), f_2(x), \ldots, f_k(x)\big) \quad \text{s.t.} \quad x \in \mathcal{X} \] 처럼 벡터 목적함수를 생각한다.

이때 중심 개념은 파레토 최적성이다. 어떤 해 \(x^\star\)가 있을 때, 한 목표도 나빠지지 않으면서 적어도 하나의 목표를 더 좋게 만드는 다른 해가 없다면 \(x^\star\)는 파레토 최적이다. 즉 "완벽한 승자"를 찾는 것이 아니라 "더 이상 공짜 개선이 없는 후보들"을 찾는 것이다.

스칼라화와 절충의 언어

가장 흔한 방법은 여러 목표를 하나의 목적함수로 합치는 것이다. 가중합은 \[ \min_x \; \sum_{i=1}^k w_i f_i(x),\quad w_i \ge 0 \] 로 쓴다. 가중치 \(w_i\)는 선호도의 손잡이처럼 작동한다. 비용을 조금 더 중요하게 볼지, 안정성을 더 중요하게 볼지 조절하며 서로 다른 파레토 해를 샘플링할 수 있다.

하지만 가중합은 만능이 아니다. 파레토 경계가 오목하게 휘어진 부분은 단순 가중합으로 놓칠 수 있다. 또 목표들의 단위가 다르면 가중치 해석이 왜곡된다. \(1\)달러와 \(1\)초와 \(1\)퍼센트포인트는 같은 숫자라도 같은 의미가 아니다. 그래서 정규화, 기준점 설정, \(\epsilon\)-제약법 같은 대안이 자주 필요하다.

의사결정 문제로 돌아오기

다목적 최적화의 결과는 보통 하나의 해가 아니라 후보 집합이다. 엔지니어링 설계에서는 무게와 강도, 운영 계획에서는 비용과 서비스 수준, 머신러닝에서는 정확도와 지연시간이 서로 당긴다. 알고리즘은 파레토 경계를 보여 주지만, 마지막 선택에는 맥락과 책임이 들어간다.

실전의 함정은 "수학적으로 깔끔한 절충"이 곧 "조직이 받아들일 절충"이라고 착각하는 것이다. 어떤 목표는 법적 하한이나 안전 기준처럼 타협 대상이 아니고, 어떤 목표는 작은 변화에도 사용자 경험을 크게 바꾼다. 따라서 다목적 모델은 숫자를 합치기 전에 무엇이 제약이고 무엇이 선호인지부터 분명히 해야 한다.

평가하기 전에 어디를 볼지 정한다

샘플링 계획은 비싼 함수 평가를 하기 전에 입력공간의 어느 지점을 관찰할지 정하는 절차다. 시뮬레이션 한 번이 몇 시간 걸리거나 실험 한 번에 비용이 큰 상황에서는, 무작정 많은 점을 찍는 방식이 통하지 않는다. 좋은 샘플링은 "아직 아무것도 모를 때의 겸손한 탐색"이다.

가장 단순한 방법은 균일 난수 샘플링이다. \(x^{(i)} \sim \mathrm{Uniform}(\mathcal{X})\)로 점을 뽑으면 구현은 쉽지만, 고차원에서는 우연히 빈 구역과 몰린 구역이 생긴다. 격자 샘플링은 질서정연하지만 차원이 늘면 필요한 점 수가 폭발한다. 각 축에 \(m\)개씩만 둬도 총점 수는 \(m^d\)가 된다.

공간 채움 설계

공간 채움(space-filling) 설계는 샘플들이 서로 너무 붙지 않고 전체 영역을 고르게 덮도록 만든다. 라틴 하이퍼큐브 샘플링은 각 변수의 범위를 여러 구간으로 나누고, 각 구간이 한 번씩 쓰이도록 조합한다. 이렇게 하면 각 축에서의 분포가 고르게 유지되어, 적은 점으로도 입력 범위를 넓게 훑을 수 있다.

또 다른 관점은 점들 사이의 최소거리를 키우는 것이다. 예를 들어 \[ \max_{\{x^{(i)}\}_{i=1}^n} \; \min_{i \ne j}\|x^{(i)}-x^{(j)}\|_2 \] 같은 기준은 샘플들이 서로 떨어지도록 유도한다. 이런 설계는 대리모델을 만들 때 특히 유용하다. 초반 데이터가 한쪽에 몰리면 모델은 넓은 영역에서 자신 없는 추측을 하게 된다.

차원과 제약이 만드는 현실감

샘플링 계획에서 차원은 조용하지만 무서운 적이다. 2차원에서 그럴듯하게 촘촘한 점들이 20차원에서는 거의 서로 멀리 떨어진 외딴 점처럼 행동한다. 그래서 고차원 문제에서는 전체 공간을 균일하게 덮겠다는 목표보다, 중요한 변수 조합을 찾거나 낮은 차원의 구조를 활용하는 전략이 필요하다.

제약이 있는 영역도 조심해야 한다. 박스 범위 안에서 점을 잘 뽑았더라도 실제 가능한 영역 \(\mathcal{X}\)가 얇은 띠 모양이면 대부분의 샘플이 버려질 수 있다. 이 경우에는 제약을 만족하는 표본 생성, 변수 변환, 초기 feasible point 주변의 지역 설계가 더 효과적이다. 샘플링은 단순한 전처리가 아니라 이후 모델과 최적화를 좌우하는 첫 단추다.

비싼 함수를 대신하는 빠른 근사

대리모델은 계산 비용이 큰 실제 함수 \(f(x)\)를 더 빠른 근사 함수 \(\hat{f}(x)\)로 대체하는 아이디어다. 항공기 형상 시뮬레이션, 재료 실험, 복잡한 공정 모델처럼 한 번 평가하는 데 큰 비용이 드는 문제에서 특히 중요하다. 목표는 진짜 함수를 완벽히 복제하는 것이 아니라, 의사결정에 필요한 만큼 정확한 지도를 만드는 것이다.

가장 단순한 대리모델은 다항 회귀다. 예를 들어 \[ \hat{f}(x) = \beta_0 + \beta^\top x + x^\top Bx \] 처럼 쓰면 선형 경향과 이차 곡률을 함께 잡을 수 있다. 데이터가 충분하고 함수가 매끄럽다면 이런 낮은 차수 모델은 해석도 쉽고 계산도 빠르다. 하지만 함수가 국소적으로 급격히 변하거나 상호작용이 복잡하면 단순 다항식은 편안한 거짓말을 할 수 있다.

보간, 회귀, 그리고 매끄러움

대리모델은 관측점을 정확히 지나가도록 만들 수도 있고, 잡음을 고려해 부드럽게 평균 경향을 추정할 수도 있다. 결정론적 시뮬레이션처럼 같은 입력에서 항상 같은 출력이 나오면 보간 모델이 자연스럽다. 반대로 실험 데이터에 측정 잡음이 있다면 모든 점을 맞히려는 모델은 잡음까지 외워 버린다.

방사기저함수(RBF) 모델은 관측점 주변에 종 모양 또는 거리 기반 함수를 놓고 이들을 합쳐 전체 근사를 만든다. 대표적으로 \[ \hat{f}(x)=\sum_{i=1}^n w_i \phi(\|x-x^{(i)}\|) \] 같은 구조를 쓴다. 여기서 \(\phi\)의 폭과 모양은 모델이 얼마나 매끄럽게 퍼질지를 결정한다. 너무 좁으면 울퉁불퉁하고, 너무 넓으면 중요한 국소 변화가 지워진다.

검증은 예의가 아니라 생존 기술

대리모델을 만들면 반드시 검증해야 한다. 훈련점에서 잘 맞는다는 사실은 낯선 점에서 잘 맞는다는 보장이 아니다. 교차검증, 홀드아웃 점, 잔차 분석을 통해 모델이 어디서 틀리는지 봐야 한다. 최적화에 쓰려는 모델이라면 평균 오차보다 최저값 근처의 순위와 곡률이 더 중요할 수 있다.

흔한 함정은 대리모델의 최적해를 실제 최적해처럼 믿는 것이다. \(\hat{x}=\arg\min_x \hat{f}(x)\)가 멋져 보여도, 그 지점은 모델의 상상력이 가장 과감해진 곳일 수 있다. 특히 관측 데이터에서 멀리 떨어진 영역의 예측은 조심해야 한다. 대리모델은 빠른 조언자이지, 현실을 대신하는 판사가 아니다.

예측값과 불확실성을 함께 말한다

확률적 대리모델은 단일 예측값뿐 아니라 그 예측의 불확실성까지 제공한다. 같은 \(\hat{f}(x)\)라도 "거의 확신하는 값"과 "데이터가 없어 조심스러운 값"은 다르게 취급해야 한다. 최적화에서는 이 차이가 탐색과 활용의 균형을 정하는 핵심 신호가 된다.

대표적인 모델은 가우스 과정(Gaussian process)이다. 함수값들의 집합을 다변량 정규분포로 보고, 커널 \(k(x,x')\)로 입력점 사이의 유사성을 표현한다. 관측 데이터 \(\mathcal{D}=\{(x^{(i)},y^{(i)})\}\)가 주어지면 새 점 \(x\)에서의 예측은 평균 \(\mu(x)\)와 분산 \(\sigma^2(x)\)로 요약된다.

커널은 함수에 대한 취향이다

커널은 모델이 어떤 함수를 그럴듯하다고 여기는지 정한다. 제곱지수 커널은 매우 매끄러운 함수를 선호하고, 마테른 계열 커널은 조금 더 거친 변화를 허용한다. 길이척도 \(\ell\)이 크면 멀리 떨어진 점들도 비슷하다고 보고, 작으면 가까운 점의 영향만 크게 본다.

단순한 1차원 예로 \[ k(x,x') = \alpha^2 \exp\left(-\frac{(x-x')^2}{2\ell^2}\right) \] 를 생각할 수 있다. 여기서 \(\alpha\)는 함수값 변화의 전형적 크기, \(\ell\)은 변화가 일어나는 입력 거리의 척도다. 이 값들이 데이터에 비해 부적절하면 모델은 과도하게 매끄럽거나 지나치게 민감해진다.

불확실성도 틀릴 수 있다

확률적 모델의 매력은 "모르는 곳을 모른다고 말한다"는 점이다. 관측점 근처에서는 \(\sigma(x)\)가 작아지고, 멀리 떨어진 영역에서는 커진다. 이 정보는 다음 실험점을 고르는 데 매우 유용하다. 좋은 값이 예상되는 곳만 볼지, 불확실성이 큰 곳을 확인할지 판단할 수 있기 때문이다.

그러나 예측 분산은 모델 가정 안에서의 불확실성이다. 커널 선택이 틀렸거나, 잡음 분포가 맞지 않거나, 입력 변수 중 중요한 것이 빠져 있으면 분산이 자신만만하게 작아도 실제로는 틀릴 수 있다. 그래서 확률적 대리모델은 진단이 중요하다. 표준화 잔차, 예측구간 포함률, 반복 실험을 통해 불확실성의 눈금이 현실과 맞는지 확인해야 한다.

모델을 믿되, 확인하면서 전진한다

대리모델 최적화는 비싼 실제 함수 \(f(x)\)를 반복적으로 조금씩 평가하면서, 싼 대리모델로 다음 후보를 고르는 전략이다. 기본 흐름은 간단하다. 초기 샘플을 뽑고, 대리모델을 학습하고, 획득함수나 탐색 규칙으로 다음 점을 고르고, 실제 함수를 평가한 뒤 모델을 갱신한다.

이 과정의 목표는 적은 평가 횟수로 좋은 해를 찾는 것이다. 모든 곳을 촘촘히 확인할 수 없으므로, 지금까지 좋아 보이는 곳을 더 파는 활용(exploitation)과 아직 불확실한 곳을 확인하는 탐색(exploration)을 균형 있게 섞어야 한다. 대리모델 최적화의 맛은 바로 이 줄타기에 있다.

획득함수는 다음 질문을 고른다

확률적 대리모델을 쓴다면 획득함수(acquisition function)가 다음 평가점을 정하는 기준이 된다. 예를 들어 현재 최고 관측값을 \(f_{\min}\)이라 할 때, 개선 가능성을 보는 기준은 \[ I(x)=\max(0, f_{\min}-F(x)) \] 로 생각할 수 있다. 기대개선(Expected Improvement)은 이 개선량의 기댓값 \(\mathbb{E}[I(x)]\)을 크게 하는 점을 고른다.

또 다른 기준은 신뢰하한(LCB)처럼 평균과 불확실성을 직접 섞는 방식이다. \[ a(x)=\mu(x)-\kappa\sigma(x) \] 를 최소화하면 평균이 낮은 곳과 불확실성이 큰 곳이 모두 후보가 된다. \(\kappa\)가 크면 더 모험적이고, 작으면 현재 모델이 좋다고 말하는 곳에 집중한다.

제약, 잡음, 병렬 평가

실전 문제에서는 목적함수만 비싼 것이 아니다. 제약 만족 여부도 비싸게 평가해야 하거나, 평가 결과에 잡음이 섞이거나, 여러 실험을 병렬로 던질 수 있다. 제약이 있으면 "좋아 보이는 점"뿐 아니라 "가능할 것 같은 점"을 함께 고려해야 한다. 확률적으로는 \(P(x \in \mathcal{X})\) 같은 가능성 점수를 획득함수에 곱하는 방식도 쓴다.

잡음이 큰 경우에는 한 점을 여러 번 평가할지, 새 점을 더 볼지 결정해야 한다. 병렬 평가에서는 서로 비슷한 후보를 여러 개 보내면 평가 예산을 낭비할 수 있으므로, 후보들 사이의 다양성도 고려한다. 대리모델 최적화는 알고리즘 하나라기보다, 예산과 실험 장비와 위험도를 함께 조율하는 운영 방식에 가깝다.

멈출 때를 아는 것도 최적화다

종료 기준은 생각보다 중요하다. 평가 예산이 다 되었을 때 멈추는 방식이 가장 흔하지만, 최근 개선량이 작아졌거나 획득함수의 최대값이 충분히 낮아졌을 때 멈출 수도 있다. 다만 "더 이상 개선되지 않는다"는 말은 실제 함수가 아니라 현재 모델 기준일 수 있다는 점을 잊지 말아야 한다.

함정은 대리모델 최적화가 자동으로 전역 최적해를 보장한다고 믿는 것이다. 초기 샘플이 나쁘거나, 커널이 부적절하거나, 차원이 너무 높으면 탐색이 편향될 수 있다. 좋은 실무자는 최종 후보를 실제 함수로 재평가하고, 주변 민감도를 확인하며, 모델이 추천한 이유를 점검한다.

좋은 해의 기준을 다시 정하기

확정적 문제에서는 \(x^\star=\arg\min_x f(x)\)라고 말하면 이야기가 꽤 깔끔하다. 하지만 불확실한 변수 \(\xi\)가 들어오면 목적은 \(f(x,\xi)\)가 되고, “가장 좋은 \(x\)”의 뜻부터 다시 정해야 한다. 평균 성능을 원하면 \(\min_x \mathbb{E}[f(x,\xi)]\), 최악의 경우를 견디고 싶으면 \(\min_x \max_{\xi \in \mathcal{U}} f(x,\xi)\) 같은 형태가 된다.

여기서 중요한 감각은 “불확실성을 제거한다”가 아니라 “불확실성에 대한 태도를 모델에 적는다”이다. 평균 최적화는 평소에는 멋져 보이지만 꼬리 위험에 둔감할 수 있고, 강건 최적화는 튼튼하지만 너무 겁이 많아질 수 있다. 좋은 모델러는 계산 전에 먼저 묻는다. 실패하면 작은 손해인가, 아니면 한 번의 실패가 회의실 온도를 5도쯤 낮추는가?

강건, 확률제약, 시나리오

대표적인 세 접근은 강건 최적화, 확률제약 최적화, 시나리오 기반 최적화다. 강건 최적화는 불확실성 집합 \(\mathcal{U}\) 안의 모든 경우를 버티게 만든다. 확률제약은 \(\mathbb{P}(g(x,\xi)\le 0)\ge 1-\alpha\)처럼 “대부분의 경우 안전”을 요구한다. 시나리오 방식은 가능한 미래를 표본 \(\xi_1,\ldots,\xi_N\)으로 뽑아 평균 또는 분위수 형태로 다룬다.

실전 함정은 \(\mathcal{U}\)를 멋있게 그려 놓고 실제 데이터와 전혀 맞지 않는 경우다. 너무 작은 집합은 가짜 안심을 주고, 너무 큰 집합은 모든 선택지를 겁쟁이 모드로 만든다. 확률제약도 마찬가지로 \(\alpha=0.01\)이라는 숫자가 멋져 보여도, 표본이 적거나 꼬리가 두꺼운 분포라면 그 1%는 종종 현실에서 1%보다 훨씬 자주 나타난다.

샘플 평균과 리스크 측도

계산에서는 기대값을 표본 평균으로 바꾸는 일이 많다. 예를 들어 \[ \min_x \frac{1}{N}\sum_{i=1}^{N} f(x,\xi_i) \] 는 단순하고 강력하다. 여기에 분산, 분위수, CVaR 같은 리스크 측도를 붙이면 평균 성능과 나쁜 날의 손해를 함께 조절할 수 있다. CVaR는 대략 “나쁜 꼬리 구간에 들어갔을 때 평균적으로 얼마나 아픈가”를 보는 도구라고 생각하면 좋다.

표본 기반 방법의 예의는 검증 표본을 따로 두는 것이다. 최적화는 표본의 약점을 찾아내는 데 묘하게 재능이 있어서, 훈련 시나리오에서는 훌륭한데 새 시나리오에서는 민망한 해를 만들 수 있다. 불확실성 아래 최적화에서는 목적값 하나보다 신뢰구간, 민감도, 실패 사례 목록이 더 솔직한 보고서가 된다.

입력 분포가 모델을 지나갈 때

모델 \(y=h(x,\xi)\)가 있을 때 불확실성 전파는 \(\xi\)의 분포가 \(y\)의 분포로 어떻게 바뀌는지 추적한다. 입력 평균과 분산만 보는 일은 출발점으로는 좋지만, 비선형 모델에서는 평균이 휘고 분산이 찢어진다. 그래서 “입력 오차가 작으니 출력 오차도 작겠지”라는 말은 증명이 아니라 소망에 가깝다.

가장 기본적인 근사는 선형화다. 기준점 주변에서 \(h\)를 미분해 \(J=\partial h/\partial \xi\)라고 하면, 입력 공분산 \(\Sigma_\xi\)는 대략 \[ \Sigma_y \approx J\Sigma_\xi J^\mathsf{T} \] 로 전파된다. 빠르고 설명하기 좋지만, 곡률이 크거나 임계값 근처에서는 얌전한 척하다가 꽤 크게 빗나갈 수 있다.

몬테카를로와 대리모델

몬테카를로 방법은 입력을 많이 뽑아 모델을 여러 번 돌리고 출력의 분포를 직접 보는 방식이다. 구현은 단순하지만 모델 평가가 비싸면 계산 예산을 금방 태운다. 이때 대리모델을 세워 빠르게 평가하거나, 라틴 하이퍼큐브 같은 샘플링으로 공간을 고르게 훑거나, 중요한 꼬리 영역에 표본을 더 배치하는 전략을 쓴다.

주의할 점은 무작정 표본 수만 늘리는 것이 능사가 아니라는 것이다. 입력 변수 사이 상관관계를 무시하면 그럴듯하지만 틀린 세계를 만들고, 희귀 사건을 놓치면 평균은 안정적인데 위험 평가는 공허해진다. 특히 제약조건 근처에서 출력이 급격히 바뀌는 모델은 표본 설계가 거의 반쯤 최적화 문제다.

민감도와 의사결정

전파의 끝은 그림 예쁘게 그리기가 아니라 의사결정이다. 어떤 입력이 출력 불확실성을 가장 키우는지 알면 센서를 더 좋은 것으로 바꾸거나, 실험을 추가하거나, 설계 여유를 어디에 둘지 정할 수 있다. 분산 기반 민감도는 전체 변동을 변수별 기여로 나누고, 국소 민감도는 특정 운전점에서 어느 방향이 위험한지 알려준다.

좋은 보고는 “출력 평균은 이렇다”에서 멈추지 않는다. 신뢰구간, 분위수, 최악 사례, 입력별 기여도를 함께 보여준다. 최적화 루프와 연결할 때는 매 반복마다 모든 불확실성을 완벽히 전파하려 들기보다, 후보가 좁혀질수록 더 정밀한 전파를 쓰는 식의 단계적 전략이 계산적으로 현명하다.

조합 폭발과 모델링

이산 최적화에서는 변수가 정수, 불리언, 순열, 그래프 구조처럼 끊어진 값을 가진다. \(n\)개의 불리언 변수만 있어도 가능한 해는 \(2^n\)개다. 그래서 문제를 “그냥 다 해보자”로 시작하면 작은 예제에서는 용감해 보이지만, 실제 크기에서는 바로 표정이 굳는다.

모델링의 핵심은 선택을 변수로, 논리를 제약으로 바꾸는 것이다. 예를 들어 \(z_i\in\{0,1\}\)는 물건 \(i\)를 고르는지 나타내고, 용량 제약은 \(\sum_i w_i z_i \le C\)처럼 쓴다. 좋은 정수계획 모델은 의미가 선명하고, 불필요하게 약한 제약을 피하며, solver가 가지치기할 단서를 충분히 준다.

완화, 분기, 경계

혼합정수계획에서는 정수 제약을 잠시 풀어 연속 문제로 완화한다. 완화해 얻은 값은 원래 문제의 낙관적 기준이 되고, 이를 이용해 더 볼 필요 없는 가지를 잘라낸다. 분기한정법의 정신은 단순하다. 가능한 해의 나무를 탐색하되, 이미 희망이 없는 가지는 예의 바르게 닫는다.

여기서 완화가 강할수록 탐색이 줄어든다. 같은 문제라도 변수 정의와 제약식 표현에 따라 solver가 보는 풍경은 완전히 달라진다. 큰 \(M\) 상수로 논리를 표현할 때는 특히 조심해야 한다. \(M\)이 너무 크면 완화가 흐물흐물해지고, 너무 작으면 좋은 해를 몰래 금지한다.

휴리스틱과 지역 탐색

정확한 최적해가 너무 비싸면 휴리스틱이 빛난다. 탐욕법, 지역 탐색, 금기 탐색, 시뮬레이티드 어닐링, 유전 알고리즘 같은 방법은 보장보다 실용 속도를 노린다. 예를 들어 순열 문제에서는 두 위치를 바꾸거나 구간을 뒤집는 이웃을 만들고, 더 좋은 해를 찾아 이동한다.

휴리스틱의 함정은 “잘 나온 한 번”을 실력으로 착각하는 것이다. 여러 초기값, 여러 난수 시드, 기준 알고리즘과의 비교가 필요하다. 또한 실무에서는 최적성 증명보다 제약 위반 0건이 먼저다. 멋진 목적값을 내는 불가능해는 계산 세계의 화려한 영수증일 뿐이다.

식과 구조를 해 공간으로 보기

연속 변수 \(x\)를 고르는 대신, 표현 최적화에서는 수식 트리, 규칙 집합, 계산 그래프, 작은 프로그램 같은 구조를 고른다. 예를 들어 데이터 \((u_i,y_i)\)에 맞는 식 \(e(u)\)를 찾고 싶다면 \[ \min_e \sum_i \ell(e(u_i),y_i) + \lambda\,\mathrm{complexity}(e) \] 처럼 정확도와 복잡도를 함께 본다. 여기서 \(\lambda\)는 “똑똑하지만 너무 수다스러운 식”을 말리는 역할을 한다.

표현 공간은 대개 이산적이고 계층적이다. \(a+b\)와 \(b+a\)처럼 의미는 같은데 모양은 다른 식이 많고, 작은 문법 변화가 출력에서는 큰 차이를 만든다. 그래서 단순한 숫자 최적화보다 중복, 동치성, 해석 가능성, 문법 제약을 함께 관리해야 한다.

재작성, 단순화, 탐색

표현을 개선하는 가장 친숙한 방법은 재작성이다. \((x+0)\)을 \(x\)로, \(x\cdot 1\)을 \(x\)로 바꾸는 단순화부터 공통 부분식 제거, 연산 순서 변경, 수치적으로 안정한 형태로의 변환까지 모두 표현 최적화의 일이다. 컴파일러가 하는 최적화와 수학적 모델링이 여기서 악수한다.

새 표현을 찾는 탐색에는 돌연변이, 교차, 문법 기반 생성, 빔 탐색, 동적계획법 등이 쓰인다. 다만 목적함수에 훈련 오차만 넣으면 식이 금세 과장된 암기장을 만든다. 검증 데이터, 복잡도 벌점, 차원 일관성, 금지 연산 목록 같은 장치가 있어야 표현이 실제 문제를 설명한다.

수치 안정성과 자동미분

표현은 예뻐 보이는 것과 잘 계산되는 것이 다르다. \(\log(1+x)\)를 작은 \(x\)에서 그대로 계산할지, 안정적인 특수 함수를 쓸지에 따라 오차가 달라진다. \(a^2-b^2\)와 \((a-b)(a+b)\)는 수학적으로 같아도 부동소수점에서는 서로 다른 성격을 가진다.

자동미분을 쓰는 최적화에서는 계산 그래프의 표현이 곧 미분 품질과 속도에 영향을 준다. 분기, 클리핑, 비매끄러운 연산은 그래디언트를 이상하게 만들 수 있고, 너무 깊은 표현은 계산 비용과 메모리를 키운다. 좋은 표현은 사람에게 읽히고, 기계에게 미분되며, 데이터 밖에서도 덜 창피해야 한다.

결합된 시스템의 변수

다학제 최적화에서는 공통 설계변수 \(x\), 분야별 상태 \(y_k\), 결합 변수 \(c_k\)가 얽힌다. 한 분야의 출력이 다른 분야의 입력이 되므로 단순히 목적함수 하나를 평가하는 데도 여러 해석기가 서로 값을 주고받아야 한다. 전체 문제는 흔히 \[ \min_x F(x,y_1,\ldots,y_m) \quad \text{s.t.}\quad R_k(x,y_k,c_k)=0,\; g(x,y)\le 0 \] 같은 모양을 가진다.

여기서 어려움은 수학뿐 아니라 조직에도 있다. 각 분야 팀은 자기 모델의 언어와 정확도 기준을 갖고 있다. 최적화 담당자는 모든 것을 하나의 거대한 방정식으로 뭉개기보다, 어떤 정보를 언제 교환하고 어떤 오차를 허용할지 설계해야 한다.

통합형과 분해형 전략

모든 분야를 한 루프 안에서 완전히 수렴시킨 뒤 설계를 바꾸는 방식은 이해하기 쉽고 안정적이지만 비쌀 수 있다. 반대로 분야별 하위문제를 나누고 조정 변수를 통해 합의를 맞추는 방식은 병렬화와 조직 운영에 유리하지만, 조정이 서툴면 각 팀이 각자 최적인데 전체는 어색한 해가 된다.

분해형 접근에서는 일관성 제약이 핵심이다. 서로 다른 분야가 공유하는 변수의 사본 \(z_k\)가 있다면 \(z_k=z\) 같은 조건으로 합의를 강제한다. 이 제약을 너무 느슨하게 다루면 빠르게 돌아가는 듯 보이지만 실제 시스템은 맞물리지 않고, 너무 엄격하게 다루면 계산이 굳어 버린다.

대리모델, 민감도, 현실의 일정표

고충실도 해석이 비싼 분야에서는 대리모델이 필수에 가깝다. 초기에는 거친 모델로 넓게 훑고, 후보가 좁혀지면 정밀 모델로 확인한다. 이때 분야별 모델 오차가 서로 다른 방향으로 누적될 수 있으므로, 대리모델의 불확실성을 목적값 옆 작은 글씨로 숨기면 안 된다.

그래디언트와 민감도는 다학제 최적화의 공용어다. 어떤 설계변수가 전체 성능에 가장 큰 영향을 주는지 알면 회의가 짧아지고 실험이 선명해진다. 다만 최종 해는 수식의 승리만으로 결정되지 않는다. 제조 가능성, 인증, 유지보수, 책임 소재까지 들어오면 “최적”은 숫자가 아니라 합의 가능한 설계 제안이 된다.

부록 A. Julia로 실험하기

Julia는 수식에 가까운 문법과 빠른 수치 계산을 함께 노릴 수 있는 언어다. 작은 문제는 직접 구현해 보고, 큰 문제는 JuMP 같은 모델링 도구와 solver를 연결해 보는 식으로 연습하면 좋다. 같은 문제를 순수 구현, 패키지 사용, 시각화까지 세 방식으로 반복하면 알고리즘의 뼈대와 도구의 편의가 함께 보인다.

부록 B. 테스트 함수 사용법

Rosenbrock, Rastrigin, Ackley 같은 테스트 함수는 알고리즘의 성격을 살피는 연습장이다. 단, 테스트 함수에서 잘한다고 실제 문제에서 자동으로 잘하는 것은 아니다. 여러 차원, 여러 초기값, 잡음 유무, 제약 유무를 바꾸며 “이 방법은 어떤 풍경에서 강하고 약한가”를 관찰하자.

부록 C. 수학 개념 복습

반복해서 돌아볼 개념은 그래디언트, 헤시안, 볼록성, 라그랑주 승수, 확률분포, 선형대수의 고유값과 조건수다. 예를 들어 헤시안 \(H\)가 양의 정부호이면 국소적으로 그릇 모양의 곡률을 주고, 조건수가 크면 같은 알고리즘도 방향에 따라 성격이 달라진다. 공식을 외우기보다 작은 2차원 그림과 코드 실험으로 몸에 붙이는 편이 오래간다.