[ML] Convex Problem

Non-linear Problem

많은 공학적 방법들이 linear problem 을 가정하고 있지만

현실 세계의 많은 문제는 본질적으로 비선형(non-linear)임.

2024.06.01 - [.../Math] - [Math] Optimization Problem 의 종류

[Math] Optimization Problem 의 종류

 

비선형 문제(non-linear problem)는
선형 문제(linear problem)보다 일반적으로 더 풀기 어려움.

 

일반적인 비선형 최적화 문제(non-linear optimization problem)는

• 일반적인 비선형 문제는 국소 최소값과 전역 최소값을 모두 가질 수 있으며,
• 이는 Optimization의 iterative algorithm을 통해 전역 최소값을 찾기 어렵게 만듬

이같은 이유로, 

Iterative Alogrithm 으로 non-linear problem을 풀 경우:

• 항상 global minimum을 찾을 수 있다는 보장이 없으며,
• 초기값(initial point)에 따라 local minimum에 수렴하거나,
• 경우에 따라서는 수렴 자체가 불안정해질 수 있음.

Non-linear problem(비선형 문제)이란,
목적 함수(objective function) 또는 제약 조건(constraint)이 변수에 대해 선형(linear)이 아닌 관계를 가지는 최적화 문제로,
중첩의 원리(superposition principle)가 성립하지 않아
일반적으로 다수의 local minimum이 존재할 수 있으며
global minimum을 찾는 것이 보장되지 않음.

---

Convex problem

일반적인 비선형 문제는 다루기 어렵지만,

현재 하위 클래스인 볼록 최적화 문제(convex optimization problem)은 매우 많은 연구가 이루어져서

interative alogrithm으로 상당히 효율적으로 해결할 수 있는 비선형 문제임.

 

convex와 concave의 차이: https://dsaint31.tistory.com/881#Convex%20%EC%99%80%20Concave-1-2

[Math] Extremum Point, Inflection Point, Saddle Point, Convex and Concave.

 

Convex optimization problem은 다음 두 조건을 동시에 만족하는 최적화 문제를 가리킴:

• 목적 함수(objective function) $f$가 convex function.
  • domain(정의역) 상의 $\mathbf{x}_1$,$\mathbf{x}_2$ 와 $\lambda \in [0,1]$ 에 대해,
  • $ \mathbf{x}_1, \mathbf{x}_2 \in \mathcal{C},\; \lambda \in [0,1] \;\Rightarrow\; \lambda \mathbf{x}_1 + (1-\lambda)\mathbf{x}_2 \in \mathcal{C}$
  • 이는 함수의 그래프(graph)가 임의의 두 점을 잇는 직선(chord) 아래로 내려가지 않음을 의미하며, 기하학적으로는 함수가 "아래로 볼록(bowl-shaped)"한 형태를 가짐을 뜻함.
• 실현 가능 집합(feasible set) $\mathcal{C}$가 convex set 이어야 함.
  • 집합 안의 임의의 두 점을 잇는 선분(line segment)이 집합 안에 완전히 포함.
  • $\mathbf{x}_1, \mathbf{x}_2 \in \mathcal{C}, \lambda \in [0,1] \Rightarrow \lambda \mathbf{x}_1 + (1-\lambda) \mathbf{x}_2 \in \mathcal{C} $

 

위의 두 조건이 동시에 충족될 때, convex optimization problem 은 다음의 결정적인 성질(key property) 을 가짐이 보장됨:

convex optimization problem에서는
Local minimum은 곧 global minimum이다.

 

이 성질은 단순해 보이지만, 그 실용적 의미는 매우 강력함.

• 비선형 문제에서의 핵심 어려움인 "어떤 local minimum에 수렴했을 때 그것이 진정한 최적해인지 알 수 없다는 불확실성"이 convex problem에서는 원천적으로 제거됨.
• 즉, Iterative algorithm이 수렴하기만 하면, 그 해는 반드시 global optimum임이 수학적으로 보장됨.

바로 이러한 이유로,

• convex problem은 optimization theory에서 매우 중요한 위치를 차지하며,
• gradient descent를 비롯한 다양한 iterative optimization method의 수렴성(convergence)과 최적성(optimality)을 분석하는 이론적 출발점이 됨.

---

같이보면 좋은 자료들

2024.06.01 - [.../Math] - [Math] Optimization 이란 (Introduction)

[Math] Optimization 이란 (Introduction)

2023.07.10 - [.../Math] - [Math] First Order Condition : Convexity

[Math] First Order Condition : Convexity

2023.07.10 - [.../Math] - [Math] Second Order Condition : Convexity

[Math] Second Order Condition : Convexity