이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다. Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다. Powell's method 를 이해하기 위한 사전 지식 Powell's method 는 Univariate search 를 응용한 것이기 때문에 이를 먼저 이해하고 있어야 합니다. Univariate search(링크) Powell's method Powell's method 를 시각화 한 영상입니다. 앞서 언급했듯이 Powell's method 는 Univariate search 를 응용한 것입니다. 두 방법을 이미지를 통해 비교하면 Powell's met..
이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다. Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다. Univariate search 를 이해하기 위한 사전 지식 아래 링크는 Univariate optimization(단변수 최적화) 를 위한 알고리즘입니다. 아래 링크의 내용을 이해하고 보시면 더 쉽게 Univariate search 를 이해할 수 있습니다. Golden section search(링크)Fibonacci search(링크) Univariate search 이미지 출처: http://mathfaculty.fullerton.edu/mathews/n..
이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다. Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다. Nelder and Mead method 를 이해하기 위한 사전지식 아래 링크는 Nelder and mead method 를 이해를 돕기 위해 위키피디아에 작성되어 있던 용어에 대한 내용을 제가 한글로 풀어서 작성한 것입니다.본문을 보다가 아래 용어 때문에 이해 안되는 부분이 있다면, 그 때 읽으면 됩니다. 1. Convex set(링크)2. Convex hull(링크)3. Simplex(링크) Nelder and Mead method Nelder and Me..
이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다. Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다. 이전 글에서 Newton's method 에서 2차 근사함수를 통해서 local mimimum 을 탐색하는 방법을 언급했습니다. 이와 유사한 방법으로 Lagrange polynomial 을 통해서 minimum 을 탐색할 수 있습니다. Lagrange polynomial 출처: https://en.wikipedia.org/wiki/Lagrange_polynomial Lagrange polynomial 은 주어진 서로 다른 지점 n 개를 포함하는 가장 낮은 차수..
이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다. Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다. 다루는 함수의 Unimodality 가 보장되어 있다면, local minimum 이 존재하는 초기구간을 줄인 상태로 Root finding 알고리즘이나 Search 알고리즘을 적용할 수 있습니다. 간단히 표현하면 Unimodal function 에서 단조 증가와 단조 감소의 경계점인 극점(extreme point)이 있는 구간을 최대한 좁히는 것입니다. 순서는 다음과 같습니다. 1. 최초의 탐색지점 x_0 를 무작위로 선정합니다.2. x_0 에서의 함수값 f..
이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다. Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다. 이전 글에서 Fibonacci search(링크), Golden section search(링크) 에 대해서 설명했습니다. 핵심 아이디어가 똑같은 두 알고리즘은 충분한 iteration 을 거치면 결과적으로는 같은 성능(Convergence rate, 수렴속도)을 보임을 증명할 수 있습니다. Wikipedia 의 Golden section search(링크) 에서도 Fibonacci search 를 언급하고 있습니다. 1. Golden section searc..
이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다. Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다. Fibonacci search 아이디어 피보나치 탐색(Fibonacci search)은 황금분할탐색(Golden section search)과 기본적인 아이디어는 똑같습니다. 황금분할탐색이 황금률(Golden ratio)를 사용했다면 피보나치 탐색은 피보나치 수열(Fibonacci number or Fibonacci sequence)을 사용한다는 점이 가장 큰 차이입니다. 황금분할탐색 설명 링크 이 글을 읽고 있다면 피보나치 수나 피보나치 수열에 대해서는 이미..
이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다. Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다. 이전 글에서 Unimodality 에 대한 내용을 언급했습니다. 다루고 있는 함수가 Unimodal 하고 local minimum 을 찾고자 한다면, 아래 그림처럼 local minimum 이 존재할 것으로 생각되는 함수의 정의역의 범위를 줄여나가면 local minimum 에 도달하는 것을 보장할 수 있습니다. 타겟 함수의 형태를 모를때 함수의 Unimodality 가 확실하다면 함수의 형태가 ①, ② 중 어느 형태인지와는 상관 없이 왼쪽 그림의 경우 [a,..
이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다. Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다. 이전 Newton's method 글에서 접선(tangent line)을 통해서 해를 찾는 방법을 얘기했습니다. 이 방법은 정확히는 x_0 에서의 Taylor series expansion 의 1차 함수까지만 전개한 함수를 사용해서 접선을 구한 것입니다. x_0 에서의 Taylor series expansion 을 2차함수까지 전개를 하면 아래 그림의 빨간 convex function 처럼 원함수 f(x) 에 대한 2차 근사함수를 구할 수 있습니다. 이후의 원..
이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다. Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다. False position method(Regula Falsi) 가 잘 설명되어 있는 영상입니다. 알고리즘 자체의 방법론과 Rate of convergence 에 대한 설명은 영상에 충분히 시각화되어 추가적인 설명이 필요 없다고 생각됩니다. 여기선 False position method 의 장점과 단점에 대해 생각해보려합니다. 장점 1. 미분이 필요 없기 때문에, 미분 불가능한 정의역이 있거나 미분 자체가 어려운 함수에 적용하기 좋습니다. 2. 이는 장점이자 ..
이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다. Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다. Secant method 가 잘 설명되어 있는 영상입니다. 알고리즘 자체의 방법론과 Rate of convergence 에 대한 설명은 영상에 충분히 시각화되어 추가적인 설명이 필요 없다고 생각됩니다. 여기선 Secant method 의 장점과 단점을 생각해보려합니다. 장점 1. 미분이 필요 없습니다. 따라서 미분이 불가능한 함수에 적용할 수 있습니다.2. Rate of convergence 가 더 높기 때문에 Bisection 에 비해 일반적으로 더 빠르게 ..
이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다. Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다. Newton's method 가 잘 설명되어 있는 영상입니다. 알고리즘 자체의 방법론과 Rate of convergence(이하 수렴률) 에 대한 설명은 영상에 충분히 시각화되어 추가적인 설명이 필요 없다고 생각됩니다. 여기서는 Newton's method 의 장점과 단점을 생각해보려 합니다. 장점 1. 이전 글에서 다뤘던 Bisection method 보다 (일반적으로) 수렴률이 높기 때문에, (일반적으로) 탐색속도가 더 빠릅니다.(모든 경우에 그런 것은 아..
이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다. Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다. Bisection method 가 잘 설명되어 있는 영상입니다. 알고리즘 자체의 방법론과 Rate of convergence 에 대한 설명은 영상에 충분히 시각화되어 추가적인 설명이 필요 없다고 생각됩니다. 여기선 Bisection method 의 장점과 단점을 생각해보려합니다. 장점 초기 두 지점 a, b 만 서로 부호가 다르게 설정된다면 반드시 해를 찾을 수 있는 방법입니다. 단점 1. 초기 두 지점 a, b 의 부호가 서로 같다면 알고리즘 적용이 불가능합..
이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다. Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다. Unimodal function 에 대한 이해를 해야 앞으로 정리할 Optimization algorithm(최적화 알고리즘) 을 이해할 수 있습니다. 위키백과의 히스토그램 항목에서 Uninodal 이 한국어로 무슨 뜻인지 찾아볼 수 있었습니다. 위키백과에 따르면 Unimodal 은 단봉 혹은 단봉형이라는 단어로 번역할 수 있습니다. 그렇다면 Unimodal function 은 단봉함수 혹은 단봉형함수로 번역 될 것입니다.(히스토그램 위키 백과 링크) 그래프를..
이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다. Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다. Univariate function 의 최적화 조건의 일반화에 대한 증명을 잘 정리해 놓은 글을 찾았습니다. 이 증명은 Higher-order derivative test 의 증명 방법 중 하나로 이해됩니다. 원문의 증명 과정중 간단하게 생략하거나 말로만 설명한 부분들의 수식을 보충해서 번역했습니다. 원문은 가장 아래에 링크를 적었습니다. 티스토리 수식입력 기능이 한글을 지원하지 않아 번역임에도 수식을 영어와 혼용해서 쓰겠습니다. 증명하고자 하는 명제는 다음과..
이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다. Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다. 출처: https://light-tree.tistory.com/156 [All about]이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다. Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다. 출처: https://light-tree.tistory.com/156 [All about]이 글은 제가 공부한 내용을 정리하는..
이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다. Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다. Taylor series expansion Unconstrained univariate optimization 에 대해서 정리하기 위해선 먼저 Taylor series(테일러 급수), Taylor series expansion(테일러 급수 전개) 를 알아야 합니다. 여기선 이를 간략하게 정리하고 넘어가겠습니다. 테일러 급수의 증명과 같은 더 자세한 내용은 따로 검색해주시길 부탁드립니다. 테일러 급수는 함수를 급수 형태로 근사(혹은 표현)하는 것입니다. 매끄러운..
이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다. Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다. 출처: https://light-tree.tistory.com/154 [All about]이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다. Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다. 출처: https://light-tree.tistory.com/154 [All about]이 글은 제가 공부한 내용을 정리하는..
이 글은 제가 공부한 내용을 정리하는 글입니다. 잘못된 내용이 있을 수 있으며, 잘못된 내용을 찾으셨다면 리플로 알려주시길 부탁드립니다. 감사합니다. Numerical Optimization, 즉 수치최적화를 공부하고 그 내용을 정리하고자 합니다. Modeling Process 먼저 문제를 정의하는 것부터 생각해야 합니다. 예를 들어 석유 공급망을 설계하는 문제를 해결하고자 한다면 1) Define the optimization problem and model parameters 석유 공급망 해결 문제의 목표는 무엇인가? → 목표가 공급망 설계의 비용을 최소화하는 것인지, 설계된 공급망의 공급 속도를 최대화 하고 싶은지, 공급중 발생하는 비용을 최소화 하고 싶은 것인지 혹은 언급된 목표들을 복합적으로 달..