Day 7: Day 7 최적화 문제의 정의

목차로 돌아가기

본 글은 인공지능을 활용하지 않고 작성된 글임을 알립니다.

최적화 문제란?

최적화 문제optimization problem는 모든 가능한 해 중에서 최적해optimal solution를 찾는 문제를 말한다. 예를 들어, 내비게이션을 개발하는 IT 기업 연구원은 “가장 빠른 교통 경로”를 사용자에게 제공하고자 할 것이고, 산업공학을 전공한 사람은 “수익성을 최대화하는 사업 모델”을 찾고자 할 것이다. 이들이 풀고자 하는 문제는 모두 최적화 문제에 속한다. 한 지점 $A$로부터 다른 지점 $B$까지 (같은 장소를 두 번 통과하지 않고) 대중교통을 타고 이동하는 경로는 여러 가지 있을 것이고, 회사가 돈을 벌 수 있게 하는 사업 모델은 무수히 많을 것이다. 하지만, 가장 빠른 시간 안에 도착할 수 있는 경로, 그리고 가장 돈을 잘 버는 사업 모델을 찾기를 원하는 것이 사람 심리 아니던가. 이와 같은 맥락에서 최적화 문제는 컴퓨터과학자와 산업공학자(혹은 경영·경제학자)에게 매우 친숙한 대상이다.

보통 어떤 상태가 최적optimal 이라 말하기 위해서는 ‘잘했다’의 기준이 필요하다. 최적화 문제는 보통 얼마나 ‘잘했는지’를 측정해주는 함수로 표현하는데, 이것이 바로 목적 함수objective function이다. 최적화 문제에서는 목적 함수를 최대화 혹은 최소화하고자 한다. 예를 들어, 첫 수학 시험을 치루는 중학생인 철수가 시험 점수를 잘 받고자 하는 상황을 생각해보자. 이 상황을 최적화 문제로 바꾸어 생각해본다면, 시험 점수가 목적 함수가 되고, 최적화 문제는 “시험 점수를 최대화”하는 것이 된다. 시험을 가장 잘 치면 100점을 받을 수 있다. 즉, 시험 점수=목적 함수=100인 상태가 최적해가 된다.

그런데 앞서 목적 ‘함수’라고 했는데, 대체 무엇의 함수라는 걸까? 철수의 경우에는 철수의 “뇌상태”가 시험 점수를 결정할 것이다. 그렇다면 이 “뇌상태”의 수학적 표현은 무엇일까? 시냅스 연결 강도를 나타내는 변수들이 $k_1, k_2, k_3, k_4, k_5, \cdots$처럼 엄청 많이 있을 때, 우리는 이를 묶어 $\theta = [k_1, k_2, k_3,k_4,k_5,\cdots]^T$처럼 벡터로 나타낼 수 있다. 즉, 시냅스 연결이 총 $n$개가 있을 때, “$n$차원 벡터 $\theta$가 시험 점수 $s$를 결정한다”과 가정할 수 있다. 따라서 시험 점수 $s$는 $\theta$의 함수라고 할 수 있다. 또한, 철수가 똑똑하다면 학습을 통해 시냅스 연결 상태 $\theta$를 적절히 변경하여 시험 점수 $s(\theta)$를 최대화할 수 있다. 철수가 열심히 공부해서 시험을 가장 잘 쳤을 때는 100점을 받게 된다. 즉, $s(\theta_0)=100$을 만족하는 $\theta_0$가 존재한다면 $\theta_0$가 최적화 문제의 해가 될 것이다(이를 최적해라고 한다).

시험 점수가 실수로 표현된다고 가정하면, $s$는 $\mathbb{R}^n$에서 $\mathbb{R}$로 가는 함수라고 할 수 있다. 이처럼, 목적 함수는 대개 $\mathbb{R}^n$에서 $\mathbb{R}$로 가는 함수로 설정한다. 최적화 문제를 표현하는 방식에는 여러 가지가 있을 수 있지만, 아래는 그 중에서도 표준 형태의 (연속) 최적화 문제를 나타낸 것이다.

\[\begin{equation}\begin{aligned}& \underset{\theta \in \mathbb{R}^n}{\text{minimize}}& & f(\theta) \\& \text{subject to}& & g_i(\theta) \leq 0, \; i = 1, \ldots, m.\\&&& h_j(\theta) = 0, \; j = 1, \ldots, p.\end{aligned}\end{equation}\]

여기서 $f$는 목적 함수, $g_i,h_j\;(i=1,\dots,m,\;j=1,\dots,p)$는 제약 조건 함수로 모두 $\mathbb{R}^n$에서 $\mathbb{R}$로 가는 함수이다. 좀전에 시험 점수를 최대화maximize한다고 했던 것과 달리, 표준 형태의 최적화 문제에서는 목적 함수 $f$를 최소화minimize하는 형태로 표현하는 것이 전통이다. 사실 최대화와 최소화는 부호 하나 차이에 불과하기 때문에, 최대화 문제를 최소화 문제로 바꾸려면 목적 함수 앞에 마이너스를 붙여주면 그만이다. 철수의 시험 점수 $s(\theta)$를 최대화하는 대신, 부호를 바꾼 $-s(\theta)$를 $f(\theta)$로 두고 최소화하면 시험 점수 최대화의 문제도 위와 같은 표준형의 형태로 나타낼 수 있다.

$g_i,h_j$는 각각 부등호 제약 조건inequality constraint과 등호 제약 조건equality constraint이다. 예를 들어, 시냅스 연결 강도가 너무 커지다보면 신경이 손상될 수도 있으니 $g_i(\theta):= \theta_i -M\;(M>0)$으로 둘 수도 있고, 시험 공부를 하더라도 어려운 것을 공부하다가 성격이 이상해지면(?) 안 되기 때문에 이전 성격 검사 결과를 $T_i$로 기록한 다음 현재 상태에서의 성격 검사 결과를 $t_i(\theta)$로 얻어내어 $h_i(\theta):= t_i(\theta)-T_i$로 둘 수 있겠다. 예시를 이해하기 힘들다면, 최적화 문제의 표준형에서 $\theta_i-M$과 $t_i(\theta)-T_i$를 각각 $g_i(\theta)$와 $h_i(\theta)$의 자리에 대입하고 $M$과 $T_i$를 오른쪽으로 이항한 뒤 다시 생각해보자.

문제 1.1

(a) 한 광고 회사 “널리알리”에서 수익을 극대화하기 위한 최적 전략을 찾고자 한다. 널리알리가 자신의 서비스에서 자유롭게 조정할 수 있는 변수는 타게팅 대상의 성비 $g$, 전체 인구 대비 광고 타게팅 대상의 비율 $p$, 그리고 평균 광고 노출 시간 $t$(단위: 초)라고 한다. 회사의 순익 $C$가 위 세 변수에 대한 함수로 나타날 때, 이를 수식 $(1)$에서와 같이 최적화 문제로 표현하시오.

(b) 전체 인구 대비 광고 타게팅 대상의 비율 $p$와 평균 광고 노출 시간 $t$의 곱이 일정한 수준 $K$를 유지하게 하려고 한다. 새로운 최적화 문제를 다시 표현하시오.

문제 1.2

(a) 이산 최적화 문제의 표준형을 제안해보시오.

(b) 이산변수와 연속변수가 모두 포함된 경우에 대한 표준형을 제안해보시오.