[LG AiMERS] Convex Optimization

이번 내용은 LG Aimers module 2 내용(KAIST 신진우 교수) 및  1학기 본전공 수업 과정인 Operation Research 1(경영과학과 운영연구1) 수업에서의 내용들을 추가하여 작성하였습니다.

standard form of optimization form

위의 form은 standard form of Optimization problem이다. 이때 f(x), g(x), h(x) 중 하나라도 비선형이면 NLP 문제라고 한다. 

이 때 subject to ~에 해당하는 식, 즉, 제약조건의 유무에 따라 Unconstrained Optimization 문제인지, 아니면 Constrained Optimization 문제인지 결정된다.

 

보통의 Linear problem과 다르게 식에 형태에 따라서 optimal point가 local optimal일 수도 있다. 

그렇기에 우리는 global optimal과 local optimal이 동일한, Convex Program에 관한 정의가 필요하다.

Unconstrained Optimization 

Unconstrained Optimization 문제에서는 f(x)가 Convex function이고, X가 convex set이면,  Convex Program이라 할 수 있다.  이는 매우 강력한 성질을 지니는데, 위에서 밝힌것과 같이 local optimal solution과 global optimal solution이 동일하다는 성질이다. 

Convexity에 관해 우선 정의해보자. 

Convex Set

convex set의 정의

convex set은 Convex set 안의 임의의 두 점을 잡았을 때, 그들의 선형 결합이 Convex set에 존재하는 Set으로 정의된다. 즉, 두 임의의 점의 line segment가 Set에 존재해야한다. 

Convex set의 예시

이는 사전적인 정의로 실제로 Convexity를 정의하기 위한 정의는 추가로 존재한다. 

Convex Function

A funtion f is convex if for any two points of funtions, we have 

$$
f\left((1-\lambda) \mathbf{x}^1+\lambda \mathrm{x}^2\right) \leq(1-\lambda) f\left(\mathrm{x}^1\right)+\lambda f\left(\mathrm{x}^2\right) \text { for } 0 \leq \lambda \leq 1 \text {. }
$$

로 정의된다. 이를 2차함수에 관해 정의하면 아래와 같이 그림으로 표현된다. 

convex function

 

How to check function is convex?: First order condtion & Second order conditon (Necessary condtion)

특정 함수가 convex function인지 확인하는 방법은 바로 first order condition과 second order condtion을 만족하는지 확인하는 것이다(둘 중 하나라도 만족하지 않으면 convex가 아님, Necessary condtion: 필요조건)

 

1. First order Condtion 

For diffferentiable functions, f is convex iff 

 

2. Second order Condtion 

 

Postive Semi Definite? Postive Definite?
PSD와 PD를 판정하기 위해 
1. Eigen value: 의 값이 모두 0보다 크거나(같은지) 확인해보는 방법
2. Superdiagonalization Algorithm:
For symmetric matrix(아니면 A'+A로 새로운 symmetic matrix Q생성) Q 
check nth main diagonal is smaller than 0(or same if checking for PD) and use Gaussian Elimination to make row of nth to be 0(except main diagonal term). 
Repeat 

*Super Diagnoalization Algorithm 예시

PSD와 PD예시

Necessary Condition For Local minimum

모든 x(임의의 x)에 관해 위의 조건을 확인하기 어려움으로  특정 x가 local minimum임을 판정해보자.

X가 Local Minimum이면 아래의 2조건을 모두 만족해야한다

1. First order condtition: gradient  x값은 0이어야한다. 

2. 2nd order condtion에 의해 Hessian matrix의 값은 Postive Semidefinite(0보다 크거나 같다)를 필요조건으로 가진다. (만족하지 않으면 local minimum이 아니다)

3. 만일 Hessian matrix가 Postive Definite이면 역으로 Sufficient Conditon(충분조건)으로 이를 만족하면 local minimum이다.

 

* Afiine 함수(다변량 1차함수 + bias가 합해진 term), 2차함수(Quadratic Form)는 Convex function임이 널리 알려져있다. 

How to solve?: Gradeint Algorithm 

Convex함수임을 확인했으면, Gradient Descent Algorithm을 이용해 해를 구할 수 있다. 

물론 Newton Method 등등 수치해석에서 배우는 다양한 방법론을 적용가능하다.

Constrained Optimization 

위에서 정의한 Optimization문제 term에 관해서(제약 조건이 있음 + inequaility가 0보다 크거나 같음)

우리는 lagrangian 승수법을 이용해 이를 재정의가능하다(equality Constraint에 관해)

Lagrangian funtion(라그랑주 승수법)
라그랑주 승수법의 기본 가정은 "제약 조건 g를 만족하는 f의 최솟값 또는 최댓값은 f와 g가 접하는 지점에 존재할 수도 있다."는 것이다. 아래 그림을 통해 우리는 쉽게 제약조건을 만족할 때 f는 g와 접할때 최대 혹은 최소값을 가짐을 확인 가능하다. 
이 말은 f와 g의 그라디언트가 상수배 관계임을 의미한다. 
그럼으로 우리는 라그랑지안 함수의 그라디언트 값(x와 람다, v에 관한 편미분(람다와 v에 관한 편미분식은 제약조건을 만족하는 식을 의미))이 0이 되는 지점을 찾음으로서 optimal한 지점을 찾을 수 있다(연립방정식 풀기)

라그랑주 승수법의 기하학적 해석

 

라그랑지안 승수법을 duality를 이용해 문제를 풀 수 도 있다. 

즉, argminL을 찾고 이 때 람다를 maximize시키는 람다를 찾는 방법으로도 해결가능하다. 이는 KKT Condition에서 더 자세히 확인해보자.

Constraint Qualification(CQ): How to find set of Active Constraints?

위의 조건들중(출처: 위키피디아) 하나만 만족하면 CQ를 만족했다고 한다. 이중  LICQ를 보편적으로 많이 사용하는데, LICQ는 h를 equality constraint, g를 inequailty constraint 식이라고 할때, 특정 point x에서의 h와 g의 gradient값이 모두 lindearly independent할 때이다. 

즉, Constraint qualification을 만족하는 제약조건만 사용된다(쉽게 생각하면 active constraint를 찾는 조건이라고 생각하면 된다) 

KKT Condition: Constrained optimization의 necessary condtion

KKT 조건을 풀어쓰면 다음과 같다. 

1. Dual Feasiblity 식: Lagrangian식의 x에 관한 gradient 식이다(-인 이유는 해당 자료의 출처에서는 g를 0보다 큰 부등식으로 잡음) ~ 해당 식은 Duality 식에서 유도됨

2. Primal Feasibility 식: 제약조건을 만족해야한다

3. Complimentary Slackness: LP와 Duality식에서 확인되는 문제, g의 경계점에 x가 있으면 g가 0이라 만족, 아니라면 u가 0이고, u가 0이면 Dual Feasibility 식에서 f와 h의 gradient 식의 합이 0임으로(local minimum), 1번도 만족된다. 

Complementary slackness:
어떤 linear program과 그것의 dual program 각각에 feasible한 solution이 서로의 program의 optimal solution이 될 필요충분조건은 두 solution이 complementary slackness condition을 만족하는 것이다.  이는 Duality를 통해서도 확인 가능하다

 

Duality와 Lagrangian function 

min f(x)의 optimal solution을 x*이라고 해보자(primal optimal, 우리가 찾고 싶은 값)

그러면 Lagrangian Dual Function을 minimize하는 식과의 관계는 아래와 같다. 

이 식에서 C는 x의 feasible한 집합이다. 위의 식이 성립하는 이유는 g는 0보다 작고, u는 0보다 크기 때문이다(식의 가정)

그렇다면 이 min x가 들어간 L(x,u,v)의 식은 결국, u,v에 관한 식이기에 이를 q(u,v)라 하면. 이 q를 maximize하더라도 f*보다 작다. 이 q를 Dual problem이라고 하고, maximize한 값을 Dual Optmial value라고 한다. 

해당 내용을 정리한 것이 Weak Duality이다.

Weak Duality
어떤 linear (minimization) program의 feasible solution이 이루는 objective function의 값은 그것의 dual program의 feasible solution이 이루는 objective function의 값보다 항상 크거나 같다.

Strong Duality
어떤 linear program과 그것의 dual program이 주어졌을 때, 각각의 optimal solution이 이루는 objective function의 값은 항상 같다. (q* = f*)

 

즉, duality문제를 풀면 primal problem의 best lower bound를 찾을 수 있다 .

정리한 내용 출처: 혁펜하임 covex optimixation

 

* Duality에 관해 LP관점으로 보여준 블로그글:

https://gazelle-and-cs.tistory.com/17

 

*추가적인 정리