convex optimization5 장벽 내부점 방법 (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. 내부점 방법 (Interior-Point Method)의 개념 다음 사진은 내부점 방법(interior-point method)에 대해서 1984년 11월 19일에 뉴욕 타임즈지에 실린 기사를 캡쳐한 것이다. 기사 제목은 'Breakthrough in Problem Solving'이다. 전문적인 수학 알고리즘에 대해서 과학 전문지도 아닌 일반 신문에 기사화되는 일은 매우 드문데, 그만큼 내부점 방법의 중요성을 말해주는 것 같다. 그럼 최적화 이론에서 혁명적인 방법으로 일컬어지는 내부점 방법에 대해서 알아보도록 하자. 내부점 방법은 기본적으로 KKT조건식의 해를 구하기 위한 방법이다. 하지만 KKT 조건식을 직접 푸는 대신 조금 수정한 식을 풀어서 점근적으로 최적해를 찾아가는 방법을 택했다. 제약조건이 있는 컨벡스(convex) 최적화 문제에 대해서 \[ \begin.. 2022. 4. 6. [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. 최적화 문제의 분류 제약조건이 있는 비선형 다변수 함수 \( 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 다음
