최적화란 무엇인가?

저도 솔직히 처음에는 ‘최적화’가 정확히 무엇인지 몰랐습니다.

데이터 사이언티스트로 회사에 들어오기 전까지 제가 생각했던 데이터 사이언스의 세계는 대체로 머신러닝과 딥러닝을 중심으로 돌아갔습니다. 데이터를 모으고, 모델을 학습시키고, 미래의 어떤 값을 예측하는 것 말입니다.

예를 들면 이런 질문들입니다.

내일 원자재 가격은 얼마일까?

또는,

다음 회의에서 중앙은행이 실제로 금리를 인하할 확률은 얼마나 될까?

첫 번째 문제에서는 과거 가격, 수급, 재고, 거시경제 지표 같은 데이터를 이용해 미래 가격을 예측할 수 있습니다. 두 번째 문제에서는 물가, 고용, 시장금리, 중앙은행의 발언 같은 정보를 이용해 금리 인하 가능성을 추정할 수 있습니다. 둘 다 상당히 전형적인 데이터 사이언스 문제처럼 보입니다.

그런데 회사에 들어가 실제 비즈니스 문제를 접하기 시작하니 조금 다른 종류의 질문이 보이기 시작했습니다. 예측이 끝난 다음의 질문이었습니다.

그래서 원자재를 지금 얼마만큼 사야 하지?

가격이 오를 가능성이 높다면 구매 시점을 얼마나 앞당겨야 하지?

금리 인하 확률을 고려하면 포트폴리오의 듀레이션을 얼마나 가져가야 하지?

제한된 예산과 생산능력 안에서 어느 공장에서 얼마를 생산해야 하지?

이 질문들은 “무슨 일이 일어날 것인가?”가 아니라 “그래서 우리는 무엇을 해야 하는가?”를 묻습니다.

앞의 문제가 주로 예측의 문제라면, 뒤의 문제는 의사결정의 문제에 가깝습니다. 그리고 이런 의사결정을 수학적으로 다루는 대표적인 방법론 중 하나가 바로 최적화였습니다.

물론 머신러닝과 최적화가 완전히 별개의 분야라는 뜻은 아닙니다. 머신러닝 모델을 학습하는 과정 자체도 흔히 어떤 손실함수를 최소화하는 최적화 문제입니다. 다만 당시의 저에게 중요한 차이는 질문의 방향이었습니다.

머신러닝에서는 주로 “무엇이 일어날까?”를 고민했다면, 제가 업무에서 만난 최적화는 “여러 현실적인 조건이 있을 때 무엇을 선택해야 가장 좋을까?”를 고민했습니다.

처음 만난 최적화는 별로 친절하지 않았다

처음에는 상당히 생소했습니다. 회사 동료들에게도 물어봤습니다.

“최적화가 정확히 뭐예요?”

인터넷에도 검색해봤습니다. 그러다 최적화 분야에서 교과서처럼 언급되는 Stephen Boyd와 Lieven Vandenberghe의 Convex Optimization이라는 책도 찾아봤습니다.

그리고 책을 펼쳐봤습니다.

볼록집합. 볼록함수. 라그랑지안. 쌍대성.

아주 친절하게도 처음 보는 단어들이 계속 나왔습니다. 저는 그냥 최적화가 뭔지 알고 싶었던 건데, 어느 순간 수학책 한가운데 들어와 있었습니다.

‘내가 알고 싶었던 게 이거였나?’ 싶었습니다.

그런데 실제 업무에서 이런저런 문제를 접하고 수학적인 표현에 조금씩 익숙해지면서 한 가지를 깨달았습니다. 사실 최적화라는 개념 자체는 전혀 낯선 것이 아니었습니다.

우리는 이미 일상에서 계속 최적화를 하고 있었습니다. 다만 거기에 목적함수, 제약조건, 의사결정변수 같은 이름을 붙이지 않았을 뿐입니다.

친구들과 저녁 약속을 잡아보자

예를 들어 친구들과 금요일 저녁에 만나기로 했다고 해봅시다. 아직 식당은 정하지 않았습니다. 그렇다고 아무 식당이나 갈 수 있는 것은 아닙니다.

우선 날짜와 시간이 정해져 있습니다. 금요일 저녁 7시.

금요일에 쉬는 식당은 아무리 맛있어도 갈 수 없습니다. 영업하더라도 오후 6시에 문을 닫는 식당 역시 후보에서 탈락합니다. 벌써 첫 번째 제약조건이 생겼습니다.

가격도 중요하다

다음은 가격입니다. 친구들끼리 가볍게 저녁을 먹는 자리라고 해봅시다. 제 기준으로는 이런 자리에서 인당 3만 원을 크게 넘어가기 시작하면 조금 부담스럽습니다.

소주나 맥주에 안주를 간단히 먹기로 했는데 누군가 갑자기 인당 15만 원짜리 스테이크 레스토랑을 예약해왔다고 생각해봅시다. 물론 스테이크는 맛있을 겁니다. 식당도 훌륭할 수 있습니다.

하지만 간단히 밥 먹자고 해놓고 그런 곳을 예약해오면 아마 친구들에게 미친놈 소리를 들을 가능성이 높습니다.

즉 우리에게는 암묵적으로 이런 조건이 있습니다.

1인당 예상 비용 ≤ 30,000원

이게 두 번째 제약조건입니다.

그리고 무엇보다 위치가 중요하다

친구 네 명이 각각 잠실, 신촌, 용산, 강남에 산다고 해봅시다. 잠실에 사는 친구가 말합니다.

“잠실에 진짜 맛있는 집 있는데 여기서 보자.”

실제로 맛집일 수 있습니다. 문제는 잠실 친구에게만 맛집이라는 것입니다. 본인은 집에서 10분이면 가는데 나머지 세 명은 한 시간을 이동해야 한다면 분위기가 조금 이상해집니다.

그렇다고 제가 사는 곳에서 걸어서 5분 거리에 있는 식당을 골라놓고 “여기가 서울의 중심이야”라고 우긴다고 해서 친구들이 순순히 받아들이는 것도 아닙니다.

친구들 사이에서는 묘한 공정성도 중요합니다. 친구만 가까우면 배가 아프고, 나만 너무 멀면 배알이 꼴립니다. 그래서 우리는 자연스럽게 모두에게 지나치게 불리하지 않은 지역을 찾습니다.

이것도 결국 하나의 최적화 문제입니다. 예를 들어 네 사람의 이동시간을 모두 더한 뒤 다음과 같은 기준을 세울 수 있습니다.

네 사람의 총 이동시간을 가장 작게 만들자.

공정성을 더 중요하게 생각한다면 다른 기준도 가능합니다.

가장 멀리 이동해야 하는 사람의 이동시간을 최소화하자.

두 기준은 비슷해 보이지만 결과가 반드시 같지는 않습니다. 그리고 여기서 최적화의 중요한 질문이 등장합니다.

무엇을 ‘좋다’고 정의할 것인가?

수학적으로 우리가 최대화하거나 최소화하고 싶은 값을 목적함수라고 부릅니다.

의사결정변수, 목적함수, 제약조건

지금까지 친구들과 저녁 약속을 잡는 문제에는 여러 조건이 생겼습니다. 식당은:

• 금요일 저녁 7시에 영업하고 있어야 하고,
• 인당 예상 가격이 대략 3만 원 이하여야 하며,
• 친구들이 이동하기 지나치게 불편해서도 안 됩니다.

이것들이 제약조건입니다.

이 조건을 만족하는 여러 식당 가운데 우리는 어떤 기준으로 가장 좋은 식당을 고르고 싶습니다. “총 이동시간을 최소화한다”거나 “맛, 가격, 이동시간을 종합한 만족도를 최대화한다” 같은 기준이 목적함수가 됩니다.

그리고 우리가 실제로 선택해야 하는 것, 즉 “A식당을 갈 것인가, B식당을 갈 것인가?”가 의사결정변수입니다.

정리하면 최적화 문제는 의외로 단순한 세 가지 질문에서 시작합니다.

1. 무엇을 결정할 것인가?
2. 무엇을 가장 좋게 만들 것인가?
3. 어떤 조건은 반드시 지켜야 하는가?

조금 더 정확하게 표현하면 최적화는 주어진 제약조건을 만족하는 선택들 가운데 목적함수를 최대화하거나 최소화하는 해를 찾는 일입니다.

그런데 그냥 모두의 중간에서 만나면 안 될까?

여기까지 들으면 이런 생각이 들 수 있습니다.

“그냥 네 사람이 사는 곳의 정확한 가운데에서 만나면 되는 거 아니야?”

물론 가능합니다. 네 사람의 위치를 좌표로 바꾸고 기하학적인 중간점을 계산할 수도 있습니다.

그런데 아주 사소한 문제가 하나 있습니다. 거기에 식당이 있다는 보장이 없습니다.

한강 한가운데일 수도 있고, 아파트 단지 한복판일 수도 있습니다. 중간지점은 완벽한데 주변에 먹을 곳이라고는 편의점 하나뿐일 수도 있습니다. 우리가 원하는 것은 중간지점을 찾는 것이 아니라 밥을 먹을 식당을 찾는 것입니다.

그래서 실제로는 먼저 선택 가능한 후보를 만듭니다.

• 홍대 A식당
• 용산 B식당
• 강남 C식당
• 을지로 D식당

그리고 이 후보들 가운데 가격, 거리, 맛, 영업시간을 비교합니다.

현실의 최적화가 재미있는 이유가 바로 여기에 있습니다. 현실에서는 모든 선택이 가능한 것이 아닙니다. 선택할 수 있는 후보가 있고, 현실적인 제약이 있고, 그 안에서 가장 나은 선택을 찾아야 합니다.

이제 맛까지 넣어보자

지금까지는 주로 거리와 가격을 생각했습니다. 그런데 식당을 고르는 이유를 생각해보면 중요한 변수가 하나 빠졌습니다. 바로 맛입니다.

용산의 B식당이 네 사람의 총 이동시간을 가장 작게 만든다고 해봅시다. 교통만 놓고 보면 완벽합니다. 그런데 평점이 2.1점입니다.

반대로 을지로의 D식당은 모두가 20분 정도 더 이동해야 하지만 정말 맛있는 식당입니다. 그러면 인간의 머릿속에서는 자동으로 계산이 시작됩니다.

“20분 더 가더라도 여기가 낫지 않을까?”

이 순간부터 문제가 훨씬 재미있어집니다. 우리는 동시에:

• 이동시간은 줄이고 싶고,
• 가격도 낮추고 싶고,
• 맛은 좋았으면 합니다.

즉 거리 ↓, 가격 ↓, 맛 ↑를 동시에 원합니다.

하지만 현실에서 이 조건을 모두 완벽하게 만족하는 식당은 거의 없습니다. 맛있는 곳은 비쌀 수 있고, 저렴하고 맛있는 곳은 멀 수 있으며, 가까운 곳은 맛이 없을 수도 있습니다.

결국 우리는 절충해야 합니다.

10분을 더 이동하는 대신 더 맛있는 식당을 선택할 것인가? 가격이 만 원 비싸지는 대신 훨씬 좋은 식당을 선택할 것인가? 친구 한 명이 조금 더 멀리 이동하는 대신 전체 만족도를 높일 것인가?

최적화는 이런 절충을 감으로만 처리하지 않고, 무엇을 얼마나 중요하게 생각하는지 명시적으로 정의하고 계산할 수 있게 만드는 방법이기도 합니다.

그렇다면 선형계획법은 무엇인가?

최적화를 공부하기 시작하면 가장 먼저 자주 만나는 이름이 선형계획법(Linear Programming)입니다. 여기서 programming은 Python 코드를 짠다는 뜻이라기보다, 주어진 자원을 어떻게 배분할지 계획한다는 오래된 표현에 가깝습니다.

그리고 linear는 목적함수와 제약조건이 의사결정변수의 선형식으로 표현된다는 뜻입니다. 말이 갑자기 딱딱해졌지만, 저녁 식당 후보 세 곳의 종합 만족도를 각각 $s_A$, $s_B$, $s_C$라고 하면 이런 형태입니다.

$$\text{maximize}\quad s_Ax_A + s_Bx_B + s_Cx_C$$

가격이 각각 $p_A$, $p_B$, $p_C$이고 예산이 3만 원이라면 다음과 같은 제약도 둘 수 있습니다.

$$p_Ax_A + p_Bx_B + p_Cx_C \le 30{,}000$$

각 변수에 어떤 숫자를 곱한 뒤 더할 뿐, $x_A^2$이나 $x_Ax_B$ 같은 항은 없습니다. 이런 목적함수와 제약조건으로 이루어진 문제가 선형계획 문제입니다.

원자재를 공급사별로 몇 톤씩 살지, 여러 제품을 각각 얼마나 생산할지처럼 양을 나누어 배분할 수 있는 문제에서는 이런 연속적인 변수가 자연스럽습니다. 예를 들어 공급사 A에서 3.5톤을 사고 B에서 6.5톤을 사는 것은 아무 문제가 없습니다.

하지만 오늘 저녁 식당은 조금 다릅니다. 단순한 선형계획 문제로 두고 $0 \le x_A,x_B,x_C \le 1$만 허용하면 계산 결과가 이렇게 나올 수도 있습니다.

A식당 30%, B식당 70%를 선택하세요.

수학적으로는 그럴듯하지만 우리는 저녁 한 끼를 먹으러 갑니다. A식당에서 애피타이저만 먹고 B식당으로 이동할 계획이 아니라면 꽤 곤란한 답입니다.

즉 목적함수와 제약식의 모양은 선형이더라도, 하나의 식당을 통째로 선택해야 한다는 현실을 표현하려면 변수에 0 또는 1이라는 정수 조건을 추가해야 합니다. 선형계획법과 정수계획법의 관계를 아주 단순하게 말하면 이렇습니다.

양을 나눌 수 있다면 선형계획법으로 충분할 수 있다. 선택을 쪼갤 수 없다면 정수 조건이 필요하다.

이제 그 정수 조건이 왜 필요한지, 예약 문제를 통해 조금 더 구체적으로 보겠습니다.

그리고 그 맛집이 예약이 안 된다면?

열심히 고민해서 드디어 최고의 식당을 찾았다고 해봅시다. 가격도 좋고, 위치도 좋고, 맛도 좋습니다. 그런데 전화를 해보니 자리가 없습니다.

이제 우리는 거리와 가격뿐 아니라 그 식당을 실제로 선택할 수 있는가라는 조건까지 생각해야 합니다. 여기에서 정수계획법(Integer Programming)의 아주 간단한 아이디어를 볼 수 있습니다.

각 식당을 선택하는지를 다음과 같이 표현해봅시다.

$$x_A = \begin{cases} 1 & \text{A식당을 선택하면} \\ 0 & \text{선택하지 않으면} \end{cases}$$

$x_B$와 $x_C$도 같은 방식으로 정의합니다. 우리에게 필요한 저녁 식당은 하나뿐이므로 다음 조건을 둘 수 있습니다.

$$x_A + x_B + x_C = 1$$

세 식당 가운데 정확히 하나를 선택한다는 뜻입니다. 그런데 A식당의 예약이 꽉 찼다면 A는 선택할 수 없습니다.

$$x_A = 0$$

A식당이 아무리 맛있고 위치가 좋아도 애초에 선택 가능한 후보가 아닌 것입니다.

일반적인 정수계획법은 의사결정변수의 일부 또는 전부가 정수값을 갖도록 제한합니다. 그중에서도 변수가 0과 1만 갖는 문제를 0-1 정수계획법(Binary Integer Programming)이라고 부릅니다.

이름만 들으면 상당히 어려운 수학처럼 느껴집니다. 하지만 가장 기본적인 아이디어는 단순합니다.

이 식당을 선택할 것인가? 예 = 1, 아니요 = 0.

기업에서 만나는 수많은 문제에도 이런 선택이 등장합니다.

• 이 공장을 가동할 것인가?
• 이 프로젝트에 투자할 것인가?
• 이 물류센터를 사용할 것인가?
• 이 차량을 이 경로에 배치할 것인가?

구조만 놓고 보면 친구들과 식당을 고르는 것과 크게 다르지 않습니다.

최적해는 반드시 하나일까?

최적화라는 말을 들으면 세상 어디엔가 단 하나의 완벽한 답이 존재한다고 생각하기 쉽습니다. 하지만 반드시 그렇지는 않습니다.

A식당과 B식당의 목적함수 값이 완전히 같다면 둘 모두 최적해가 될 수 있습니다. 여러 목표를 동시에 고려하면 문제는 더 복잡해집니다. 가장 저렴한 식당, 가장 맛있는 식당, 가장 가까운 식당이 모두 다를 수 있습니다.

이런 목표 사이의 관계를 다루는 방법에는 다목적 최적화(Multi-objective Optimization)와 파레토 최적성(Pareto optimality) 같은 개념도 있습니다. 이것은 조금 뒤의 이야기로 남겨두겠습니다.

첫 번째 단계에서는 이렇게 이해하면 충분합니다.

최적화는 하나의 마법 같은 정답을 찾는 기술이라기보다, 우리가 무엇을 중요하게 생각하는지 명확히 정의하고 그 기준에서 가장 좋은 선택을 찾는 방법이다.

예측과 최적화는 이어져 있다

처음 이야기했던 데이터 사이언스 문제로 돌아가 보겠습니다. 우리는 모델을 이용해 내일의 원자재 가격이나 다음 중앙은행 회의의 금리 인하 확률을 예측할 수 있습니다.

하지만 회사의 의사결정은 보통 여기서 끝나지 않습니다. 진짜 중요한 질문은 그 다음에 나옵니다.

그렇다면 원자재를 오늘 얼마만큼 구매할 것인가?

가격 상승 위험에 대비해 재고를 얼마나 확보할 것인가?

금리 인하 가능성을 반영해 포트폴리오의 금리 위험을 어떻게 가져갈 것인가?

예측이 세상에 대한 정보를 제공한다면, 최적화는 그 정보를 가지고 무엇을 할 것인지 결정하는 역할을 할 수 있습니다. 실제 문제에서는 다음 흐름으로 함께 사용되는 경우가 많습니다.

데이터
  ↓
예측 / 추정
  ↓
최적화
  ↓
의사결정

예측 결과가 최적화 모델의 입력이 되고, 최적화 모델이 실제 행동을 제안할 수 있습니다. 머신러닝과 최적화를 완전히 별개의 세계로 볼 필요가 없는 이유이기도 합니다.

결국 최적화는 선택의 수학이다

저는 처음 최적화를 접했을 때 이 개념을 이해하는 데 생각보다 시간이 걸렸습니다.

선형계획법. 정수계획법. 볼록 최적화. 라그랑지안. 쌍대성.

처음에는 이런 단어들부터 마주쳤기 때문에 최적화가 아주 특수하고 어려운 수학 분야라고 생각했습니다. 물론 깊이 들어가면 정말 어렵습니다. 하지만 최적화가 해결하려는 문제 자체는 놀라울 정도로 일상적입니다.

우리는 언제나 원하는 것이 있고, 현실에는 제한이 있습니다. 돈도, 시간도, 사람도 무한하지 않습니다. 공장의 생산능력, 저장공간, 차량과 예산도 제한되어 있습니다. 그런 상황에서도 우리는 계속 선택해야 합니다.

친구들과 어느 식당에서 만날지 결정하는 것, 기업이 어느 공급사에서 원자재를 얼마나 구매할지 결정하는 것, 어떤 공장에서 얼마를 생산할지 결정하는 것, 배송 차량이 어떤 순서로 고객을 방문할지 결정하는 것, 여러 자산에 돈을 얼마씩 투자할지 결정하는 것.

겉으로 보기에는 전혀 다른 문제지만 그 안의 구조는 의외로 비슷합니다.

결정해야 할 것이 있고, 지켜야 할 조건이 있고, 가장 좋게 만들고 싶은 것이 있습니다.

결국 최적화란 어렵게 표현하면 수학적 최적화이지만, 조금 더 직관적으로 저는 이렇게 생각합니다.

최적화는 제약이 있는 현실에서 가장 좋은 선택을 찾는 ‘선택의 수학’이다.

이 관점이 생기고 나서야 Convex Optimization에 등장하던 수식들도 조금씩 다른 의미로 보이기 시작했습니다. 수식이 먼저가 아니었습니다. 우리가 매일 하는 수많은 선택을 더 명확하게 정의하고 계산할 수 있도록 만든 언어가 최적화였던 것입니다.

다음 글: 모두에게 완벽한 식당이 없다면 — 파레토 최적화

이번 글에서는 최적화가 무엇인지 최대한 직관적으로 이야기했습니다. 그런데 저녁 식당 문제에는 아직 해결하지 않은 질문이 하나 남아 있습니다.

이동시간, 가격, 맛과 공정성을 동시에 가장 좋게 만들 수 없다면 무엇을 최적이라고 불러야 할까요?

다음 글에서는 이 질문을 통해 파레토 최적화(Pareto Optimization)를 살펴보겠습니다. 어떤 식당이 다른 식당보다 모든 기준에서 더 나은지, 어느 한 기준을 개선하려면 반드시 다른 기준을 포기해야 하는 지점은 어디인지 비교해보겠습니다.

• 파레토 지배(Pareto dominance)는 무엇인가?
• 파레토 최적해(Pareto optimal solution)는 왜 하나가 아닐 수 있는가?
• 파레토 프런티어(Pareto frontier)는 선택 가능한 상충 관계를 어떻게 보여주는가?
• 여러 후보 가운데 최종 선택은 결국 누구의 선호를 반영하는가?

아마 모두를 완벽하게 만족시키는 식당은 찾지 못할 것입니다. 하지만 적어도 누군가의 이동시간을 줄이려면 누구의 만족도를 포기해야 하는지는 훨씬 분명하게 말할 수 있을 것입니다.

다음 문제도 여전히 금요일 저녁 식사입니다. 다만 이번에는 “가장 좋은 식당은 어디인가?”보다 조금 더 현실적인 질문을 해보려 합니다.

서로 충돌하는 여러 기준 사이에서, 어떤 선택들을 합리적인 후보로 남겨야 하는가?