본문 바로가기

backtracking line search3

라인서치 (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.
등식 제약조건에서의 뉴턴방법 (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.