Gradient-Free Optimization 이건 언제 사용하는 거냐? gradient가 계산하기 복잡하거나 계산을 할 수 없는 경우(function evaluation 값이 noisy하거나 아니면 목적 함수가 continuous 하지 않거나, 블랙박스로 싸여있는 legacy 코드라 고칠수가 없는데 noisy하거나 어떤 값이 나오는지 알 수 없을 경우거나, 어떤 경우에 아예 에러가 나오는데 최적화를 수행해야 할 때)에 gradient-free optimization이 유용하게 사용될 수 있다. multi-modal function …

Read More

Multiobjective Optimization 최적화 문제에서 목적함수 objective가 여러개 (주로 2, 3, 4정도) 있는 경우에 다목적 최적화 multiobjective optimization 를 수행한다. 근데 결국에는 하나를 선택해야 될 것인데 왜 다목적 최적화가 필요한 것인가? 그 이유는 objectives의 tradeoff를 quantify 할 수 있기 때문이다. - 보통 objectives 들에 어떤 커플링이 있는데 mutliobjective optimization을 통해서 design variable의 변화에 대한 objectives …

Read More

Sampling Methods sampling method 중에서도 optimization에서 주로 쓰이는 방법은 random sampling, Latin Hypercube Sampling(LHS), Low-discrepancy sequences 중에 하나인 Halton sequence이다. ramdom sampling은 그냥 random하게 sample을 선택하는 방법인데 이게, 도메인을 골고루 커버하지 못 할수가 있다. 특히 sampling 수를 줄이면 결과가 더 안좋은데 그래서 Latin Hypercube Sampling이 이를 개선한다. Latin …

Read More

Discrete Optimization Optimization의 Design variables가 discrete한 문제를 discrete optimization problem이라고 한다. 이는 discrete variable의 종류에 따라 3가지로 분류될 수 있다. binary (0 or 1) integer (vehivle의 wheel의 갯수 등을 선택하는 문제) discrete (예를 들어 금속의 종류를 선택한다거나 등의 문제) discrte opimization은 nondeterministic polynomial time complete 이므로 solution이 …

Read More

Penalty method 제약조건이 있는 Constrained optimization을 간단하게 제약조건이 없는 unconstrained optimization으로 변환할 수 있는 방법이다. penalty parameter 설정에 의해서 true optimum에 수렴하지 않을 경우가 있어서 gradient based optimization에서는 더이상 사용되지 않는다. graient free method에서 사용되기도 하고, constrained optimization을 이해하는데 도움이 되기 때문에 살펴보자. 일단 constrained optimization …

Read More

Complex step은 수치 미분값을 구하는 방법 중에 하나다. finite differencing을 유도할 때 small step $h$으로 real number가 아니라 imaginary로 취하고 Taylor expansion을 적용하면 아래와 같다. $$f(x+ih) = f(x) + ihf'(x) - \frac{h^2}{2}f''(x)-\frac{ih^3}{3!}f'''(x)+\cdots$$ 여기서 imaginary part만 모아서 보자. $$\text{Imag}[f(x+ih)] = hf'(x) - \frac{h^3}{3!}f'''(x)+\cdots$$ …

Read More

수치적으로 미분값 구하는 방법은 4가지가 있는데 1) symbolic derivative 2) finite differencing 3)complex step method 4) automatic differenciation 이다. 그 중에서 가장 간단하게 자주 쓰이는 방법이 finite differencing 이다. 먼저 symbolic derivative는 함수의 analytic한 derivative를 찾는 방법이다. 예를 들어서 $f=\sin(x)$의 경우에 symbolic derivative는 $f=\cos(x)$이다. 그런데 이 방법은 implicit …

Read More

$$\underset{x}{\text{minimize}} f(x)$$ 위의 식과 같이 constraint가 없는 최적화 문제에 problem domain이 모든 영역에서 differentiable하면 (미분가능, 이건 연속이랑 다른 개념이라는 걸 고딩 때 배우지) 해당 함수의 gradient, $\nabla f = 0$ 지점이 함수의 극 값, 즉 maximum이나 minimum이 된다. 그래서 최적화 문제 풀 때 $\nabla f(x) = 0$ 의 방정식을 푸는데 (이 방정식을 만족시키는 x를 구한다) 이 과정에서 line search가 나온다. 수치해석적으로 $x$ …

Read More

Search Direction line search 할 때 어디로 line 그어서 어느 방향으로 이동할 지를 결정해서 one dimensional problem을 반복적으로 푸는 것이다. 오늘은 이 search direction을 어떻게 정하는지 알아 보자. Matines & Andrew 의 text book에서는 아래의 5가지 방법을 소개한다. Steepest Descent Conjugate Gradient Newton's Method Quasi-Newton Methods Limited-Memory Quasi-Newton Methods Steepest …

Read More

Trust-Region Methods Line search에서는 방향과 step을 정해서 이동하면서 minimum인지 아닌지 확인하는 반면에 trust region methods에서는 radius를 정해서 그 안에서 approximated function의 minimum을 찾고 그 minimum으로 이동하여 다시 더 큰 radius의 region을 그리고 그 안에서 minimum을 찾는 행위를 반복한다. 최적값으로 수렴하기 전에는 항상 boundary에서 minimum 값을 갖지만 수렴하게되면 radius를 더 크게 해도 boundary …

Read More