Least Square Loss는 언제나 Convex하다.

y-Ax 의 제곱이 Least Square Loss인데, 이를 제곱하면 Quadratic Function이 되고, Quadratic Function의 최고차항의 계수가 \(A^TA\), 즉 Positive Semi Definite이다.

Quadratic Function의 최고차항의 계수가 PSD이면 늘 convex하다.

이번에는 기본적인 용어들과, 1st order optimality, 그리고 문제에 변형을 하더라도 솔루션은 변하지 않는, Equivalent transformation에 대해 배울 것이다.

Optimization terminology

min f(x)
x in D

subject to

g(x) <= 0
Ax = b

f는 criterion, objective function

g는 inequality constraint

g를 만족하는 x에 대하여 Ax=b라면 feasible point

모든 feasible point x에 대해 f(x)의 min을 optimal value라고 하고, f* 로 표기한다.

feasible하고 f(x)=f*를 만족하는 x는 optimal이다. 이는 solution, minimizer라고도 불린다.

x가 feasible하고 f(x) <= f* + epsilon 이라면 x를 \(\epsilon\)-suboptimal이라고 한다.

x가 feasible하고 g(x)=0 이라면 g를 x에서 active하다고 한다.

convex minimization은 concave maximization과 대치될 수 있지만 둘 다 convex optimization이라고 부른다.

convex optimization problem은 convex optimization program이라고도 부르는데, 아마 알고리즘처럼 정해진 공식에 따라서 처리할 수 있기 때문에 사용하는 말이 아닐까 하고 추측하지만, 정확하진 않다.

Convex Solution sets

어떤 convex problem은 미분가능한 f에 대해 다음을 만족하면 feasible한 x지점에서 미분 가능하다.

\[\grad f(x)^T (y-x) \ge 0 \text{ for all } y \in C\]

이는 C상의 어떤 지점에 대해서, 해당 방향으로 움직일 때의 gradient가 더 커져야 한다는 것이다. 만약에 더 줄어드는 방향이 있다면, 해당 방향으로 움직인 점의 방향에 더 작은 값이 있을 것이다.

만약 \(C=R^n\)이라면(즉, unconstrained optimization)

최적화 조건은 \(\grad f(x)=0\)

\(f(x)=1/2 x^TQx+ b^Tx + c\) where Q psd.

The first-order condition says that solution satisfies

\[\grad f(x) = Qx+b=0\]

if Q pd -> unique solution \(x=Q^{-1}b\)

Lagrange multiplier