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$


Linear programming


Convex optimization problem

업데이트: