본문 바로가기

AI 수학61

플롭 (Flop) 선형대수 수치 알고리즘의 복잡성을 표현하는 방법 중의 하나로 알고리즘을 수행하는 데 필요한 부동소수점 연산의 총 횟수를 사용한다. 부동소수점 연산 (floating point operation)을 간단히 플롭(flop)이라고 하는데, flop은 두 개의 부동소수점 숫자의 덧셈, 뺄셈, 곱셈 또는 나눗셈 등을 한 번 수행하는 것으로 정의한다. 컴퓨터의 성능을 수치로 나타내는 단위로서 사용되는 FLOPS도 있다. 이 때의 FLOPS는 FLoating point Operations Per Second의 약자로 해당 컴퓨터가 처리할 수 있는 초당 얼마나 많은 연산을 처리하는 지를 나타내는 단위다. 여기서는 부동소수점 연산(flop)의 횟수(count) 라는 의미의 flops에 대해서 설명한다. 플롭의 횟수, 즉.. 2023. 11. 9.
심플렉틱 행렬 (Symplectic Matrix) 심플렉틱 행렬(symplectic matrix)은 다음식을 만족하는 정사각형 행렬 \( M \in \mathbb{R}^{2n \times 2n}\) 으로 정의한다. \[ M^T JM=J \tag{1} \] 여기서 \[ J= \begin{bmatrix} 0 & I_n \\ -I_n & 0 \end{bmatrix} \] 이고 \(I_n\) 은 \(n \times n\) 단위행렬이다. 심플렉틱 행렬은 다음과 같은 몇가지 특징을 갖는다. 첫째 심플렉틱 행렬의 행렬식(determinant)은 항상 \(1\) 이다. 증명은 다음과 같다. 식 (1)에서 \[ \begin{align} \det ⁡J = 1 &= \det⁡(M^T ) \det⁡ J \det⁡ M \tag{2} \\ \\ &=(\det ⁡M )^2 \en.. 2023. 7. 1.
좌(왼쪽) 고유벡터 (left eigenvector) 고유벡터에도 좌파와 우파가 있다. 일반적으로 고유벡터라고 하면 우(오른쪽) 고유벡터(right eigenvector)를 의미한다. 그러면 좌(왼쪽) 고유벡터(left eigenvector)란 무엇이고 우(오른쪽) 고유벡터와는 어떤 관계가 있을까. 정방행렬 \(A \in \mathbb{R}^{n \times n}\) 의 우(오른쪽) 고유값(eigenvalue) \(\lambda\) 와 고유벡터 \(\mathbf{v}\) 는 다음과 같이 정의된다 (https://pasus.tistory.com/8). \[ A \mathbf{v} = \lambda \mathbf{v}, \ \ \ \mathbf{v} \ne 0 \tag{1} \] 반면 정방행렬 \(A\) 의 좌(왼쪽) 고유값 \(\kappa\) 와 고유벡터 \.. 2023. 2. 10.
Frobenius Norm 최소화 문제 행렬 \(A \in \mathbb{R}^{n_1 \times n_2} \), \(B \in \mathbb{R}^{n_3 \times n_4}\), \(Y \in \mathbb{R}^{n_1 \times n_4}\) 가 주어졌을 때, 다음과 같은 프로베니우스 놈(Frobenius norm)을 최소화하는 행렬 \(X \in \mathbb{R}^{n_2 \times n_3}\) 를 구하는 문제를 프로베니우스 놈 최소화 문제라고 한다. \[ X_{opt}= \arg \min_{X} \lVert AXB-Y \rVert_F \tag{1} \] 참고로 어떤 행렬 \(M\) 의 프로베니우스 놈 \( \lVert M \rVert _F\) 는 다음과 같이 정의된다. \[ \lVert M \rVert _F= \sqrt{ t.. 2022. 11. 3.
라인서치 (Line Search) 방법 제약조건이 없는 최적화 문제 \[ \min_{\mathbf{x}}⁡ f(\mathbf{x}) \tag{1} \] 는 보통 초기 추측값 \(\mathbf{x}^{(0)}\) 에서 시작하여 이터레이션(iteration)을 통하여 일련의 중간 단계의 해 \(\mathbf{x}^{(k)}\) 를 구하며 점진적으로 최적해에 접근하는 방법을 취한다. 이터레이션의 다음 단계의 해 \(\mathbf{x}^{(k+1)}\) 는 현 단계 해 \(\mathbf{x}^{(k)}\) 에서 일정 스텝(step) \(\Delta \mathbf{x}^{(k)}\) 으로 일정한 스텝사이즈 \(\eta^{(k)}\) 만큼 이동시켜 구하게 된다. \[ \mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} + \eta^{(k.. 2022. 4. 21.
프라이멀-듀얼 내부점 방법 (Primal-Dual Interior-Point Method) 제약조건이 있는 컨벡스(convex) 최적화 문제에 대해서 \[ \begin{align} & \min_{\mathbf{x}}⁡ f(\mathbf{x}) \tag{1} \\ \\ & \mbox{subject to : } \ \ g_i (\mathbf{x}) \le 0, \ \ i=1, ...,m \\ \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ A \mathbf{x}=\mathbf{b} \end{align} \] KKT(Karush-Kuhn-Tucker) 수정식은 다음과 같다. \[ \begin{align} & \nabla_{\mathbf{x}} f(\mathbf{x})+ \sum_{i=1}^m \mu_i \nabla_{\mathbf{x}} g_i (\mathbf{x.. 2022. 4. 15.
장벽 내부점 방법 (Barrier Interior-Point Method) 다음과 같은 등식과 부등식 제약조건이 있는 컨벡스(convex) 최적화 문제는 \[ \begin{align} & \min_{\mathbf{x}}⁡ \ f(\mathbf{x}) \tag{1} \\ \\ & \mbox{subject to : } \ \ g_i (\mathbf{x}) \le 0, \ \ i=1, ...,m \\ \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ A\mathbf{x}=\mathbf{b} \end{align} \] KKT 수정식이나 지시함수(indicator function)를 이용하면 다음과 같이 등식 제약조건만을 갖는 컨벡스 최적화 문제로 근사화할 수 있다. \[ \begin{align} & \min_{\mathbf{x}}⁡ \ f(\mathb.. 2022. 4. 13.
등식 제약조건에서의 뉴턴방법 (Newton’s Method) 뉴턴방법(Newton's method)은 제약조건이 없는 최적화 문제에서 최적해를 이터레이션(iteration)으로 구하는 방법이었다. 하지만 뉴턴방법은 등식 제약조건을 갖는 최적화 문제로도 확장 적용될 수 있다. 등식 제약조건(equality constraints)을 갖는 컨벡스 최적화 문제(convex optimization problem)는 다음과 같다. \[ \begin{align} & \min_{\mathbf{x}}⁡ f(\mathbf{x}) \tag{1} \\ \\ & \mbox{subject to : } \ \ A\mathbf{x}=\mathbf{b} \end{align} \] 여기서 \(\mathbf{x} \in \mathbb{R}^n\) 은 최적화 변수이고, \(f(\mathbf{x})\.. 2022. 4. 10.
뉴턴방법 (Newton’s Method) 경사하강법(gradient descent)이 어떤 함수의 최소값을 향한 방향을 계산하는데 1차 미분을 사용하는 반면 뉴턴방법(Newton's method)는 2차 미분을 사용한다. 따라서 뉴턴방법이 경사하강법보다는 성능이 훨씬 좋다. 제약조건이 없는 최적화 문제는 다음과 같다. \[ \min_{\mathbf{x}} f(\mathbf{x}) \tag{1} \] 여기서 \(\mathbf{x} \in \mathbb{R}^n\) 은 최적화 변수이고, \(f(\mathbf{x})\) 는 목적함수(objective function)이다. 목적함수는 두 번 미분가능하다고 가정한다. 뉴턴방법의 기본 개념은 최적화 변수의 시작값(starting point) \(\mathbf{x}\) 에서 목적함수 \(f(\mathbf{.. 2022. 4. 8.
내부점 방법 (Interior-Point Method)의 개념 다음 사진은 내부점 방법(interior-point method)에 대해서 1984년 11월 19일에 뉴욕 타임즈지에 실린 기사를 캡쳐한 것이다. 기사 제목은 'Breakthrough in Problem Solving'이다. 전문적인 수학 알고리즘에 대해서 과학 전문지도 아닌 일반 신문에 기사화되는 일은 매우 드문데, 그만큼 내부점 방법의 중요성을 말해주는 것 같다. 그럼 최적화 이론에서 혁명적인 방법으로 일컬어지는 내부점 방법에 대해서 알아보도록 하자. 내부점 방법은 기본적으로 KKT조건식의 해를 구하기 위한 방법이다. 하지만 KKT 조건식을 직접 푸는 대신 조금 수정한 식을 풀어서 점근적으로 최적해를 찾아가는 방법을 택했다. 제약조건이 있는 컨벡스(convex) 최적화 문제에 대해서 \[ \begin.. 2022. 4. 6.