YeonjeeJung's Blog

Subgradient 만약 함수 $f(x)$가 미분불가능하다면, 우리는 임의의 gradient를 정해야 한다. subgradient를 정의할 수 있는데, 인 모든 $g$를 subgradient라고 한다. $\partial f(x)$가 subgradient의 집합을 의미한다. 원래함수 $f(x)$가 convex라면 subgradient에서 gradient descent를 써서 같은 결과를 낼 수 있다. subgradient는 저 조건만 충족하면 되기 때문에 한 점에서 여러 개의 subgradient가 발생할 수 있다....

Proximal Gradient Proximal Gradient Descent 일반적으로 우리는 $f(x)$가 미분가능한 함수라고 생각하고 문제를 풀었지만, 사실 그렇지 않은 경우가 더 많다. 이런 경우를 잘 해결하기 위해 $f(x)$를 $g(x)$와 $h(x)$로 쪼갤 수 있다. 여기서 $g(x)$는 미분가능한 nice function이고, $h(x)$는 미분불가능할 수도 있지만 해석하기 쉬운 additional function 이다. $g(x)$와 $h(x)$는 둘다 convex이다. 사실 gradient...

Barrier Method Inequality Constrained Problems 최적화해야 하는 함수 $f(x)$가 제한된 집합 $X$에서 정의될 때 projected gradient descent 외의 다른 방법을 소개한다. 이런 constrained optimization 문제를 다르게 말하면, ‘어떤 함수 $h, g$에 대하여 모든 $1\le i \le m$인 $i$들에 대해 $h_i(x)=0$을 만족하고, 모든 $1\le j \le r$인 $j$들에 대해 $g_j(x)\le 0$을...

Projected Gradient Descent Projected Gradient : $\alpha$-strongly convex & $\beta$-smooth (Recall) Unconstrained Vanilla Analysis vanilla analysis에서는 을 얻을 수 있었다. 이 때 마지막 부등식은 라는 성질에 의해 를 얻어서 성립한 것이다. Constrained Vanilla Analyasis constrained에서는 $(* 1)$가 아닌 가 성립한다. 따라서, 가 성립하므로, 이다. 따라서 결론적으로, Projected Gradient Descent를 사용하면...

Projected Gradient Descent Constrained Optimization Constrained Problem은 $f(x)$를 최소화하는 $x$를 찾는 문제인데, $x$의 범위 $X$가 주어져 있다는 점에서 이전과 다르다. 이 문제를 해결하는 방법에는 두 가지가 있는데, Projected Gradient Descent를 이용하는 방법과 unconstrained problem으로 바꿔서 해결하는 방법이 있다. 이번 단원은 첫번째 방법에 대한 내용이다. Projected Gradient Descent Project 는 ,...