1.Introduction
서울대학교 심형보 교수님의 강의
모두를 위한 컨벡스 최적화
youtube에 올라온 stanford, Convex Optimization
를 듣고 공부하며 블로그에 정리를 할 계획 입니다.
Introduction
최적화 문제(Optimization problems)란 목적 함수(Objective Function)를 최소화 혹은 최대화 시키는 변수의 조합을 찾는 문제를 의미합니다.
Mathematical optimization
위를 만족하고 objective function $f_0$ 를 최소로 만드는 벡터 $x$ 를 $x^*$로 표현하며 이를 solution 혹은 optimal point라 합니다.
Examples
최적화 문제가 적용될 수 있는 예시입니다.
portfolio optimization
- variables : amounts invested in different assets
- constraints : budget, max/min investment per asset, minimum return
- objective : overall risk or return variance
device sizing in electronic circuits
- variables : device widths and lengths
- constraints : manufacturing limits, timing requirements, maximum area
- objective : power consumption
data fitting
- variables : model parameters
- constraints : prior information, parameter limits
- objective : measure of misfit or prediction error, plus regularization term
Solving optimization problems
general optimization problem
- very difficult to solve
- methods involve some compromise(very long computation time, not always finding the solution)
하지만 다음은 효율적이고 안정적으로 해결할 수 있습니다.
- least-squares problems
- linear programming problems
- convex optimization problems
Least-squares
최소자승법으로 근사적으로 구하려는 해와 실제 해의 오차의 제곱의 합이 최소가 되는 해를 구하는 방법입니다.
analytical solution : $x^*=(A^TA)^{-1}A^Tb$