학습 목표
CH2. Basic Concept of Optimization
CH3. UE / SO Formulation
CH4. Optimization Algorithms
CH2. Basic Concepts in Minimization Problems
- Unconstrained Optimization
- Constrained Optimization
- Nonnegativity & Equality Constraints
- Lagrangian
- Lagrangian with Nonnegativity & Equality Constraints
CH3. Formulating the Assignment Problem as a Mathematical Program
- UE(User Equilibrium) basic formulation(=modeling)
- UE with Lagrangian formulation with nonnegativity, linear equality constraints
- SO(System Optimization Program) formulation
- Braess's Paradox
CH4. Review of Some Optimization Algorithms
앞선 CH3에는 UE와 SO를 수식으로 나타내었으니, CH4에서 Minimization(=Optimization)수행
- 1D minimization
- Multivariate Minimization
- Convex Combinations Method
원래는 위에서 multivariate 나 single variable 이나
1. 방향찾기
2. alpha 찾기
두가지 절차를 나누어서 진행해야 했지만, 여기서는 방향찾는 문제를 linear minimization problem으로 수식화하여 나타냈다. 그리고 아래의 alpha 구하는 방식도 convex combination 문제로, 두가지 문제를 합쳐서 생각가능하다.
Convex Combination Method 가 좋은경우는, linear minimization problem을 쉽게 풀 수 있을때이다.
궁금증
1. Frank-Wolfe 알고리즘에서 왜 y(auxilary flow)가 all-or-nothing 수행한 결과인가?
책의 Convex Combinations Method 파트에서는 y^n을 임의로 잡는법을 안가르쳐주었다. 사실 어떻게 찾는지도 모르기도 하다. 가장 best 는 steepest descent 에서 비롯되긴 하는데, 그 방향이 어딘지 마냥 searching 하기에는 computation 이 모자라다.
댓글