프락시멀 그래디언트 메서드
📂최적화이론프락시멀 그래디언트 메서드
정의
미분불가능한 목적함수 H(x):Rn→R가 미분가능한 함수 f와 미분불가능한 함수 g로 분해된다고 하자.
H(x)=f(x)+g(x)
다음과 같은 반복 알고리즘으로 H에 대한 최적화문제를 푸는 방법을 프락시멀 그래디언트 메서드proximal gradient method라 한다.
x(k+1)=proxλg(x(k)−λ∇f(x(k)))
설명
경사하강법과 프락시멀 최적화를 같이 쓰기 때문에 proximal gradient method이다.
유도
※ f(x)를 테일러 정리로 근사하여 유도하는 방식은 수식 전개가 매끄럽지않아 알고리즘 공식을 납득하기 어렵다고 생각하기 때문에 소개하지 않는다.
우리가 최적화하고 싶은 함수는 H인데 이를 미분가능한 부분 f와 미분이 불가능한 부분 g로 나눠서 생각한다. 다시말해 f와 g를 동시에 최적화하고 싶은 것이다. 그런데 f는 미분이 가능하므로, 경사하강법을 통해 다음 스텝의 최적점을 얻을 수 있다.
xf=x−λ∇f(x)
이 점에서 멀리 떨어져있지 않으면서 동시에 g를 최적화하는 점은 프락시멀 최적화로 얻을 수 있다.
x∗=proxλg(xf)=vargmin{g(v)+2λ1∥v−xf∥22:v∈Rn}
따라서 다음과 같은 최적해의 업데이트 공식을 얻는다.
x(k+1)=proxλg(x(k)−λ∇f(x(k)))=vargmin{g(v)+2λ1v−(x(k)−λ∇f(x(k)))22:v∈Rn}
■