1) 엔지니어링 문제 해결과 2) 의사 결정을 하는데 많이 중요한 도구이다. ex) 컨테이너의 적재 무게 밸런싱, 식단 구성화(고객 만족도↑, 식단 금액↓) etc
다음의 기본요소를 갖는다 1) Objective function // 목적 함수 y = f(x) ex) 여행 거리를 나타내는 함수를 최소화하면서도, 여행에 필요한 시간은 최대한 짧게 만드는 함수 2) Decision variable or unknown // 결정 변수 혹은 미지수 ex) 도시 간의 이동 경로, 출발 시간 3) Constraints // 제약 조건 ex)최대 운행 시간, 예산
다음의 절차를 갖는다 1) 위의 기본 요소의 ① Objective function ② Decision variable or unknown ③ Constraints를 확인한다. (= 모델링) 2) 최적의 해를 갖는다.
수학적 모델
주어진 조건 하에서 최솟값을 갖는 과정
min f(x) subject to g_i(x) ≤ 0, i = 1, ..., m
근데 왜 주어진 조건 g_i(x)는 0보다 작아야하는 걸까?
좀 생각해볼 때, 다음과 같이 쭈욱 g1, g2...gi가 있다고 해보자. 그럴 때 우리가 원하는 목적함수는 최솟값을 찾는 것이다. 아래 그림에서 최솟값은 g1이나 g5의 값보다 g2, g3, g4와 같이 음수일 때 최솟값과 가까워짐으로 g_i(x)는 0보다 작다고 조건을 두는 것이다. 즉, 목적 함수를 최소화하면서도 유효한 해의 공간을 정의하기 위함이다.
그렇다면 내가 생각하는 최적화의 정의가 "최대화"일 수 있잖아?
맞다! 그렇다면, 우리는 아래와 수식과 같이 생각해줄 수 있다! 목적함수를 마이너스(-)로 하여 두고, 제약조건을 마이너스하여 부등호를 바꾸는 식으로 어떤가? 즉, 우리는 최소화하는 것을 표준화로 생각해주면 된다!
그럼 이제 최적화 문제를 어떻게 수학적으로 표현하는지 알아보았으니 이제 최적화 문제를 본격적으로 풀어보자!
Solving Optimization Problems
1.Analytic Approach (해석적 접근)
1차원이고, 제약조건이 따로 없을 때, f'(x) = 0 이 되는 곳이 최소가 되는 것을 알 수 있다.
n차원일 때,
참고로, 역삼각형처럼 쓰는 이 녀석은 나블라(Nabla)또는델(Del)이라고 한다. 변수가 여러개인함수에서 변화량을 표현할 때 쓴다고 한다. 우리가 고등학교 미적 시간에는 변수가 하나인 함수에서 변화량은 삼각형△(대문자),δ(소문자)로 표기하고 델타(Delta)라고 부르듯 말이다.
자, 그러면 n차원일 때도 기하학적으로 살펴보자. ex)
함수의 도함수(미분)가 0이 되는 지점에서 최솟값을 찾는 것이 해석적으로 어려운 경우가 있다. 이럴 때는 경사 하강법(Gradient Descent)과 같은 반복적인 최적화 방법을 사용할 수 있다.
2. Iterative Approach
함수의 도함수(미분)가 0이 되는 지점에서 최솟값을 찾는 것이 해석적으로 어려운 경우가 있다. 이럴 때는 경사 하강법(Gradient Descent)과 같은 반복적인 접근 방법을 사용할 수 있다.
특정 포인트 X에서 X'가 커질 수록 함수값이 커지는 중이라면 우리의 표준화 목적 함수 즉, 최솟값을 찾는 것을 실패하는 것이므로 X'을 작도록 옯겨야할 것이다. 즉, 해당 파라이터에서 학습률 * 기울기를 뺴면 최소값이 되는 장소를 찾을 수 있을 것이다. https://hackernoon.com/life-is-gradient-descent-880c60ac1be8
자, 같이 예제를 하나 풀어보도록 하죠!
그렇다면 이제 우리는 이 α에 대해 보다 살펴보자!
Choosing Step Size α
너무 작으면 섬세하게 움직여서 좋으나, 많이 반복하여 시간이 오래 걸림
너무 크면 지나치게 훅훅 넘어갈 거임(overshoot)
그러니까 너무 작아도 안 되고, 너무 커도 안 되니, 일단 좀 크게 잡아서 시간이 지날수록 미세 조정을 통해서 하는 것이 방법이 됨.
그럼 우리는 항상 이렇게 Gradien Decent 방법을 통해 최적화를 할 수 있을까?
Converge (수렴성)
일단 위 질문에 답부터 먼저 하자면, No이다 왜냐하면 ...
왼쪽과 같이 convex(볼록)한 경우, 지역적인 최솟값이 그래프 전체의 최솟값을 갖는 것을 알 수 있다. 그러나 Non-convex한 경우, 존재하지 않을 수 있기 때문이다.
그러면 오른쪽 같은 경우 우리는 어떻게 최적화를 할 수 있을까?
위의 그림에서 보듯, 어디서 시작하느냐에 따라서 다르므로 시작을 잘 해야할 것이며, 그만큼 많이 시도함으로써 최적화하는 값을 찾는 것도 방법이 될 수 있다!!
마지막으로 우리는 실용적으로 어떻게 최적화 문제를 풀까?
Practically Solving Optimization Problems
많은 종류의 최적화 문제에 대해 이미 수치 알고리즘을 개발하는 데 필요한 "어려운 작업"을 사람들이 이미 수행했다
