보론
1. 부등식 제약조건이 있는 다변함수 최적화 형태
□ 제약조건이 등식이 아닌 부등식으로 주어진 경우
[예제]
“비음(nonnegative)인 n개의 변수를 가진 목적함수 를 m개의 부등식 제약식 ≤ , ≤ , ... ≤ 을 만족시 키면서 극대화하여라.”
≤
≤
≤
≥
⇨ [특징]
① 제약조건이 부등호
② 변수의 영역이 비음으로 지정
□ 각 제약식마다 좌변에 비음인 여유(slack) 변수인 를 더해주면 다음과 같은 제약조건 으로 문제를 변형할 수 있음
≥
≥
⇨ 비음에 대한 조건을 고려하지 않는다면, 라그랑지안 함수를 다음과 같은 형태로 표현이 가능함
′
but, 각 변수가 비음이라는 조건을 포함하지 않고 있음에 유의해야 함 (각 변수가 비음이라는 사실을 고려하는 1계 조건이 필요함)
2. 쿤-터커의 1계 필요조건
□ 변수들의 비음조건이 없어지지 않는 한 주어진 부등식 제약조건이 있는 문제를 제약조 건이 있는 문제로 변형한다고 해도 라그랑지안 승수법을 적용할 수 없음
⇨ 이를 구하기 위한 새로운 조건으로 쿤-터커 조건 필요함
′
(주어진 문제를 등식 제약조건의 문제로 변형하지 않고, 비음조건과 부등식 조건을 무시한 태 표현한 라그랑지안 함수법)
번호 조건식 풀이
1
≤ 라그랑지안 함수를 각 변수 로 편미분한 결과는 극값에서 음이거나 0이어야 한다.2
≥ 라그랑지안 함수를 라그랑지 승수로 편미분한 결과는 비음 이어야 한다.
3
최적해에서 변수 와
를 곱한 값이 0이어야 한다.
4
최적해에서 변수 와
를 곱한 값이 0이어야 한다.
5 ≥ 최적해에서 변수는 비음이어야 한다.
6 ≥ 최적해에서 라그랑지안 승수는 비음이어야 한다.
□ 쿤-터커 조건을 적용하여 최적해를 구하는데 중요한 전제가 필요함
① mzximize 문제임
② 제약식이 ≤ 의 형태임
③ 모든 변수가 비음임
⇨ 위 3가지 특징을 충족하지 않으면 쿤-터커 조건으로 문제를 풀 수 없음 그러나 문제를 변형시켜
≤
≤
≤
≥
의 조건으로 바꾸면 됨
(예: minimize문제라면 목적식에 -를 붙여 곱한 후에 maximize문제로 변형시키면 되고, 제약식이 ≥라면, 양변에 -를 곱해 ≤의 형태로 변형시키면 되고....♬)
[예제 1] 다음과 같은 부등식 제약조건이 있는 최적화 문제의 해를 구해라.
≤
≤
≥
❶ [쿤-터커 기본조건 확인]
먼저, 최적화의 문제 형태가 쿤-터커 조건의 적용이 가능한 형태인지를 확인
⇨ max문제, 제약식이 모두 ≤의 형태, 모든 변수(x,y)가 비음이므로 가능
번호 조건식 풀이
1
≤ ≤ ≤ .2
≥ ≥ ≥
3
4
5 ≥ ≥ ≥
6 ≥ ≥ ≥
❷ 라그랑지안 함수 형태로 표시
[예제 2] 다음의 최적화 문제의 해를 구해라.
≤
≤
≥ ≥ ≥
⇨ 부등식 제약조건이 있는 최적화 문제에서 쿤-터커 조건을 적용해야 하는데 바로 적용 할 수 없음 (모두 비음이나 max문제가 아니고, 제약식의 형태가 모두 ≤가 아님)
∴ 변형을 할 필요성이 있음
≤
≤
≤ ≤
≥
□ 라그랑지안 형태로 표현
□ 다음의 21개의 부등식과 등식을 만족하는 를 찾아야 함
번
호 조건식 풀이
1
≤ . ≤
≤
≤
2
≥
≥
≥
≥
3
4
5 ≥ ≥ ≥ ≥
6 ≥ ≥ ≥ ≥ ≥
⇨ (매우 어려운 작업) 결과만 제시하면 이 됨
꼭 풀어볼 문제
1. 다음 최적화의 문제의 해를 구하여라.
≤
≥
2. 다음 최적화 문제에 대해서 아래 물음에 답하여라.
≤
≥ ≥
(1) 위 문제를 라그랑지안 함수이 형태로 나타내어라.
(2) 위 문제에 대한 쿤-터커 조건을 기술하여라.
(3) 쿤-터커 조건을 만족하는 해를 구하여라.
