[Math] Lagrangian from Standard Form using Indicator Function

Standard Form of Optimization Problem

Equailty constraints와 Ineqaulity contraints를 가지고 있는

Optimization Problem (minimization의 경우)은 다음과 같이 표현된다.

 

$$\begin{aligned}&\text{minimize }f(\textbf{x})\\ & \text{s.t:}\\ & g_i(\textbf{x}) \le 0, i=1,\dots,m \\ & h_j(\textbf{x})=0,j=1,\dots,k\end{aligned}$$

 

이 문제를 convex optimization problem이라고 한정할 경우
(이는 loss function $f(\textbf{x})$ 이 convex function 인 경우를 의미함),

constraint가 없다면 간단히 solution을 구할 수 있음.

 

하지만, constraint들이 주어질 경우엔 간단히 solution을 구하기 어려워짐.

 

때문에 Optimization Problem을 간단히 풀기 위해선
constraints들을 없는 convex optimization 의 형태
로 바꾸어서 푸는 접근방식이 사용된다

 

이같은 방식을 Lagrangian Method라고 부름.

 

이 문서에서는

equality constraints와 inequality constraints를 모두 가진 optimization problem을 위한

Lagrangian Method (KKT조건을 이용한)를 간략히 소개한다.

---

참고: "일반 Lagrange Method"와 "KKT조건으로 확장된 Lagrange Method".

Lagrange 방법은 일반적으로 equality constraints를 가진 최적화 문제에 적용되는 게 일반적이며,

inequality constraints를 포함하는 경우에는 Karush-Kuhn-Tucker Condition (KKT Condition) 을 이용한 확장이 필요함.

 

이 문서에서는 KKT 조건을 이용한 확장된 Lagrange method을 다룸.

2023.05.17 - [.../Math] - [Math] Karush-Kuhn-Tucker Conditions (KKT Conditions)

[Math] Karush-Kuhn-Tucker Conditions (KKT Conditions)

 

참고로 다음은 equality constraint만을 가진 경우만을 고려하는 Lagrangian에 대해 자세히 설명이 된 URL임 (참고할 것)

2023.06.26 - [.../Math] - [Math] Lagrange Method or Lagrange Multiplier Method

[Math] Lagrange Method or Lagrange Multiplier Method

 

좀 더 사족을 달자면, Lagrange method는 non-convex optimization에도 적용이 가능함.

하지만 주로 convex로 한정된 경우에 많이 사용된다.

---

(Ideal) Indicator Function의 도입

이상적으로 다음과 같은 indicator function을 도입하면, constraints를 없앨 수 있음.

• indicator function은  contraints가 없는 형태로의 변환에 사용되는데,
• 이는 일반적인 Lagrange 방법의 확장으로써,
• KKT 조건과 같은 방식으로 contraints를 다루게 해줌.

---

$I_\text{inequal}(q) : \mathbb{R} \to \mathbb{R}$ 인 다음의 scalar function을 indicator function 으로 삼아, inequality constraints들에 적용.

$$I_\text{inequal}(q)=\left\{ \begin{matrix} 0 &,q \le 0\\ \infty &, q>0\end{matrix}\right. \\ q=g_i(\textbf{x}), i=1,\dots,m$$

 

indquality에서 부등호의 방향을 주의하자.

---

$I_\text{equal}(e) : \mathbb{R} \to \mathbb{R}$ 인 다음의 scalar function을 indicator function 으로 삼아, equality constraints들에 적용.

$$I_\text{equal}(e)=\left\{ \begin{matrix} 0 &,e = 0\\ \infty &, e\ne0\end{matrix}\right. \\ e=h_j(\textbf{x}), j=1,\dots,k$$

---

위의 indicator function들은

• constraints을 만족하는 경우에만 유한한 값 $0$을 가질 뿐,
• constraints에 어긋날 경우 무한대의 값을 가지는 함수들임.

따라서 이들 indicator function을 다음과 같이 도입할 경우,

위에 주어진 Standard form을 constraints가 없는 형태로 변경할 수 있음.

$$\text{min }\left[ f(\textbf{x}) + \sum_{i=1}^m I_\text{inequal}(g_i(\textbf{x})) + \sum_{j=1}^k I_\text{equal}(h_j(\textbf{x})) \right]$$

 

---

Lagrangian (Primal) : Practical Case

앞서 살펴본 indicator function은 이상적인 것으로

• 무한대의 값을 가지며
• 함수가 continuous하지 않다는 특징을 가지고 있어서
• 실제 convex optimzation을 적용하기 어려움.

---

때문에 이를 다음과 같이 실제 사용가능한 형태의 indicator function으로 변경한다.

• $I_\text{inequal}(q) = \alpha q, \quad \text{ where } \alpha \ge 0$
• $I_\text{equal}(e) = \mu e$

위의 식들은 앞서 살펴본 ideal indicator function에 대한 일종의 approximation(근사)로 볼 수 있다.
즉, 이들로 ideal indicator function을 대신할 수 있음.

---

위를 사용하여 contraints가 없는 optimization problem으로 만들면 다음과 같다..

(복수의 constraint에 대해, 각각 다른 $\alpha_i$와 $\mu_k$가 주어짐을 주의할 것.)

$$\text{min } \left[ f(\textbf{x}) + \sum_{i=1}^m \alpha_i g_i(\textbf{x}) + \sum_{j=1}^k \mu_j h_j(\textbf{x}) \right]$$

• $\textbf{x}$가 feasible set에 있을 경우 ,
  • $f^\prime (\textbf{x}) = 0$ 이고 (=Stationarity)
  • equality constraints와 inequality constraints를 모두 만족하기 때문에(=Primal Feasibility)
• 두번째 항은 $\alpha_i \ge 0$이므로 항상 음수이고, (=Dual Feasibility)
• 세번째 항은 항상 0이 된다. (=Complementary Slackness)

---

즉, feasible set $S$에 속하는 $\textbf{x}\in S$에 대해
object function의  값인 $f(\textbf{x})$는 다음과 같이 위의 식에 대한 일종의 supremum (상한, 최소상계)이 됨:

$$\underset{\textbf{x}\in S}{\text{min }}f(\textbf{x}) \ge \underset{\textbf{x}\in S}{\text{min }} \left[ f(\textbf{x}) + \sum_{i=1}^m \alpha_i g_i(\textbf{x}) + \sum_{j=1}^k \mu_j h_j(\textbf{x}) \right]$$

 

이같이 indicator를 이용하여 표기하는 식 (=Lagrangian multiplier를 도입한 식)이

바로 Lagrangian 또는 Lagrangian function으로 불리는 것으로,

$L(\textbf{x},\boldsymbol{\alpha}, \boldsymbol{\mu})$ 으로 표기된다.

 

이 Lagrangian은 constraints를 가진 optimization을 풀 때 많이 사용된다.

• duality에 의해 Lagrangian dual로 바꾸어 푸는 경우도 있기 때문에, Lagrangian Primal이라고도 많이 불림.
• primal과 dual 중에서 풀기 쉬운 것을 골라서 풀게 된다.

2023.07.05 - [.../Math] - [Math] Lagrangian Primal and Lagrangian Dual

[Math] Lagrangian Primal and Lagrangian Dual

 

또한 위의 Lagrangian에서 도입한 $\alpha_i$와 $\mu_j$를 Lagrangian multiplier (라그랑지 승수) 또는 dual variable라고 부른다.

---

Lagrangian (Primal) : Vector Equation 표기

이들 Lagrangian multipliers는 equality constraints와 inequality constraints 들에 대해 하나씩 주어지므로

이들을 각각 column vector로 표현하면 다음과 같이 inner prodcut로 표기할 수 있음.

이를 통해 vector를 이용하여 Lagrangian을 표현하면 다음과 같음.

 

$$L(\textbf{x},\boldsymbol{\alpha},\boldsymbol{\mu})=f(\textbf{x})+\boldsymbol{\alpha}\cdot\textbf{g}(\textbf{x})+\boldsymbol{\mu}\cdot\textbf{h(x)}$$

 

• $\textbf{x} \in \mathbb{R}^n, \boldsymbol{\alpha} \in \mathbb{R}^m, \boldsymbol{\mu} \in \mathbb{R}^k$ 이고,
• $f:\mathbb{R}^n\to \mathbb{R}, \textbf{g}:\mathbb{R}^n\to \mathbb{R}^m, \textbf{h}:\mathbb{R}^n\to \mathbb{R}^k$ 이므로 다음이 성립함

$$L: \mathbb{R}^n \times \mathbb{R}^m \times \mathbb{R}^k \to \mathbb{R}$$

 

 

---