최적화와 볼록최적화 (Optimization and Convex Optimization)

Created on March 02, 2025 , last updated on July 01, 2026

2025   ·   convex   optimization   ·   공부   최적화

최적화의 기본요소

  1. 목적함수(Objective Function) : 무엇을 최대화 or 최소화 할 것인가
  2. 변수(Descision Variable or unknown)
  3. 제약조건(Constraints)

과정

  1. 모델링하기
  2. optimization algorithm을 사용한 solution찾기

수학적 모델

  • 최소 모델
\[\begin{aligned} \min_{x} \quad & f(x) \\ \text{subject to} \quad & g_i(x) \le 0, \quad i = 1, \cdots,m \end{aligned}\]

( x \in \mathbb{R}^n ) : 의사 결정 변수 (Decision Variables)

( f : \mathbb{R}^n \rightarrow \mathbb{R} ) : 목적 함수 (Objective Function)

( C = {\, x : g_i(x) \leq 0,\ i = 1,\ldots,m } ) : 제약 조건을 만족하는 해의 집합 (Feasible Region)

( x^* \in \mathbb{R}^n ) is an optimal solution if ( x^* \in C ) and ( f(x^*) \leq f(x) ) for all ( x \in C ).

등가 변환

  • 최적화 문제는 다양한 형태로 변환할 수 있으며, 일부 변환을 통해 더 다루기 쉬운 형태로 바꿀 수 있다.
\[\begin{aligned}&\min f(x) &&\quad\longleftrightarrow\quad \max\bigl(-f(x)\bigr),\\&g_i(x) \leq 0 &&\quad\longleftrightarrow\quad -g_i(x) \geq 0,\\&h(x) = 0 &&\quad\longleftrightarrow\quad \bigl\{\,h(x) \geq 0,\; h(x) \leq 0\bigr\}\end{aligned}\]

즉, 최소화 문제를 최대화 문제로 변환할 수 있으며, 부등식을 반대 방향으로 바꿀 수도 있다. 등식 제약 조건은 두 개의 부등식으로 표현할 수도 있다.

Unconstrainted vs Constrainted

최적화 문제는 크게 두 가지로 나뉜다.

1. 제약이 없는 최적화 문제 (Unconstrained Optimization)

\[min_x f(x)\]
  • 제약 조건이 없어 단순한 미분을 통한 최적화가 가능하다.

2. 제약이 있는 최적화 문제 (Constrained Optimization)

\[\begin{aligned}&\min_x f(x) \\&\text{subject to } g_i(x) \leq 0, \quad i = 1,\ldots,m,\\&\phantom{\text{subject to }}h_i(x) = 0, \quad i = 1,\ldots,p\end{aligned}\]
  • 제약 조건이 있으므로 라그랑주 승수법(Lagrange multipliers) 또는 내리막 경사법(Gradient Descent) 등의 기법을 활용해야 한다.

Convex Optimization

표준 모델이 아래의 수식과 같을 때, 두가지 조건을 만족하면 convex Optimization을 할 수 있다.

\[\begin{aligned} \min_{x} \quad & f(x) \\ \text{subject to} \quad & g_i(x) \le 0, \quad i = 1, \cdots,m \end{aligned}\] \[\begin{aligned} &\bullet \quad f:\mathbb{R}^n \to \mathbb{R} \text{ is a convex function and} \\ &\bullet \quad \text{Feasible region } \mathcal{C} \text{ is a convex set.} \end{aligned}\]

  1. obejct function이 convex function일때

  2. Feasible region C 가 convex set일때

장점

  • Local Optimum이 Global Optimum이 됨 볼록 최적화 문제에서는 지역 최적해(Local Optimum)와 전역 최적해(Global Optimum)가 같기 때문에, 전역 최적해를 보장할 수 있다.
  • 해법이 빠르고 안정적 기존의 비볼록 최적화(Non-convex Optimization)보다 해를 찾는 알고리즘이 빠르고 신뢰성이 높다.
  • CVX 및 CVXPY 사용 가능 Python에서는 CVXPY 등의 라이브러리를 활용하여 볼록 최적화 문제를 쉽게 풀 수 있다.

Linear Interpolation between Two points

두 점 x,y 사이의 Linear Interpolation을 을 통해, Convex Optimization와 Convex set좀더 직관적으로 이해할 수 있다.

\[\vec{z} = \vec{y} + \theta (\vec{x} - \vec{y}), \quad 0 \leq \theta \leq 1 \\ = \theta \vec{x} + (1 - \theta) \vec{y}\] \[\vec{z} = \alpha \vec{x} + \beta \vec{y}, \quad \alpha + \beta = 1 \quad \text{and} \quad 0 \leq \alpha, \beta\]

이 개념은 Convex Optimization와 Convex set과도 유사하다.

Convex Function and Convex Set

\[\begin{aligned} & \textbf{for any } x,y \in \mathbb{R}^n \textbf{ and } \theta \in [0,1] \\ & \ f(\theta x + (1 - \theta)y) \leq \theta f(x) + (1 - \theta) f(y) \end{aligned}\]
  • 이는 함수가 중간값에서 최댓값을 가지지 않으며,Linear Interpolation이 가능함을 의미한다.

\[\begin{aligned} & \textbf{for a } x,y \in \mathcal{C} \textbf{ and } \theta \in [0,1], \\ & \theta x + (1 - \theta)y \in \mathcal{C} \end{aligned}\]

즉, 집합 내의 두 점을 선형 결합한 결과가 여전히 집합 안에 속해야 한다.

정리 출처

https://www.youtube.com/watch?v=QJSSWNIAPlw