Convex Optimization 문제는 Optimization 문제 중에서 해결하기 가장 좋은 성질을 가진 문제입니다.
이는 전역 최적해(global optimum)를 보장할 수 있기 때문입니다.
일반적으로 Optimization 문제는 여러 개의 지역 최적해(local optimum)를 가질 수 있는데, Convex Optimization 문제에서는 이런 문제가 발생하지 않습니다.
Strong Duality(강한대칭성)
Optimization 문제에서 원래 문제(primal problem)와 이와 관련된 대칭 문제(dual problem)가 있습니다.
강한 대칭성이 존재한다는 것은, 대칭 문제를 통해 원래 문제의 최적해를 찾을 수 있음을 의미합니다. 이는 문제를 해결하는 데 있어 매우 강력한 도구가 됩니다.
convex func과 convex set의 차이
Convex Function과 Convex 집합은 비슷한 개념이지만, 서로 다른 수학적 객체입니다.
Convex Function는 실수 값을 출력하는 Function이고, Convex 집합은 특정 조건을 만족하는 점들의 집합입니다.
기계 학습에서는 이 둘을 구분하지 않고 다루는 경우가 많습니다.
Def 7.2: Convex Set
집합 C는 다음 조건을 만족할 때 Convex 집합입니다.
Convex 집합은 두 점을 연결하는 선분이 항상 집합 내에 포함되는 특성을 가집니다. 즉, 어떤 두 점을 선택하더라도 이 두 점을 잇는 직선이 집합을 벗어나지 않는다는 것을 의미합니다.
7.5는 두선분을 연결해도 직선이 집합을 벗어나지 않지만 7.6은 어떤 집합안의 어떤 두점을 연결한 직선이 집합을 벗어내게 됩니다.
Convex Function(Convex Functions)
Convex Function는 두 점을 선택하고 이 두 점을 잇는 직선이 Function의 그래프보다 위에 위치한다는 성질을 가지고 있습니다. 즉, 이 Function는 ‘아래로 오목한’ 형태를 가집니다.
Def 7.3: Convex Function(Convex Function)
Convex Function의 정의는 두 점을 잇는 직선의 Function 값이 해당 구간의 Function 그래프보다 크거나 같다는 것입니다.
이는 Convex Function가 항상 두 점을 잇는 직선보다 아래에 위치한다는 것을 의미합니다.
Concave Function
Concave Function는 Convex Function의 음수입니다. 즉, 그래프가 위로 오목한 형태입니다.
Concave Function는 Convex Function의 반대 형태를 가집니다. 그래프가 위로 오목한 형태이며, Convex Function의 정의를 뒤집은 형태로 생각할 수 있습니다.
에피그래프(Epigraph)
Function f의 에피그래프는 Convex Function에 물을 부어 채운 것과 같은 형태로 얻어진 집합입니다. 이 에피그래프는 Convex 집합입니다.
에피그래프는 Function의 그래프 위쪽에 위치한 모든 점들의 집합을 의미합니다. Convex Function의 에피그래프는 항상 Convex 집합이 됩니다. 이는 Convex Function의 특성 때문에 가능한 것입니다.
Example 7.3 (Negative entropy)
예제에서는 음수 엔트로피 함수 f(x)=xlog2x가 볼록함을 두 가지 방법으로 보여줍니다.
정의에 의한 증명
- 두 점 x=2와 x=4를 선택하여 볼록성 정의를 적용합니다.
- 볼록성의 정의에 따르면, 임의의 두 점 사이의 중간 지점에서의 함수 값은 두 점에서의 함수 값의 가중 평균보다 작거나 같아야 합니다.
- 여기서 θ=0.5로 설정하여 계산한 결과는 좌변 f(3)≈4.75, 우변값은 5를 비교하여 위의 정의를 만족함을 보여줍니다.
미분을 통한 증명
- 함수가 미분 가능하므로 도함수를 사용하여 볼록성을 검증합니다.
- 도함수 ∇f(x)를 계산하여 특정 점에서의 기울기를 구합니다.
여기서 x와 y는 임의의 두 점입니다. 우리는 두 점 x=2, y = 4 를 선택하여 이 조건을 검증합니다
정리
Convex 특정한 조건을 만족하는 Function과 집합을 활용하여 Optimization 문제를 효과적으로 해결하는 방법입니다.
Convex Function과 Convex Set은 수학적 성질이 잘 정의되어 있어, 기계 학습에서 Optimization 문제를 다룰 때 매우 유용하게 사용됩니다.
이들을 이용하면 문제의 전역 최적해를 효율적으로 찾을 수 있으며, 문제를 해결하는 과정에서 강한 대칭성을 활용할 수 있습니다.
