AI 수학/최적화23 [KKT 조건 - 3] 프라이멀 문제와 듀얼 문제 최적화 문제는 두 가지 관점에서 문제를 표현할 수 있는데 프라이멀 문제(primal problem)와 듀얼 문제(dual problem)가 그것이다. 어떤 문제에서는 프라이멀 문제보다도 듀얼 문제로 바꾸어 푸는 것이 더욱 효과적일 수 있다. 먼저 프라이멀 문제는 등식과 부등식 제약조건이 있는 본래의 최적화 문제를 말한다. \[ \begin{align} & p^\star = \min_{\mathbf{x}} f(\mathbf{x}) \\ \\ \mbox{subject to: } \ \ & g_i (\mathbf{x}) \le 0, \ \ \ i=1,...,m \\ \\ & h_j (\mathbf{x}) = 0, \ \ \ j=1,...,k \end{align} \] 이 문제에 대한 라그랑지안을 다음과 같이 .. 2021. 2. 17. [KKT 조건 - 2] KKT 조건과 적용 예제 등식과 부등식 제약조건이 있는 일반적인 최적화 문제에 대해서 \[ \begin{align} & p^\star = \min_{\mathbf{x}} f(\mathbf{x}) \\ \\ \mbox{subject to : } \ & g_i (\mathbf{x}) \le 0, \ \ \ i=1,...,m \\ \\ \ & h_j (\mathbf{x}) = 0, \ \ \ j=1,...,k \end{align} \] KKT 조건(Karush-Kuhn-Tucker conditions)은 다음과 같다. \[ \begin{align} & \mbox{1. stationarity: } \ \nabla_{\mathbf{x}} f(\mathbf{x} ) + \sum_{i=1}^m \mu_i \nabla_{\mathbf{x}} .. 2021. 1. 18. [KKT 조건 - 1] 등식과 부등식 제약조건이 있는 최적화 문제 제약조건이 없는 일반적인 최적화 문제는 다음과 같다. \[ p^\star= \min_{\mathbf{x}} f(\mathbf{x}) \] 여기서 \(\mathbf{x}\)는 최적화 변수이고, \(f(\mathbf{x})\)는 목적함수(objective function)이다. \(\mathbf{x}^\star\)가 로컬(local) 최소점이 되기 위한 필요조건(necessary condition)은 \(\mathbf{x}=\mathbf{x}^\star\)에서 \(f\)의 그래디언트(gradient)가 \(0\)이 되는 것이다. \[ \nabla_{\mathbf{x}} f(\mathbf{x}^\star )=0 \] 등식 제약조건이 있는 일반적인 최적화 문제는 다음과 같다. \[ \begin{align} &.. 2021. 1. 14. 최소화의 필요조건과 충분조건 다음과 같이 제약조건이 없는 일반적인 함수의 최적화 문제에서, \[ \min_\mathbf{x} f(\mathbf{x}) \] 함수 \(f(\mathbf{x})\)가 \( \mathbf{x}^\star\)에서 로컬(local) 최소값이 되기 위한 필요조건(necessary condition)은 \( \mathbf{x}=\mathbf{x}^\star\)에서 계산한 \(f\)의 그래디언트(gradient)가 \(0\)이 되는 것이다. \[ \nabla_\mathbf{x} f(\mathbf{x}^\star ) = 0 \] 위 조건을 \(\mathbf{x}^\star\)이 최소점이 되기 위한 1차(first order) 필요조건이라고 한다. 사실 위 조건은 로컬 최대점에서도 성립한다. 그럼 또 다른 필요조건이 .. 2021. 1. 10. SGD에서 데이터를 무작위로 추출해야 하는 이유 배치(batch) 경사하강법은 학습 데이터 전체를 사용해서 손실함수(loss function)의 그래디언트(gradient)를 계산하고 신경망 파라미터를 업데이트한다. 반면에 확률적 경사하강법(SGD, stochastic gradient descent)은 전체 데이터에 비해 훨씬 적은 수의 데이터를 무작위로 추출하고 그 데이터만으로 손실함수의 그래디언트를 계산한 후 신경망 파라미터를 업데이트한다. 확률적(stochastic)이라는 용어는 데이터를 무작위로 추출한다는 뜻에서 나온 말이다. 그러면 왜 데이터를 무작위로 추출해야 할까. 대부분 신경망 학습 알고리즘은 손실함수를 정하는 것으로 시작한다. 손실함수를 \( \mathcal{L}(\mathbf{\theta} \ ; (\mathbf{x}^{(i )}, .. 2021. 1. 4. 함수의 최소화 또는 최대화의 조건 다음과 같이 제약조건이 없는 일반적인 최적화 문제가 있다. \[ \min_{\mathbf{x}} f(\mathbf{x}) \ \ \ \ 또는 \ \ \ \ \max_{\mathbf{x}} f(\mathbf{x}) \] 여기서 \( \mathbf{x} \in R^n \)은 최적화 변수이고, \( f(\mathbf{x}) \)은 목적함수(objective function)이다. 이 목적함수를 최소화 또는 최대화하기 위한 조건은 무엇일까. \( \mathbf{x} \)의 독립적 변화에 의해 유도된 함수 \( f(\mathbf{x}) \)의 변화량을 계산해 보자. \( \mathbf{x} \)의 변화량을 \( \Delta \mathbf{x} \)라고 하면, 함수의 증분(increment) \( \Delta f .. 2020. 10. 20. 라그랑지 곱수법의 증명 라그랑지 곱수(Lagrange multiplier)법을 증명해 보자. 먼저 기하학적 직관을 이용해서 증명해 본다. 다음과 같이 변수가 \( \mathbf{x} \in R^2 \)이고 등식 제약조건이 한 개 있는 최적화 문제를 살펴보자. \[ \begin{align} & p^* = \min_{x_1, x_2} f( x_1, x_2 ) \\ \\ subject \ to \ \ \ & h (x_1, x_2) = 0 \end{align} \] 등식 제약조건은 평면상의 곡선의 식을 나타낸다. 먼저 목적함수와 등식 제약조건 식을 \( x_1,x_2 \)을 축으로 하는 평면에 그려보자. 검은색 선은 \( f(x_1,x_2 )=c \)의 등고선을 나타낸다. 등고선이란 동일한 함수 값 \(c\)를 산출하는 변수 \( x.. 2020. 10. 1. 라그랑지 곱수법 라그랑지 곱수(Lagrange multiplier)법은 등식 제약조건이 있는 최적화 문제를 풀기 위해 고안된 방법이다. 등식 제약조건이 있는 최적화 문제는 다음과 같다. \[ \begin{align} & p^* = \min_{\mathbf{x}} f( \mathbf{x} ) \\ \\ subject \ to \ \ \ & h_j ( \mathbf{x} ) = 0, \ \ \ j=1,...,p \end{align} \] 여기서 \( \mathbf{x} \in R^n \) 은 최적화 변수, \( f( \mathbf{x}):R^n \to R \) 은 목적함수, \( h_j (\mathbf{x}):R^n \to R \) 은 등식 제약함수이다. 라그랑지 곱수법에 의하면 등식 제약조건이 있는 최적화 문제를 제약조건.. 2020. 10. 1. 경사하강법 제약조건이 없는 일반적인 최적화 문제는 다음과 같다. \[ p^* = \min_{\mathbf{x}} f(\mathbf{x}) \] 또는, \[ \mathbf{x}^* = \arg \min_{\mathbf{x}} f(\mathbf{x}) \] 여기서 \( \mathbf{x} \in R^n \) 은 최적화 변수이고, \( f(\mathbf{x}) \)은 목적함수(objective function)이다. 대부분 신경망 학습 알고리즘은 손실함수(loss function)를 정하거나 최적화를 위한 목적함수를 만드는 것으로 시작한다. 경사하강법(gradient descent) 또는 경사상승법(gradient ascent)은 목적함수를 최소화(minimization)하거나 최대화(maximization)하기 위해 .. 2020. 9. 30. 최적화 문제의 분류 제약조건이 있는 비선형 다변수 함수 \( f(\mathbf{x}) \)의 최소값 (또는 최대값)을 구하는 문제를 정적 최적화(static optimization) 문제 또는 비선형 프로그래밍 문제(NLP, nonlinear programming problem)라고 한다. 수식으로 표현하면 다음과 같다. \[ \begin{align} & p^* = \min_{\mathbf{x}} f(\mathbf{x}) \\ \\ subject \ to \ \ \ & g_i (\mathbf{x}) \le 0, \ \ \ i=1,...,m \\ \\ & h_j (\mathbf{x}) = 0, \ \ \ j=1,...,p \end{align} \] 여기서 \( \mathbf{x} \in R^n \)을 최적화 변수(optimi.. 2020. 9. 30. 이전 1 2 3 다음
