최적화이론

수학에서는 주어진 함수 $f: X \to \mathbb{R}$ 의 최대값과 최소값을 찾는 것을 최적화라 한다. 이 대상 함수가 우리 삶의 문제에 직결된 경우 응용수학의 관점에서 큰 관심을 받으며, 이를 풀어내는 최적화이론의 중요성은 두말할 것도 없을 것이다.

• 수학에서의 최적화 기법
  • 최적값: 최대값과 최소값 $\max$, $\min$
  • 최적해: 최대인수와 최소인수 $\text{argmax}$, $\text{argmin}$
  • 1계 필요 조건
  • 2계 필요/충분 조건
• 교대 최적화

선형 계획법

• 선형 계획 문제

표준형

• 방정식 폼
  • 최적해의 존재성
• 기저가용해
  • 기저가용해의 유일성
  • 최적해가 존재한다면 그 중 하나는 기저가용해다
• 선형계획법의 기본정리 증명

심플렉스 메소드

• 딕셔너리와 태블로
• 심플렉스 메소드
  • 초기화와 보조문제
  • 대상 함수의 무한성
  • 심플렉스 메소드의 사이클링
• 심플렉스 메소드의 브랜드 룰

듀얼러티

• 프라이멀 문제와 듀얼 문제
• 약한 쌍대성 정리 증명
• 강한 쌍대성 정리 증명

실습

• 엑셀로 선형계획문제 푸는 법
• 줄리아로 선형계획문제 푸는 법 JuMP.jl
• 파이썬으로 선형계획문제 푸는 법 scipy
• 매트랩로 선형계획문제 푸는 법 Optimization Toolbox
• R로 선형계획문제 푸는 법 lpSolve

비선형 계획법

• 라그랑주 승수법

경사 하강법

• 경사하강법
• 확률적 경사하강법
• 뉴턴 메서드
• 서브그래디언트
• 서브그래디언트 메서드

프락시멀 알고리즘

• 프락시멀 오퍼레이터 $\operatorname{prox}_{\lambda f} (\mathbf{x})$
• 프락시멀 최소화 알고리즘 $\mathbf{x}^{(k+1)} = \operatorname{prox}_{\lambda f}(\mathbf{x}^{(k)})$
• 프락시멀 그래디언트 메서드 $\mathbf{x}^{(k+1)} = \operatorname{prox}_{\lambda g}(\mathbf{x}^{(k)} - \lambda \nabla f(\mathbf{x}^{(k)})) $
• PALM(Proximal Alternating Linearzed Minimization)

진화 계획법

휴리스틱

파티클 스웜

주요 참고문헌

• Luenberger. (2021). Linear and Nonlinear Programming (5th Edition)
• Matousek. (2007). Understanding and Using Linear Programming
• Vanderbei. (2020). Linear Programming(5th Edition)