기말고사를 위하여 - 비선형계획법

비선형계획법..

 

우선 알고가야할 것들은 

 

1. 기울기 벡터

 

- 함수값을 최대화 하는 방향이다 = 목적함수 값을 개선하는 방향이다.

 

2. 라그랑주 승수법

 

3. feasiblility 

 

 

  자 시작하자 

 

목적함수와 제약식가 linear 하지 않고 non - linear 일 때를 뜻하죠 . 

 

난 공학미적분학2를 안 들어서 최대최소 하면 미분해서 0하거나 산술기하 정도밖에 몰랐는데 

 

내가 고등학교 1학년때 오픈채팅 수학방에서 이런저런 문제풀이하는 걸 구경한 적이 있음 . 

 

그때 어떤 초딩새끼가 어디 KMO 같은데 나갈 법한 새끼가 하나 있었는데 

 

뭔 라그랑주 승수법이니 ㅈㄹ해서 찾아봤다가 람다 기호 보고 도망갔던 기억이 있음

 

여튼 최대최소 >> 최대화 하거나 최소화 한다 >> 최적화 문제라고 해석 가능함 

 

non -linear 한 상황에서 국지최적해를 찾는 방법이 일반적으로 라그랑주 승수법인거죠.

 

근데 조건이 있는데 1. 미분가능해야하고 2. 제약식이 선형독립이어야 한다. (regularity condition) 

 

무시합시다. 

 

뾰족한 경우에는 미분불가능하고 그땐 local  maximum  이 뾰족할 경우에도 나타날 수 있잖아.

 

그리고 제약식이.. 선형 독립이어야겠지 .. 그냥 느낌상 그렇지 않나

 

왜냐면 독립 아니란 소리가 제약식 요리조리 하다보면 제약식 하나가 소거가 되버린단 소린데.. 그럼 조건 하나가 빠져버리는거잖아? 뭔가 이상하지 

 

    일단 

 

최대최소 문제는 크게 두가지 형태 꼴로 나뉘게 됨 . 

------------------------------------------------------------------------------------------------------------------

1. 제약식의 등호 (=) 으로만 표현된 문제

 

2. 제약식에 부등호가 섞인 문제

------------------------------------------------------------------------------------------------------------------

 

1번이 라그랑주로 풀면 되는 거지 . 

 

1. 한 점에서 목적함수의 기울기벡터가 제약식의 기울기 벡터와 평행하고 

2. 그 점에서 제약식의 등호를 만족시킨다.

 

그럼 그 점이 최적해라는거잖아. 그 x 값들을 목적함수에 넣으면 최대 or 최솟값이고 

 

 

2번이 문제고, KKT는 여기에 사용되는 거임. 

 

일단 1번의 같은 경우에는 제약식이 "등호" 이기 때문에, 특이점 즉 제약식간의  "교점 or 교선" 이 발생했고, 그 곳에서 최적해가 나왔다는 것을 알 수 있음. 

 

근데 2번의 경우, 제약식이 부등호로 이루어져있기 때문에, 교점, 교선도 발생하지만 결국 가능해 범위는 "범위" 로 주어짐.

 

용어 정리 한번 하고 가자. 가능해 범위 = feasiblity = 개선가능한 방향 

 

최적화 문제가 뭐라고? 이미 ㅆㅅㅌㅊ라서, 개선이 불가능하다고. 

 

그럼 생각을 해봐. 목적함수값의 기울기 벡터가 feasiblility 한 범위를 가리키고 있으면?

 

개선이 가능하단 소리잖아. 그럼 ㅅㅂ 최적해가 아니지

 

어떻게 해야해 ? feasibility 하지 않게, 목적함수의 기울기 벡터와 방향이 같거나, 반대여야하지. 이거는 maximize 인지 

minimize 문제인지에 따라 조금 다름 

 

 

근데 이게 우리가 알고있듯이,