0%

최적화 문제란?

Posted on Edited on In , , Disqus:

최적화 문제

  • 목적함수의 값을 최대화 혹은 최소화 하는 변수 x의 값을 찾는것 \[ x^{\ast} = \arg \max_x f(x) \] \[ x^{\ast} = \arg \min_x f(x) \]
  • 최소화하려는 함수 \(f(x)\)를 목적함수(objective function), 비용함수(cost function), 손실함수(loss function) 오차함수(error function) 등으로 부른다

그리드 서치

  • 목적함수의 값을 찾는 가장 쉽고 단순한 방법은, 값을 여러개 넣어보고 가장 작은 값을 찾아내면 된다. 이런 방법을 그리드 서치라 한다.

수치적 최적화

  • 기울기 필요조건 : 최저점에서는 기울기가 항상 0이다.
  • 최대경사법 \[x_{k+1} = x_{k} - \mu \nabla f(x_k) = x_{k} - \mu g(x_k) \]
    • 현재 위치 \(x_k\)에서의 기울기 \(g(x_k)\)를 이용하여 다음번 위치 \(x_{k+1}\)의 위치를 찾는 방법이다.
    • 스텝사이즈(혹은 학습률) \(\mu\)를 잘 선택해야 한다.
    • \(x_k\) 에서 기울기가 음수면 곡면이 아래로 향하고 \(g(x_k) < 0\)이 되므로 앞으로 진행(위로 올라감)
    • \(x_k\) 에서 기울기가 양수면 곡면이 위로 향하고 \(g(x_k) > 0\)이 되어 뒤로 진행하여, 점점 낮은위치로 이동한다.(최저점으로 간다)
    • \(x_k\)가 최저점에 도달하면 \(g(x_k) = 0\)이 되므로, 더이상 움직이지 않는다.
  • 진동현상 : 함수 곡면의 모양이 계곡처럼 생길 경우 최저점에 도달하지 못하고 계속 움직인다.
  • 뉴턴방법 : 스텝사이즈 없이, 목적 함수가 2차식이라는 가정하에 그레디언트 벡터에 해시안 행렬의 역행렬을 곱하여 한번에 최저점을 찾는다
  • sp.minimize(목적함수, 초깃값 벡터, 그레디언트 벡터를 출력하는 함수(옵션))

전역 최적화 문제

  • 국소 최저점(local minima)를 가지고 있으면 수치적 최적화 방법으로는 전역 최저점(global minimum)에 도달한다는 보장은 없다.
  • 따라서, 결과는 초기 추정값 및 알고리즘, 파라미터 등에 의존한다.

컨벡스 문제

  • 목적함수의 2차 도함수의 값이 항상 0 이상이 되는 영역에서만 정의된 최적화 문제를 컨벡스(convex) 문제라고 한다.
  • 다변수 목적함수에선 헤시안 행렬이 항상 양의 준정부호라는 조건

symbol 연산

  • 미지수(x,y)등을 설정해 방정식을 연산할수 있게 하는 sympy의 기능 
    1
    2
    x, y = sympy.symbols('x y')
    f = (1-x)**2+100*(y-x**2)**2

다차식의 최적화

  • 다차식에선 그레디언트 벡터를 출력하는 함수(jac)를 설정할때 np.array로 설정해서 넣어줘야 함 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    #함수 정의
    x1,x2,x3 = sympy.symbols('x1 x2 x3')
    f = (1-x1)**2 + (1-x2)**2 + 100*((x2-x1**2)**2+ (x3-x2**2)**2)
    # 각 함수의 도함수를 구함
    sympy.simplify(sympy.diff(f,x1))
    sympy.simplify(sympy.diff(f,x2))
    sympy.simplify(sympy.diff(f,x3))

    sympy.simplify(sympy.diff(f,x1,x2))
    sympy.simplify(sympy.diff(f,x1,x3))
    sympy.simplify(sympy.diff(f,x2,x3))

    # 3차식에선 np.array로 x1,x2,x3에 대한 도함수 3개 다 넣어줘야 함
    def f(x):
        return (1-x[0])**2 + (1-x[1])**2 + 100*((x[1]-x[0]**2)**2 + (x[2]-x[1]**2)**2)

    def jac2(x):
        return np.array([400*x[0]*(x[0]**2-x[1])+2*x[0]-2,-200*x[0]**2-400*x[1]*(-x[1]**2+x[2])+202*x[1]-2,-200*x[1]**2 + 200*x[2]])

    x = (0,0,0)
    result = sp.optimize.minimize(f,x,jac=jac2)
    print(result)

제한 조건이 있는 최적화 문제

  • "등식" 제한 조건이 있는 최적화 문제
    • 라그랑주 승수법
  • "부등식" 제한 조건이 있는 최적화 문제
    • KKT(karush-kuhn-Tucker)을 필요로 한다

선형계획법 문제와 이차계획법 문제

  • 선형계획법 문제(Linear Programming) : 방정식 혹은 부등식 제한 조건을 가지는 "선형모형"의 값을 최소화 하는 문제
    • sp.optimize.linprog(목적함수의 계수 벡터, 등식 제한조건의 계수행렬, 등식 제한조건의 상수 벡터)
  • 이차계획법 문제(Quadraic Programming) : 방정식 혹은 부등식 제한 조건을 가지는 "이차형식"의 값을 최소화 하는 문제