1. Optimization
Optimization(최적화)는 하나 이상의 변수에 의존하는 함수의 최대치와 최소치를 찾는 것이다.
Machine learning 역시 최적화 기술 중 하나다. f(x) = a1x15 + a2x24 + ... + b에서 AI는 학습으로 a1, a2, .. , b를 찾는다. 즉, Training(학습)은 함수의 수많은 파라미터의 값을 결정하는 과정으로, 학습 데이터를 사용하여 최적의 θ = { a1, a2, .. , b }를 구해야 한다. 학습의 목표는 Loss(오류)를 최소화하는 방향으로 이루어진다.
1차우너 문제에는 단일 종속 변수에 의존하는 함수가 포함된다. f(x)와 같은 예시가 있다. Multidimensional Optimization의 경우, 2개 이상의 종속 변수에 의존하는 함수를 포함하며 f(x, y)와 같은 예시가 있다.
global optimum은 가장 좋은 해결책을 나타내는 반면, local optimum은 가까운 값들보다 더 나은 해결책을 나타낸다. local optima를 포함하는 경우를 multimodal이라고 한다. 일반적으로, global optimum을 사용하여 최적의 해를 찾는다.
(1) Golden-Section Search
Golden-Section Search란 최솟값이 하나인 구간 [xl, xu]에서 최솟값을 찾기 위한 검색 알고리즘이다. [1] 황금비 Φ = 1.6180... 을 사용하여 두 내부 지점 x1과 x2의 위치를 파악한다. 참고로 xl로부터 x1을, xu로부터 x2를 구한다. [2] f(x1) < f(x2)일 경우, new xl = x2가 되고 new x2 = x1이 된다. [3] else if f(x1) > f(x2)일 경우, new xu = x1이 되고 new x1 = x2가 된다.
-> 어느 경우든 x2는 x1의 왼쪽에 위치한다.
-> 어느 경우든 새로운 내부 점은 1개만 필요하고, 기능 역시 1번만 더 평가된다.
Golden ratio(황금비)란 '(a+b)가 a에 대한 비율은 a가 b에 대한 비율과 같다'는 것이다.
Error 공식은 아래와 같다.
예제를 풀어보겠다. z = z0 + m/c(v0 + m*g/c)*(1 - exp(-c/m*t)) - m*g/c*t인 함수에서 xl = 0, xu = 8로 두고 최적화를 하여라.
function [x, fx, ea, iter] = goldmin(f, xl, xu, es, maxit, varargin)
if nargin<3, error('at least 3 input arguments required'), end
if nargin<4|isempty(es), es=0.0001; end
if nargin<5|isempty(maxit), maxit=50; end
#% 황금비 phi, 초기 구간의 길이 d를 계산.
phi = (1-sqrt(5))/2; d = (phi-1)*(xu-xl);
iter = 0; x1 = xl + d; x2 = xu - d;
#% 초기 구간을 분할한 두 점 'x1'과 'x2'에서 함수 값을 계산.
f1 = f(x1, varargin{:}); f2 = f(x2, varargin{:});
while(1)
xint = xu - xl;
if f1 < f2
xopt = x1; xl = x2; x2 = x1; f2 = f1;
x1 = xl + (phi-1)*(xu-xl); f1 = f(x1, varargin{:});
else
xopt = x2; xu = x1; x1 = x2; f1 = f2;
x2 = xu - (phi-1)*(xu-xl); f2 = f(x2, varargin{:});
end
iter = iter + 1;
if xopt ~= 0, ea = (2-phi)*abs(xint/xopt)*100; end
if ea <= es | iter >= maxit, break, end
end
x = xopt; fx = f(xopt, varargin{:});
(2) Parabolic Interpolation
Parabolic Interpolation은 최적 위치를 추정하기 위해 3개 점의 포물선 보간법을 사용한다. 아래는 3개 점의 보간으로 정의된 포물선의 최대/ 최소 위치를 나타낸 식이다. 이렇게 해서 얻어진 새로운 점 x4와 이를 둘러싼 2개의 점(x1과 x2 or x2와 x3)은 알고리즘의 다음 반복에 사용된다.
예제를 풀어보겠다. 아래 공식을 x1 = 0, x2 = 1, x3 = 4로 두고 풀어보자.
(3) Newton-Rapson Method
Newton-Rapson Method도 최적화 방법 중 하나로 사용될 수 있다. 최적화란 도함수의 root를 찾는 문제와 동일하기 때문이다. 따라서 기존의 Newton-Rapson 방법에서 함수식들을 한 번씩만 더 미분하면, 최적화에 사용할 수 있다.
2. MATLAB's Function
(1) fminbnd Function
fminbnd 함수는 앞서 말한 최적화 방식 중 (1), (2)를 결합한 기능을 가진다. fzero와 유사하게 optimset를 사용하여 4번째 인수를 통과할 수 있다.
#% xmin : x의 최솟값
[xmin, fval] = fminbnd(function, x1, x2)
#% 예제
g = 9.81; v0 = 55; m = 80; c = 15; z0 = 100;
z = @(t) -(z0+m/c*(v0+m*g/c)*(1-exp(-c/m*t))-m*g/c*t);
[x, f] = fminbnd(z, 0, 8)
(2) fminsearch Function
fminsearch 기능은 다차원 함수의 최소값을 결정할 수 있다.